Skip to content
The methodOpen data
Back to the collection

Simple and Effective Type Check Removal through Lazy Basic Block Versioning

Maxime Chevalier-Boisvert, Marc Feeley

2014 · arXiv

Programming languagesAlgorithms
Read the paper
HN score
0
Mentions
6
Readers
5
Months
6
What’s in a score?

From the abstract

Dynamically typed programming languages such as JavaScript and Python defer type checking to run time. In order to maximize performance, dynamic language VM implementations must attempt to eliminate redundant dynamic type checks. However, type inference analyses are often costly and involve tradeoffs between compilation time and resulting precision. This has lead to the creation of increasingly complex multi-tiered VM architectures. This paper introduces lazy basic block versioning, a simple JIT compilation technique which effectively removes redundant type checks from critical code paths. This novel approach lazily generates type-specialized versions of basic blocks on-the-fly while propagating context-dependent type information. This does not require the use of costly program analyses, is not restricted by the precision limitations of traditional type analyses and avoids the implementation complexity of speculative optimization techniques. We have implemented intraprocedural lazy basic block versioning in a JavaScript JIT compiler. This approach is compared with a classical flow-based type analysis. Lazy basic block versioning performs as well or better on all benchmarks. On average, 71% of type tests are eliminated, yielding speedups of up to 50%. We also show that our implementation generates more efficient machine code than TraceMonkey, a tracing JIT compiler for JavaScript, on several benchmarks. The combination of implementation simplicity, low algorithmic complexity and good run time performance makes basic block versioning attractive for baseline JIT compilers.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

6 selected excerpts · 6 total mentions

whizzter
Neutral mention · rule
Afaik the only ones that's somewhat successfully used LLVM for a dynlang JIT is the Safari guys, and iirc that one was only for the highest optimization level (and that is an important hint on their direction and one that most dynlang JIT's should head). The goals and constraints of practical dynlang JITs often differ a bit from those for statically typed languages. The JITs for statically typed languages are often fairly "straightforward" since the basic/primitive types are often known, and with the exception for dispatch optimizations, many large wins comes from register allocation,etc. A dynlang JIT on the other hand far more often has unstable basic types that goes…
Read the full comment
along with type guards,etc. You have a ton of optimizations in that regard that comes before it's even time to consider more than basic register allocation optimizations (See for example the recent posts on the new Erlang JIT). In this particular case Maxime's PHd was a JS JIT that implemented something called Basic-Block-Versioning, you can see an early paper on this at https://arxiv.org/abs/1411.0352 My suspicion is that the existing codegens you mention comes with a lot of baggage that might be in the way of how a lazy codegen like they want should be structured. I wrote a small experimental lazy dynamic JIT once and the structure definitely got twisted around and "direct" access to all parts definitely was a plus.
Original comment Ruby: Porting YJIT to Rust
PeCaN
Neutral mention · rule
Because with 80%+ unused code, your instruction cache is gonna choke. Also JITs can remove many more type checks, because it knows when a check would be redundant. See e.g. Lazy Basic Block Versioning[1], but existing tracing JITs do quite well also. 1. http://arxiv.org/abs/1411.0352
Original comment Experimental support for WebAssembly in V8
PeCaN
Neutral mention · rule
Dart's performance is pretty good; its authors are VM geniuses. If it doesn't already[1], it could leverage the optional typing for block versioning on initial compilation, and assume that version is correct most of the time (generating the most-optimized version initially because you expect to not bail out of this block version). This way you wouldn't have to warm up for type inference. If the program type-checks you can get almost static type performance. Dart also has an advantage in app startup time since you can just load your snapshot. -- 1: I'm not familiar with the internals of the Dart VM, but I don't believe it leverages block versioning[2] at the moment. That seems like a low hanging fruit when you already have type hints. Your initial baseline compile can generate a specialized version from the get-go then lazily add other blocks if the type hints are wrong. 2: http://arxiv.org/abs/1411.0352
Original comment Kotlin for Android Developers

Keep following the thread.

More in Programming languages

More from the same topics.