9 ms·

When pigs fly: optimising bytecode interpreters

190 points by lelf 8y ago

0xcde4c3db 8y ago
Although the article is framed around language implementation, the underlying principle is also valid for interpreting CPU instruction sets. I read quite a few years ago that Apple at one point abandoned a particular 68K->PowerPC JIT because an optimized interpreter was faster at running real-world applications for cache-related reasons (keep in mind that this was the early 90s, when mainstream L1 caches were 4/8/16KB and L2 cache was off-chip).
- vkazanov 8y ago
  That's very true. In fact, I took one of the techniques (traces) directly from a paper describing how the Bochs x86 virtual machine works :-) But it goes deeper than that. I believe the whole "trace" thing in both jits and vms comes from a few papers describing trace-based instruction predecoding for hardware CPUs.
  - blattimwind 8y ago
    Yes I believe that's true, with the idea of a trace cache originating in the 90s to work around perceived I-cache limitations, "Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching" is the seminal paper on it.
    - vkazanov 8y ago
      Interestingly trace caches are now gone in both hardware CPUs and major jit compilers :-) Correct me if I am wrong..?
      - blattimwind 8y ago
        Yes, nowadays x86 cores have µop caches which store the decomposition of individual instructions and then other "optimizers" that target specific constructs (e.g. loop stream detector).
    - cfallin 8y ago
      The idea of straight-line traces goes back even further, to Josh Fisher's work on trace scheduling in compilers in the early 80s (linearizing one control-flow path gives a much wider scope for optimizations): https://en.wikipedia.org/wiki/Josh_Fisher#Trace_Scheduling https://en.wikipedia.org/wiki/Josh_Fisher#Trace_Scheduling He combined this with a VLIW processor architecture to build Multiflow, a hardware startup. (Interesting history tidbit: Robert Colwell, who architected the P6, the first out-of-order Intel core, started his career at Multiflow before joining Intel. The P6 didn't have any trace-cache influences, but the P4, a few years later, infamously did...)
  - bogomipz 8y ago
    Might you or anyone else have a link to that Bochs x86 virtual machine paper? Similarly might you have links for those papers that describe "trace-based instruction predecoding for hardware CPUs."? Cheers
    - naasking 8y ago
      I think it's the first result when googling "bochs x86 paper".
