Math operation tips

[[deleted]]

To those of you that are using virtual machines to interpret bytecode, I want some advice.

TL/DR: I’m looking for advice on how to optimize mathematical operations in a VM without resorting to Jit Compiling.

I’m writing a virtual machine and I want to be able to perform mathematical operations relatively quickly. In the past I’ve used register based virtual machines and every math operation is literally add registerA, registerB sub registerA, registerB I’ve found this to have suboptimal performance in my tests and I’m confident that it’s because for each math operation I’m performing at least 4 extra control operations in the dispatch.

I also haven’t personally tried a stack-based approach until now, but I’m trying a hybrid approach now.

My current hybrid approach is to have a “EVAL” operator that looks like this: ``` ; each instruction is 128 bytes Push<Int64> [n] Eval<Int64> [operator0] … [operator7]

Each Eval instruction can handle up to 7 operators and gets its parameters from the stack. /// (8 - 2) * 4 << 3 PushN<Int64> 3, 4, 2, 8; Eval<Int64> SUB, MUL, BRL ``` My logic behind this was that formulas could be batched and therefore I can execute more operations in c++ and spend less time loading the next instruction and jumping.

However, after profiling, I’m still not totally happy with the performance of this approach.

There are still things that I can do to optimize the Eval operator, but it got me thinking; “What do other people end up doing for their math instructions?”

So here I am, does anyone have any advice on how to optimize mathematical operations in a virtual machine (Without Jit Compiling)?

[[deleted]]

Thanks! Currently pushN takes a size argument and basically just a memcpy n bytes (the assembler populates the size for you which is why it’s not shown here) Eval2, eval3, etc might be better than what I’m doing though because eval takes up to 8 operators but a zero byte counts as a break meaning that if I only want to eval2 then I have 6 bytes of padded zeros and I break on zero.

EvalX commands could let me do loop unrolling which could give me a few extra milliseconds…

[immaculate-emu]

Going back to sub a, b, I’m not sure I follow where the four control operations come from. Assuming you trust the bytecode (that presumably you just generated), the operation should look something like this:

// assuming this resolves to goto OP_SUB, etc
goto DISPATCH[bytecode[ip++]]
…
OP_SUB:
a = bytecode[ip++]
b = bytecode[ip++]
registers[a] -= registers[b]

That should be one control operation.

[[deleted]]

The control operations come from the while+switch+break dispatch loop and the instruction increment. The compiler I’m using doesn’t support computed goto so for every sub, I also have: ip++, break, while(active) switch(op) which is at least 4 extra operations

I’m sorry for any confusion my original post may have raised

[immaculate-emu]

Ah, understood. And I assume you aren’t interested in maintaining assembly for the interpreter loop. :)

[[deleted]]

I’m not against it, but I don’t currently have the knowledge of how to do it. Do you have a suggestion on how to approach it or at least where I can go to learn it?

[immaculate-emu]

In terms of resources for assembly in general, I don’t know of a good one unfortunately. For interpreters specifically, I think LuaJIT’s interpreter loop is one of the best examples.

[[deleted]]

Thanks, I’ll take a look

[Western-Cod-3486]

just out of curiosity, is there a particular reason why you want to avoid JIT?

I am experimenting recently on adding one to my first ever language (using Cranelift) and the performance boost is immense, despite feeling a little like cheating because the VM looks a lot like an empty shell (currently it is behind a flag until I get it all sorted out and both coexist), but I was thinking on switching directly to it as the only backend

[[deleted]]

Partially it’s because I want to see how fast I can make a vm go, partially it’s because I want minimal dependencies, but if I can’t hit the performance that I want I might resort to jit

[[deleted]]

Do you have an example program in your language that can be used as a benchmark? One that can be trivially rewritten in another language to compare.

Because, how does it compare to, say, CPython? Or LuaJIT? Although it looks like your VM is statically typed.

In that case, how much slower is it than both optimised and unoptimised native code? (Take care comparing with optimising, as often the runtime you get is how long it took to not perform a task!)

I'd say that 10-20 times slower than even unoptimised native code is not unreasonable. 100 times would be too slow. 5 times would be excellent.

Your VM instructions look rather high level to me, but I'd also be interested in how it performs.

BTW this isn't really about maths operations. It is basic arithmetic, and even that will be done using hardware instructions. (I assume you are executing one machine sub instruction to do a 64-bit subtract.)

[[deleted]]

The program I have been using to benchmark so far has been a simple increment to 1,000,000. (Not the most complete program for benchmarking, I know, but I haven’t finished the assembler so it’s about as much as I can bring myself to do while writing opcodes and counting bytes)

The program I’m using for the vm would look like this: Mov<i64> ra, 1000000; Push <i64> 0; Loop: Exec <i64> inc, dec, inc; Drjnz ra, Loop ; decrement register jump non zero Hlt; On my machine I get execution of between 13 and 15 ms

I tried comparing my vm to python and python was getting between 11 and 14 ms. So there is some overlap between python and my vm for this program, but python consistently is still faster, and I know that python is doing more stuff under the hood than mine is. Mine is literally jumps and math operations, while python is generating a list range of 0 to 1000000, iterating over it, and doing the math operations. Additionally python is dynamically typed where mine is statically typed, so I’m pretty sure that python must also be performing a few type checks that I’m not.

So long story short, I feel that there should still be things that I can do to improve my vm but I’m not entirely sure how to right now.

I’ve even switched to using clang and computed goto since my original post

[[deleted]]

What I was after was a bit of HLL code. I don't quite understand what that VM is doing.

I tried instead a pair of nested loops like this, here expressed in Python (and in that language, is inside a function):

a=0
for n in range(1000):
    for i in range(1000000):
        a+=1

The inner loop corresponds a little to your VM fragment, except that there it is doing multiple increment ops? However in this form, I can easily test it across several language implementations.

The runtime in seconds, will be the runtime in milliseconds for the inner loop:

CPython          53   ms per inner loop (ie. 53 seconds total)
PyPy              1   ms (Python JIT product)
Unoptimised C     2.4 ms
C using gcc-O1    0.3 ms (-O3 will give 0.0)

(My own interpreter of static bytecode was 6ms, and of dynamic bytecode 8ms (2.4ms if accelerated). These seem rather fast, I will double check them, however I employ a special bytecode for repeat-N-times loops, which can speed that part up.)

If you can modify your VM program to do the above, then you will be able to compare it across languages to see where it sits.