6
$\begingroup$

Do guarantees provided by the type systems enable better performance optimizations by the modern compilers? I found a 20+ year article suggesting that it would. Also, intuitively speaking, knowing more about the code in advance should also be useful. However, a friend claims that modern JIT compilers make such claim irrelevant. In his words:

This is a paper from 1998. Today, JIT compilers eliminate many of the cases mentioned in the paper for dynamically typed systems. For example, JavaScript uses integer arithmetic for integer types, without knowing the type declarations in advance. I doubt if predeclared types are as significant for performance today as they were two decades ago. Native instruction set and memory management mechanisms seem to have much more influence on performance to me.

What's the situation in modern compilers?

Improve this question
$\endgroup$
3
  • $\begingroup$ The conventional wisdom is that statically typed languages are still faster -- this is seen in the trend to stick with languages like C/C++, Rust, and Go for performance-critical code (and avoid dynamically typed languages like Python). I suspect that JIT compilation closes the gap for some, but not all cases: the rule of thumb is that any compiler is just not as smart as what can be done by an expert by hand, so there will be cases where any compiler technique that tries to imitate the benefits of static types fails to deduce the required typing information. $\endgroup$
    – 6005
    Dec 26 '20 at 23:51
  • 1
    $\begingroup$ See StackOverflow. But I would be interested to see an answer from an expert in modern compilers and compiler performance; there is probably more subtlety to the issue than what I say above. $\endgroup$
    – 6005
    Dec 26 '20 at 23:51
  • 1
    $\begingroup$ @6005: You have to be careful not to confound multiple independent variables. For example, in many benchmarks I have seen, people are comparing a C compiler optimized for decades by dozens of highly experienced compiler developers with a Ruby interpreter written over a couple of weekends by a single person who even admits to knowing nothing about writing language implementations. Also, these benchmarks are typically run on operating systems and CPUs that are optimized for C, whereas we know from experience that e.g. virtual memory absolutely hurts languages like Java with no benefit. $\endgroup$
    – Jörg W Mittag
    Dec 27 '20 at 14:03
7
$\begingroup$

I think your friend somewhat presents a false dichotomy.

I will just give one example: when it first came out, the Self VM was one of the fastest dynamic language implementations. In fact, the Smalltalk VM written in Self that shipped as part of the Self system was one of the fastest Smalltalk VMs of its time, despite being written in a dynamic language (much more dynamic than Smalltalk, Python, or Ruby) and running on top of another VM.

Even more, at the time it was first released, Self was one of the fastest OO language implementations in general, even competing with some C++ compilers of that time.

However, it achieved this performance precisely because of its aggressively optimizing JIT compiler aided by dynamic type inference and type feedback!

It is precisely because JIT compilers have more and better type information than AOT compilers that JIT-compiled language implementations can be so fast.

A JIT compiler can potentially have all the same information available that an AOT compiler has. But, a JIT compiler also has runtime information that an AOT compiler cannot possibly have because of all our favorite impossibility results such as the Halting Problem, Rice's Theorem, etc.

For example, Escape Analysis is equivalent to solving the Halting Problem. So, an AOT compiler cannot know in every circumstance whether a reference will escape the local scope or not, and thus must conservatively allocate it under the assumption that it will escape. A JIT compiler, however, can simply assume that the reference will never escape and compile the code accordingly, and then when it observes the reference escaping at runtime, it recompiles the code. (This is sometimes called Escape Detection.)

Likewise, Class Hierarchy Analysis is equivalent to solving the Halting Problem (in languages with dynamic code loading at least). So, an AOT compiler is limited in its ability to de-virtualize and thus inline potentially overridden methods. A JIT compiler, however, can simply look at the class hierarchy at runtime and see whether the method is overridden or not, and thus potentially inline it. And if it observes a piece of code loaded later that overrides the method after the fact, it can re-compile the code so that the method is no longer inlined but dynamically dispatched again.

So, yes, type information is helpful, and JIT compilers do use type information in their optimizations, including type information empirically collected at runtime that is not available to AOT compilers.

Your friend even uses an example of using type information in their own example! Modern ECMAScript execution engines indeed use type information about numeric values collected at runtime to optimize them even though semantically ECMAScript only has IEEE Std 754-2019 binary64 as its one and only numeric type. (The recently added bigint is a distinct type with distinct numeric literals.) Typically, modern ECMAScript execution engines will segregate numeric values into at least doubles and 53 bit integers, possibly even more.

Similarly, they will detect the type of arrays and represent them as machine arrays (i.e. contiguous pieces of memory) even though semantically, an array is actually just a dictionary whose keys are the strings "0", "1", "2", etc.

