Doing the impossible and kicking common sense in the pants—that’s the life of the Gurren-Dan! © Kamina
This article enters into a technical debate with a 2015 article by Atakua, whose approaches I am attacking. Atakua explores 7 types of bytecode interpreters, but does so disrespectfully - the fastest turns out to be binary translation, which is essentially no longer a bytecode interpreter, but a form of Ahead-Of-Time compiler. This binary translation translates bytecode into machine code, which is a chain of calls to compiled service routines. The very same ones that are responsible for executing each opcode in a bytecode interpreter.
But Atakua didn't squeeze all the possible speed out of bytecode interpreters. So this article is a tutorial: how to write a bytecode interpreter that can outperform JIT/AOT compilation in speed. Interested? Read on!
A benchmark is included. There will be a bit of hardcore and not a single AI-generated image!
For starters, let's look at the histogram. I'm using Atakua's benchmark, adding my own results to it. The rightmost, and also the smallest blue bar (native), is the native code provided by Atakua as an estimate of the optimization limits. It's not entirely correct for evaluation because it lacks checks for the number of steps, stack boundaries, procedure call counters, and other virtual machine attributes - it's just a demonstration of the minimum time limit for the chosen prime number finding algorithm.
My results are marked in red. Yes, I managed to outperform binary translation. By a factor of three.
Why is this important and who needs it?
Because a bytecode interpreter is one of the best ways to implement an execution environment "in place". This allows solving many problems in an elegant way. For example?
to add a scripting language to your product for automating user actions,
for developing a variant of regular expressions to analyze not text, but sequences of events coming from mobile application telemetry - from millions of devices and in real-time,
for porting abandonware to modern architecture (emulators),
creating secure "sandboxes" for executing and heuristically analyzing untrusted code,
developing a plugin system for your new browser,
you are making a cross-platform application and looking for a way to write a minimum of architecture-dependent code,
you are trying to make Ethereum smart contracts work on the Solana blockchain, which they were not designed for,
you are writing a code instrumentation utility, a program monitor, or an emulating debugger for a brand new System-On-Chip,
ridding humanity of the headache of finding drivers,
writing your own Forth for your own pleasure.
Almost a silver bullet, judging by the breadth of applications!
All this requires an understanding of how fast a bytecode interpreter can be. And knowledge of methods to make it fast. Especially if you are not ready to use heavy artillery like JIT compilation and want to get by with "minimal bloodshed".
This article will help you understand how to write, perhaps, the fastest bytecode interpreter.
Let's restore some context. Here is a picture from Atakua's article that explains everything (if not, it's worth refreshing your memory of his article)
His tail-recursive variant is good: it demonstrates the best speed among his interpreters. Why? Because at the end of each service routine is what Forth programmers call "NEXT": inlined code for three operations: ADVANCE_PC, FETCH_DECODE, and finally, DISPATCH. This last DISPATCH performs the tail call.
Why is this method the fastest? The processor's branch predictor associates a history with each branch. History improves predictions. There is logic in the sequence of bytecode instructions: for example, a comparison procedure is usually followed by a conditional branch procedure. Thus, each tail DISPATCH develops assumptions about where it will need to jump. These assumptions are known even before this jump begins to execute. Therefore, the processor starts executing the next instruction in advance, and if it guessed wrong, it can simply discard the execution results.
Atakua did an excellent job leading us to the implementation of a tail-recursive virtual machine, for which, of course, it was necessary to consider all the previous options (they are also interesting). And now we can move forward.
Let's try to globally optimize the entire program: our task is well-suited for this because the program itself, i.e., the bytecode interpreter, is compact.
To begin with, we can make all interpreter state data global variables. This will save on passing function parameters, their prologues and epilogues, and saving and restoring registers. Tail calls do not need return addresses, so we don't need call/ret, and all calls within service routines are already inlined.
This is where we can beat the compiler, whose optimizations are local. A global analysis of any program would require the compiler to analyze too many execution paths. But, unlike the compiler, we know for sure that in tail-recursive execution, all paths have a common pattern - service routines jump into one another until they reach Halt or Break. Here we are smarter, or rather, more informed than the compiler, which has to operate within the constraints of the most general scenario.
Let's look at the data structures that manage the state of the virtual processor and the virtual machine as a whole:
typedef uint32_t Instr_t; typedef enum { Cpu_Running = 0, Cpu_Halted, Cpu_Break } cpu_state_t; /* Simulated processor state */ typedef struct { int32_t sp; /* Stack Pointer */ uint64_t steps; /* Statistics - total number of instructions */ uint32_t stack[STACK_CAPACITY]; /* Data Stack */ uint32_t pc; /* Program Counter */ const Instr_t *pmem; /* Program Memory */ cpu_state_t state; } cpu_t; /* A struct to store information about a decoded instruction */ typedef struct { Instr_t opcode; int length; /* size of instruction (1 or 2 for our bytecode) */ int32_t immediate; /* argument of opcode if exists */ } decode_t;
Oh, Atakua wrote a very minimalistic virtual machine! What if we move all of this into registers? Then our virtual machine, in the course of its work, could avoid touching memory at all (except for the stack):
#define sp %rsp #define steps %r8 #define pc %r9 #define prog_mem %rsi #define state %r15 #define opcode64 %rdx #define opcode32 %edx #define immed64 %r14 #define immed32 %r14d
In Atakua's original virtual machine, the stack is 32-bit and can hold up to 32 values. This is something we have to live with: if we do it differently, the comparative benchmark becomes irrelevant. But when implementing such a stack "head-on," you have to deal with an array, access to which will be performed using a combination of the stack's base address and the stack cell's offset. This is less optimal than using the host machine's 64-bit stack. Therefore, for the sake of optimization, we can change the way we work with the stack:
use 64-bit stack elements instead of 32-bit ones, leaving the upper bits as zero,
use the stack pointer in the %RSP register as the offset (offsets will become multiples of the stack element size)
Thus, we eliminate the code that manually recalculates the stack pointer, instead using processor instructions that simultaneously push/pop a stack element and modify %RSP. This simplifies addressing and gains speed in the hottest part of the stack machine's code - stack operations.
All these parts of the interpreter work together; improving performance in one aspect opens up opportunities for improvement in another. At the same time, by optimizing the interpreter, we are not changing anything in the virtual machine itself. To eliminate ambiguity, I will provide an explanation from ruv:
One should distinguish between the concepts of a "machine" (or "virtual machine") and the "runtime environment" (or "execution environment") for that machine.
The concept of a "stack machine" (or "virtual stack machine") implies that the instructions of this machine take parameters from the stack and put the results on the stack. The stack is part of the virtual machine. Different stack machines have different formats of "executable" code.
The code is "executable" in quotes because there is a question of who/what executes it. If a real CPU executes it directly, then it is truly executable code. Otherwise, this code is executed by another program. In Forth terminology, this program is called an "address interpreter"; for bytecode, it would be called a "bytecode interpreter".
The interpreter is part of the runtime environment. The service routines that implement the machine's instructions are also part of the runtime environment. The implementation details of different parts of the runtime environment are interconnected — i.e., if you change the implementation of the address interpreter, you may need to change the service routines as well.
Different execution environments can be made for the same virtual machine (and code format).
The code format (threaded code, subroutine-threaded code, bytecode, etc.) characterizes the virtual machine, not the execution environment.
The implementation details of the address interpreter (if it exists) characterize the execution environment, not the virtual machine.
If the address interpreter uses a stack, then, formally, it is a different stack, not the stack machine's stack. In some cases, the address interpreter itself (or bytecode interpreter) can be a finite state machine and not use a stack at all.
In our case, the interpreter itself does not use a stack, as it is built on tail calls and does not need a stack to call the next service instruction. Only one service routine (Print) uses the stack in the classic way - to call printf(), the rest use the stack to manipulate the data that the virtual machine's bytecode operates on.
There is another important thing for the stack - its boundaries. Since they are checked with every stack operation, we should definitely put them in registers. The boundary values must be calculated at the start of the virtual machine, before bytecode execution begins.
/* Удобно запомнить, если воспринимать "b" в имени регистра как "border" */ #define stack_max %rbp #define stack_min %rbx
What else (that is frequently used) can be put into registers to make the interpreter run faster? Two things remain: the first is the limit on the number of steps the interpreter can take, and the second is the base address of the array of procedure pointers. Each of these procedures services its own virtual machine opcode.
#define steplimit %rcx #define routines %rdi
Excellent! We have placed all variables in registers and even have some registers left over. Two of them can be used for frequently used constants:
# 1 = Cpu_Halted #define one %r11 # 2 = Cpu_Break #define two %r12
And there are still two registers left that can be used to cache the top two elements of the stack. This is used in the implementation of Forth machines and helps improve the performance of frequently executed SWAP and OVER. I will show this technique in detail below.
#define top %rax #define subtop %r10
Note the choice of %RAX as the register that caches the top of the stack (top). Some machine instructions, such as DIV, use the %RAX register as an implicit operand. And if we already have an operand at the top of the stack, we won't have to load it, which will save us one assembly instruction in the implementation of the MOD service routine later.
So, we have occupied all registers except one. Let's call it the "accumulator" and use it when necessary:
# define acc %r13
И на третий день Бог создал "Ремингтон" со скользящим затвором, чтобы человек стрелял в динозавров и прикладных программистов... Аминь! (с)
"But wait!" says the person with the compiler, "Can we really manually allocate all the registers, leaving none for the compiler? Even Atakua in his binary translation pinned only one variable to the %r15 register!"
Recommending that the compiler bind one global variable to a register is just a recommendation, and the compiler can ignore it. But pinning all the registers is just trolling. Therefore, let's spare the compiler's feelings and break out the assembler. Which assembler to use? Of course, we will use an assembler designed to serve as a backend for GCC, not for a human to write in. An assembler with an inside-out operand order, so explosive that it's even reflected in its name: GAS.
So, each service routine in Atakua's implementation ends with the following sequence:
ADVANCE_PC(); *pdecoded = fetch_decode(pcpu); DISPATCH();
..and this code is repeated almost everywhere and is an excellent candidate for optimization. So what's happening in it?
#define DISPATCH() service_routines[pdecoded->opcode](pcpu, pdecoded); #define ADVANCE_PC() do { \ pcpu->pc += pdecoded->length; \ pcpu->steps++; \ if (pcpu->state != Cpu_Running \ || pcpu->steps >= steplimit) \ return; \ } while(0); static inline decode_t fetch_decode(cpu_t *pcpu) { return decode(fetch_checked(pcpu), pcpu); }
Decode places the current instruction into the opcode variable and calculates its length. If the instruction has an immediate operand that follows it, it is placed in the immediate variable. fetch_checked checks if the program_counter has gone beyond the program's bytecode:
static inline Instr_t fetch_checked(cpu_t *pcpu) { if (!(pcpu->pc < PROGRAM_SIZE)) { printf("PC out of bounds\n"); pcpu->state = Cpu_Break; return Instr_Break; } return fetch(pcpu); }
Perhaps I'd better not show you what the compiler turns this code into (children might be reading!): even at high optimization levels, you can't look at it without crying. Many people now say that compilers are much better at optimization than humans. But I suspect that's because while the average compiler was getting smarter, the human it was competing with was doing who knows what. Needless to say, these days some virtual machine developers even allow themselves to have a family!
So, we will follow the path laid out by Atakua: using assembler macros will replace inlining for us for the purpose of code embedding. For quick visual recognition, I will name them in all caps.
.macro FETCH_DECODE FETCH_CHECKED DECODE .endm
These two, FETCH_CHECKED and DECODE, always go together.
.macro FETCH_CHECKED .if MAX_PROGRAM_SIZE_CHECK ... .endif FETCH .endm
The check for going beyond the 512 program cells is made switchable (using a compile-time variable) so that we can estimate how much it slows down execution (it hardly slows it down at all). If it triggers, the bytecode interpreter prints a message and exits, as in other error handling cases.
Now let's move on to the more important part: FETCH and DECODE. Their task is to get the opcode and its immediate operand, if the opcode accepts one. But using a whole conditional branch to analyze whether the opcode needs an immediate operand is wasteful. It's better to always fetch it, and if the opcode doesn't need it, that's not our problem. Thus, we can reduce it all to two lines:
.macro FETCH mov (prog_mem, pc, 4), opcode32 # prog_mem[pc] .endm .macro DECODE mov 4(prog_mem, pc, 4), immed32 # prog_mem[pc+1] .endm
You do remember that in GAS the source operand is on the left and the destination operand is on the right? Okay, I was just asking, just in case.
An experienced assembly programmer might notice that we could get rid of the base address prog_mem by adding it to pc at the start of the program. I fell into this trap at first too. As a result, the program becomes slightly slower. This is because in the Jump and Je service routines, which are responsible for jumps in the bytecode, it becomes necessary to multiply the immediate operand by 4 (the size of the virtual machine's word in bytes). Since the immediate operand of jumps can be a negative number (for backward jumps), the optimal way to do this is to use the SAR arithmetic shift. But even in this case, it's an extra instruction in a frequently executed routine that takes time. On my machine, this means, on average, a difference between 3.02 and 2.94 seconds for the entire program's execution. One could make such sacrifices if it were necessary to save a register for prog_mem, but there's no need: we have enough registers for now.
Another discarded idea is to try reading one 64-bit value instead of two 32-bit values and apply shifts and moves to get the required halves. But this takes more time than it saves - perhaps on machines with slower memory access this would have worked better.
Finally, let's move on to DISPATCH - the last instruction of each service routine:
.macro DISPATCH jmp *(routines, opcode64, 8) .endm
We are making a jump to an address located in an array of pointers. The address of the array is in routines, the array element number is in opcode64, and the address size is 8 bytes. Essentially, this means getting the value from routines+(opcode64*8) and jumping to that address. Perhaps these detailed explanations will be useful for those unfamiliar with GAS assembler.
An interesting fact about the life of opcode64: it is initialized in FETCH and used in DISPATCH. And until the next FETCH, any service routine can use it as a temporary register, just making sure that its upper half is filled with zeros before the next FETCH. Almost the same can be said about immed64 - especially for those routines that do not use an immediate value. Thus, we already have 3 free registers - with them, we can go all out! But, don't try to explain such a register usage strategy to the compiler...
Oh yes, we almost forgot about ADVANCE_PC:
.macro ADVANCE_PC cnt:req .if \cnt == 1 inc pc .else lea \cnt(pc), pc .endif .if (STEPLIMIT_CHECK || STEPCNT) # Аксакалы верят что если разнести инкремент и проверку, то # это позволит процессору выполнить все быстрее inc steps .endif .if STATE_RUNNING_CHECK test state, state # Cpu_Running(0) != state jne handle_state_not_running .endif .if STEPLIMIT_CHECK cmp steps, steplimit # steps >= steplimit jl handle_steplimit_reached .endif .endm
Since each service routine knows whether it has an immediate operand or not, I parameterized this macro to increment the Program Counter depending on the passed argument. In the virtual machine under study, there are no opcodes where the Program Counter needs to be shifted by more than 2, so using INC or LEA is optimal for all cases.
Ускорение петли обратной связи может привести к пороговым эффектам. Замедление петли обратной связи может привести к упущенным возможностям.
So, our virtual machine is a stack machine; service routines get values from the stack and place their results on the stack. For convenience, there is even a notation for stack diagrams that resembles a runic ornament:
A typical service routine in Atakua's implementation looks like this:
void sr_Swap(cpu_t *pcpu, decode_t *pdecoded) { uint32_t tmp1 = pop(pcpu); uint32_t tmp2 = pop(pcpu); BAIL_ON_ERROR(); push(pcpu, tmp1); push(pcpu, tmp2); ADVANCE_PC(); *pdecoded = fetch_decode(pcpu); DISPATCH(); }
Therefore, the first thing we'll need are the helper subroutines push() and pop() - they are inlined into almost all service routines. Their special feature is that they check for stack boundary violations:
static inline void push(cpu_t *pcpu, uint32_t v) { assert(pcpu); if (pcpu->sp >= STACK_CAPACITY-1) { printf("Stack overflow\n"); pcpu->state = Cpu_Break; return; } pcpu->stack[++pcpu->sp] = v; } static inline uint32_t pop(cpu_t *pcpu) { assert(pcpu); if (pcpu->sp < 0) { printf("Stack underflow\n"); pcpu->state = Cpu_Break; return 0; } return pcpu->stack[pcpu->sp--]; }
So we must do the same:
.macro PUSH_IMM reg .if STACK_CHECK cmp sp, stack_min jae handle_overflow .endif push \reg .endm .macro POP_IMM reg .if STACK_CHECK cmp sp, stack_max jb handle_underflow .endif pop \reg .endm
An experienced systems programmer will immediately notice here that some of these checks can be avoided: indeed, if a procedure takes two words from the stack and then puts two words on the stack, only one check is needed! Fortunately, it won't be necessary to write a complex macro to calculate a combined check, because a classic optimization from Forth language implementations awaits us: caching the top of the stack in registers!
To explain this, a picture is required:
I measured the performance without caching, with caching the top stack value, and with caching the top two values, and decided to stick with the last option (it showed the best results).
Take a look, the SWAP procedure doesn't touch the stack at all:
RTN Swap xchg top, subtop ADVANCE_PC 1 FETCH_DECODE DISPATCH
(RTN is a very simple macro that forms the beginning of the next procedure, adding an increment to the procedure call counter so that one can estimate which procedures are called more often - a small convenience that can be disabled with a compile-time variable):
.macro RTN name .global srv_\name .type srv_\name, @function srv_\name: .if DBGCNT incq cnt_\name(%rip) .endif .endm
You are probably wondering how many times each service routine is called during the execution of our algorithm? Here is the data:
Counters : cnt_Print : 9592 cnt_Je : 910487889 cnt_Mod : 455189149 cnt_Sub : 455298740 cnt_Over : 1820985370 cnt_Swap : 910387890 cnt_Dup : 0 cnt_Drop : 99998 cnt_Push : 100000 cnt_Nop : 0 cnt_Halt : 1 cnt_Break : 0 cnt_Inc : 455198741 cnt_Jump : 455198741
The last two lines strongly suggest that they can be automatically combined into a single super-instruction - they follow each other in the bytecode. And there are plenty of such places, for example, the sequence "OVER, OVER, SWAP" is practically a lab exercise in peephole optimization. I hope I've interested someone and soon we'll be able to read a third article on virtual machine optimization, with even more impressive results.
Of course, sometimes you have to pay for stack tricks. Simple procedures, like DROP, force values to be pushed through the cache in a chain (which is why more than two stack elements are usually not cached):
RTN Drop movq subtop, top # subtop -> top POP_IMM subtop # from stack -> subtop ADVANCE_PC 1 FETCH_DECODE DISPATCH
But on the other hand, we make more complex procedures touch the stack only once, or at most twice. Take a look at OVER, for example:
RTN Over xchg top, subtop PUSH_IMM top ADVANCE_PC 1 FETCH_DECODE DISPATCH
Here is its crude alternative, without using caching of the top stack elements (5 stack accesses):
RTN Over POP_IMM immed64 POP_IMM acc PUSH_IMM acc PUSH_IMM immed64 PUSH_IMM acc ADVANCE_PC 1 FETCH_DECODE DISPATCH
Yes, of course, it can be made more elegant using indirect addressing, but even so, it would be slower. My best version was this:
RTN Over movq 8(sp), acc PUSH_IMM acc ADVANCE_PC 1 FETCH_DECODE DISPATCH
In the same way (almost unconsciously), all the other procedures needed to execute the original Primes algorithm are implemented. I didn't implement anything beyond what was necessary:
Print
Je
Sub
Dup
Push
Nop
Halt
Break
Inc
Jump
One procedure deserves consideration - MOD:
RTN Mod # Так как мы для top выбрали RAX то не требуется # делать "mov top, %rax" для подготовки к делению test subtop, subtop je handle_divide_zero xor %rdx, %rdx # rdx = opcode64 div subtop # rdx:rax / operand -> rax, rdx movq %rdx, top POP_IMM subtop ADVANCE_PC 1 FETCH_DECODE DISPATCH
In it, we see that from the point of view of stack operations, it is as simple as DROP.
Один вводящий в заблуждение бенчмарк может за минуту достичь того, что невозможно получить за годы хорошей инженерной работы. (с) Dilbert.
Here are my results from profiling the program in gprof.
Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls Ts/call Ts/call name 31.23 0.86 0.86 srv_Swap 24.37 1.54 0.68 srv_Over 19.86 2.09 0.55 srv_Mod 16.25 2.54 0.45 srv_Je 3.61 2.64 0.10 srv_Sub 2.53 2.71 0.07 srv_Jump 1.08 2.77 0.03 srv_Inc
And these are the time measurement results from Atakua's original benchmark. Compared to the picture in his article, you can see that computers have become faster since 2015, but, of course, not as much as one would like. Therefore, people who understand how to optimize performance will always have something to do.
So, is an optimized bytecode interpreter for a virtual machine capable of outperforming binary translation? Or, as many novice compiler writers believe, is it impossible? Is JIT (or AOT) our last hope for performance? I think I have been able to answer this question.
Let's see what the community of compiling virtual machine enthusiasts has to say about this. If it exists, then in about 7-9 years, I hope to read another article..
The article is written, and I had a great time, now it's time to get to work! Thanks for your attention!
All the source code can be found in my fork of Atakua's repository.