64
$\begingroup$

I wonder if it is possible to build compilers for dynamic languages like Ruby to have similar and comparable performance to C/C++? From what I understand about compilers, take Ruby for instance, compiling Ruby code can't ever be efficient because the way Ruby handles reflection, features such as automatic type conversion from integer to big integer, and lack of static typing makes building an efficient compiler for Ruby extremely difficult.

Is it possible to build a compiler that can compile Ruby or any other dynamic languages to a binary that performs very closely to C/C++? Is there a fundamental reason why JIT compilers, such as PyPy/Rubinius will eventually or will never match C/C++ in performance?

Note: I do understand that “performance” can be vague, so to clear that up, I meant, if you can do X in C/C++ with performance Y, can you do X in Ruby/Python with performance close to Y? Where X is everything from device drivers and OS code, to web applications.

$\endgroup$
  • 1
    $\begingroup$ Can you rephrase the question so it encourages answers backed by proper evidence over others? $\endgroup$ – Raphael Mar 28 '12 at 23:29
  • $\begingroup$ @Raphael I've gone ahead and edited. I think my edit doesn't fundamentally change the meaning of the question, but makes it less inviting of opinion pieces. $\endgroup$ – Gilles 'SO- stop being evil' Mar 29 '12 at 0:19
  • 1
    $\begingroup$ In particular, I think you need to fix one (or a few) concrete performance measures. Runtime? Space usage? Energy usage? Developer time? Return of investment? Note also this question on our meta that concerns this question (or rather its answers). $\endgroup$ – Raphael Mar 29 '12 at 0:20
  • $\begingroup$ This question is a typical initiator of religous wars. And as we can see from the answers, we're having one, albeit a very civilized one. $\endgroup$ – Andrej Bauer Jan 6 '13 at 9:55
  • $\begingroup$ There are dynamic languages allowing optional type annotations (e.g.: Clojure). From what I know the performance associated with the type-annotated functions is equivalent to when a language would be statically typed. $\endgroup$ – Pedro Morte Rolo May 13 '16 at 11:24

10 Answers 10

68
$\begingroup$

To all those who said “yes” I’ll offer a counter-point that the answer is “no”, by design. Those languages will never be able to match the performance of statically compiled languages.

Kos offered the (very valid) point that dynamic languages have more information about the system at runtime which can be used to optimise code.

However, there‘s another side of the coin: this additional information needs to be kept track of. On modern architectures, this is a performance killer.

William Edwards offers a nice overview of the argument.

In particular, the optimisations mentioned by Kos can’t be applied beyond a very limited scope unless you limit the expressive power of your languages quite drastically, as mentioned by Devin. This is of course a viable trade-off but for the sake of the discussion, you then end up with a static language, not a dynamic one. Those languages differ fundamentally from Python or Ruby as most people would understand them.

William cites some interesting IBM slides:

  • Every variable can be dynamically-typed: Need type checks
  • Every statement can potentially throw exceptions due to type mismatch and so on: Need exception checks
  • Every field and symbol can be added, deleted, and changed at runtime: Need access checks
  • The type of every object and its class hierarchy can be changed at runtime: Need class hierarchy checks

Some of those checks can be eliminated after analysis (N.B.: this analysis also takes time – at runtime).

Furthermore, Kos argues that dynamic languages could even surpass C++ performance. The JIT can indeed analyse the program’s behaviour and apply suitable optimisations.

But C++ compilers can do the same! Modern compilers offer so-called profile-guided optimisation which, if they are given suitable input, can model program runtime behaviour and apply the same optimisations that a JIT would apply.

Of course, this all hinges on the existence of realistic training data and furthermore the program cannot adapt its runtime characteristics if the usage pattern changes mid-run. JITs can theoretically handle this. I’d be interested to see how this fares in practice, since, in order to switch optimisations, the JIT would continually have to collect usage data which once again slows down execution.

In summary, I’m not convinced that runtime hot-spot optimisations outweigh the overhead of tracking runtime information in the long run, compared to static analysis and optimisation.

