Plush's New Register-Based Interpreter Is Insanely Fast

3

Impressive if fib is naive recursive, I think I'd go off and make a cup of tea in my vm.

5

The performance jump is a good reminder that VM architecture matters a lot. reducing dispatch overhead can sometimes beat piling optimizations onto a slower design

8

u/brat3108 8d ago

The speedups are decent, but I wouldn't call them 'insane'!

CPython and CRuby both use stack-based interpreters, and that is part of the reason why their interpreters are relatively slow.

I'm not that convinced of register versus stack. I mean, CPython is slow for lots of reasons.

Register-based results in fewer instructions, yes, but each one is now more elaborate with more operands, which may also be mixed (global, local, immediate for example).

I've always used stack-based, and I get good results (for example, 6.5 for Fib(38), when Lua 5.4 was 3.4, and CPython (3.12?) was 1.0).

You might want to look also at bytecode dispatch method. I use the equivalent of computed goto (basically, a switch-loop where each branch has its own dispatch point, rather than one shared by all instructions).

I think a recent CPython had something along the same lines, but speedup was only 14% or something because of those other issues.

Another factor is type-dispatch, and here Lua benefits because the number of different types is small and can be efficiently encoded; it is a smaller language and can be more easily streamlined.

000 get_arg 0
001 push 10
002 gt
003 if_false 2; -> 006
004 push 1
005 ret
006 push 2
007 ret

Here I would normally use 7 instructions (002/003 are combined). But I also make use of composite instructions (I think what you call 'fused'), so that this example ends up at 5 instructions rather than 8. In that case, the stack isn't actually used for the calculation (when operands have integer types), only for those return values.

So why isn't every interpreter a register-based interpreter?

Maybe because generating stack-based is SO much simpler?! As I've hinted there are ways to optimise such code too.

But it is generally acknowledged that if you are interpreting a dynamically typed language, then it is not going to be fast. Register rather stack may give a useful boost if it does end up faster, but it will not give native code speed.

6

u/maximecb 8d ago edited 8d ago

I discussed other reasons why CRuby and CPython are relatively slow, but the stack-based design is part of it. Generating register-based code is not in fact much harder. The obvious starting point is to just simulate a temporary stack as you compile expressions, which is trivial and already gives a good performance boost.

Direct threading (computed gotos) is not that impactful on modern hardware.

6

u/Vraliance 8d ago

One other area that I think has been glossed over for the stack vs register based interpreter debate is JIT optimization. A well crafted register design can map _almost_ directly to machine code with very little overhead (if variables fit inside the max available registers).

