I was not impressed by author’s surprise that original emulation ran at 1/10th speed. For the past 50 years, that’s usually the target for calling (“unaccelerated”) emulation good enough. Especially for architectures that are current or in development or otherwise require some sort of instruction translation.
The last 30 years we’ve seen innovations like dynamic recompilation, fat binaries, JIT VMs, and profile guided optimization. So that has created an expectation of sub-order of magnitude run time performance. It’s a fanciful time we live in.
Hey, author here. That's fair, I didn't have the background. I knew interpreters would be slow, I just didn't expect it to still be ~10x after all the optimizations. After reading about it more though, that does seem to be the norm
The coolest interpreter technique I saw was one that put instruction bodies in static functions which the "compiler" main loop would memcpy the body of the function out to straight-line code that would be executed from memory - a poor man's jit. All instruction functions had the same args and gcc would emit position independent code with the same predictable register calling convention. Brittle as hell, sure, but great compilation speed with low run-time overhead. It was able to run interpreted code at 1/5th of compiled code speed, compared to 1/10th speed for typical highly optimized computed goto loop interpreters.
I can't find a link, but if anyone recalls or wrote such an jit interpreter, please post.
Odd that the Wikipedia article gives 2021 as the first description of this technique when it is far, far older than that. I worked with a software rasterizer JIT that used it in ~2003 and I thought similar techniques were used in the classic MacOS m68k emulator on PowerPC.
Neat, I guess this gets you the same output as a per-instruction translator without having to run an assembler and linker over the whole program. I should try this and add it to the post for completeness
CPU architectures evolve and often get replaces, eg Mac has moved from 68k -> Power -> x86 -> ARM or even Windows PC have also jumped from 32 to 64 bits and the same is also true of SIMD.
Why dont O/S support executables with something like LLVM binaries and generate the native code at load time ?
This would solve so many problems including the need for emulators, because all binaries would work on all CPUS, and the OS would produce the best code at load time.
No more cpu detection, vector stuff always works on the latest & widest instructions that are available. CPUs can also retired old legacy instructions without worry and more.
This does exist, we call it Java (or C# or probably a dozen other implementations)
The big tradeoff you're making is that you have significantly less time to run your optimizer, since not everybody has a beefy machine or the patience to wait a day for their browser to start first time.
You could try doing optimization ahead of time, but I think (I could be wrong here) you would inevitably end up adding in some CPU assumptions if you went much further.
This also somewhat conflicts with an advantage of VM based execution, that new optimizations apply to old binaries.
I'll also note that hand rolled assembly/SIMD code still beats compilers at the extreme end and you would either have to throw that away, or get all the disadvantages mentioned above without all the advantages
You can work around this in various ways yes (I'll add dynamic recompilation to your list of workarounds), but you're always going to have the problem of "Somebody downloaded a program and want to run it now"
Yeah, however in that very specific scenario it isn't about any winning SPEC benchmark suit.
Adding another workaround, shipping the JIT cache metadata alongside the program, and dynamically sharing it across all devices of the same category, as done in Android.
I do most of my work in java (https://github.com/mP1)... so i am familiar with it. Java is a high level language, and the native optimisations are done by the JVM vendor which basically boils down to Oracle today.
Some people might write some native code that is faster, but that is hardly the norm.
There are many classes of programs that dont work particularly well if written in java, such as video editing or graphics because you know the rest.
Regarding OSes still being sold today that use this idea, IBM i with Timi, Unisys ClearCase (started as Burroughs B5000 in 1961), Android, Java and .NET on embedded devices.
Then we have the ones from past times, Xerox PARC workstations with programmable microcode, Modula-2 M-Code on Lilith, Oberon slim binaries, Inferno with Limbo, Pascal UCSD P-Code, Andrew Compiler Toolkit...
Ah, and the WebAssembly folks pretending they are the very first with this idea.
«Why dont O/S support executables with something like LLVM binaries and generate the native code at load time ?»
I've wondered this too. I can think of two systems "IBM i" (formerly OS/400) [1] and Oberon "Slim Binaries" [2] off the top of my head. I suspect that the answer to your question is some mix of path dependence and engineering trade-offs.
For example, if the system has unix-style paged virtual memory (which Oberon did not), it's probably convenient to be able to directly map pages of native instructions into memory without needing to translate or massage them first.
In the case of "IBM i", which I've only ever read about, it sounds like it moves complexity from e.g. the compiler into the loader and so closer to the Kernel of the operating system. If I wanted to better understand the net cost/benefit analysis of this design I'd look for more detail on work done to port to PowerPC.
Apple used to require apps submitted to its iOS App Store to be in the Bitcode format, and they would «recompile» the Bitcode into the exact user's iPhone CPU architecture at the download time – pretty much what OS/400 does. For reasons unknown, they have discontinued Bitcode.
Contrary to other bytecode formats, LLVM bitcode is not stable, even across minor releases.
So anyone using it as bytecode format, like Apple, has to keep their own branch, and eventually it becomes too much work.
Microsoft did the same for DirectX DXIL, as did Khronos with the original SPIR definition, thus SPIR-V came to be as replacement, and recently Microsoft also decided to replace DXIL with SPIR-V.
Functionally, Bitcode delivers – a .bc file can be compiled into any architecture LLVM supports. I have tested a few supported architecture, and it worked like a charm.
Stability of the Bitcode format across releases is orthogonal to the functionality it provides. Given that OS/400's TIMI has been a long-running success, it is possible to put extra effort into stabilising the Bitcode format as well. Benefits would be numerous and significant, ranging from CI/CD to apps taking advantage of new or enhanced ISA extensions.
Yeah but that is the thing, for those that care about stability there are better options already.
Starting by the hyped WebAssembly, which I reckonignise it is useful, only not as breakthrough as it gets advertised given how many bytecode formats have existed since 1958.
Self modifying code is not allowed on some o/s because pages with code are marked as non writable, because bad things can happen when code is writable, eg buffer overflows.
Yeah, I went back and forth on the title. It's definitely not an interpreter. I still think of emulation as the umbrella term though, running code for one architecture on another, with interpretation and dynamic/static recompilation being different ways to get there
Emulation visits instructions as they are executed. Static recompilation will (at translation time) visit instructions that can be discovered, even if they never run.
eg:
if (rand64() == 0x123456789abcdef0ull)
baz = bar;
an emulator will likely never visit that assignment. A static recompiler will translate it.
IDK, a lot of the emulators I've seen and a couple I've written will visit that. Not everything is built on simple traces, but a lot of the time will translate more complex graphs at a time.
In my limited understanding, static recompiling is like JIT transpilation from one arch to another where emulation runs each instruction calling behaviour depending on the instruction. As for tradeoffs my knowledge is not wide enough to declare anything certain.
Author here, thanks for all the comments, didn't expect this to get picked up.
I've been working on speeding up RISC-V emulation for work and wrote this up as I went. Still learning this space, so I'd be keen to hear from people who've worked on emulators or binary translation, especially where you think this approach falls short
I was not impressed by author’s surprise that original emulation ran at 1/10th speed. For the past 50 years, that’s usually the target for calling (“unaccelerated”) emulation good enough. Especially for architectures that are current or in development or otherwise require some sort of instruction translation.
The last 30 years we’ve seen innovations like dynamic recompilation, fat binaries, JIT VMs, and profile guided optimization. So that has created an expectation of sub-order of magnitude run time performance. It’s a fanciful time we live in.
Hey, author here. That's fair, I didn't have the background. I knew interpreters would be slow, I just didn't expect it to still be ~10x after all the optimizations. After reading about it more though, that does seem to be the norm
The coolest interpreter technique I saw was one that put instruction bodies in static functions which the "compiler" main loop would memcpy the body of the function out to straight-line code that would be executed from memory - a poor man's jit. All instruction functions had the same args and gcc would emit position independent code with the same predictable register calling convention. Brittle as hell, sure, but great compilation speed with low run-time overhead. It was able to run interpreted code at 1/5th of compiled code speed, compared to 1/10th speed for typical highly optimized computed goto loop interpreters.
I can't find a link, but if anyone recalls or wrote such an jit interpreter, please post.
Sounds like a copy and patch JIT ( https://en.wikipedia.org/wiki/Copy-and-patch ). The python interpreter was experimenting with this and it provides a decent speedup.
Odd that the Wikipedia article gives 2021 as the first description of this technique when it is far, far older than that. I worked with a software rasterizer JIT that used it in ~2003 and I thought similar techniques were used in the classic MacOS m68k emulator on PowerPC.
Yeah, I think it was in use before. The wiki article is probably incorrect in the 2021 date.
Neat, I guess this gets you the same output as a per-instruction translator without having to run an assembler and linker over the whole program. I should try this and add it to the post for completeness
qemu used to use that technique, but as you note, it was pretty brittle. They switched to the more traditional TCG backend.
CPU architectures evolve and often get replaces, eg Mac has moved from 68k -> Power -> x86 -> ARM or even Windows PC have also jumped from 32 to 64 bits and the same is also true of SIMD.
Why dont O/S support executables with something like LLVM binaries and generate the native code at load time ?
This would solve so many problems including the need for emulators, because all binaries would work on all CPUS, and the OS would produce the best code at load time.
No more cpu detection, vector stuff always works on the latest & widest instructions that are available. CPUs can also retired old legacy instructions without worry and more.
This does exist, we call it Java (or C# or probably a dozen other implementations)
The big tradeoff you're making is that you have significantly less time to run your optimizer, since not everybody has a beefy machine or the patience to wait a day for their browser to start first time.
You could try doing optimization ahead of time, but I think (I could be wrong here) you would inevitably end up adding in some CPU assumptions if you went much further. This also somewhat conflicts with an advantage of VM based execution, that new optimizations apply to old binaries.
I'll also note that hand rolled assembly/SIMD code still beats compilers at the extreme end and you would either have to throw that away, or get all the disadvantages mentioned above without all the advantages
> significantly less time to run your optimizer,
Not necessarily, you work around this with JIT caches, which allow the optimiser not to start always from zero.
Additionally your can also AOT compile, with or without PGO data.
All modern bytecode implementations, at least for Java and .NET, use a mix of JIT with caching/AOT/PGO.
You can work around this in various ways yes (I'll add dynamic recompilation to your list of workarounds), but you're always going to have the problem of "Somebody downloaded a program and want to run it now"
Yeah, however in that very specific scenario it isn't about any winning SPEC benchmark suit.
Adding another workaround, shipping the JIT cache metadata alongside the program, and dynamically sharing it across all devices of the same category, as done in Android.
I do most of my work in java (https://github.com/mP1)... so i am familiar with it. Java is a high level language, and the native optimisations are done by the JVM vendor which basically boils down to Oracle today.
Some people might write some native code that is faster, but that is hardly the norm.
There are many classes of programs that dont work particularly well if written in java, such as video editing or graphics because you know the rest.
They do, this idea is as old as UNCOL in 1958.
Regarding OSes still being sold today that use this idea, IBM i with Timi, Unisys ClearCase (started as Burroughs B5000 in 1961), Android, Java and .NET on embedded devices.
Then we have the ones from past times, Xerox PARC workstations with programmable microcode, Modula-2 M-Code on Lilith, Oberon slim binaries, Inferno with Limbo, Pascal UCSD P-Code, Andrew Compiler Toolkit...
Ah, and the WebAssembly folks pretending they are the very first with this idea.
How many users does UNCOL or Xerox PARC have today ?
Not many.
The main o/s we all use today such as Linux/MAC/Windows dont and Im asking why not given the advantages such a binary would give.
«Why dont O/S support executables with something like LLVM binaries and generate the native code at load time ?»
I've wondered this too. I can think of two systems "IBM i" (formerly OS/400) [1] and Oberon "Slim Binaries" [2] off the top of my head. I suspect that the answer to your question is some mix of path dependence and engineering trade-offs.
[1] https://en.wikipedia.org/wiki/IBM_i [2] https://dl.acm.org/doi/pdf/10.1145/265563.265576
For example, if the system has unix-style paged virtual memory (which Oberon did not), it's probably convenient to be able to directly map pages of native instructions into memory without needing to translate or massage them first.
In the case of "IBM i", which I've only ever read about, it sounds like it moves complexity from e.g. the compiler into the loader and so closer to the Kernel of the operating system. If I wanted to better understand the net cost/benefit analysis of this design I'd look for more detail on work done to port to PowerPC.
It does exist in LLVM and is called Bitcode, a binary format for the LLVM IR - https://llvm.org/docs/BitCodeFormat.html
Apple used to require apps submitted to its iOS App Store to be in the Bitcode format, and they would «recompile» the Bitcode into the exact user's iPhone CPU architecture at the download time – pretty much what OS/400 does. For reasons unknown, they have discontinued Bitcode.
The reasons are quite clear.
Contrary to other bytecode formats, LLVM bitcode is not stable, even across minor releases.
So anyone using it as bytecode format, like Apple, has to keep their own branch, and eventually it becomes too much work.
Microsoft did the same for DirectX DXIL, as did Khronos with the original SPIR definition, thus SPIR-V came to be as replacement, and recently Microsoft also decided to replace DXIL with SPIR-V.
Functionally, Bitcode delivers – a .bc file can be compiled into any architecture LLVM supports. I have tested a few supported architecture, and it worked like a charm.
Stability of the Bitcode format across releases is orthogonal to the functionality it provides. Given that OS/400's TIMI has been a long-running success, it is possible to put extra effort into stabilising the Bitcode format as well. Benefits would be numerous and significant, ranging from CI/CD to apps taking advantage of new or enhanced ISA extensions.
Yeah but that is the thing, for those that care about stability there are better options already.
Starting by the hyped WebAssembly, which I reckonignise it is useful, only not as breakthrough as it gets advertised given how many bytecode formats have existed since 1958.
Would that support self modifying code?
Self modifying code is frowned upon on modern platforms, due to its security implications.
Self modifying code is not allowed on some o/s because pages with code are marked as non writable, because bad things can happen when code is writable, eg buffer overflows.
At the end it is not emulation but static recompilation (which is, arguably, cooler)
Yeah, I went back and forth on the title. It's definitely not an interpreter. I still think of emulation as the umbrella term though, running code for one architecture on another, with interpretation and dynamic/static recompilation being different ways to get there
How do you differentiate the two? What is the benefit of such a distinction? Why not use eg threaded emulation vs recompiled emulation?
Emulation visits instructions as they are executed. Static recompilation will (at translation time) visit instructions that can be discovered, even if they never run.
eg:
an emulator will likely never visit that assignment. A static recompiler will translate it.IDK, a lot of the emulators I've seen and a couple I've written will visit that. Not everything is built on simple traces, but a lot of the time will translate more complex graphs at a time.
Hm. What is the utility of this distinction?
Anyway, qemu certainly seems like it would fall under your definition of "emulator" despite obviously dynamically recompiling.
which is why i said "static recompiler" and not just "recompiler"
distinction is that an emulator is much simpler, while a static recompiler is a lot more work and thus ~30% more cool
Ah. I admit I've only ever made dynamic recompilers
In my limited understanding, static recompiling is like JIT transpilation from one arch to another where emulation runs each instruction calling behaviour depending on the instruction. As for tradeoffs my knowledge is not wide enough to declare anything certain.
What is the distinction in your mind? Can recompiling not call each instruction? Can threaded interpretation not perform optimization?
Author here, thanks for all the comments, didn't expect this to get picked up.
I've been working on speeding up RISC-V emulation for work and wrote this up as I went. Still learning this space, so I'd be keen to hear from people who've worked on emulators or binary translation, especially where you think this approach falls short