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.