Preface

There are two classic designs for virtual machines: stack and register. In both, sequences of operations are encoded into instructions that act on digital values and, in this classification, the type of machine is decided by both how those values are identified and how the results of one operation are mapped onto the input of another.

The stack machine operates primarily on values situated at its top. An operation consumes its inputs by popping and produces outputs by pushing them atop. Unary operations consume one value and replace one, binary operations consume two and so on. In exchange for locating values implicitly, it often needs additional instructions to juggle the out-of-order values before calculation. The register machine instead defines a set of bit-pattern-named locations called registers and uses those names in instructions that use registers as either input or output.

Machine Operation

The operation of these machines occurs in some variation of the following stages:

Instructions are fetched to be read by the machine before execution, various arguments are decoded from within it, control is dispatched to the handler for the identified operation, input and output values for the operation are accessed (before, during or after execution), the named operation is executed, then an instruction pointer is advanced to the next location in code to execute, and the loop begins again.

In the stack machine, fetch is comparatively cheap. Because there are no registers to name, the instruction can be smaller, which makes the whole code smaller, which allows more of it to be performantly fetched. There’s comparatively less information to decode from a smaller instruction, so that’s usually cheaper, too. Stack instructions are often easier to reason about and so easier to generate performant code for. The register machine, with its larger instruction size, trades some of that advantage in favor of dispatch. It can represent in one instruction what often takes several in a stack machine, saving the cost of additional dispatches and additional fetches and so on.

Experiment

There’s a wisdom among internet commenters that register machines are naturally favored by modern CPUs and that, all else equal, they ought to be expected to perform better. A not-insignificant amount of authority on this question seem to stem from two related papers, one from 2003 and another from 2008:

Generally, we would expect that the increase in fetches is likely to be large, since most VM instructions need one or two extra immediate operands to specify register locations. The cost of each of these fetches is likely to be low, however, since each usually corresponds to just an additional load instruction.

Ertl and Gregg³ found that virtual machine interpreters contain very large numbers of indirect branches (up to 13% of all executed real machine instructions). Furthermore, these branches are highly (60%-97%) unpredictable on current desktop and workstation processors. The cost of each indirect branch misprediction is high, because it requires that the entire pipeline be drained, consuming 6–20 cycles, depending on the length of the pipeline. Ertl and Gregg³ found that more than half of the execution time of many efficient interpreters is spent on indirect branch mispredictions. Almost anything that reduces the number of dispatches has the potential to significantly improve performance.

Experimental results show that a register format reduces the number of executed instructions by 34.88%, while increasing the number of bytecode loads by an average of 44.81%. Overall, this corresponds to an increase of 2.32 loads for each dispatch removed.

So the claim is that virtual fetches map to physical fetches, virtual dispatch maps to physical dispatch and for this Pentium 4 – which, in addition to hosting some experimentation with deeper pipelining, is also old enough to vote – the branch misprediction cost is higher than the corresponding additional memory load cost. But processors have changed. At least, caches are larger and branch predictors should be better. It’s notable that commercially-produced general-purpose hardware itself (e.g. x86, ARM, accelerators like GPUs and TPUs) is overwhelmingly register in kind. (Although I’ll leave the comparison to the hardware folks.)

Can we see a preference in well-known language projects? Not neatly. The zeitgeist, to my eyes, is split and JIT techniques are widespread, which allow for hybrid approaches that don’t fit the binary well:

• V8 is register but JIT-compile,
• JVM, CLR and PyPy are stack but JIT-compile,
• CRuby is stack but has an optional component YJIT,
• PHP’s Zend is register but has an optional component opcache.jit,
• mruby is register,
• WasmKit translates abstract stack WebAssembly to register (with the rest seemingly native),
• and Perl doesn’t use a compact representation

…which leaves CPython (and several Forths) as the only notable, truly-stack standouts. But this, too, might be affinity rather than engineering: as one StackOverflow commenter observes, the people who are accustomed to writing register assembly might prefer to write register assembly-likes.

So I ask: does that natural advantage still exist? Can we measure it?

I propose a set of machines that I think represent this dimension:

• S8, an 8-bit stack machine,
• S16, a 16-bit stack machine,
• R16, a 16-bit register machine, and
• R32, a 32-bit register machine.

The numbers indicate the fixed-size of the instruction it operates on and the prefix indicates how the operand bits (if any) are decoded. Instruction size isn’t exactly the distinction I made before but a relationship is pretty obvious: with fewer bits per instruction, there’s more implicit behavior and a stronger affinity for the stack. We can ask about instruction size, too. R32 most resembles today’s physical machines and the assembly that most are accustomed to reading. S16 resembles CPython. R16 is an odd variant that I haven’t seen before but contrasts type. And S8 has extreme density but its liberal alignment, I think, makes it a natural choice.