$\endgroup$
  • 2
    $\begingroup$ @Raphael That’s a “shortcoming” of the compiler then. In particular, did javac ever profile-guided optimisation? Not as far as I’m aware of. In general it doesn’t make sense to make the compiler of a JITted language well at optimising since the JIT can handle it (and at the very least, this way more languages profit from the effort). So (understandably) there never was put much effort into the javac optimiser, as far as I know (for the .NET languages this is definitely true). $\endgroup$ – Konrad Rudolph Mar 28 '12 at 13:10
  • 1
    $\begingroup$ @Raphael The key word is: maybe. It doesn’t show it either way. That is all I wanted to say. I have given reasons (but no proof) for my assumption in the preceding paragraphs. $\endgroup$ – Konrad Rudolph Mar 28 '12 at 14:22
  • 1
    $\begingroup$ @Ben I don’t deny that it’s complicated. This is merely an intuition. Tracking all that information at runtime comes at a cost, after all. I’m not convinced by your point about IO. If this is predictable (= typical use-case), then PGO can predict it. If it’s spurious, I’m not convinced that the JIT could optimise it either. Maybe once in a while, out of sheer luck. But reliably? … $\endgroup$ – Konrad Rudolph Mar 28 '12 at 22:26
  • 2
    $\begingroup$ @Konrad: Your intuition is false. It's not about varying at runtime, it's about unpredictability at compile time. The sweet spot for JITs vs static optimisation isn't when the behaviour of the program changes at runtime "too fast" for profiling, it's when the behaviour of the program is easy to optimise in each individual run of the program, but varies wildly between runs. A static optimiser will generally have to optimise for only one set of conditions, whereas a JIT optimises each run separately, for the conditions that happen to occur in that run. $\endgroup$ – Ben Mar 30 '12 at 3:15
  • 3
    $\begingroup$ Notice: This comment-thread is developing into a mini chat room. If you'd like to continue this discussion, please bring it to chat. Comments should be used to improve the original post. Please discontinue this conversation here. Thanks. $\endgroup$ – Robert Cartaino Apr 9 '12 at 19:41
20
$\begingroup$

if you can do X in C/C++ with performance Y, can you do X in Ruby/Python with performance close to Y?

Yes. Take, as an example, PyPy. It is a collection of Python code that performs close to C in doing interpretation (not all that close, but not all that far away either). It does this by performing full-program analysis on the source code to assign each variable a static type (see the Annotator and Rtyper docs for details), and then, once armed with the same type information you give C, it can perform the same sorts of optimizations. At least in theory.

The tradeoff of course is that only a subset of Python code is accepted by RPython, and in general, even if that restriction is lifted, only a subset of Python code can do well: the subset that can be analyzed and given static types.

If you restrict Python enough, optimizers can be built that can take advantage of the restricted subset and compile it to efficient code. This is not really an interesting benefit, in fact, it's well known. But the whole point of using Python (or Ruby) in the first place was that we wanted to use interesting features that perhaps don't analyze well and result in good performance! So the interesting question is actually...

Additionally, will JIT compilers, such as PyPy/Rubinius ever match C/C++ in performance?

Nah.

By which I mean: sure, maybe as code runs accumulate you can get enough typing information and enough hotspots to compile all of the code all the way down to machine code. And maybe we can get this to perform better than C for some code. I don't think that's hugely controversial. But it still has to "warm up", and performance is still a bit less predictable, and it won't be as good as C or C++ for certain tasks that require consistently and predictably high performance.

The existing performance data for Java, which has both more type information than Python or Ruby, and a better-developed JIT compiler than Python or Ruby, still doesn't match up to C/C++. It is, however, in the same ballpark.

