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]
[0x4bcf00][REG_A][2]
[0x4bcf10][REG_A][REG_B]
[0x4bca05]
goto *ip;
[1] https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html
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...
on x64, token threading is
; goto tokens[program[ip]]
mov r0, [program_instructions + ip]
jmp [tokens + r0]
; goto program[ip]
jmp [program_instructions + ip]
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
What other books cover bytecode interpreters? (In other words, the part of the book that you are 2 chapters into.)
I can't think of any! Many people learn about the front end in a "compilers" class. The Dragon Book and "Modern Compiler Implementation in X" are two of the most popular books, but they don't cover interpreters at all.
The other branch people learn about is Lisp interpreters, which are often tree intepreters (as in the first section of your book). And when they are bytecode interpreters, I think they have a compilation process that's fairly different from say Python/Lua/JavaScript. For example the "nanopass" style is somewhat popular for teaching, and pretty different from what I understand. The source language is further from the machine model.
It seems like the best sources are the Lua papers you mentioned, but I would call those primary sources.
I can't think of any "secondary sources". Terrence Parr's Language Implementation Pattern does part of a bytecode interpreter, but it's in Java, and it leaves out the bytecode compiler as far as I remember.
So somewhat surprisingly I think everybody who implements bytecode VMs these days just looks at Lua and Python?
I guess Lua was influenced heavily by Scheme, and I don't know where Python got its implementation style, maybe from the ABC precursor.
Anyway I'd be interested in hearing about other sources (primary and secondary), but it dawned on me that this is the ONLY full bytecode interpreter I've seen in a textbook. And I have a whole bunch of books and have been doing this for a few years.
So if that's the case, then kudos for filling this gap! :)
EDIT: A primary source that has been useful for me is The ZINC experiment: an economical implementation of the ML language, which is a description of the predecessor to OCaml (both written by Xavier Leroy). Although OCaml is statically typed and functional, the bytecode interpreter itself has some similarities to Python/Lua. They mention keeping your top-of-stack register in a CPU register, the relationship between runtime values and garbage collection, etc.
The book "Real World OCaml" reviews a little of this material.
https://scholar.google.com/scholar?cluster=11229975720599781...