JIT based on precompiled code templates

Question

This is a crazy idea that I just came up with, and I'm interested in knowing if it would be workable, or if someone already wrote about or implemented it.

Imagine you are on a platform (a game console, iOS, ...) where you cannot implement a JIT compiler due to technical reasons¹ - you cannot make writable memory executable. You can write an interpreter, but you'd like to make it faster. Now, memory is fairly cheap and code is relatively small compared to other assets, so you can always add more pre-compiled code.

What if you just add lots of (ahead-of-time) compiled code pieces to your binary - one for every sequence of instructions you're likely to need? You can make the pieces configurable by passing arguments in through registers or memory. One trivial example is replacing a simple loop (pseudocode)

for i in range(100000):
    array[i] = 0;

with memset(&array, 0, 100000). But you can do a lot better. Compile some typical programs, take the 1000 top N-grams of instructions, and put them in your binary. Now string them together - either using computed jumps (I don't know if they would be available in a typical locked-down system) - or by wrapping the larger ones in functions, or by using some return-based-programming trickery.

There are a few trade-offs here:

• One is that there is much overhead since you have to compile in a lot more code than you actually will use. However, it might be that performance-critical code (for a given platform and use case) has a lot of common pieces. Think graphics code for example.

• Another one is that, while executing the compiled code bits is faster than interpreting them, you have some overhead due to jumping around between the code bits. I also have a hunch that the lack of cache locality between far-apart code pieces might be bad. Both these should be especially true on modern processors.

So, I'm wondering if someone smarter than me already thought about this, and can tell me about these trade-offs, and how well this would work in reality.

---

¹⁾ Note I'm not asking about the legal aspects, which is beyond the scope of the site anyway. Someone might forbid you from writing a JIT compiler, and then you invent something that is technically not a JIT, but the same thing in spirit, and you've just created a lot of work for lawyers. This question is about technical aspects - say you want something JIT-like on a Havard architecture computer.

Answer 1

This idea is... less crazy than I'd have said at first glance. To cast it in more sober language, this would mean:

1. Identifying common patterns in the interpreted code
2. Writing or generating native code equivalent to those patterns
3. Replacing instances of these patterns with calls to the native code

Minus the third step, which is often left to users of the language, this is a very popular way to make dynamic languages faster. Well, they don't grab random N-grams out of the code, they choose meaningful operations for which a separate function makes semantic sense, but still, they speed up (e.g.) Python code by writing common operations in C and calling it in their Python program.

With this prior art in mind, your concerns seem unfounded to me. It will be just like any other natively implemented function, and calling those is usually quite efficient. There is a tiny bit of overhead from the jump (but keep in mind that you have at least one jump per bytecode instruction), and some more from the icache pressure, but if the function was worth optimizing in the first place then the speedup will far outweigh those concerns.

But as always, the devil is in the details. Here are just a few:

• You probably don't want to go by which patterns occur most often, but by which patterns take the most time, which puts you into the realm of profile-guided optimizations. Certainly doable, but quite a hassle in practice.
• If the pattern writes to variables used outside of the pattern or does complicated control flow like returning from the surrounding function, you either need to include the surrounding code in the pattern (and lose opportunities for applying it) or do complicated, problem-specific rewriting of the surrounding code.
• Unless you do the second step manually, the translation to native code can probably not do much better than simply chaining together the dynamically-typed, late-bound operations that the interpreter would perform while interpreting the original code. This often gives a nice speedup, but it's rarely anywhere as drastic as going from an interpreted loop to memset.
• It may be quite hard to choose the appropriate boundaries for the patterns automatically. Maybe you want to assume some inputs are constant, maybe you want to generalize other parts to apply the optimization more generally, etc.
• Dynamic languages usually have quite extensive capabilities to break optimizations.
• Oh my god don't even get me started on how hard it is to statically optimize dynamic languages.
• Really, don't.
• It's so hard you wouldn't believe.
• At the very least you'd have to assume all values involved have one concrete type (and ideally a built-in one that can't be modified) and bail out of the pattern if you find yourself with different types. And even that can break in languages like Ruby where you can even redefine even arithmetic on numbers.
  • (Of course you could stomp your foot and declare that these things are not permitted, but then it's not the same language any more and you could get much greater wins across the board by optimizing the interpreter for this new restriction, or perhaps even make it a static compiler.)

Maybe you can fix some of these problems by getting more inspiration by JIT compilers, specifically tracing ones. That is, run the program, let the JIT compiler identify hot code paths (including assumptions made during optimization) and statically insert these optimized traces into the program. Tracing JIT compilers already know how to handle all these things. It would be mostly an engineering challenge (making data structures and machine code suitable for a static binary).

Another variant on the same idea is to give up on automating the second and third step: Use tools to find patterns that might benefit from optimization, then optimize them manually. Less shiny, but also more likely to actually work.

Conclusion: Nice idea for a thesis, but I wouldn't bet on it working out in its current form.

Answer 2

Congratulations, you invented the DLL.

Edit: Yes, that was a bit brief. A comment would have done. So let me elaborate. A little.

Using pre-compiled code to make compilation of your application faster, particularly targeting parts that are executed often, that is what a dynamic link library offers. It also allows sharing compiled code among different applications. The code in it can be addressed from both compiled languages and interpreted languages. That is the case for the Microsoft Windows world, I do not know about other environments.

DLL's where common in the Win32 era. Most if the Windows operating system is implemented as DLL's. The concept remains in the .net world, the extension of the files is still DLL, although we prefere to call them assemblies there.

So my point is that it is a great idea (although it took Microsoft a while to iron out the versioning issues, commonly known as "DLL hell"), but you are not the first one who came up with it.