Can a dynamic language like Ruby/Python reach C/C++ like performance?

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.

Ichiro

Posted 2012-03-28T01:27:42.453

Reputation: 805

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. – Pedro Rolo – 2016-05-13T11:24:41.283

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. – Andrej Bauer – 2013-01-06T09:55:42.200

I think your question is very badly phrased. "C++ like" - what is like? If C++ does in in 1ns, and ruby does it in 1ms, is that "like" enough? No, a language missing optimization paths can never be as fast as one that knows everything that there is to know. Many of the answers are hypothetical compilers that know some things about your code. But plain Ruby/Python does not guarantee you anything those assume. You need to check at runtime, by design. And even if it's just a single instruction more, you have just proven that this code is slower - by just one instruction - slower nonetheless. – mmlac – 2017-06-07T03:39:31.490

1Can you rephrase the question so it encourages answers backed by proper evidence over others? – Raphael – 2012-03-28T23:29:45.300

@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. – Gilles 'SO- stop being evil' – 2012-03-29T00:19:18.083

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).

– Raphael – 2012-03-29T00:20:56.050

Answers

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.

Konrad Rudolph

Posted 2012-03-28T01:27:42.453

Reputation: 848

Your last sentence is far too strong. Bookkeeping clearly pays off as evidenced when comparing Java w/o JIT against Java w/ JIT. – Raphael – 2012-03-28T11:32:28.113

@Raphael I meant: compared to static analysis and optimisation. – Konrad Rudolph – 2012-03-28T12:22:18.670

Me too. javac used to do that stuff but does not anymore (as JIT is hampered). The observation is that unoptimised (byte-)code with JIT is faster than optimsed (byte-)code. – Raphael – 2012-03-28T12:38:31.887

2@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). – Konrad Rudolph – 2012-03-28T13:10:23.620

I can not say how good javac ever was. However, saying "That’s a “shortcoming” of the compiler then." is not an argument; the statement already assumes you are right. – Raphael – 2012-03-28T13:27:23.650

@Raphael That’s why I put it in quotes. As the rest of the comments explains, I don’t actually consider it a shortcoming. But in principle my argument is (or at least I’m not convinced of the opposite, despite regular insistence) that a static compiler (with PGO) can produce more efficient programs than a JIT, if we include the cost of keeping track of runtime program flow information. And the fact that javac never performed as well as the JIT doesn’t invalidate my point, it just shows that javac never optimised that well. – Konrad Rudolph – 2012-03-28T14:16:42.960

No, it does not show that. Maybe JIT is better than statically compiled code. You do not give reasons for your assumption (static compiler produces faster code than JIT), you take it as granted. Without this assumption, you can not make the statement about javac. – Raphael – 2012-03-28T14:21:03.647

1@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. – Konrad Rudolph – 2012-03-28T14:22:43.780

You offer an interesting point about profile-guided optimisations. I'm not aware that any existing profile-based optimising compilers emit multiple specialised versions of the code they compile (i.e. after seeing a profile where 30% of the time one code path is taken through a function and 25% of the time another path is taken, plus the fully general version to handle anything else), which JIT compilers do automatically. But in theory, yes, with sufficiently detailed profiles there's no reason C++ compilers couldn't do this. – Ben – 2012-03-28T22:07:46.400

However, it's a bit of an apples-oranges situation. You wouldn't make a JIT compiler for C, for the reasons you state. Much information is available ahead of time, so there's less left to gain at runtime, and it would be hard to make the additional overhead less than the gain. For dynamic languages though, most of the information is already being tracked just to implement the semantics of the language, so the overhead is less and the potential payoff bigger. – Ben – 2012-03-28T22:12:02.603

Plus, there really are optimisations that can never be applied by an ahead-of-time compiler. Any "hotspot" that depends on information that is only gathered at runtime (IO basically) can in principle be JIT-optimised for the specific case at hand, but even a profile-based ahead-of-time optimiser is never going to be able to do that. I don't know that your supposition is wrong, but I don't find your arguments conclusive; it's a much more complicated topic than that. – Ben – 2012-03-28T22:21:37.263

1@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? … – Konrad Rudolph – 2012-03-28T22:26:41.900

@Konrad Take PyPy's meta-tracing JIT. It works at the level of the interpreter's code, not at the level of the Python program being run by the interpreter. It effectively optimises the operations of the interpreter, specialised to the user-input Python program it happens to be running. No amount of profile-guided optimisation of the PyPy interpreter could do anything like that. And you can't even statically compile Python at all, let alone PGO it. – Ben – 2012-03-29T00:49:43.830

