2

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


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

5
  • 3
    read up on threaded code, an implementation technique mainly used by Forth compilers to produce extra-small executables.
    – amon
    Jan 13, 2016 at 19:54
  • @amon: Thanks, I was looking for something like that! There is even a direct connection from the hacking techniques (ROP) that inspired this question back to the idea of threaded code.
    – jdm
    Jan 13, 2016 at 23:44
  • Now there is Copy and Patch (PDF) which implements this idea!
    – tekknolagi
    May 3 at 1:39
  • While this is cool, it still needs to write to executable memory, failing the framework of the question. May 3 at 6:53
  • Ah, I missed that. Then there is TCTI, which is used in QEMU on restricted platforms: twitter.com/ktemkin/status/1376019469730934784 / github.com/tctiSH/qemu
    – tekknolagi
    May 3 at 15:38

2 Answers 2

5

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.

2
  • Thanks for this very detailed answer! Comments: - I was thinking about going beyond the equivalent of numpy or C extensions in Python. E.g., the pieces of machine code would not necessarily be functions, they wouldn't maintain a stack or adhere to the calling convention. - I'd not start from scratch, I know the difficulties in compiling dynamic languages. The baseline would be ~an existing JIT compiler (like PyPy, V8, ...), and you'd use this trick to get around "write XOR execute" limitations. And I agree, a cool idea for a thesis, but beyond my capabilities...
    – jdm
    Jan 13, 2016 at 23:08
  • @jdm Not making them functions raises other problems though. For one, how do you ensure the code snippet can be used in all places where you want to use them? For example, the snippet needs to read and write local variables, but in many bytecode VMs you need the right register number/stack offset to access locals, and these will vary at each use site. As for directly using JIT compilers: This still has significant engineering challenges. For example, PyPy can't cache its traces to the disk because the traces directly embed many pointers that are only valid for the current process.
    – user7043
    Jan 14, 2016 at 15:54
-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.

5
  • I realize this is a somewhat descriptive answer. It would be a much better one if you could describe how a DLL lines up with the concepts presented in the question post and if there are any parts of the question that don't align properly with DLL. This would be especially useful for the programmers who haven't gone deeply into writing DLLs (as a unix side coder I know about shared libraries - but the idea of a DLL for perl or python or lua or dc doesn't ring any bells).
    – user40980
    Jan 13, 2016 at 22:11
  • I don't see what any of this has to do with the question.
    – user7043
    Jan 13, 2016 at 23:12
  • I should have said it explicitly (and I did but edited it out), but the idea was to go far beyond optimizing individual functions by putting them in DLLs. In the terminology of exploits and shellcode, the idea was to intentionally put a lot of "gadgets" into memory and connect them via something like return-oriented-programming and clever use of conditional jumps, moves, etc..
    – jdm
    Jan 13, 2016 at 23:14
  • Perhaps I still do not understand the question. Putting executable code in memory upfront only strengthens my association with DLLs. Be it that a DLL does not contain "guesses" or "may be useful", it is just compiled source code. Part of the miscommunication may be that you seem to be from a UNIX environment and I am familiar with Windows. Is shell code your reference? I may have to move my frame of reference from C(#) to PowerShell. Which does pre-load objects in memory to be used by the script. We call them cmdlets rather than gadgets. Anyway, I am sorry if I am missing the point. Jan 14, 2016 at 7:05
  • @MartinMaat: Ahh, no shell code is only indirectly related to shells like powershell or bash :-) It comes from hacking/cracking jargon. If you find a buffer overflow etc. in a program on another PC, you can write a piece of evil machine code, the "shellcode", and inject it. The program crashes, executes the evil code, and gives you a shell, meaning you now have a command line on the hacked system! There are specific techniques used to build this kind of code - you have to circumvent protection mechanisms and use bytes already in memory. I proposed to use these tricks to build a new compiler.
    – jdm
    Jan 14, 2016 at 17:44

Not the answer you're looking for? Browse other questions tagged or ask your own question.