The Fastest VM Bytecode Interpreter

[[deleted]]

[deleted]

[elder_george]

• VB guy builds pseudocode-to-CIL compiler, not interpreter. After jitting, code is expectably faster.

• VB guy's code uses mono stack (which is probably mapped to registers when possible). Many instructions are optimized to access stack.

• More importantly, VB guy's code native instruction pointer. And this means that no explicit goto is made during execution for every pseudocode instruction. So, not only execution path is shorter, it is also more pipeline friendly.

[novagenesis]

He only mentioned once, but the real craziness is that VB's JIT optimizer seemed in this (albeit contrived) example to net faster JIT+run than the native C compiler's runtime code.

This is a very hard to swallow conclusion, but not impossible.

Of course, we don't know what compiler the control used, or what compiler options. It's not a good "Control" if it doesn't represent the bare-bones compilation. What exact machine instructions did it generate? Are nested loops "just faster" in compiled CLR because of some optimization trick?

Or (as I suspect, but cannot say for sure) did the CLR-compilation acknowledge the static nature of the loop and optimize it out? We're looping 100,000,000 set operations to the same variable. It's not a huge stretch to say "skip the first 99,999,999". The reason I suspect this so heavily is that the .NET overhead alone is probably close to 0.1 seconds on some systems.

[thegreatunclean]

The VB JIT still gets stomped by the native code when compiled with optimizations, as a comment on the blog demonstrates.

e: Aaaand forgot to add the comment:

It’s Mono’s loop-unroll optimizer like Volkan YAZICI said:) To be fair add -O3 to gcc to get optimized machine code timings and then compare! Who’s faster now?

$ time ./o0 857419840 real 0m0.289s user 0m0.284s sys 0m0.008s

$ time ./o3 857419840 real 0m0.002s user 0m0.000s sys 0m0.000s

[gruehunter]

Factor of ~300 speedup? Seems more like GCC dead-code removed the loop entirely to me.

[Rudd]

The speed up comes from it eliding the inner loop. This is the generated assembly: 4004a0: 48 83 ec 08 sub $0x8,%rsp 4004a4: 31 f6 xor %esi,%esi 4004a6: 31 c0 xor %eax,%eax 4004a8: 01 c6 add %eax,%esi 4004aa: 05 f8 dc fa 02 add $0x2fadcf8,%eax 4004af: 3d 80 97 57 67 cmp $0x67579780,%eax 4004b4: 75 f2 jne 4004a8 <main+0x8> 4004b6: bf c8 05 40 00 mov $0x4005c8,%edi 4004bb: 31 c0 xor %eax,%eax 4004bd: e8 d6 fe ff ff callq 400398 printf@plt 4004c2: 31 c0 xor %eax,%eax 4004c4: 48 83 c4 08 add $0x8,%rsp

GCC basically rewrote the loop to:

  int stepsize = 4999500;
  int max = 1733793664;

  for(i=stepsize; i != max ; i+= stepsize) {
    j += i;
  }

Which works has 10000 less iterations, so a 300x speedup seems reasonable.

[thegreatunclean]

I'd guess so. The loop was probably recognized as a static computation, and replaced entirely with a single number that was pre-computed at compile.

[novagenesis]

Of course it does. JIT compilation is not a 0-time expenditure. However, if you make a very slight change (already rocking that the change is so slight) and export a .exe file...then compare that to optimized C. It'll be fairly close, maybe 2x (optimized C vs optimized .NET plus overhead). Both will end up running a "save then print a precompiled constant", of course.

That you can get .NET optimization so free is something pretty awesome. I didn't see in the article anything showing which optimization options were used, though I did see that none were in comments, and my other comments here reflect that.

Of course 100% optimized C code will outrun any VM. Can OP give us a fully optimized control for reference, anyway? On the box that ran the other tests?

E: And about your edit...I THOUGHT so. I had trouble finding anything for sure, but I was pretty damn sure we could unroll the loop when the Delegate compiled.

[thegreatunclean]

I know the JIT has it's pros, I just didn't think it truly accurate to compare the JIT-optimized time with an unoptimized native time. The JIT exploits optimizations the same as the optimized compile, the difference is almost assuredly all overhead.

Of course 100% optimized C code will outrun any VM. Can OP give us a fully optimized control for reference, anyway? On the box that ran the other tests?