- byuu 8y ago
  The problem I face with my CPU interpreters (I've written about 15 of them) is in the synchronization between components. If a CPU ran on its own, then there's no end to our optimization potential. If it were a strict Harvard architecture where instructions could only run in immutable (ROM) areas, we could translate the instructions, remove all unnecessary flag calculations, and then statically recompile the result to a native program. But when the CPU needs to talk to the audio chip, the video chip, the other audio CPU running alongside it, etc ... the reason everything ends up so slow is that there's no viable path for speeding up that synchronization. You try and do it with real hardware resources: a real CPU core/thread for each emulated chip, and performance falls off a cliff. Even with simple atomic reads/writes for one thread/chip to set a "waiting on you" flag, and another thread/chip to clear it, modern CPUs can only do this around 100,000 times a second ... and that's before the overhead of your emulation. So, if you want to emulate two CPUs that run at more than 0.1 MIPS (which even the NES surpasses), you're out of luck. So you try and do it with a single thread, but you get destroyed through context switches. You're in the middle of executing a 68K instruction, but that instruction writes to RAM that the Z80 can read from. You don't know if the Z80 is going to read there, so you have to run the Z80 until it's "ahead" in time to the 68K. Switching into the Z80 interpreter absolutely murders your performance. Pretty much the primary key to optimizing CPU emulators is to synchronize less often. Making assumptions like, "it's very unlikely the Z80 is going to write to the CPU instruction stream in the middle of it executing instructions ... the 68K is most likely executing code in ROM anyway" and not synchronizing the Z80 when the 68K fetches an opcode or operand byte. But these optimizations always come at a cost. When you get a library of thousands of programs designed to eke out every last drop of performance from old, legacy 2MHz hardware, there's always that one program ... either by design or by fluke, does something crazy and relies on something you optimized away as extremely improbable, and breaks as a result. In my view, the way to optimize real-world emulation of machines is that we need to be able to spawn lots of 1 core = 1 thread objects, and have their synchronizations be as cheap as humanly possible. The cores do not have to be lightning fast, they just have to be able to synchronize as quickly and as cheaply as real code running on a 90s era 68K+Z80 machine (eg a Sega Genesis) is able to. Many, many bonus points if the "waiting on another chip" operation can result in sapping less power for that thread, without increasing the latency necessary for it to resume operating once the condition is met. The industry has, for decades, been moving in the complete opposite direction, so I don't have a lot of hope. At this point, I think it's more viable (but still very unlikely) to put FPGAs into home computers for this purpose.
- mehrdadn 8y ago
  There were JITs back then?!
  - vkazanov 8y ago
    What's so surprising? Jit-like techniques are older than I am, and I am not that young anymore :-)
    - mehrdadn 8y ago
      I guess I don't know what time period this was referring to exactly but it sounded like it'd have been the mid-1990s... is that correct? Idk I just didn't expect JITs to have existed back then for some reason.
      - gsnedders 8y ago
        Most of the work over the past decade on dynamic language JITs (especially JS) really just builds on top of the work on the Self JIT in the mid-80s. JITs themselves are older still.
      - dragontamer 8y ago
        JITs were far more important in the 1980s when people regularly used grossly different computing systems. Think of the popular 1980s computers: IBM PC (Intel 8086), Amiga (Motorola 68000), Commodore 64 (MOS Technology 6510), TRS-80 (Zilog Z80), Apple II (WDC 65C02), Acorn Electron (Synertek SY6502A). The solution at that time was to use p-code ("portable" code), such as https://en.wikipedia.org/wiki/UCSD_Pascal https://en.wikipedia.org/wiki/UCSD_Pascal In fact, Pascal's popularity in the 1980s was probably due to the large number of p-code interpreters and Pascal -> p-code compilers. -------------- Ironically, we still use "p-code", now called Bytecode, today. But we really don't move between systems aside from ARM and x86. GPU assembly is special, since its an entirely different model so you can't really port Java or Python to the GPU. I guess LLVM shows that the high-level translation to LLVM-intermediate language just simplifies compiler optimization, to the point that its useful even if you're making code for a specific machine. EDIT: I think the modern CPU have more or less settled on the same features. They're all Multithreaded, cache-coherent Modified 64-bit Harvard machines with out-of-order execution, super-scalar front-end with speculative branch prediction, with ~6 uop dispatch per clock tick and roughly 2 or 3 load/store units with 64kB L1 cache and 64-byte cache lines with a dedicated 128-bit SIMD unit The above lines describes ARM Cortex-A72, Intel Skylake, AMD Zen, and POWER9... except Skylake has 256-bit SIMD units I guess, and Apple's A12 has 96kB L1 cache. Not very big differences anymore between CPUs.
- tasty_freeze 8y ago
  I have written an emulation for an old microcoded machine. Although the straight-forward implementation was a multiple of times faster than the original machine, I couldn't resist going for a little more performance. The microinstruction is 23 bits wide (plus one for parity). Rather than doing a lot of masking, shifting, and testing to extract fields (some fields are non-contiguous even), I instead use 64b per microword. bits [23:0] -- original microinstruction bits [31:24] -- 8b op-dependent predecode value bits [39:32] -- 8b interpreter dispatch index bits [47:40] -- 8b op-dependent predecode value bits [63:48] -- 16b op-dependent predecode value There are a few oddball instructions which could use more than the 8b and 16b predecode fields, and instead do the old shift and mask on the raw microword to figure out what is needed. Overall, it nearly doubled my performance.
  - bogomipz 8y ago
    >"The microinstruction is 23 bits wide (plus one for parity)." I'm curious why does the microinstruction need a parity bit? What happens if the parity is wrong, a machine check exception? >"bits [23:0] -- original microinstruction bits [31:24] -- 8b op-dependent predecode value bits [39:32]" What do the pre-decode bits do exactly? Which microcoded machine was this?
    - tasty_freeze 8y ago
      bogomipz -- sorry, I didn't see you replied to this. The machine traps to a parity error handler (one for microcode RAM, and a different one for data ram) and prints out a message indicating the error code and the address being read when it was detected. There are a number of microinstruction formats, and fields aren't always contiguous. Making up an example, say the instruction is "ADD R1,#imm8" to add an 8b immediate to the R1 register. But the 8b immediate value is stored in bits [14:10] and [4:2] of the microword. The straight-forward way would be to write "uint8_t imm = ((instr >> 7) & 0xF8) | ((instr >> 2) & 0x07;" Instead, when the writable control store is written, that quantity is decoded and stored in an 8b aligned predecode field, so getting the value is just "uint8_t imm = instr_struct.imm8;" The machine is the Wang 2200. There were two architectures: the first used a 20b word in ROM, the second used a writable control store so the BASIC could have bug and feature updates by mailing out floppies.
- bsder 8y ago
  > I read quite a few years ago that Apple at one point abandoned a particular 68K->PowerPC JIT because an optimized interpreter was faster at running real-world applications for cache-related reasons (keep in mind that this was the early 90s, when mainstream L1 caches were 4/8/16KB and L2 cache was off-chip). The big problem was that Apple was lousy at specifying how much cache they needed. IBM told Apple that it needed a LOT more cache on the 603 unless everything was running native. Apple ignored the advice. The result was that the 603 and 604 were performance dogs because so much was still running in emulation. So, IBM went back and bumped the cache for the 603e, and performance went up dramatically. This then led to the unfortunate situation wherein the "low-power" chip from IBM (the 603e) tended to be far more performant than the "high-performance" chip (the 604) from Motorola.
- rasz 8y ago
  self modifying code? Doom/Quake are such examples in qemu, getting slower with every new jit update https://virtuallyfun.com/wordpress/2019/03/05/degrading-qemu-performance-in-doom/ https://virtuallyfun.com/wordpress/2019/03/05/degrading-qemu... https://virtuallyfun.com/wordpress/2019/03/15/degrading-qemu-performance-in-doom-part-ii/ https://virtuallyfun.com/wordpress/2019/03/15/degrading-qemu...
deleted 8y ago
[deleted]
blattimwind 8y ago
Excellent article. > Everyone knows that pigs can’t fly — just like everyone thinks they know that bytecode interpreters, as a technology for executing high-level languages, can’t be sped up without resorting to labour-intensive dynamic compilation. [citation needed] PHP (in recent versions) is a good example for a bytecode VM that's quite quick. So we already have a spectrum that probably covers an order of magnitude or so, just in the basic speed of bytecode execution.
- willvarfar 8y ago
  Some interpreters are faster than others. But lets list some interpreters and their (usually jit) compilation equivs: cpython vs pypy lua vs luajit dalvik vs art (which isn't jit) zend vs hhvm Okay, that last one, php7 is reckoned to be faster than hhvm on some sites. My gut feeling, though is that is because of the inefficiencies in php, many inherent in the language design, rather than because php7 were the only people to know how to write a fast interpreter. It seems a sound generalisation that you get another order of magnitude by moving from interpretation to compilation.
  - pjmlp 8y ago
    ART is surely a JIT after Android 7.
    - willvarfar 8y ago
      Ah I thought it was compile-on-install?
      - pjmlp 8y ago
        Only in Android 5 and 6. Compile-on-install was taking so long that in Android 7, they re-introduced the JIT and have been improving it since. So on Android 7, ART is an hand-optimized Assembly interpreter, which gathers data to a PGO JIT, which likewise gathers data to PGO AOT when the device is idle. Afterwards they started to optimize this workflow and optimizations being done, and as of Android P, PGO files are uploaded to the Play Store, which are then delivered to identical devices when they fresh install the APK so that they can reach the AOT step with a good level of optimizations faster. Just follow all the links available on the left sidebar here, https://source.android.com/devices/tech/dalvik https://source.android.com/devices/tech/dalvik There are also a couple of Google IO talks for Android 7, 8 and 9 talking about some of these changes.
kwindla 8y ago
Lovely article! Following up on the section about threaded code, Andrew W. Appel's book _Compiling With Continuations_ really blew my mind and changed how I think about the interconnections between compilation, optimization, and language design. There are many ways into that deep set of ideas; I recommend the Appel book as one of them! https://books.google.com/books/about/Compiling_with_Continuations.html?id=0Uoecu9ju4AC And, of course, if there's an influential meme in CS, there's a Haskell paper with a clever title that references it. :-) https://www.microsoft.com/en-us/research/wp-content/uploads/2016/11/compiling-without-continuations.pdf
- toolslive 8y ago
  you should however also read the reply paper: https://www.microsoft.com/en-us/research/wp-content/uploads/2007/10/compilingwithcontinuationscontinued.pdf?from=https%3A%2F%2Fresearch.microsoft.com%2F%7Eakenn%2Fsml%2FCompilingWithContinuationsContinued.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... with an even lovelier title.
  - naasking 8y ago
    And yet another: https://www.cs.purdue.edu/homes/rompf/papers/cong-preprint201811.pdf https://www.cs.purdue.edu/homes/rompf/papers/cong-preprint20...
Animats 8y ago
"it is entirely possible to speed up the work of such interpreters by a factor of at least 1½." Story of CPython.
kayamon 8y ago
If you really want to speed up your bytecode interpreter, switch to a register-based VM instead of a stack-based one.
mratsim 8y ago
I'm surprised their threaded interpreter was slower than switch, this doesn't reflect my benchmark as well even for post-Haswell CPU. Also this is not true on non-x86 hardware and I unfortunately didn't test on AMD. The article should at least cite this paper regarding Haswell branch prediction: https://hal.inria.fr/hal-01100647/document https://hal.inria.fr/hal-01100647/document "Branch Prediction and the Performance of Interpreters - Don’t Trust Folklore", 2015, Rohou et al. Also I'm leaving my interpreter optimization resources here with decades of research papers and highlights of the techniques I found most interesting when implementing a fast VM: https://github.com/status-im/nimbus/wiki/Interpreter-optimization-resources https://github.com/status-im/nimbus/wiki/Interpreter-optimiz...
- vkazanov 8y ago
  Yeah, it's a very good collection you got there! some of the papers I read, others are in the queue. I was also surprised to see the switch-based solution winning here. But I was even more surprised to see how a simple change (a primitive stack top caching) suggested by one of the readers radically changed my perf benchmarks: the threaded interpreter was the fastest interpreter again.

190 points by lelf 8y ago

Although the article is framed around language implementation, the underlying principle is also valid for interpreting CPU instruction sets. I read quite a few years ago that Apple at one point abandoned a particular 68K->PowerPC JIT because an optimized interpreter was faster at running real-world applications for cache-related reasons (keep in mind that this was the early 90s, when mainstream L1 caches were 4/8/16KB and L2 cache was off-chip).

vkazanov 8y ago
That's very true. In fact, I took one of the techniques (traces) directly from a paper describing how the Bochs x86 virtual machine works :-) But it goes deeper than that. I believe the whole "trace" thing in both jits and vms comes from a few papers describing trace-based instruction predecoding for hardware CPUs.
- blattimwind 8y ago
  Yes I believe that's true, with the idea of a trace cache originating in the 90s to work around perceived I-cache limitations, "Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching" is the seminal paper on it.
  - vkazanov 8y ago
    Interestingly trace caches are now gone in both hardware CPUs and major jit compilers :-) Correct me if I am wrong..?
    - blattimwind 8y ago
      Yes, nowadays x86 cores have µop caches which store the decomposition of individual instructions and then other "optimizers" that target specific constructs (e.g. loop stream detector).
  - cfallin 8y ago
    The idea of straight-line traces goes back even further, to Josh Fisher's work on trace scheduling in compilers in the early 80s (linearizing one control-flow path gives a much wider scope for optimizations): https://en.wikipedia.org/wiki/Josh_Fisher#Trace_Scheduling https://en.wikipedia.org/wiki/Josh_Fisher#Trace_Scheduling He combined this with a VLIW processor architecture to build Multiflow, a hardware startup. (Interesting history tidbit: Robert Colwell, who architected the P6, the first out-of-order Intel core, started his career at Multiflow before joining Intel. The P6 didn't have any trace-cache influences, but the P4, a few years later, infamously did...)