@Konrad The same sort of principle will apply to any program whose operations are controlled by outside input (if you like, anything "interpreter-like" for a very wide definition of "interpreter", that includes web-servers for example). JIT compilation will detect "hotspots" that actually occur this time the program is run. PGO will detect "hotspots" that occurred in the profile. How do you profile an application whose behaviour varies in an unbounded manner based on runtime information? – Ben – 2012-03-29T00:55:57.473

1@Ben My intuition is that there are two general classes of runtime situations: those without great variability, which are well approximated by a profile; and those which are not, but vary too fast even for the JIT to respond to properly (it first needs to collect quite a lot of profile data, after all). There certainly exists a sweet spot between the two extrema which favours JIT but my intuition is that this sweet spot is very small and doesn’t offset (both in terms of occurrence and gains) the overhead of the JIT. – Konrad Rudolph – 2012-03-29T07:09:49.060

@Ben You said “you can't even statically compile Python at all” … that’s the point: the original question wasn’t AOT vs. JIT, it was static languages vs. dynamic languages. – Konrad Rudolph – 2012-03-29T08:36:55.503

1You could, of course, define a static language which compiles to very inefficient binary, so that any real-world dynamic language would beat it; and vice versa. As I mentioned in another comment, C/C++ can trivially beat or tie any other language in terms of performance, since you can inline assembly directly into the source, and since you could replicate in C/C++ the functioning of any program written in a dynamic language (as well as the associated runtime). If you think that's cheating, let the statically compiled language be bare machine code. You could compile that by hand, if you wanted. – Patrick87 – 2012-03-29T13:14:52.563

1@Patrick87 That’s a valid comment. Nevertheless, I would advance that for typical high-quality code we can make somewhat meaningful comparisons. For instance, even if you require high performance you would usually not use inline assembler in C++ – there’s simply no need to (especially since modern optimisers are pretty smart and know more about the CPU architecture than most programmers). – Konrad Rudolph – 2012-03-29T13:45:51.487

@KonradRudolph Right, but the point is that you have to artificially restrict statically compiled languages in order for there to exist any meaningful comparison. Otherwise, it's rather rather like asking whether whole grains are better for you than food: on the average, this might have a meaningful answer, and for specific examples, it may go either way, but ultimately, the answer is no, since you can do at least as well with food as with whole grains, since anything you can eat that's a whole grain, you can also eat because it's food... – Patrick87 – 2012-03-29T16:31:16.777

4@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. – Ben – 2012-03-30T03:15:56.070

Likewise @Patrick87, unless you want to hand write multiple specialised versions of all your assembler (or write assembler that emits specialised assembler at runtime, i.e. a JIT compiler), it's not true that you can do anything in C/assembler ahead-of-time that a JIT language could do at runtime. And even if you are hand-specialising, you will never write every possible specialised version (and if you did it would probably blow out memory and actually perform worse), so you (or the compiler) can still be surprised. – Ben – 2012-03-30T03:19:58.093

1@Konrad Yes, the original question was static vs dynamic languages, but all your arguments for your "no, by design" answer stem on it costing more to track runtime information than you can possibly gain in runtime-optimisations, which is basically about JITs. I'm not convinced that your intuition is correct, but I don't know that you're wrong either. – Ben – 2012-03-30T03:29:40.687

@Ben My argument follows from the fact that dynamic languages need to track runtime information, and efficient execution of dynamic languages necessitates a JIT with HotSpot optimisation. – Konrad Rudolph – 2012-03-30T10:14:42.097

@Ben "(or write assembler that emits specialised assembler at runtime, i.e. a JIT compiler)" I think you just refuted your own refutation, if that's what the comment was intended to be. In any event, yes, that was the idea. – Patrick87 – 2012-03-30T16:39:00.280

1@Patrick87 So your argument that statically optimized C++ can always do at least as well as a JIT compiler because you can hand code a JIT compiler in C++? Technically true, but I find it uninteresting. I find it more interesting (and fair) to compare what an optimising JIT compiler can do to "normal" code and what an optimising AOT compiler can do to "normal" code. Very very few programmers will ever hand-write a JIT compiler, but very very many programmers will make use of JIT optimisation and AOT optimisation. – Ben – 2012-04-02T00:27:53.797

@Konrad: That dynamic languages need to track runtime information anyway makes them very good candidates for dynamic runtime optimisation (and very poor candidates for static optimisation). It doesn't say anything either about whether dynamic runtime optimisation is inherently unable to make up for the overhead of tracking that runtime information. The only reason you've offered for that claim is that PGO can be done without tracking runtime information and is just as good as JIT optimisation; and that's not true, either in theory or of current PGO-ing compilers that I'm aware of. – Ben – 2012-04-02T00:33:36.517