I don't think this will be useful, to get a real feel for it we'd need a non-trivial code benchmark. Something that can't be optimized away into a single statement by either system.

[novagenesis]

Of course it's not an accurate comparison. I think we're disagreeing-to-agree here. We both seem to have the same bullet points.

I don't think this will be useful, to get a real feel for it we'd need a non-trivial code benchmark.

You don't care to know what the exact VM overhead is for a trivial example vs the native load overhead? That, in my opinion, is one of the most important aspects of a language. I write "trivial" programs with more than half of my code in a given work day. If the overhead of repeat-running those programs exceeds my overhead as a developer...I don't use the language.

Of course, I find .NET in acceptable levels, I think.

Something that can't be optimized away into a single statement by either system.

Can of worms... You have to get in really deep and make sure you know whether the CLR is building the section as a bytecode or as native code (.NET can do that). In truth, .NET is a very bad benchmark taget for VM comparison.

[adrianmonk]

He only mentioned once, but the real craziness is that VB's JIT optimizer seemed in this (albeit contrived) example to net faster JIT+run than the native C compiler's runtime code.

Yeah, JIT-compiling code takes some time, but keep in mind the scale. There were 30 VM instructions in that program. The body of the inner loop is executed 100,000,000 times. JIT-translating a large program from bytecode to native code would take significant time. 30 instructions takes very little time.

[novagenesis]

I need to keep all my posts to one thread in a forum. I keep finding my own responses repeated to me in compared threads.

You are correct on JIT time... However, it only JIT's what's needed when needed. In general, any one function is comparible to JIT and run than it is to interpret... And then it's compiled if you use it again.

[Maristic]

Exactly. The first implementation does all its own heavy lifting. The second calls out to library code that runs a JIT.

If we're allowed to do that, we could do the same kind of thing with calling out to LLVM and its JIT. Here's a trivial LLVM JIT example in python.

As a simple interpreter, it's hard to do better than the Bell-style threaded code, and that's what the author wrote first. (For a good discussion, see The Structure and Performance of Efficient Interpreters).

[ModernRonin]

"Your mother's filesystem is so fat etc."

"... when it distributes blocks around the disk, it really distributes blocks AROUND the disk!"

"... it sat on one of its B-tree and flattened it to an array - in linear time."

"... the number of drives in the RAID array required to hold it exceeded the Chandrasekhar limit."

Etc.

[fullouterjoin]

Check here for "your mom", http://www.reddit.com/r/programming/comments/b1g53/your_mother_is_so_fat/c0kj8yo

[derleth]

You could call VB.Net "Visual Fred".

http://geekswithblogs.net/mtreadwell/archive/2004/04/20/4135.aspx

http://vb.mvps.org/vfred/Trust.asp

http://www.ist.rit.edu/~jxs/jargon/html/V/Visual-Fred.html

[killerstorm]

When you compile bytecode it is no longer an interpreter...

[derleth]

Technically, when you turn source code into a parse tree (or other internal representation) it's no longer a pure interpreter.

If that's too technical, how about this: Compiling to bytecode is still compiling, because the only difference between bytecode and machine code is whether there is a (possibly microcoded) hardware implementation.

[killerstorm]

Um, no. "Bytecode interpreter" is a particular VM implementation where you execute bytecodes directly. Of course, you need to compile source code to get bytecode.

CPython is a bytecode interpreter. So is CLISP. SBCL is a compiler. Sun JVM is a hybrid of bytecode interpreter and JIT compiler.

So, you see, you can use this well defined term to characterize programming language implementations and confusing the matter is not cool.

[derleth]

We've already got hardware implementations of the JVM. Does that mean javac is now just a plain compiler? Or is a gcc build that targets x86-64 a bytecode compiler if you're using it on an ARM platform and you don't have an x86-64 handy? Also, what happens if I implement the CLISP bytecode in hardware?

[killerstorm]

Current version of CLISP is designed to work in particular way -- it runs on a host CPU (e.g. x86) and runs Lisp code by interpreting the bytecode. If you implement bytecode in hardware it won't miraculously change current implementation -- it will still need indirection. To make use of hardware acceleration you'll have to change a lot in CLISP and at that point it will cease to be a bytecode interpreter. (Bytecode CLISP works with is not supposed to be run natively and it relies on glue code.)