- bogomipz 8y ago
  Might you or anyone else have a link to that Bochs x86 virtual machine paper? Similarly might you have links for those papers that describe "trace-based instruction predecoding for hardware CPUs."? Cheers
  - naasking 8y ago
    I think it's the first result when googling "bochs x86 paper".
byuu 8y ago
The problem I face with my CPU interpreters (I've written about 15 of them) is in the synchronization between components. If a CPU ran on its own, then there's no end to our optimization potential. If it were a strict Harvard architecture where instructions could only run in immutable (ROM) areas, we could translate the instructions, remove all unnecessary flag calculations, and then statically recompile the result to a native program. But when the CPU needs to talk to the audio chip, the video chip, the other audio CPU running alongside it, etc ... the reason everything ends up so slow is that there's no viable path for speeding up that synchronization. You try and do it with real hardware resources: a real CPU core/thread for each emulated chip, and performance falls off a cliff. Even with simple atomic reads/writes for one thread/chip to set a "waiting on you" flag, and another thread/chip to clear it, modern CPUs can only do this around 100,000 times a second ... and that's before the overhead of your emulation. So, if you want to emulate two CPUs that run at more than 0.1 MIPS (which even the NES surpasses), you're out of luck. So you try and do it with a single thread, but you get destroyed through context switches. You're in the middle of executing a 68K instruction, but that instruction writes to RAM that the Z80 can read from. You don't know if the Z80 is going to read there, so you have to run the Z80 until it's "ahead" in time to the 68K. Switching into the Z80 interpreter absolutely murders your performance. Pretty much the primary key to optimizing CPU emulators is to synchronize less often. Making assumptions like, "it's very unlikely the Z80 is going to write to the CPU instruction stream in the middle of it executing instructions ... the 68K is most likely executing code in ROM anyway" and not synchronizing the Z80 when the 68K fetches an opcode or operand byte. But these optimizations always come at a cost. When you get a library of thousands of programs designed to eke out every last drop of performance from old, legacy 2MHz hardware, there's always that one program ... either by design or by fluke, does something crazy and relies on something you optimized away as extremely improbable, and breaks as a result. In my view, the way to optimize real-world emulation of machines is that we need to be able to spawn lots of 1 core = 1 thread objects, and have their synchronizations be as cheap as humanly possible. The cores do not have to be lightning fast, they just have to be able to synchronize as quickly and as cheaply as real code running on a 90s era 68K+Z80 machine (eg a Sega Genesis) is able to. Many, many bonus points if the "waiting on another chip" operation can result in sapping less power for that thread, without increasing the latency necessary for it to resume operating once the condition is met. The industry has, for decades, been moving in the complete opposite direction, so I don't have a lot of hope. At this point, I think it's more viable (but still very unlikely) to put FPGAs into home computers for this purpose.
mehrdadn 8y ago
There were JITs back then?!
- vkazanov 8y ago
  What's so surprising? Jit-like techniques are older than I am, and I am not that young anymore :-)
  - mehrdadn 8y ago
    I guess I don't know what time period this was referring to exactly but it sounded like it'd have been the mid-1990s... is that correct? Idk I just didn't expect JITs to have existed back then for some reason.
    - gsnedders 8y ago
      Most of the work over the past decade on dynamic language JITs (especially JS) really just builds on top of the work on the Self JIT in the mid-80s. JITs themselves are older still.
    - dragontamer 8y ago
      JITs were far more important in the 1980s when people regularly used grossly different computing systems. Think of the popular 1980s computers: IBM PC (Intel 8086), Amiga (Motorola 68000), Commodore 64 (MOS Technology 6510), TRS-80 (Zilog Z80), Apple II (WDC 65C02), Acorn Electron (Synertek SY6502A). The solution at that time was to use p-code ("portable" code), such as https://en.wikipedia.org/wiki/UCSD_Pascal https://en.wikipedia.org/wiki/UCSD_Pascal In fact, Pascal's popularity in the 1980s was probably due to the large number of p-code interpreters and Pascal -> p-code compilers. -------------- Ironically, we still use "p-code", now called Bytecode, today. But we really don't move between systems aside from ARM and x86. GPU assembly is special, since its an entirely different model so you can't really port Java or Python to the GPU. I guess LLVM shows that the high-level translation to LLVM-intermediate language just simplifies compiler optimization, to the point that its useful even if you're making code for a specific machine. EDIT: I think the modern CPU have more or less settled on the same features. They're all Multithreaded, cache-coherent Modified 64-bit Harvard machines with out-of-order execution, super-scalar front-end with speculative branch prediction, with ~6 uop dispatch per clock tick and roughly 2 or 3 load/store units with 64kB L1 cache and 64-byte cache lines with a dedicated 128-bit SIMD unit The above lines describes ARM Cortex-A72, Intel Skylake, AMD Zen, and POWER9... except Skylake has 256-bit SIMD units I guess, and Apple's A12 has 96kB L1 cache. Not very big differences anymore between CPUs.
tasty_freeze 8y ago
I have written an emulation for an old microcoded machine. Although the straight-forward implementation was a multiple of times faster than the original machine, I couldn't resist going for a little more performance. The microinstruction is 23 bits wide (plus one for parity). Rather than doing a lot of masking, shifting, and testing to extract fields (some fields are non-contiguous even), I instead use 64b per microword. bits [23:0] -- original microinstruction bits [31:24] -- 8b op-dependent predecode value bits [39:32] -- 8b interpreter dispatch index bits [47:40] -- 8b op-dependent predecode value bits [63:48] -- 16b op-dependent predecode value There are a few oddball instructions which could use more than the 8b and 16b predecode fields, and instead do the old shift and mask on the raw microword to figure out what is needed. Overall, it nearly doubled my performance.
- bogomipz 8y ago
  >"The microinstruction is 23 bits wide (plus one for parity)." I'm curious why does the microinstruction need a parity bit? What happens if the parity is wrong, a machine check exception? >"bits [23:0] -- original microinstruction bits [31:24] -- 8b op-dependent predecode value bits [39:32]" What do the pre-decode bits do exactly? Which microcoded machine was this?
  - tasty_freeze 8y ago
    bogomipz -- sorry, I didn't see you replied to this. The machine traps to a parity error handler (one for microcode RAM, and a different one for data ram) and prints out a message indicating the error code and the address being read when it was detected. There are a number of microinstruction formats, and fields aren't always contiguous. Making up an example, say the instruction is "ADD R1,#imm8" to add an 8b immediate to the R1 register. But the 8b immediate value is stored in bits [14:10] and [4:2] of the microword. The straight-forward way would be to write "uint8_t imm = ((instr >> 7) & 0xF8) | ((instr >> 2) & 0x07;" Instead, when the writable control store is written, that quantity is decoded and stored in an 8b aligned predecode field, so getting the value is just "uint8_t imm = instr_struct.imm8;" The machine is the Wang 2200. There were two architectures: the first used a 20b word in ROM, the second used a writable control store so the BASIC could have bug and feature updates by mailing out floppies.
bsder 8y ago
> I read quite a few years ago that Apple at one point abandoned a particular 68K->PowerPC JIT because an optimized interpreter was faster at running real-world applications for cache-related reasons (keep in mind that this was the early 90s, when mainstream L1 caches were 4/8/16KB and L2 cache was off-chip). The big problem was that Apple was lousy at specifying how much cache they needed. IBM told Apple that it needed a LOT more cache on the 603 unless everything was running native. Apple ignored the advice. The result was that the 603 and 604 were performance dogs because so much was still running in emulation. So, IBM went back and bumped the cache for the 603e, and performance went up dramatically. This then led to the unfortunate situation wherein the "low-power" chip from IBM (the 603e) tended to be far more performant than the "high-performance" chip (the 604) from Motorola.
rasz 8y ago
self modifying code? Doom/Quake are such examples in qemu, getting slower with every new jit update https://virtuallyfun.com/wordpress/2019/03/05/degrading-qemu-performance-in-doom/ https://virtuallyfun.com/wordpress/2019/03/05/degrading-qemu... https://virtuallyfun.com/wordpress/2019/03/15/degrading-qemu-performance-in-doom-part-ii/ https://virtuallyfun.com/wordpress/2019/03/15/degrading-qemu...

deleted 8y ago

[deleted]

blattimwind 8y ago

Excellent article. > Everyone knows that pigs can’t fly — just like everyone thinks they know that bytecode interpreters, as a technology for executing high-level languages, can’t be sped up without resorting to labour-intensive dynamic compilation. [citation needed] PHP (in recent versions) is a good example for a bytecode VM that's quite quick. So we already have a spectrum that probably covers an order of magnitude or so, just in the basic speed of bytecode execution.

willvarfar 8y ago
Some interpreters are faster than others. But lets list some interpreters and their (usually jit) compilation equivs: cpython vs pypy lua vs luajit dalvik vs art (which isn't jit) zend vs hhvm Okay, that last one, php7 is reckoned to be faster than hhvm on some sites. My gut feeling, though is that is because of the inefficiencies in php, many inherent in the language design, rather than because php7 were the only people to know how to write a fast interpreter. It seems a sound generalisation that you get another order of magnitude by moving from interpretation to compilation.
- pjmlp 8y ago
  ART is surely a JIT after Android 7.
  - willvarfar 8y ago
    Ah I thought it was compile-on-install?
    - pjmlp 8y ago
      Only in Android 5 and 6. Compile-on-install was taking so long that in Android 7, they re-introduced the JIT and have been improving it since. So on Android 7, ART is an hand-optimized Assembly interpreter, which gathers data to a PGO JIT, which likewise gathers data to PGO AOT when the device is idle. Afterwards they started to optimize this workflow and optimizations being done, and as of Android P, PGO files are uploaded to the Play Store, which are then delivered to identical devices when they fresh install the APK so that they can reach the AOT step with a good level of optimizations faster. Just follow all the links available on the left sidebar here, https://source.android.com/devices/tech/dalvik https://source.android.com/devices/tech/dalvik There are also a couple of Google IO talks for Android 7, 8 and 9 talking about some of these changes.

kwindla 8y ago

Lovely article! Following up on the section about threaded code, Andrew W. Appel's book _Compiling With Continuations_ really blew my mind and changed how I think about the interconnections between compilation, optimization, and language design. There are many ways into that deep set of ideas; I recommend the Appel book as one of them! https://books.google.com/books/about/Compiling_with_Continuations.html?id=0Uoecu9ju4AC And, of course, if there's an influential meme in CS, there's a Haskell paper with a clever title that references it. :-) https://www.microsoft.com/en-us/research/wp-content/uploads/2016/11/compiling-without-continuations.pdf

toolslive 8y ago
you should however also read the reply paper: https://www.microsoft.com/en-us/research/wp-content/uploads/2007/10/compilingwithcontinuationscontinued.pdf?from=https%3A%2F%2Fresearch.microsoft.com%2F%7Eakenn%2Fsml%2FCompilingWithContinuationsContinued.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... with an even lovelier title.
- naasking 8y ago
  And yet another: https://www.cs.purdue.edu/homes/rompf/papers/cong-preprint201811.pdf https://www.cs.purdue.edu/homes/rompf/papers/cong-preprint20...

Animats 8y ago

"it is entirely possible to speed up the work of such interpreters by a factor of at least 1½." Story of CPython.

kayamon 8y ago

If you really want to speed up your bytecode interpreter, switch to a register-based VM instead of a stack-based one.

mratsim 8y ago

I'm surprised their threaded interpreter was slower than switch, this doesn't reflect my benchmark as well even for post-Haswell CPU. Also this is not true on non-x86 hardware and I unfortunately didn't test on AMD. The article should at least cite this paper regarding Haswell branch prediction: https://hal.inria.fr/hal-01100647/document https://hal.inria.fr/hal-01100647/document "Branch Prediction and the Performance of Interpreters - Don’t Trust Folklore", 2015, Rohou et al. Also I'm leaving my interpreter optimization resources here with decades of research papers and highlights of the techniques I found most interesting when implementing a fast VM: https://github.com/status-im/nimbus/wiki/Interpreter-optimization-resources https://github.com/status-im/nimbus/wiki/Interpreter-optimiz...

vkazanov 8y ago
Yeah, it's a very good collection you got there! some of the papers I read, others are in the queue. I was also surprised to see the switch-based solution winning here. But I was even more surprised to see how a simple change (a primitive stack top caching) suggested by one of the readers radically changed my perf benchmarks: the threaded interpreter was the fastest interpreter again.