$\endgroup$
  • 1
    $\begingroup$ "The tradeoff of course is that only a subset of Python code is accepted, or rather, only a subset of Python code can do well: the subset that can be analyzed and given static types." This isn't quite accurate. Only the subset can be accepted at all by the RPython compiler. Compiling to RPython to reasonably efficient C only works precisely because the difficult-to-compile parts of Python are guaranteed to never occur in RPython programs; it's not merely that if they occur they won't be optimised. It's the compiled interpreter that handles all of Python. $\endgroup$ – Ben Mar 28 '12 at 5:27
  • 1
    $\begingroup$ About JIT: I have seen more than one benchmark where Java outclassed several flavors of C(++). Only C++ with boost seems to stay ahead reliably. In that case, I wonder about performance per developer time, but that is another topic. $\endgroup$ – Raphael Mar 28 '12 at 6:58
  • $\begingroup$ @Ben: once you have RPython, it is trivial to create a compiler/interpreter that falls back to using CPython interpreter when the RPython compiler fails, therefore "only a subset of Python code can do well: ..." is totally accurate. $\endgroup$ – Lie Ryan Mar 28 '12 at 8:06
  • 9
    $\begingroup$ @Raphael It's been shown many times that well written C++ code outperforms Java. It's the "well written" part that's quite a bit harder to get in C++ though, so in many benches you see the results that Java outperforms C++. C++ is, therefore, more expensive, but when the tight mem control and metal grit are needed, C/C++ is what you turn to. C in particular is just a c/p assembler. $\endgroup$ – TC1 Mar 28 '12 at 9:26
  • 7
    $\begingroup$ Comparing the maximal performance of other languages to languages like C/C++ is sort of an exercise in futility, since you can inline assembly directly as part of the language spec. Anything that the machine could do running a program written in any language, you can at worst duplicate by writing assembly from a trace of executed instructions. A much more interesting metric would be, as @Raphael suggests in an earlier comment, performance per development effort (man hours, lines of code, etc.). $\endgroup$ – Patrick87 Mar 28 '12 at 13:20
18
$\begingroup$

The short answer is: we don't know, ask again in 100 years. (We might still not know then; possibly we'll never know.)

In theory, this is possible. Take all the programs that have ever been written, manually translate them to the most efficient possible machine code, and write an interpreter that maps source codes to machine codes. This is possible since only a finite number of programs have ever been written (and as more programs get written, keep up the manual translations). This is also, of course, completely idiotic on practical terms.

Then again, in theory, high-level languages might be able to reach the performance of machine code, but they won't surpass it. This is still very theoretical, because in practical terms, we very rarely resort to writing machine code. This argument does not apply to comparing higher-level languages: it doesn't imply that C must be more efficient than Python, only that machine code cannot do worse than Python.

Coming from the other side, on purely experimental terms, we can see that most of the time, interpreted high-level languages perform worse than compiled low-level languages. We tend to write non-time-sensitive code in very high-level languages and time-critical inner loops in assembly, with languages like C and Python falling in between. While I don't have any statistics to back this up, I think this is indeed the best decision in most cases.

However, there are uncontested instances where high-level languages beat the code that one would realistically write: special-purpose programming environments. Programs like Matlab and Mathematica are often far better at solving certain kinds of mathematical problems than what mere mortals can write. The library functions may have been written in C or C++ (which is fuel towards the “low-level languages are more efficient” camp), but that's none of my business if I'm writing Mathematica code, the library is a black box.

Is it theoretically possible that Python will get as close, or maybe even closer, to optimal performance than C? As seen above, yes, but we are very far from that today. Then again, compilers have made a lot of progress in the past decades, and that progress is not slowing down.

High-level languages tend to make more things automatic, so they have more work to perform, and thus tend to be less efficient. On the other hand, they tend to have more semantic information, so it can be easier to spot optimizations (if you're writing a Haskell compiler, you don't have to worry that another thread will modify a variable under your nose). One of several efforts to compare apples and oranges different programming languages is the Computer Language Benchmark Game (formerly known as the shootout). Fortran tends to shine at numerical tasks; but when it comes to manipulating structured data or high-rate thread commutation, F# and Scala do well. Don't take these results as gospel: a lot of what they are measuring is how good the author of the test program in each language was.

An argument in favor of high-level languages is that performance on modern systems is not so strongly correlated with the number of instructions that are executed, and less so over time. Low-level languages are good matches for simple sequential machines. If a high-level language executes twice as many instructions, but manages to use the cache more intelligently so it does half as many cache misses, it may end up the winner.

On server and desktop platforms, CPUs have almost reached a plateau where they don't get any faster (mobile platforms are getting there too); this favors languages where parallelism is easy to exploit. A lot of processors spend most of their time waiting for an I/O response; the time spent in computation matters little compared with the amount of I/O, and a language that allows the programmer to minimize communications is at an advantage.

All in all, while high-level languages start with a penalty, they have more room for improvement. How close can they get? Ask again in 100 years.

Final note: often, the comparison is not between the most efficient program that can be written in language A and the same in language B, nor between the most efficient program ever written in each language, but between the most efficient program that can be written by a human in a certain amount of time in each language. This introduces an element that cannot be analyzed mathematically, even in principle. In practical terms, this often means that the best performance is a compromise between much how low-level code you need to write to meet performance goals and how much low-level code you have time to write to meet release dates.