The two key differences between an AOT compiler and a JIT compiler are:

  • The JIT compiler has more information available: it can theoretically gather all the same static information that an AOT compiler can, but it also has runtime information available that the AOT compiler cannot possibly have.
  • On the flip side, the AOT compiler has "infinite" resources available (it can take as long to compile and use as much RAM as it wants), whereas the JIT compiler is competing with the user program for the same resources while the user is waiting for their program to start.

However, the kinds of information and the kinds of optimizations are mostly the same for both. Both like long stretches of straight-line code, both like type information, etc.

Personally, I believe that the best possible performance will come from an approach that has not yet been heavily explored commercially: use an AOT compiler to crunch out as much static information as possible, and perform heavy and expensive optimizations, but keep all that information around and keep a rich representation of the program. Then, hand this off to a JIT compiler which can use all of the expensively calculated information and the rich representation to even further optimize at runtime.

Real world systems typically work differently. For example, C++ compilers are highly sophisticated, by they typically produce very low-level "anemic" output such as x86 machine code which has no types and loses almost all of the information and intent of the original program. On the other hand, we have typical Java implementations which have sophisticated JIT compilers but very stupid practically non-optimizing AOT compilers.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Regarding "keep all that information around". This is not without performance penalties: more code = more memory bandwidth needed, caches get polluted, prefetching becomes less effective etc. I am not saying that what you propose is not an interesting idea, but there are all manner of subtleties here, which might explain why the "approach that has not yet been heavily explored commercially". Optimising compilation whether JIT or AOT is hardL everything obvious has been tried. $\endgroup$
    – Martin Berger
    Dec 28 '20 at 20:14
  • 1
    $\begingroup$ The optimisations a JIT compiler makes can also become obsolete over time. JIT compilers, due to the extreme performance cost of compilation, only compile small fragments of code, so called hot code. The decision of which code is hot can be wrong. A good example of this is JIT-compilation of programming language interpreters: standard techniques for hot-code detection systematically get this wrong. And trigger worst-case performance. This probable has lead to the development of meta-tracing (pioneered by PyPy). $\endgroup$
    – Martin Berger
    Dec 28 '20 at 20:15
  • $\begingroup$ @MartinBerger: I like the pragmatic approach that was at one point taken by V8: compiled code is allocated on the GC heap like any other object and weakly referenced. So, anytime a full GC happens, the code is thrown out, and on the next execution, it traps into the JIT again. I believe they no longer use that strategy, but it was an interesting approach through radical simplification. $\endgroup$
    – Jörg W Mittag
    Dec 28 '20 at 20:18
  • $\begingroup$ JITs are most effective when the language run-time (1) needs to maintain a lot of dynamic information in order to work correctly anbd (2) in hot loops most of the edge cases don't show up, so most of that dynamic information is not actually needed for the execution of the loop. Statically typed languages simply need less information at run-time to work correctly. So a JIT has less to optimise away. $\endgroup$
    – Martin Berger
    Dec 28 '20 at 20:20
  • $\begingroup$ Regarding the pragmatic approach, JIT compilers, especially tracing JITs produce a huge amount of ~junk~ information (see already the tracing cache of Dynamo: A Transparent Dynamic Optimization System, the first tracing JIT). But note that recompiling is a very expensive operation at run-time. $\endgroup$
    – Martin Berger
    Dec 28 '20 at 20:22
2
$\begingroup$

If the language allows that the same variable x could have different types on different executions of a procedure, that doesn't mean the programmer actually wants to use this feature, or does use the feature. Typically you have three cases: 1. x has always the same type (but without proof). 2. x has the same type in 99.99% of all cases. 3. It happens quite regularly that x has different types.

In the first case, which I assume you are mostly interested in, most likely you will end up with code like "if x has type T then ... else "generate and execute code for another type". The performance impact will depend on how often the test has to be done. For example if you have a loop iterating for start <= i <= end, there's a good chance that the code looks like "if "start" has type int and "end" has type int then "run a loop assuming that "start", "end", "i" and variables derived from them all have type int" else "generate and execute code for other cases". The performance impact will be minimal.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Indeed. On many modern highly-pipelined CPUs with branch prediction and speculative execution, a correctly predicted branch is essentially free. Type tags are typically implemented as comparing an immediate constant against a pointer value near the top of the object header (thus likely in L1 or even in a register already). Typically, JIT compilers generate very different code for monomorphic, low-polymorphic, and "megamorphic" call sites. The keyword here is Polymorphic Inline Cache, which I believe was one of the innovations of the Self VM. $\endgroup$
    – Jörg W Mittag
    Dec 27 '20 at 23:52

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.