Does strong typing contribute to better performance optimization by compiler?

Question

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?

Answer 1

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.

Answer 2

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.