$\endgroup$
  • $\begingroup$ I think the distinction between high-level and low-level is the wrong one. C++ can be (very) high level. Yet modern, high-level C++ doesn’t (necessarily) perform worse than a low-level equivalent – quite the contrary. C++ and its libraries were carefully designed to offer high-level abstractions without performance penalty. Same goes for your Haskell example: its high-level abstractions often enable rather than prevent optimisations. The original distinction between dynamic languages and static languages makes more sense in this regard. $\endgroup$ – Konrad Rudolph Mar 29 '12 at 9:27
  • $\begingroup$ @KonradRudolph You're right, in that low-level/high-level is a somewhat arbitrary distinction. But dynamic vs static languages doesn't capture everything either; a JIT can eliminate much of the difference. Essentially, the known theoretical answers to this question are trivial and useless, and the practical answer is “it depends”. $\endgroup$ – Gilles 'SO- stop being evil' Mar 29 '12 at 21:54
  • $\begingroup$ Well then, I think the question just becomes “just how good can JITs become, and if they overtake static compilation, can statically compiled languages also profit from them?” At least that’s how I understand the question once we take JITs into account. And yes, I agree with your assessment but surely we can get some informed guesses which go beyond “it depends”. ;-) $\endgroup$ – Konrad Rudolph Mar 29 '12 at 22:26
  • $\begingroup$ @KonradRudolph If I wanted guesses, I'd ask on Software Engineering. $\endgroup$ – Gilles 'SO- stop being evil' Mar 29 '12 at 22:28
  • 1
    $\begingroup$ The language shootout is unfortunately a questionable source for quantative benchmarks: they don't accept all programs only those deemed typical of the language. This is a tricky and very subjective requirement; it means that you can't assume that a shootout implementation is actually any good (and in practice, some implementations have obviously superior alternatives rejected). On the flip side; these are microbenchmarks and some implementations use unusual techniques you'd never consider in a more normal scenario just to win performance. So: it's a game, not a very reliable data source. $\endgroup$ – Eamon Nerbonne Apr 3 '12 at 11:18
10
$\begingroup$

The basic difference between the C++ statement x = a + b and the Python statement x = a + b is that a C/C++ compiler can tell from this statement (and a little extra information that it has readily available about the types of x, a, and b) precisely what machine code needs to be executed. Whereas to tell what operations the Python statement is going to do, you need to solve the Halting Problem.

In C that statement will basically compile to one of a few types of machine addition (and the C compiler knows which one). In C++ it might compile that way, or it might compile to calling a statically known function, or (worst case) it might have to compile to a virtual method lookup and call, but even this has a fairly small machine code overhead. More importantly though, the C++ compiler can tell from the statically known types involved whether it can emit a single fast addition operation or whether it needs to use one of the slower options.

In Python, a compiler could theoretically do nearly that good if it knew that a and b were both ints. There's some additional boxing overhead, but if types were statically known you could probably get rid of that too (while still presenting the interface that integers are objects with methods, hierarchy of super-classes, etc). The trouble is a compiler for Python can't know this, because classes are defined at runtime, can be modified at runtime, and even the modules that do the defining and importing are resolved at runtime (and even which import statements are executed depends on things that can only be known at runtime). So the Python compiler would have to know what code has been executed (i.e. solve the Halting Problem) in order to know what the statement it is compiling will do.

So even with with most sophisticated analyses that are theoretically possible, you simply can't tell much about what a given Python statement is going to do ahead of time. This means that even if a sophisticated Python compiler were implemented, it would in almost all cases still have to emit machine code that follows the Python dictionary lookup protocol to determine the class of an object and find methods (traversing the MRO of the class hierarchy, which can also change dynamically at runtime and so is difficult to compile to a simple virtual method table), and basically do what the (slow) interpreters do. This is why there aren't really any sophisticated optimising compilers for dynamic languages. It's not merely hard to create one, the maximum possible payoff isn't as big as it is for languages like C/C++.

Note that this isn't based on what the code is doing, it's based on what the code could be doing. Even Python code that is a simple series of integer arithmetic operations has to be compiled as if it might be invoking arbitrary class operations. Static languages have greater restrictions on the possibilities for what the code could be doing, and consequently their compilers can make more assumptions.