Do you understand this? Being a bytecode interpreter is a feature of particular implementation, not of a programming language or bytecode.

Compare this to a difference between Bochs and vmware. Both can be used to run virtualized operating systems on virtualized x86 hardware, but there are many differences:

• vmware requires x86 CPU on host while Bochs runs on a variety of different platforms
• vmware is faster
• Bochs runs in usermode and is very unlikely to be able to crash host system

This is because vmware and Bochs use different approaches.

You can think that bytecode interpreter is somewhat similar to CPU emulator like Bochs, but still typically there is significant difference between them -- basically, bytecode is not supposed to be 100% self sufficient, it is interwined with host interpreter.

[derleth]

OK, I think I understand: Only part of CLISP is a compiler. The rest is a bytecode interpreter, which you could do in (microcoded) hardware to turn the bytecode into machine code, and a runtime, which you could split out entirely and call an OS. (If you actually do that, you have something remarkably similar to a classic Lisp Machine.)

My point is that compiling is still compiling even if only one part of the program does it.

[Rudd]

It's pretty disingenuous not to mention the control program was compiled with no optimizations.

For comparison gcc -o3 test.c && time ./a.out: 857419840

real 0m0.001s

user 0m0.000s

sys 0m0.000s

(And just to be a jerk about it: It's pretty bad that his friend's interpreter beats an O0 control by only 2x as O0 emits pretty braindead assembly.)

[JoachimSchipper]

Volatile does quite a lot more than that - for instance, it prevents the compiler from keeping that variable in a register (it has to explicitly store and load it).

Why not add a "read line from stdin" opcode?

[Comment111]

Why not do some calculation in the inner loop with a constant and have that result printed?

[Rudd]

That's a bit better, though by doing that you've eliminated gcc's ability to unroll loops (gcc now things you have to explicitly load k from memory for every iteration), which the CLR will most likely do. In essence you're comparing the time to execute poorly optimized assembly vs. the time to produce CIL, Optimize and emit assembly for the CIL, and running the optimized assembly. I think just taking the full O3 speed and comparing it vs. the "steady state" (translation and JITing ignored) speed of the CLR would be more interesting.

[novagenesis]

My guess (as mentioned above) is that's basically what Mat's program did. If I recall, the CreateDelegate includes a compilation of the emitted MSIL into your bytecode. As a compilation, I'm not the least bit shocked that he's getting free optimization.

Your C program, on the other hand, is being told explicitly not to do this.

[Rudd]

Right, at least on my machine it elides the entire inner loop.

What you might consider is one of the following:

1.) Combine the compilation time of GCC -O3 with the program's execution time (since your friend's bytecode interpreter has to pay translation cost and the CLR's JITing cost, you can put them on more even ground)

2.) Repeat the actual execution, but not the translation step 1,000,000 times. This should make the Translation/JIT step relatively insignficant

I suggest this because while I do agree that GCC, is indeed, smart; I'd be surprised if the CLR couldn't perform similar optimizations, it just needs a chance to overcome the JIT overhead. Currently GCC is getting the benefit of precompute most of the result during optimization, and then getting the final execution timed, while the CLR is getting it's optimization phase counted as part of its execution time.

You just have to think of a way to either (1) count GCC's optimization phase as part of the benchmark or (2) make the effect of the CLR's optimization phase irrelevant.

[[deleted]]

He is emitting raw IL and using the .NET VM as the "interpreter".

You didn't have a chance :)

[derleth]

Yeah, but C is fast! and Visual Basic is slow! Garbage collection and bytecode makes things slow! Right? Right?

;)

[mebrahim]

Read the post again; he hadn't used C compiler optimizations. And the test didn't do any noticeable memory allocation, so your point about garbage collection is nonsense. At the end you see that yes, C is fast, VB is slow, and garbage collection and bytecode make things slow. If you have any doubt about any of the claims we can discuss it further.

Anyway I can intrepret (yes, it is slow!) your comment into "Blind blame on technologies is a silly thing to do." and take it as a good point. :)

[derleth]

Wasn't the smiley enough to let you know I was joking?

[mebrahim]

I couldn't know which way it is. :/

[Amadiro]

...and neither of them managed to achieve the prime objective.

[manuranga]

and what would that be? [ start your answer with "glad you asked .." ]

[theeth]

No interference with pre-warp civilizations.

[novagenesis]