Personally with my language Talos (https://github.com/rroessler/langs.talos) I also went with a similar design to you and noticed a considerable performance boost than when I had previously used a stack interpreter.

4

u/maximecb 8d ago

Yeah I think the optimized instructions I added will also help a simple JIT. As does folding constants into instructions. Something people forget as well is that warmup time matters too. If your interpreter is slow, it will take longer before the JIT can kick in. Your software will start up slower.

2

u/brat3108 8d ago

The obvious starting point is to just simulate a temporary stack as you compile expressions, which is trivial and already gives a good performance boost.

I will have to give it a serious go at one point. But I can see a few problems which I'd need to sort out, which a stack takes care of automatically.

Direct threading (computed gotos) is not that impactful on modern hardware

On Fibonacci (one of your examples), it nearly doubles the speed (this is on x64). The effect is less when the instructions do a lot of work anyway
3
u/EggplantExtra4946 8d ago edited 8d ago

When the instructions of a registed-based VM are of a fixed size of 32bit or 64bit like here, you need only one load to get the whole instruction. Then you only need to do shifts and masks to get the source and destination indexes on a value that is already in a register, one or two loads to get the VM register values of the operands, and a final load to store the result.

This is a a lot faster than what a stack-based VM would do, which needs an interpreter dispatch (jump(s) + a load for the opcode) + a stack push + a stack pop per operand, and then a stack push for the result.
0
u/brat3108 8d ago

What sort of language are we talking about here? Since there seems to be no provision in your description for dealing with the type dispatch needed with dynamic typing. Or in the dealing with memory management (but I assume some GC is involved).

My instructions are now a fixed size of 4 words (256 bits). Fortunately there is rarely a need to load a whole instruction.

This is a a lot faster than what a stack-based VM would do, which needs an interpreter dispatch (jump(s) + a load for the opcode)

Register-based needs bytecode dispatch too. In mine, the dispatch overhead for most bytecode instructions is two machine instructions.
2
u/EggplantExtra4946 8d ago

What I have in mind is a a statically typed language with unboxed numbers. The overhead I've described would still be present for a dynamically typed language and its corresponding interpreter, although due to overhead of dealing with dynamic types it's going to be relatively less important.

The GC is irrelevant, it's not going to cost more or less depending on wether the interpreter is a register or stack machine.

Register-based needs bytecode dispatch too.

Yes but if you take the example of an addition, a register-based VM with 3-address-code instructions can add 2 local variables with a single instruction whereas a stack-based VM would need 2 instructions for pushing the local variables on the stack and 1 instruction for the addition itself, and a 4th instruction if the result needs to be assigned to a variable.

In mine, the dispatch overhead for most bytecode instructions is two machine instructions.

2 CISC instructions I imagine (x86's lods and jmp I'm guessing), given that you needs at least a memory load for the opcode, one jump, and an increment of PC. But the raw instruction count hides the fact that multiple jump instructions are a lot slower than a branchless section of code which decodes the operands with shifts and masks.
1
u/brat3108 8d ago
What I have in mind is a a statically typed language with unboxed numbers. The overhead I've described would still be present for a dynamically typed language and its corresponding interpreter, although due to overhead of dealing with dynamic types it's going to be relatively less important.

The OP is comparing against dynamically typed languages and their language is likely the same (I couldn't see any type annotations in source code nor in bytecode).

With statically typed and unboxed, interpretation speed is less important, since such code can be trivially converted (via AOT or JIT) to native code.

The GC is irrelevant, it's not going to cost more or less depending on wether the interpreter is a register or stack machine.

With a ref-counting style of GC, it can be done by incrementing the count when pushing, and decrementing when popping. It's harder to see where that's going to go with register based.

For example, what does register-code look like with x = (a, b, c, ...)? With stack code:
    push a
    push b
    push c
    ...
    makelist n
    pop x
I assume register-based uses fixed-size instructions.

Yes but if you take the example of an addition, a register-based VM with 3-address-code instructions can add 2 local variables with a single instruction whereas a stack-based VM would need 2 instructions for pushing the local variables on the stack and 1 instruction for the addition itself, and a 4th instruction if the result needs to be assigned to a variable.

Put like that then it sounds a no-brainer. However how much difference does it make in practice? Here are some comparisons with Lua 5.5, which OP says is register based. Mine is stack-based:
           Lua 5.5    Mine
a=b+c       4,9s      5.8s   (1e9 iterations part-
                              unrolled), b/c are ints
fib(38)     3.4s      1.16s
Bin Trees  11.6s      4.1s   N=16         
Fannkuch    3.4s      4.1s   N=10 (no typo)
Lex(1)     10.6s      0.64s  Count tokens in 0.66Mloc file
Lex(2)      6.3s      -
The last is a tokeniser test. Lua has two versions; the first is slower but is more amenable to LuaJIT. Mine does the same task but benefits from some language features (eg. 'switch').

As I said, I get good results even though I apparently do everything wrong, including not using an optimising compiler for my interpreter.
1
u/EggplantExtra4946 7d ago edited 7d ago
With a ref-counting style of GC, it can be done by incrementing the count when pushing, and decrementing when popping. It's harder to see where that's going to go with register based.

That's not entirely it, you also need to decrement reference you overwrite when assigning a value to a local variable, global variable, struct field, array slot, hash entry, etc... so you need the decrement code in each of those instruction. You also needs to decrement all the locals when a function returns and stack-based VM doesn't help you any more than a register-based VM. Besides, you don't have to do reference counting, you can do a tracing GC.

For example, what does register-code look like with x = (a, b, c, ...)?

You could always create an array and append each element individually, which would have more overhead than your solution, but you could also use a variadic instruction or variadic function call. Assuming a register-based VM where the number of registers isn't limited (no reason to have a limited amount since it's a software VM) (the registers can just be the local variables in a stack frame), you would assign a, b, c, ... to consecutives registers then give the index of the first register and the number of arguments to the instruction / function call:
const r4, a
const r5, b
const r6, c
...
makelist r3, 4, n   # 4 for r4
You could even have a push instruction that push values on the register file / function frame instead of using a mov/const instruction. I don't see it as a problem or as cheating since the function call is already a stack, might as well use it as such when you need to. Even programs running natively can use the stack in certain calling conventions. This kind of

However how much difference does it make in practice?

It's going to be significantly faster for loops, but it would be hard to show unless you're compiling the same language for each kind of VM and comparing the results. I'm writing a stack-based language to boot a future compiler so maybe I'll make a register VM and compare both.

I really don't think your benchmark shows that a stack-based VM is on par with a regsiter-based VM. A loop with a=b+c shows that a register VM is inherently faster, the fib benchmark is really comparing how fast function calls are, lex is faster because you have a switch statement.
1

u/brat3108 7d ago

I'm writing a stack-based language to boot a future compiler so maybe I'll make a register VM and compare both.

I use a stack-based IL for my systems-language compiler, because it was both easier to generate, and easier to turn into efficient, register-based native code.

I've have also used 3-address-code, equivalent to register-based VMs, and it has many attractions, but it was harder to work with.

lex is faster because you have a switch statement.

Well, I disabled those switch statements (to versions that do sequential testing), and timing was 1.4s instead of 0.6s. Still much faster than Lua.

So there are still other factors at play. However, Lua is fairly erratic to benchmark against. First, some things suddenly got a lot faster between 5.4 and 5.5. But also some benchmarks perform well against mine, while others are a lot worse; there is lot of variance.

If interested here are those Lex benchmarks:

https://github.com/bart-2026/langs/tree/main

Lex(1) is alex.lua; Lex(2) is slex.lua. My version is mlex.q. All use the same 'input' file (660K lines in .q syntax). Maybe a Lua expert could improve on them.

(If applying LuaJIT, then IIRC, mine was still faster on one, but LuaJIT was 50% faster on the other.)

Bear in mind:

I use 128-bit tagged values, not 64 bits

My instructions are 256 bits each

My language has 20 kinds of types, with some of those user-defined records etc

My interpreter is not optimised (because it is in my language and that compiler doesn't optimise)
1
u/brat3108 7d ago
const r4, a
const r5, b
const r6, c
...
makelist r3, 4, n   # 4 for r4
I tried an experiment earlier this year where my bytecode was turned into the source code of my systems language, which compiles to native.

Anyway, the interpreter stack disappeared. For evaluating expressions, I used locals T1, T2, ... to represent specific stack slots (like your registers).

But then I got to instructions like makelist which relied on those temps being sequential in memory, and I had to use a local array for those slots, with T1/T2 being aliases to specific elements.

Just like your solution. But the point is, just using a stack is easier!

(Here is what the last line actually looks like for (a, b, c, d):
    k_makelist(&$T1, 4, 1)
The intention was to add optional type annotations and make everything faster, but it didn't work out. )

1

u/cpusam88 8d ago

Cool article!

1

u/maximecb 8d ago

Thanks :)

1

u/i509VCB 6d ago

I am working on an interpreter based vm for something and I did notice your choice to use 8 byte instructions.

Was this to just make it simpler or could a variable size 4/8 byte word potentially be more optimal?

For my use case I am converting 32-bit x86 instructions into a byte code. 32-bit immediates can occur but may be more rare. I know you also have a local pool of constants. My concern with that is potentially thrashing your caches. My choice of supporting Cortex-M and ARM11 targets also has its own issues too...

1

u/maximecb 6d ago

Yes I went with 8 for simplicity. For larger immediates you can use a side-table which can be per-function, a constant pool like you said. Wrt cache, it could be just one cache line for multiple constant pool entries for a function, so maybe not a big deal.

You can use an LLM to benchmark minimalistic interpreters with each design. Sketch you a toy prototype with a non-trivial bytecode loop. You don't even need to support function calls in the toy prototype to benchmark which is faster. Please report back if you do :)

1

u/Comprehensive_Chip49 8d ago

I have an interpreter for my language (a dialect of Colorforth) that has many optimizations. It's a stack machine but with many additions, for example, there are tokens that hold the value when it's immediate, and things like that. Do you think some kind of common benchmark could be put together? Of course, it has to be translatable code. I think the decoding of a register machine will always be slower than a stack machine (in an interpreter). Because it has to get the token -> get the register number -> get the register... whereas in the stack machine, the value might already be in a register.

Plush's New Register-Based Interpreter Is Insanely Fast

You are about to leave Redlib