JIT compilers gain on this by waiting until runtime to compile/optimise. This lets them emit code that works for what the code is doing rather than what it could be doing. And because of this JIT compilers have a much huger potential payoff for dynamic languages than for static languages; for more static languages much of what an optimiser would like to know can be known ahead of time, so you might as well optimise it then, leaving less for a JIT compiler to do.

There are various JIT compilers for dynamic languages that claim to achieve execution speeds comparable to that of compiled and optimised C/C++. There are even optimisations that can be by a JIT compiler that cannot be done by an ahead of time compiler for any language, so theoretically JIT compilation (for some programs) could one day outperform the best possible static compiler. But as Devin rightly pointed out, the properties of JIT compilation (only the "hotspots" are fast, and only after a warmup period) means that JIT-compiled dynamic languages are unlikely to ever be suitable for all possible applications, even if they become as fast or faster than statically compiled languages generally.

$\endgroup$
  • 1
    $\begingroup$ That's now two down-votes with no comments. I would welcome suggestions for how to improve this answer! $\endgroup$ – Ben Apr 4 '12 at 1:16
  • $\begingroup$ I didn't downvote, but you are incorrect about "need to solve the halting problem". It has been demonstrated in many circumstances that code in dynamic languages can be compiled to optimal target code, whereas to my knowledge none of these demonstrations has included a solution to the halting problem :-) $\endgroup$ – mikera Feb 8 '13 at 2:24
  • $\begingroup$ @mikera I'm sorry, but no, you are incorrect. No one has ever implemented a compiler (in the sense that we understand that GCC is a compiler) for fully general Python, or other dynamic languages. Every such system only works for a subset of the language, or only certain programs, or sometimes emits code that is basically an interpreter containing a hard-coded program. If you would like, I will write you a Python program containing the line foo = x + y where predicting the behaviour of the addition operator at compile time depends on solving the halting problem. $\endgroup$ – Ben Feb 8 '13 at 6:44
  • $\begingroup$ I am correct and I think you're missing the point. I said "in many circumstances". I didn't say "in all possible circumstances". Whether or not you can construct a contrived example linked to the halting problem is largely irrelevant in the real world. FWIW, you could also construct a similar example for C++ so you wouldn't be proving anything anyway. Anyway, I didn't come here to get into an argument, just to suggest improvements to your answer. Take it or leave it. $\endgroup$ – mikera Feb 8 '13 at 7:29
  • $\begingroup$ @mikea I think you might be missing the point. In order to compile x + y to efficient machine addition operations, you need to know at compile time whether it is or not. All of the time, not just some of the time. For dynamic languages this is almost never possible with realistic programs, even though reasonable heuristics would guess right most of the time. Compilation requires compile-time guarantees. So by talking about "in many circumstances" you're actually not addressing my answer at all. $\endgroup$ – Ben Feb 8 '13 at 9:35
9
$\begingroup$

Just a quick pointer that outlines the worst case scenario for dynamic languages:

$\qquad$Perl parsing is not computable

As a consequence, (full) Perl can never be compiled statically.


In general, as always, it depends. I am confident that if you try to emulate dynamic features in a statically compiled language, well-conceived interpretors or (partially) compiled variants can come near or undercut performance of statically compiled languages.

Another point to keep in mind is that dynamic languages solve another problem than C. C is barely more than nice syntax for assembler while dynamic languages offer rich abstractions. Runtime performance is often not the prime concern: time-to-market, for instance, depends on your developers being able to write complex, high-quality systems in short timeframes. Extensibility without recompilation, for instance with plugins, is another popular feature. Which language do you prefer in these cases?

$\endgroup$
5
$\begingroup$

In an attempt to offer a more objectively scientific answer to this question, I argue as follows. A dynamic language requires an interpreter, or runtime, to make decisions at run time. This interpreter, or runtime, is a computer program and, as such, was written in some programming language, either static or dynamic.

If the interpreter/runtime was written in a static language, then one could write a program in that static language which (a) performs the same function as the dynamic program it interprets and (b) performs at least as well. Hopefully, this is self-evident, since to provide a rigorous proof of these claims would require additional (possibly considerable) effort.