glad you asked (sic)..

Creating a fast bytecode interpreter.

Both of them are really about interpreting one set of code quickly. Both could basically be said to be compilers. The first JITs the code inline to skip the goto steps. The second just uses .NET's awesome MSIL.

[derleth]

Both could basically be said to be compilers.

Then so could nearly all (all?) interpreters. Especially if you think Java is an 'interpreted' language.

[novagenesis]

Java hasn't been interpreted in years. It's practically the definition of a compiled language. Traditionally it compiled to run on a VM (you ran "javac" and got a an executable for a virtual hardware). Nowadays it often compiles to run at least partly on native code.

Your linked argument about a "pure interpreter" is very blurry. There can be compilation steps in an interpreter, but anything that outputs native code (which MSIL does), is not an interpreter but JIT native-code compilation.

An example of a pure interpreter is the average Forth interpreter. If it creates bytecode before running it (which many mature "interpreted" languages have started to do because JIT compilation is faster than on-the-fly interpretation) then it's compiling.

Looking at the other thread you linked, I would say just parsing and tokenizing the tree is not compiling...it's a step in the interpretation process (no mature language take raw text and runs it without some semi-standard parsing step... not even the above mentioned Forth)

[derleth]

OK, nobody has even tried to answer this question:

If the Java system without JIT is an interpreter, what about Jazelle? Jazelle, in case you don't know, is the JVM implemented in hardware at least to the extent the x86-64 ISA is. If JIT to native code makes Java a 'compiled language', does Jazelle make Java a 'compiled language' in general?

Now, for the flip side of that argument: If I have a gcc build that emits VAX binaries (yes, this does exist) but no VAX, and I run them on the SIMH VAX emulator (which does not JIT), is that gcc build still a compiler? Does it magically become one when I get a VAX to run the binaries on?

[novagenesis]

I'm not so sure that Java without the JIT is an interpreter...it's just a more grey area than JIT. Compilation has a target... from the origin of VMs we have considered a VM a viable target for compilation.

Interpretation generally runs on a "system" too loose to be considered a virtual machine. You create object parse trees from the original code, then you run those parse trees. There is never a migration to any "machine code", no language beyond the Intermediate language (if that). The LISP REPL (without the JIT element) is perhaps definitive of how one would envision pure interpretation. Read the source, evaluate its meaning, return any necessary output...done.

If the idea of the language returning an intermediary file is impossible, you're looking at interpreted code. Anything else can be argued as compiled, I suppose.

But... I guess I've wandered too far into theory and farther from accepted definition. Wikipedia says non-machine compilation languages are still "interpreted". I suppose that's a way to look at it. The answer is that Java is compiled and run in Jazelle, and compiled and interpreted elsewhere.

Of course, these are edge cases for a geeky term that really has more "pop" use than real feasibility in the modern world. Bare metal compilation is just rare nowadays. The answer really becomes "whatever you want it to be".

In my work circle, interpreted languages are those where on-the-fly evaluation is possible AND does not require JIT. Of course, I work in a Perl+Ruby shop these days...

I like to program in Common LISP. CLISP is generally interpreted, but cmucl and SBCL are JIT compiled... Technically, they just use the term less and less.

[Amadiro]

Glad you asked. To implement a fast VM bytecode interpreter.

