6 ms·

The Fastest VM Bytecode Interpreter

110 points by m0th87 16y ago

steveklabnik 16y ago
So... who wants to take a crack at why this would be?
- stefano 16y ago
  The VB "interpreter" emits opcode for the .NET VM. This codes is then optimized and jitted. This means that both these interpreters run native code in the end, with the difference that the VB version can take advantage of the optimizations implemented by the .NET JIT.
  - rbarooah 16y ago
    Indeed - frankly when I saw it I was surprised the guy had accepted this as valid in their contest - if he's allowed to use an offboard compiler the 'interpreter' could just as well emit some generated C to a file and pass it through GCC -O3.
pmjordan 16y ago
Anyone got a cache of this? Site seems to be getting hammered.
- Groxx 16y ago
  try googling for: cache:url :)
  - pmjordan 16y ago
    That does indeed work now (though it didn't when I originally checked).
deleted 16y ago
[deleted]
Groxx 16y ago
Oh come on. gcc simvm.c time ./a.out 857419840 real 0m0.374s user 0m0.359s sys 0m0.003s meanwhile: gcc -O3 simvm.c -o fast.out time ./fast.out 857419840 real 0m0.006s user 0m0.001s sys 0m0.003s Comparing optimized compiled code against unoptimized compiled code is worthless. .NET does some optimizations as it runs, and JITs, your standard `gcc` does very few. /me goes to comment on the blog. edit: bah! Foiled! >Hmmm, your comment seems a bit spammy. We're not real big on spam around here. Please go back and try again. edit2: holy cow, that spam filter hates me. I can't get anything to post...
- FooBarWidget 16y ago
  -O3 is too smart, it optimizes away the loop and transforms the code into printf(the_result).
  - Groxx 16y ago
    Hah, nice. Didn't check the resulting code. Know what the other optimization levels do? I'm don't really know x86 assembler. I do still side with the optimization though, in that the .NET-VM could do this as well. The loop is pretty simple, and can be optimized away. Why shouldn't it?
    - bad_user 16y ago
      Your answer received lots of votes for what are basically assumptions. The author of the article updated his post for -O3 by using a volatile variable for the for-loop test, which makes the compiler not optimize away the loop. For .NET you can look at the generated assembly, and if it does optimize away the loop you can use the same trick. No reasons for guessing. We are software engineers after all.
      - JoachimSchipper 16y ago
        "volatile" forces the C compiler to issue load and store instructions for each access (although real-world C compilers are notoriously buggy here), so it makes the loop much slower. That's not a fair comparison.
fleitz 16y ago
His 'VB' emits byte code for the .NET VM which is highly optimized. Also, VB.NET runs on the same VM. VB.NET has a lot of 'features' that are performance nightmares but it's not that slow if you know what to avoid. Oh, I didn't see that VB was run on mono, run that code on a windows machine and I bet it will beat the -O3 optimized C
jasonwatkinspdx 16y ago
This is a compiler, not an interpreter, as it uses .NET's dynamic assembly api to emit .NET IL which is then JIT'd to native code. The benchmark is also likely optimized away by static analysis. For an actual benchmark of various bytecode interpretation schemes see: http://www.complang.tuwien.ac.at/forth/threading/ http://www.complang.tuwien.ac.at/forth/threading/ These micro benchmarks also take some care to attempt realistic branch prediction rates. Running these on current hardware, switch based interpreters still perform quite well. Direct threading gets you slightly more performance. I'd say that sticking to ANSI c and just using switch is a good plan. If you need more performance then you likely should go ahead and implement a native JIT of some sort or use JVM/.NET.
- stcredzero 16y ago
  This is a compiler, not an interpreter This phrase, what does this mean anymore? Do these things exist in the form of real, non-toy software anymore? What's the difference between compiling to an AST, byte code, or LLVM intermediate? I think these words have more to do with cultural expectations than with VM/compiler technology.
  - another 16y ago
    I'm sorry, but there is a qualitative difference between, eg, a Java application running on a modern JVM and a Python application executing through the CPython runtime, neither of which are toys. (Although it's true that CPython is one of the few extant members of a dying breed.) The connotations of "compiled" and "interpreted" might have plenty to do with vague expectations, but the words still mean something in the context of language implementation: even though it is reasonable to call the situations you list "compilation", it would not be accurate to call a language that was compiled to LLVM IR, then interpreted with lli, "compiled".
    - wisty 16y ago
      Note, CPython hasn't strictly been an interpreter for a long long time. It compiles .py files into .pyc files, then runs them. It also does a fair bit of caching. However, it's virtual machine doesn't do much optimization. Yeah, it pre-allocates lots of common data-structures, and reuses old ones rather than using new ones if possible, and I think it might do some stuff with iterators ... but it's nothing like PyPy or a modern JVM.
zokier 16y ago
There is one important lesson here to be learned. Doing stuff at low level (asm/c) doesn't automagically make your code fast.