Assuming these claims to be true, the only way out is to require that the interpreter/runtime be written in a dynamic language, as well. However, we run into the same issue as before: if the interpreter is dynamic, it requires an interpreter/runtime, which also must have been written in a programming language, dynamic or static.

Unless you assume that an instance of an interpreter is capable of interpreting itself at runtime (I hope this is self-evidently absurd), the only way to beat static languages is for each interpreter instance to be interpreted by a separate interpreter instance; this leads either to an infinite regress (I hope that this is self-evidently absurd) or a closed loop of interpreters (I hope this is also self-evidently absurd).

It seems, then, that even in theory, dynamic languages can perform no better than static languages, in general. When using models of realistic computers, it seems even more plausible; after all, a machine can only execute sequences of machine instructions, and all sequences of machine instructions can be statically compiled.

In practice, matching the performance of a dynamic language with a static language could require re-implementing the interpreter/runtime in a static language; however, that you can do that at all is the crux and point of this argument. It's a chicken and egg question and, provided you agree with the unproven (though, in my opinion, mostly self-evident) assumptions made above, we can actually answer it; we have to give the nod to the static, not dynamic, languages.

Another way to answer the question, in light of this discussion, is this: in the stored-program, control=data model of computing which lies at the heart of modern computing, the distinction between static and dynamic compilation is a false dichotomy; statically compiled languages must have a means of generating and executing arbitrary code at run time. It's fundamentally related to universal computation.