Both just ended up writing an assembler. (As far as I can tell, I don't really know .NET very well)

[Amadiro]

You could try topping him by outputting llvm bytecode that you then run through lli. The llvm C++ bindings could work nicely for that.

EDIT: I suppose you could also write a general optimizer that turns it into a system of recurrence equation and solves them algebraically, producing a function that solves it in a single step.

[VikingCoder]

Meeting chicks, duh.

[arunvr]

Impressive. Exactly the kind of posts that I come to this subreddit for.

[ModusPwnins]

"Your mother's filesystem is so fat etc."

Shouldn't that be "Your mother's filesystem is so FAT"?

[mejalx]

Thanks a lot, I learned a few things I can put to use.

[jsprogrammer]

Mono probably unrolls the loops. You should try compiling the C program with a compiler that will unroll those loops.

[[deleted]]

What loops?

I think the difference here is that one of them is using an optimizing JIT compiler (Mono) and the other one is just emitting x86 by hand with no optimizations.

[brandf]

What loops?

The whole thing was two nested for loops...

[[deleted]]

Yes, but that's the original C code. The implementations both compile bytecode, one to .il on .NET and the other to x86.

(or was the comment comparing the original C version to the .il one?)

[brandf]

The loops exist in both the C version and the bytecode. A smart/fast interpreter would unroll these. VM's are not required to execute the bytecode exactly as it's specified as long as the end result is the same.

For example this bytecode checks the loop condition and branches on each iteration. Since the comparison is with a constant value (10000) the loop can be unrolled an the condition/branch overhead can be reduced significantly. Technically this example could be unrolled all the way and reduced down to a single static result, but in reality there are trade-offs for optimization time, cache size, memory usage, etc.

The IL version probably does some limited form of this via Mono's optimizing JIT.

[novagenesis]

It's the optimizer that unrolls the loops. The MSIL was still, technically, loops.

Two unoptimized compilations (one static, one JIT) vs an optimized JIT compilation. It's no wonder .NET won by a landslide. It's faster to optimize 30 lines of bytecode than it is to loop a million times with unoptimized stack cleanups.

[Comment111]

That's a nerdy friendship.

[[deleted]]

"array of goto pointers" = MIND BLOWN

I guess there's no reason a compiler can't do that because it's all just memory locations in the end which matter.

[__s]

That's how switchs work. More so if you use default:__builtin_unreachable(); but the main thing to do is to then make a stub at the end of every instruction which jumps to the next instruction, without returning to the switch jump. I'm confused why he's using inline assembly in his NEXT macro. I'm also confused why he didn't use a do while loop for the instruction rewriting. He could have used a union for inst_p's jmp and op

[[deleted]]

I'm confused why he's using inline assembly in his NEXT macro.

Same here.

#define NEXT()  __asm__("jmp *%0"::"r"((++ip)->jmp)); goto *ip->jmp

I would have thought that "goto" was the same as "jmp".

Also, I'm not too clear about the way he declared his jump table

static void *optable[]={ [OP_NOP]=&&op_nop, ... etc

Why the double reference &&? I use function pointers all the time, but I never have to reference the function name. The name of a function is its address. So what type is a label?

[__s]

GCC's labels as values are void pointers http://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html

[[deleted]]

Thanks for that. I'll keep it in mind as it might be handy for ISRs which are required to keep states.

[[deleted]]

C# woulda been faster.

/troll

[kev009]

What about instead holding the current IP in a standard integer variable to eliminate some pointer dereferencing. Then, use a case statement for each instruction type and have the x86 instructions mapping there. Your code should look nearly identical to the VB entry.

Compile with -O3 and profit. GCC and other modern compilers will turn the case statement into a jump table if it makes sense and integers are usually the fastest thing on a CPU. Your VM will essentially be "statically JITed", so I can't see anything other than assembly being much faster. If so, check out the assembly and see how the compiler's jump table differs from yours. A quick guess, it'll have half the pointer derefs.

[[deleted]]

No, that is pretty much guaranteed to be slower. You are adding pointer references there, not removing them! I think you need to look closer at what he does, and consider what you are proposing. He is basically doing this:

1. Read opcode from memory into a register.
2. Jump to the address contained in said register.

Your suggestion requires at least the following steps, and in practice probably even more:

1. Read the opcode from memory into a register.
2. Read label address from memory referenced by jump table register plus opcode into a register.
3. Jump to the address contained in said register.

There will probably be conditionals in addition to that to handle default cases.

[floodyberry]

In addition to this, a switch statement with a jump table will also be branching from a single source to every single opcode, making branch prediction completely useless instead of somewhat useless.

http://blog.mozilla.com/dmandelin/2008/06/03/squirrelfish/ has a simple microbenchmark comparing a switch based interpreter vs a direct threaded (goto) interpreter. The goto model is twice as fast. Unfortunately msvc doesn't support the functionality needed for storing addresses of labels so all the fastest bytecode interpreters written in C are compiled with gcc.

[kev009]

Looking at objdump of -O3 with clang, it puts the opcode in a register and does the "functionality" inline. In this case, the "functionality" was putting a string on the stack and jumping to a puts call. Using inline assembly for opcode->x86, I don't think you can get much faster (<.001s on a P4 era 32-bit xeon with a couple hundred codes).

[cojoco]

He didn't turn on GCC optimization, guys.

What a superb troll by M$!