@Ben Uninteresting, maybe, but clearly true, and clearly an answer to the question. If you want to limit static languages to make the question more interesting, go for it; but you should carefully define what limitations you're assuming, and exactly what it is you're comparing. If you're talking about "usual" (=average?) statically compiled programs, are you comparing to "usual" dynamic programs, which might not make very good use of the JIT? Are dynamic programs allowed to implement JIT (or static?) compilers, if doing so would boost performance? – Patrick87 – 2012-04-02T00:49:06.327

@Patrick: To be honest, the performance of a JIT handwritten in assembler is not what I would describe as "C/C++ like performance", any more than I would describe the performance of a Python program that is largely a CPython extension as "Python-like performance". The question is about language implementations (i.e. the C++ compiler and the Python interpreter), not about what you can get by rewriting large amounts of your program in a lower level language that effectively bypasses that implementation. – Ben – 2012-04-02T03:01:39.210

@Ben My impression was that the question was about dynamic vs. static language performance. In any event, inline assembler is part of of the C/C++ language, right? It's not an extension... anyway, I think it's probably fine to agree to disagree. You think my approach misses the point, and I think yours relies on notions which aren't well defined. That's OK. – Patrick87 – 2012-04-02T03:12:31.077

@Patrick Doesn't inline assembler rely on compiler extensions to the language spec? I wouldn't call inline assembler C++, more of a foreign language interface. Much as many languages support including fragments of C in their source files to support interfacing with libraries written in C; by your argument I could claim that the performance of every one of those languages is equal or better than C++ in all instances. But that's useless as an attempt to look at language performance. – Ben – 2012-04-02T05:09:16.313

@Ben “[You claim] that PGO … is just as good as JIT optimisation; and that's not true …” – No. I claim (1) that PGO is just as good in most (not all!) cases, and (2) that the overhead a JIT inherently carries outweighs the small edge it may occasionally gain on PGO. And once again, I acknowledge that I have no empirical data to back this up and that collecting such data in a comprehensive and impartial manner is very hard, maybe impossible. – Konrad Rudolph – 2012-04-02T09:09:25.357

3Notice: 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. – Robert Cartaino – 2012-04-09T19:41:04.127

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.

Devin Jeanpierre

Posted 2012-03-28T01:27:42.453

Reputation: 317

@Patrick87: Sorry to necrocomment but I would object since there is no such thing as inline assembly in the standard C or C++ languages (which we're talking about here). They're not talking about extensions to those languages. Otherwise someone could hypothetically assume a version of Python that allows embedded C++ or even assembly and then it'd be a meaningless question in the first place. – user541686 – 2016-12-13T07:45:00.280

1"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. – Ben – 2012-03-28T05:27:03.597

1About 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. – Raphael – 2012-03-28T06:58:50.733

@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. – Lie Ryan – 2012-03-28T08:06:48.940

@Ben Lie caught my intention. I didn't want to say only a subset was possible to compile, because that's not actually true (it just happens to be true for RPython), so I settled for, "or rather, only a subset can do well". I'll edit it to make this more clear though. – Devin Jeanpierre – 2012-03-28T09:26:09.233

9@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. – TC1 – 2012-03-28T09:26:17.100

@TC1: True enough. In the context of this question, however, we can say that "when the tight mem control and metal grit are needed" you have clearly left the space of scenarios dynamic languages were designed for, so the question becomes moot/unfair. – Raphael – 2012-03-28T09:56:48.390

@Raphael There's no need to compare Java with compiled C++, since you can compare Java to compiled Java directly. This makes the issue of good/bad C++ code moot. The GNU Compiler Collection has the gcj compiler which effectively parses Java for the C++ backend. My own experiments with this (term paper way back when) was that compiled Java did better than JIT Java in most cases. – Pedro – 2012-03-28T09:58:59.460

@LieRyan: Not really trivial. The type inference that makes RPython work is a whole program analysis. So it's all or nothing. Plus, RPython is so different from Python that it's extremely unlikely for normal Python code to be compatible with it, so in practice your RPythoncompiler with fallback to interpreter would just be an interpreter. I do not believe these facts are accidental. Other projects may be able to work as you describe, but RPython simply isn't a Python implementation, and cannot be made to be one. – Ben – 2012-03-28T11:13:08.010

@Pedro: True, but immaterial. What we really compare is (partially) interpreted execution vs native code, at least if we talk about Java vs C++. If you compile Java to native code, most if not all differences are expected to vanish, anyway. – Raphael – 2012-03-28T12:40:04.130

@Raphael: I think you may have misunderstood my point. If you compare JIT Java to compiled Java, you get the semantically identical code, once with JIT, and once without. Once with dynamic analysis, once with static analysis. This is probably the most powerful comparison you can get, since it avoids any language-dependent side-effects. – Pedro – 2012-03-28T12:54:06.340

7Comparing 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.). – Patrick87 – 2012-03-28T13:20:33.750

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.}

Gilles 'SO- stop being evil'