I sic AI at an implementation, a compiler for a shared C-like language and an optimizer for each. I then task them with a set of defined workloads. I measure code size, wall time, branch misprediction, etc. and – hopefully under conditions similar to the papers' above – look for similar evidence. My approach is not as rigorous, though. I try to be fair to the competitors but, e.g. pursue an optimization for one if I'm curious about the effect.

I also learn more of the limits of AI tools. (And maybe have fun doing it!)

Machine Design

The common design is spartan. All values are unsigned 32-bit values, program memory is fixed-sized and preallocated, I/O is governed by explicit load and write operations, with initial and final binary translated through a Javascript wrapper to and from text files. All dispatch is done by switch table.

Operations were first populated by whatever inspiration AI draws upon, then tinkered a bit to my taste, with the remaining unclaimed filled by “fusion” operations that combine the effects of multiple.

S8, having no arguments, reserves the lower half of its table just for summoning immediate values. It uses specialized accumulation operations to cobble together 7-bit sequences into larger values.

enum s8_op : uint8_t {
    S8_OP_NOP = 128,
    S8_OP_C2,        // ( a b -- (a << 7) | b )
    S8_OP_C3,        // ( a b c -- (a << 14) | (b << 7) | c )
    S8_OP_C4,        // ( a b c d -- (a << 21) | (b << 14) | (c << 7) | d )
    S8_OP_C5,        /* ( a b c d e -- (a << 28) | (b << 21) | (c << 14)
                                         | (d << 7) | e ) */
/* … */

0000019b  03  LIT 3        ; constant 7628140 inline via 3 81 74 108 C4
0000019c  51  LIT 81
0000019d  4a  LIT 74
0000019e  6c  LIT 108
0000019f  83  C4

It uses a standard Forth vocabulary for stack manipulation and both arithmetic and logic are as expected.

S8_OP_DUP,       // ( a -- a a )
S8_OP_DROP,      // ( a -- )
S8_OP_SWAP,      // ( a b -- b a )
S8_OP_OVER,      // ( a b -- a b a )
S8_OP_DUP2,      // ( a b -- a b a b ); cell pairs
S8_OP_DROP2,     // ( a b -- )
S8_OP_SWAP2,     // ( a b c d -- c d a b )
S8_OP_OVER2,     // ( a b c d -- a b c d a b )
/* ... */
S8_OP_NEG,       // ( a -- -a )
S8_OP_ADD,       // ( a b -- a + b )
/* ... */
S8_OP_AND,       // ( a b -- a & b )
S8_OP_OR,        // ( a b -- a | b )
/* ... */
S8_OP_LT,        // ( a b -- a < b )
S8_OP_LTE,       // ( a b -- a <= b )
/* ... */

AI made S16 a half-hearted adaptation of S8. Lots of operations waste their operand byte. The initial version had immediate construction similar to S8, except for 14-bit chunks but it never really wanted to generate those, preferring instead its own duplicate (and inferior) APPEND8.

This was a problem because that required a NEG at every backwards jump, so I thought to overload NEG's operand with an immediate to add. It ignored this in generation. I was able to get it to generate signed values in a full width-representation LIT24 but it still didn't want to use it for those jumps. So we settled on a hacky CALLNEG.

enum s16_op : uint8_t {