110 points by m0th87 16y ago

steveklabnik 16y ago

So... who wants to take a crack at why this would be?

stefano 16y ago
The VB "interpreter" emits opcode for the .NET VM. This codes is then optimized and jitted. This means that both these interpreters run native code in the end, with the difference that the VB version can take advantage of the optimizations implemented by the .NET JIT.
- rbarooah 16y ago
  Indeed - frankly when I saw it I was surprised the guy had accepted this as valid in their contest - if he's allowed to use an offboard compiler the 'interpreter' could just as well emit some generated C to a file and pass it through GCC -O3.

pmjordan 16y ago

Anyone got a cache of this? Site seems to be getting hammered.

Groxx 16y ago
try googling for: cache:url :)
- pmjordan 16y ago
  That does indeed work now (though it didn't when I originally checked).

deleted 16y ago

[deleted]

Groxx 16y ago

Oh come on. gcc simvm.c time ./a.out 857419840 real 0m0.374s user 0m0.359s sys 0m0.003s meanwhile: gcc -O3 simvm.c -o fast.out time ./fast.out 857419840 real 0m0.006s user 0m0.001s sys 0m0.003s Comparing optimized compiled code against unoptimized compiled code is worthless. .NET does some optimizations as it runs, and JITs, your standard `gcc` does very few. /me goes to comment on the blog. edit: bah! Foiled! >Hmmm, your comment seems a bit spammy. We're not real big on spam around here. Please go back and try again. edit2: holy cow, that spam filter hates me. I can't get anything to post...

FooBarWidget 16y ago
-O3 is too smart, it optimizes away the loop and transforms the code into printf(the_result).
- Groxx 16y ago
  Hah, nice. Didn't check the resulting code. Know what the other optimization levels do? I'm don't really know x86 assembler. I do still side with the optimization though, in that the .NET-VM could do this as well. The loop is pretty simple, and can be optimized away. Why shouldn't it?
  - bad_user 16y ago
    Your answer received lots of votes for what are basically assumptions. The author of the article updated his post for -O3 by using a volatile variable for the for-loop test, which makes the compiler not optimize away the loop. For .NET you can look at the generated assembly, and if it does optimize away the loop you can use the same trick. No reasons for guessing. We are software engineers after all.
    - JoachimSchipper 16y ago
      "volatile" forces the C compiler to issue load and store instructions for each access (although real-world C compilers are notoriously buggy here), so it makes the loop much slower. That's not a fair comparison.

fleitz 16y ago

His 'VB' emits byte code for the .NET VM which is highly optimized. Also, VB.NET runs on the same VM. VB.NET has a lot of 'features' that are performance nightmares but it's not that slow if you know what to avoid. Oh, I didn't see that VB was run on mono, run that code on a windows machine and I bet it will beat the -O3 optimized C

jasonwatkinspdx 16y ago

This is a compiler, not an interpreter, as it uses .NET's dynamic assembly api to emit .NET IL which is then JIT'd to native code. The benchmark is also likely optimized away by static analysis. For an actual benchmark of various bytecode interpretation schemes see: http://www.complang.tuwien.ac.at/forth/threading/ http://www.complang.tuwien.ac.at/forth/threading/ These micro benchmarks also take some care to attempt realistic branch prediction rates. Running these on current hardware, switch based interpreters still perform quite well. Direct threading gets you slightly more performance. I'd say that sticking to ANSI c and just using switch is a good plan. If you need more performance then you likely should go ahead and implement a native JIT of some sort or use JVM/.NET.

stcredzero 16y ago
This is a compiler, not an interpreter This phrase, what does this mean anymore? Do these things exist in the form of real, non-toy software anymore? What's the difference between compiling to an AST, byte code, or LLVM intermediate? I think these words have more to do with cultural expectations than with VM/compiler technology.
- another 16y ago
  I'm sorry, but there is a qualitative difference between, eg, a Java application running on a modern JVM and a Python application executing through the CPython runtime, neither of which are toys. (Although it's true that CPython is one of the few extant members of a dying breed.) The connotations of "compiled" and "interpreted" might have plenty to do with vague expectations, but the words still mean something in the context of language implementation: even though it is reasonable to call the situations you list "compilation", it would not be accurate to call a language that was compiled to LLVM IR, then interpreted with lli, "compiled".
  - wisty 16y ago
    Note, CPython hasn't strictly been an interpreter for a long long time. It compiles .py files into .pyc files, then runs them. It also does a fair bit of caching. However, it's virtual machine doesn't do much optimization. Yeah, it pre-allocates lots of common data-structures, and reuses old ones rather than using new ones if possible, and I think it might do some stuff with iterators ... but it's nothing like PyPy or a modern JVM.

zokier 16y ago

There is one important lesson here to be learned. Doing stuff at low level (asm/c) doesn't automagically make your code fast.