$\endgroup$
  • $\begingroup$ Re-reading this, I don't think it's true. JIT compilation breaks your argument. Even the most simple code, e.g. main(args) { for ( i=0; i<1000000; i++ ) { if ( args[0] == "1" ) {...} else {...} } can significantly sped up once the value of args is known (assuming it never changes, which we may be able to assert). A static compiler can not create code that drops the comparison ever. (Of course, in that example you just pull the if out of the loop. But the thing may be more convoluted.) $\endgroup$ – Raphael May 24 '13 at 13:19
  • $\begingroup$ @Raphael I think JIT probably makes my argument. Programs that do JIT compilation (e.g., JVM) are typically statically-compiled programs. If a statically-compiled JIT program could run a script faster than some other static program could do the same work, just "bundle" the script with the JIT compiler, and call the bundle a statically compiled program. This must do at least as well as the JIT operating on a separate dynamic program, contradicting any argument that JIT must do better. $\endgroup$ – Patrick87 May 28 '13 at 16:36
  • $\begingroup$ Hm, that's like saying bundling a Ruby script with its interpreter gives you a statically compiled program. I don't agree (since it removes all distinctions of languages in this regard), but that's an issue of semantics, not concepts. Conceptually, adapting the program at runtime (JIT) can do optimisations you can't do at compile-time (static compiler), and that is my point. $\endgroup$ – Raphael May 28 '13 at 17:39
  • $\begingroup$ @Raphael That there's not a meaningful distinction is sort of the point of the answer: any attempt to rigidly classify some languages as static, and thus suffering from performance limitations, fails for exactly this reason: there's not a compelling difference between a prepackaged (Ruby, script) bundle and a C program. If (Ruby, script) can make the machine execute the right sequence of instructions to efficiently solve a given problem, so could a cleverly crafted C program. $\endgroup$ – Patrick87 May 28 '13 at 20:44
  • $\begingroup$ But you can define the difference. One variant sends the code at hand to the processor unchanged (C), the other compiles at runtime (Ruby, Java, ...). The first is what we mean by "static compilation" while the latter would be "just in time compilation" (which allows data-dependent optimisations). $\endgroup$ – Raphael May 29 '13 at 10:10
4
$\begingroup$

Can you build compilers for dynamic languages like Ruby to have similar and comparable performance to C/C++?

I think that the answer's "yes". I also believe that they can even surpass the current C/C++ architecture in terms of efficiency (even if slighly).

The reason is simple: There's more information in run-time than in compile-time.

Dynamic types are only a slight obstacle: If a function is always or almost-always executed with the same arguments types, then a JIT optimizer can generate a branch and machine code for that specific case. And there's so much more that can be done.

See Dynamic Languages Strike Back, a speech by Steve Yegge of Google (there's also a video version somewhere I believe). He mentions some concrete JIT optimisations techniques from V8. Inspiring!

I'm looking forward to what we're going to have in the next 5 years!

$\endgroup$
  • 2
    $\begingroup$ I love the optimism. $\endgroup$ – Dave Clarke Mar 28 '12 at 10:12
  • $\begingroup$ I believe there were some very specific criticisms of inaccuracies in Steve’s talk. I’ll post them when I find them. $\endgroup$ – Konrad Rudolph Mar 28 '12 at 10:18
  • 1
    $\begingroup$ @DaveClarke that's what keeps me running :) $\endgroup$ – Kos Mar 28 '12 at 11:07
2
$\begingroup$

People who apparently think this is theoretically possible, or in a far future, are completely wrong in my opinion. The point lies in the fact that dynamic languages provide and impose a totally different programming style. Actually, the difference is twofold, even if both aspect are interrelated:

  • Symbols (vars, or rather id<->datum bindings of all kinds) are untyped.
  • Structures (the data, all what lives at runtime) are untyped as well by the types of their elements.

The second point provides genericity for free. Note that structures here are composite elements, collections, but also types themselves, and even (!) routines of all kinds (functions, actions, operations)... We could type structures by their element types, but due to the first point the check would happen at runtime anyway. We could have typed symbols and still have structured ones untyped according to their element types (an array a would just be typed as an array not as an array of ints), but even this few is not true in a dynamic language (a could as well contain a string).

The best perf we can achieve in dynamic programming is, in my opinion, equivalent to the following: implement in C the model of a dynamic language, let's call it $L$, ie a kind of fictional machine, or a complete runtime lib. And then program (in C directly) using only the model, no plain C features. This means having:

  • a totally polymorphic (C) Element type, which includes $L$ type annotations (or a ref to the actual representation of $L$'s type in the model)
  • all symbols are of that type Element, they can hold elements of any $L$ type
  • all structures (again, including model routines) receive only Element's

It is clear for me that this only is a huge perf penalty; and I don't even touch all consequence (the myriad of runtime checks of all kinds necessary to ensure program sensibility) well described in other posts.

$\endgroup$
  • $\begingroup$ +1 Very interesting. Have you read my answer? Your and my thinking seem similar, although your answer does provide more detail and an interesting perspective. $\endgroup$ – Patrick87 Apr 13 '12 at 13:54
  • $\begingroup$ Dynamic languages don't have to be untyped. Implementing a model of a dynamic language in C severely restricts the optimization possibilities; it makes it very hard for the compiler to recognize high-level optimizations (e.g. immutable data), and forces some fundamental operations (e.g. function calls) to go through C. What you describe is not far from a bytecode interpreter, with the bytecode decoding preevaluated; native compilers tend to perform significantly better, I doubt that the bytecode decoding can justify the difference. $\endgroup$ – Gilles 'SO- stop being evil' Apr 13 '12 at 22:05
  • $\begingroup$ @Patrick87: you are right, our lines of thought seem very similar (had not read before, sorry, my reflexion comes from presently implementing a dyn lang in C). $\endgroup$ – spir Apr 14 '12 at 18:28
  • $\begingroup$ @Gilles: I rather agree about "...don't have to be untyped", if you mean not statically typed. But this is not what people think of dyn langs in general, I guess. I personly consider genericity (in the general sense given in the answer above) a feature far more powerful and far harder to live without. We can easily find ways to do with static types by widening our thinking about how a given (seemingly polymorphic) type may be defined, or by giving more flexibility to instances directly. $\endgroup$ – spir Apr 14 '12 at 18:34
1
$\begingroup$

I did not have the time to read all answers in detail ... but I was amused.

There was a similar controversy in the sixties and early seventies (computer science history often repeats itself): can high level languages be compiled to produce code as efficient as the machine code, well, say assembly code, produced manually by a programmer. Everyone knows a programmer is much smarter than any program and can come up with very smart optimisation (thinking actually mostly of what is now called peephole optimization). This is of course irony on my part.

There was even a concept of code expansion : the ratio of the size of the code produced by a compiler to the size of code for the same program produced by a good programmer (as if there had been too many of these :-). Of course the idea was that this ratio was always greater than 1. The languages of the time were Cobol and Fortran 4, or Algol 60 for the intellectuals. I believe Lisp was not considered.

Well there were some rumors that someone had produced a compiler that could sometimes get an expansion ratio of 1 ... until it simply became the rule that compiled code was much better than hand written code (and more reliable too). People were worried about code size in those times (small memories) but the same goes for speed, or energie consumption. I will not go into the reasons.

Weird features, dynamic features of a language do not matter. What matters is how they are used, whether they are used. Performance, in whatever unit (code size, speed, energy, ...) is often dependent on very small parts of programs. Hence there is a good chance that facilities that give expressive power will not really get in the way. With good programming practice, advanced facilities are used only in a disciplined way, to imagine new structures (that was the lisp lesson).

The fact that a language does not have static typing has never meant that programs written in that language are not statically typed. On the other hand it might be that the type system a program uses is not yet sufficiently formalized for a type checker to exist now.

There have been, in the discussion, several references to worst case analysis ("halting problem", PERL parsing). But worst case analysis is mostly irrelevant. What matters is what happens in most cases or in useful cases ... however defined or understood or experienced. Here comes another story, directly related to program optimisation. It took place a long time ago in a major university in Texas, between a PhD student and his advisor (who was later elected in one of the national academies). As I recall, the student was insistent on studying an analysis/optimisation problem the advisor had shown to be untractable. Soon they were no longer on speaking terms. But the student was right: the problem was tractable enough in most practical cases so that the dissertation he produced became reference work.

And to comment further on the statement that Perl parsing is not computable, whatever is meant by that sentence, there is a similar problem with ML, which is a remarkably well formalized language. Type checking complexity in ML is a double exponential in the lenght of the program. That is a very precise and formal result in worst case complexity ... which does not matter at all. Afaik, ML users are still waiting for a practical program that will explode the type checker.

In many cases, as it was before, human time and competence is scarcer than computing power.

The real problem of the future will be to evolve our languages to integrate new knowledge, new programming forms, without having to rewrite all the legacy software that is still used.

If you look at mathematics, it is a very large body of knowledge. The languages used to express it, notations and concepts has evolved over the centuries. It is easy to write old theorems with the new concepts. We do adapt the main proofs, but do not bother for lots of results.

But in the case of programming, we might have to rewrite all the proofs from scratch (programs are proofs). It may be that what we really need is very high level and evolvable programming languages. Optimizer designers will be happy to follow.

$\endgroup$
0
$\begingroup$

A couple of notes:

  • Not all high level languages are dynamic. Haskell is very high level, but is fully statically typed. Even systems programming languages like Rust, Nim, and D can express high-level abstractions succinctly and efficiently. In fact, they can be as concise as dynamic languages.

  • Highly optomizing ahead-of-time compilers for dynamic languages exist. Good Lisp implementations reach half the speed of equivalent C.

  • JIT compilation can be a big win here. CloudFlare's Web Application Firewall generates Lua code that is executed by LuaJIT. LuaJIT heavily optimizes the execution paths actually taken (typically, the non-attack paths), with the result that the code runs much faster than code produced by a static compiler on the actual workload. Unlike a static compiler with profile-guided optimization, LuaJIT adapts to changes in execution paths at runtime.

  • Deoptimization is also crucial. Instead of JIT-compiled code needing to check for a class being monkeypatched, the act of monkeypatching triggers a hook in the runtime system that discards the machine code that depended on the old definition.

$\endgroup$
  • $\begingroup$ How is this an answer? Well, bullet three maybe, if you added references. $\endgroup$ – Raphael Sep 8 '15 at 7:10
  • $\begingroup$ I’m very sceptical of the claim that PGO couldn’t match the performance of the LuaJIT for web application code under typical workload. $\endgroup$ – Konrad Rudolph Sep 8 '15 at 12:47
  • $\begingroup$ @KonradRudolph The key advantage of a JIT is that the JIT adapts the code as different paths become hot. $\endgroup$ – Demi Sep 8 '15 at 15:33
  • $\begingroup$ @Demetri I know this. But it’s very hard to quantify whether this is an advantage — see my answer and the comment discussion there. In a nutshell: while the JIT can adapt to change in usage, it also needs to track stuff at runtime, which incurs an overhead. The break-even for this is intuitively only where frequent changes in behaviour occur. For web apps, there’s probably just a single (or very few) usage pattern for which optimisation pays off, so the minimal performance increase due to adaptability doesn’t offset the overhead of continuous profiling. $\endgroup$ – Konrad Rudolph Sep 8 '15 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.