    /* … */
   S16_OP_NEG,      // ( a -- 0u - (a + u8) )
    /* … */
   S16_OP_APPEND8,  // ( a -- (a << 8) | u8 )
    /* … */
   S16_OP_LIT24,   // push (u8 << 16) | following native uint16 word
   S16_OP_CALLNEG, // ( magnitude -- ); call by 0u - magnitude words
}

A notable addition is immediate versions of arithmetic operations. My gut tells me that using displacement as immediate in the branching instructions is not ideal. I didn’t study this, though.

S16_OP_ADDI,     // ( a -- a+u8 )
S16_OP_SUBI,     // ( a -- a-u8 )
S16_OP_MULI,     // ( a -- a*u8 )
S16_OP_DIVI,     // ( a -- a/u8 )
/* … */
S16_OP_CALLI,    // ( -- ); s8 displacement; save next PC
S16_OP_JNZI,     // ( condition -- ); s8 displacement; jump if nonzero
S16_OP_JZI,      // ( condition -- ); s8 displacement; jump if zero
S16_OP_BEQI,     // ( a b -- ); s8 displacement; jump if a == b
S16_OP_BNEI,     // ( a b -- ); s8 displacement; jump if a != b

In general, AI gave R16 a lot of grief:

• it modeled decoding with nested switch statements, which observably punished in performance,
• when the table was flattened, it left arbitrary gaps in the opcode enums, hindering jump table construction,
• it cautiously memcpy’d the uint16_t instruction in the dispatch loop for fear of violating (self-imposed) alignment rules, into which musl’s fortify-headers placed an overlap check,
• it underbudgeted offset bits and, to compensate, generated a great many trampolines, and,
• additionally, failed to track those trampolines in the optimizer and duplicated all of them per-CALL.

This machine reserves seven bits for the operation and nine bits to name three operands among eight registers.

enum r16_op : uint8_t {
    // 0x00..0x12: three-register arithmetic and comparisons; op7 d3 a3 b3.
    R16_OP_ADD = 0,  // d:3 a:3 b:3; R[d] = R[a] + R[b]
    R16_OP_SUB,      // d:3 a:3 b:3; R[d] = R[a] - R[b]
    R16_OP_MUL,      // d:3 a:3 b:3; R[d] = R[a] * R[b]
    R16_OP_DIV,      // d:3 a:3 b:3; R[d] = R[a] / R[b]; zero divisor traps
    /* … */
}

The register designs allocate some fixed-sized frame per CALL and provide three different operations for access into the same array: one for register-to-register (MOVE), one for the rest of the frame (LOAD_FRAME/STORE_FRAME) and a third for preparing values just beyond it (ARG).

// 0x64..0x6b: each op5 prefix covers four selectors; op5 register3 slot8.
 R16_OP_LOAD_FRAME = 100,  // d:3 slot:8; load one value, R[d] = F[slot]
 R16_OP_STORE_FRAME = 104, // s:3 slot:8; store one value, F[slot] = R[s]

 // 0x6c..0x6f is an op5 prefix; arguments occupy the next value frame.
 R16_OP_ARG = 108, // s:3 slot:8; values[base + frame_size + slot] = R[s]

 // 0x70 is op7 u9; sizes outside 8..256 are invalid encodings.
 R16_OP_FRAME = 112, // u9:9; set frame_size after checking value capacity

R32 has enough addressable range that it can satisfy reasonable argument list sizes and so could plausibly reject functions with too many (as I think Lua does). R16 does not and so must handle this problem more carefully. I'm pretty sure that this frame concept is undeveloped and deficient. I think a clearer convention would’ve been to treat the in-frame and out-of-frame values alike, using just one index.

I was curious to see if these SKIPs would be effective. I felt like this would pack well, paired with a long-immediate jump. I saw, though, that none were generated. I assumed this was the most boring part for him and didn’t push further.

// 0x1b..0x20: comparison skips; op7 a3 b3 unused3.
  R16_OP_SKIP_LT,      // a:3 b:3 unused:3; skip if !(R[a] < R[b])
  R16_OP_SKIP_LTE,     // a:3 b:3 unused:3; skip if !(R[a] <= R[b])
  R16_OP_SKIP_GT,      // a:3 b:3 unused:3; skip if !(R[a] > R[b])
  R16_OP_SKIP_GTE,     // a:3 b:3 unused:3; skip if !(R[a] >= R[b])
  R16_OP_SKIP_EQ,      // a:3 b:3 unused:3; skip if R[a] != R[b]
  R16_OP_SKIP_NEQ,     // a:3 b:3 unused:3; skip if R[a] == R[b]

It also emitted this neat GNU extension case-range syntax, which I’d never seen before:

case R16_OP_LOAD_FRAME ... R16_OP_LOAD_FRAME + 3: {
     const uint32_t slot = word & 255u;
     if ( slot >= size ) TRAP( VM_VALUE_BOUNDS );
     registers[ ( word >> 8 ) & 7u ] = registers[ slot ];
     break;
 }

The last machine, R32, has eight bits of op and sixteen registers to make twelve bits in order to name three operands. It doesn’t add anything remarkable but we should expect that its wider addressing should give it a significant advantage over R16 by way of reduced spillage.

Compilers and Tooling

const END = 0xffffffff;

fn main() {
    let sum = 0;
    let first = read();
    while (first != END) {
        let second = read(); if (second == END) { break; }
        let third  = read(); if (third == END) { break; }
        let fourth = read(); if (fourth == END) { break; }
        let value = first | (second << 8) | (third << 16) | (fourth << 24);
        sum = sum + value;
        first = read();
    }
    write(sum);
    write(sum >> 8);
    write(sum >> 16);
    write(sum >> 24);
}

A common frontend is used to parse the common language, check identifiers and function calls, assign identities to local variables, and evaluate constant expressions while respecting the abstract arithmetic. Results are lowered into separate stack and register intermediate representations and passed to corresponding pipelines. Both types enjoy constant folding, arithmetic simplification, constant and copy propagation, and limited inlining. Register allocation uses a colored interference-graph with no SSA, live-range splitting or eviction. A final peephole pass substitutes fusion operations. Memory access and tail-calls remain unoptimized.

Here, the effects of compilation techniques were the most difficult for me to interrogate honestly. I was able to identify obviously-deficient bytecode sequences and changes that disproportionately punished only one machine but not much more.

As expected, AI shined at the tedious bits of project setup. I was impressed with the neat style it produced in the Makefile. It produced ad-hoc generators and solvers and verifiers, instrumented the VM binary with separate timing and instruction-counting runs and hooked both up to a Javascript runner that output very nice HTML dashboards.

Workloads

The workloads were chosen to exaggerate the effects of different features of the compilers and runtime:

• array-sum is a predictable stream-processing loop,
• merge-sort introduces recursion and dependent-reads,
• maze pushes dependent-read further into a graph-traversal problem,
• pbkdf2 introduces register pressure,
• ratsnest is adversarially-large call graph meant to induce instruction cache and procedure-call pressure, and
• interpreter is a broad load with a mix of operations.

The loads chosen were medium in size:

• array-sum sums 4MiB,
• merge-sort sorts 1MiB,
• maze is sized 513x511,
• ratsnest calls a tree of 2,047 with depth ten 32 times and
• PBKDF2 iterates 256 times.

In my humble opinion, AI did not have a good intuition about what would make a good test. Pressing it yielded worse and worse candidates.

Methodology

Timing runs are warmed, split into three trials of 10 executions each and measured with clock_gettime() and CLOCK_MONOTONIC_RAW. Allocation and verification are excluded from timings and memory isn’t cleared between runs. Execution is pinned to a core and, although thermal readings don’t swing anywhere near throttling limits, a five-second pause is introduced between trials.

Execution steps and branch misprediction are produced in separate suites.

Results

We can see the outline of the expected direct relationship between instruction size and program size but poor stack compilation often leaves R16 an outlier and loses S8 to R16 in merge-sort. Here, S8 takes 15 bytes to encode what R16 accomplishes in eight:

  LIT 64
  DUPMUL       ; 64² = 4096, the VALUES base
  PICK3        ; copy left
  LIT 2
  SHLADD       ; base + (left << 2)
  LOAD32
  LIT 4
  PUT          ; save a

  LIT 64
  DUPMUL       ; reconstruct VALUES
  PICK2        ; copy right
  LIT 2
  SHLADD
  LOAD32
  PUT3         ; save b

  LI r4, 16
  APPEND8 r4, 0             ; r4 = 4096
  LOAD32_INDEX r5, r4, r2   ; a = load32(base + left*4)
  LOAD32_INDEX r4, r4, r1   ; b = load32(base + right*4)

The relationship between instruction size and count of VM steps is clearer, where hot loops aggressively multiply those savings.

The broad thesis on performance by execution time mostly holds, although it's now R16 that's misbehaving.

I would've expected register pressure and subsequent spills to explain the difference but a combination of expensive offset calculation and higher total CALL volume seem likelier.

This is also borne out in branch mispredictions, where S16's maze and R16's pbkdf2 runs stand out. The latter indicates register spill but I'm lacking for explanation for the former.

Maybe the specific fusions chosen skew toward predictable operation sequences.

Conclusion and Further Work

My first and most obvious deficiency in experimentation is a lack of control. There remain significant differences in the machines explained by my specific interrogation and token budget. Some fusions look like cheating. A more thorough investigation would look to unify the machines to compare.

Another problem, too, is that the chosen workloads – while having some representation in execution pattern – likely don't represent the memory access of most real-world ones. We would want to choose larger and more exotic structures to examine.

All told, though, every expectation more-or-less held throughout all variations. A reasonable conclusion might be that while – yes, performance in any individual situation will depend on those individual circumstances – the naive implementer should more often find themselves in more fortunate ones with the register approach. To qualify further, other decisions – like computed-goto/threaded dispatch, host-register allocation, bounds and correctness checks, more complex memory models – all could easily eclipse the differences in machine type alone.

One might also JIT.

My experience with AI reinforces my belief that it still lacks taste and so is still poorly-suited to design work.

And one lesson I learned here is the value in organizing performance data. I knew to keep a journal so I could later explain the work but the very-many variations with different suites with different settings, etc. were not well-suited to bespoke text files. If I were to continue, I'd look into storing and annotating runs in SQLite.