Hacker News Reader

Comment by CodeArtisan | Hacker News Reader

Virtual Machines: Versatile Platforms for Systems and Processes covers both virtual machines for implementing programming languages and virtual machines for emulating cpu architectures. One of my favorite optimization techniques explained in this book is pre-decoding:

After loading the program's instructions, every opcode is replaced by the address of the corresponding routine implementing the instruction. For example,

      [OP_ADD][REG_A][2]
      [OP_MUL][REG_A][REG_B]
      [OP_RET]

become

      [0x4bcf00][REG_A][2]
      [0x4bcf10][REG_A][REG_B]
      [0x4bca05]

Then, using goto from GNU C[1], decoding is now just

      goto *ip;

I think this is still the state-of-art technique for interpreting instructions.

[1] https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html

View on HN

Ah thanks, I think this is the terminology I mentioned in this comment!

https://news.ycombinator.com/item?id=16777516

that is, "system" VMs vs. "process" VMs. I don't really like those terms, but the distinction is a good one. I think the author must have been at the VM summer school I linked there.

-----

BTW this 2015 paper is saying that the labeled gotos technique isn't a big deal on Haswell:

Branch prediction and the performance of interpreters -- Don't trust folklore

https://scholar.google.com/scholar?cluster=20257610669850946...

In other words the branch predictors improved enough on Intel such that it's not a big optimization. But I don't like how they didn't mention other CPU architectures. Intel is not all we care about!

Also, it would be nice to have an update on this 2015 paper to account for 2017-2018 Spectre/Meltdown mitigations...

The first part of the paper compares token threading vs naive switch in cpython 3.2 which has a compile flag to disable token threading[1]. I were referring to direct threading but the difference is probably minor or irrelevant.

on x64, token threading is

    ; goto tokens[program[ip]]
    mov r0, [program_instructions + ip]
    jmp [tokens + r0]

while direct threading is

    ; goto program[ip]
    jmp [program_instructions + ip]

the paper says

Nehalem shows a few outstanding speedups (in the 30 %– 40 % range), as well as Sandy Bridge to a lesser extent, but the average speedups (geomean of individual speedups) for Nehalem, Sandy Bridge, and Haswell are respectively 10.1 %, 4.2 %, and 2.8 % with a few outstanding values for each microarchitecture. The benefits of threaded code decreases with each new generation of microarchitecture.

but looking at the graphic, it seems a few benchmarks still had a +5% speed boost on Haswell.

It would also have been interesting if the paper provided the generated code by gcc for the switch statement. If the switch statement's cases are linear (0, 1, 2, 3, ...) and if there are more than 4 cases, then gcc token threads the code.[2]

[1] https://hg.python.org/cpython/file/v3.3.2/Python/ceval.c#l82... [2] https://godbolt.org/g/yRjFto

Thanks for mentioning this book, it sounds amazing. If I hadn't just bought Lisp in Small Pieces I'd probably be looking at picking this up, but I need to work through that book first. However this is going on my future buy list.

So this is a kind of decoding of token threaded code to subroutine threaded code? How does the actual argument passing work, i.e., how does the routine starting at 0x4bcf00 know where to look for its operands?

Reply on news.ycombinator.com