Posted 2012-03-28T01:27:42.453

Reputation: 39 868

@Eamon Nerbonne : 1) There is NO requirement that programs be "typical of the language". 2) In a normal scenario you'd use whatever techniques were required to meet the performance goals. 3) It is a reliable source of data about the programs presented. It is not a prophesy about the performance of some other programs. – igouy – 2016-05-26T21:21:27.960

@Gilles : No reason to cross-out "apples and oranges" (see http://benchmarksgame.alioth.debian.org/dont-jump-to-conclusions.html#apples-and-oranges ) and please update the URLs.

– igouy – 2016-05-26T21:29:15.410

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. – Konrad Rudolph – 2012-03-29T09:27:44.737

@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”. – Gilles 'SO- stop being evil' – 2012-03-29T21:54:17.733

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”. ;-) – Konrad Rudolph – 2012-03-29T22:26:37.883

@KonradRudolph If I wanted guesses, I'd ask on [programmers.se]. – Gilles 'SO- stop being evil' – 2012-03-29T22:28:30.330

Well, informed guesses are rather different from conventional guesses. Incidentally, I think your answer does a very good job in this department (informed guess, that is). – Konrad Rudolph – 2012-03-29T22:31:07.923

1The 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. – Eamon Nerbonne – 2012-04-03T11:18:00.857

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.

Ben

Posted 2012-03-28T01:27:42.453

Reputation: 1 464

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 :-) – mikera – 2013-02-08T02:24:24.697

@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. – Ben – 2013-02-08T06:44:42.080

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. – mikera – 2013-02-08T07:29:23.113

@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. – Ben – 2013-02-08T09:35:06.787

Not sure why you want to argue with me. Go read up on type inference instead. A significant proportion of the time, it can prove the types in a dynamic language and compile to optimal target code. Clojure often does this in primitive maths expressions, for example, and exactly matches Java's static-typed performance. Also dynamic type specialisation (as in V8) and polymorphic inline caches (as in many JVM JITs) can often get you to near-optimal solutions as well. These are all proven solutions for realistic programs. – mikera – 2013-02-08T11:13:18.613

@mikera I know plenty about type inference, thank you. For exmaple, I understand how Haskell and RPython's type inference works. Clojure I don't know much about, so I'll defer to you there. But if you'd read my answer, you'd see my whole point was that efficient ahead-of-time compilation is not generally possible for dynamic languages, but JIT compilation is. So we're basically saying the same thing from a practical point of view, only you chose to start by saying that I was incorrect. Read my answer. It already addresses everything you've said, and comes to the same conclusion you do. – Ben – 2013-02-08T16:41:15.477

1That's now two down-votes with no comments. I would welcome suggestions for how to improve this answer! – Ben – 2012-04-04T01:16:53.060

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?

Raphael

Posted 2012-03-28T01:27:42.453

Reputation: 69 237

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!

Kos

Posted 2012-03-28T01:27:42.453

Reputation: 167

2I love the optimism. – Dave Clarke – 2012-03-28T10:12:58.397

I believe there were some very specific criticisms of inaccuracies in Steve’s talk. I’ll post them when I find them. – Konrad Rudolph – 2012-03-28T10:18:46.297

1@DaveClarke that's what keeps me running :) – Kos – 2012-03-28T11:07:14.723

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.

Patrick87

Posted 2012-03-28T01:27:42.453

Reputation: 12 349

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.) – Raphael – 2013-05-24T13:19:06.957

@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. – Patrick87 – 2013-05-28T16:36:13.013

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. – Raphael – 2013-05-28T17:39:57.750

@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. – Patrick87 – 2013-05-28T20:44:38.927

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). – Raphael – 2013-05-29T10:10:58.277

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.

spir

Posted 2012-03-28T01:27:42.453

Reputation: 29

+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. – Patrick87 – 2012-04-13T13:54:27.483

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. – Gilles 'SO- stop being evil' – 2012-04-13T22:05:22.290

@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). – spir – 2012-04-14T18:28:06.783

@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. – spir – 2012-04-14T18:34:25.557

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.

babou

Posted 2012-03-28T01:27:42.453

Reputation: 18 549

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.

Demi

Posted 2012-03-28T01:27:42.453

Reputation: 509

How is this an answer? Well, bullet three maybe, if you added references. – Raphael – 2015-09-08T07:10:13.103

I’m very sceptical of the claim that PGO couldn’t match the performance of the LuaJIT for web application code under typical workload. – Konrad Rudolph – 2015-09-08T12:47:05.670

1@KonradRudolph The key advantage of a JIT is that the JIT adapts the code as different paths become hot. – Demi – 2015-09-08T15:33:56.187

@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. – Konrad Rudolph – 2015-09-08T15:40:33.613