Main loop in assembly for a Brainfuck interpreter

Question

I have written 2 Brainfuck interpreters, one in C++, then another in C++ with Assembly inner loop. My interpreter code can be found here (C++/ASM, requires MSVC and MASM) and here (C++).

Both are benchmarked using the mandelbrot BF program, run 20 times. After trying for a while, I managed to make the Asm version about 10% faster than the C++ version, but I'm wondering if it can be made even faster. The main bottlenecks appears to be branch mispredictions and uOps cache. The benchmark ran on SkylakeX CPU.

The inner loop looks like this:

interpret proc C
.code
 push rbx ; these are callee saved ?
 push rsi
 push rdi
 push rbp
 push r12
 push r13
 push r14
 push r15
 sub rsp, 32 ; shadow space?
 xor rsi, rsi ; "program counter", which instruction we are at
 mov rdi, r8 ; "memory pointer", where we are pointing to in the interpreter memory
 xor r14, r14 ; store the value of current mem cell, which of course starts at 0
 lea r15, [jumptable] ; load the address of the table
 mov r13, rcx ; base address of instruction array
lbl_interp_loop: ; beginning of new interpreter cycle
 movzx r10, word ptr [r13 + rsi*4]
 movzx r11, word ptr [r13 + rsi*4 + 2]
 inc rsi ; advance to the next instruction
 jmp qword ptr [r15 + r10 * 8]
ALIGN 4
lbl_Loop:
 cmp byte ptr [rdi], 0
 jne lbl_set_loop_ip
 add rsi, r11
lbl_set_loop_ip:
 movzx r10, word ptr [r13 + rsi*4]
 movzx r11, word ptr [r13 + rsi*4 + 2]
 inc rsi ; advance to the next instruction
 jmp qword ptr [r15 + r10 * 8]
ALIGN 4
lbl_Return:
 cmp byte ptr [rdi], 0
 jne lbl_set_return_ip
 movzx r10, word ptr [r13 + rsi*4]
 movzx r11, word ptr [r13 + rsi*4 + 2]
 inc rsi ; advance to the next instruction
 jmp qword ptr [r15 + r10 * 8]
lbl_set_return_ip:
 sub rsi, r11
 movzx r10, word ptr [r13 + rsi*4]
 movzx r11, word ptr [r13 + rsi*4 + 2]
 inc rsi ; advance to the next instruction
 jmp qword ptr [r15 + r10 * 8]
ALIGN 4
lbl_Right:
 add rdi, r11
 movzx r10, word ptr [r13 + rsi*4]
 movzx r11, word ptr [r13 + rsi*4 + 2]
 inc rsi ; advance to the next instruction
 jmp qword ptr [r15 + r10 * 8]
ALIGN 4
lbl_Left:
 sub rdi, r11
 movzx r10, word ptr [r13 + rsi*4]
 movzx r11, word ptr [r13 + rsi*4 + 2]
 inc rsi ; advance to the next instruction
 jmp qword ptr [r15 + r10 * 8]
ALIGN 4
lbl_Add:
 add byte ptr [rdi], r11b
 movzx r10, word ptr [r13 + rsi*4]
 movzx r11, word ptr [r13 + rsi*4 + 2]
 inc rsi ; advance to the next instruction
 jmp qword ptr [r15 + r10 * 8]
ALIGN 4
lbl_Minus:
 sub byte ptr [rdi], r11b
 movzx r10, word ptr [r13 + rsi*4]
 movzx r11, word ptr [r13 + rsi*4 + 2]
 inc rsi ; advance to the next instruction
 jmp qword ptr [r15 + r10 * 8]
lbl_Print:
 movzx rcx, byte ptr [rdi]
 call printChar
 jmp lbl_interp_loop
lbl_Read:
 jmp lbl_interp_loop
lbl_Invalid:
 jmp lbl_interp_loop
jumptable: ; MASM cannot emit relative address in .data, so must put it in .code this way (agner)
 dq lbl_Loop
 dq lbl_Return
 dq lbl_Right
 dq lbl_Left
 dq lbl_Add
 dq lbl_Minus
 dq lbl_Print
 dq lbl_Read
 dq lbl_Invalid
 dq lbl_End
lbl_End:
 add rsp, 32
 pop r15
 pop r14
 pop r13
 pop r12
 pop rbp
 pop rdi
 pop rsi
 pop rbx
 ret
interpret endp
end

Here is the report from V-Tune:

V-Tune perf

1. Before this inner loop begins, the interpreter does a couple of simple transformation on the BF source, turning it into instructions that consist of a 2 byte opcode and 2 byte operand. Repeated instructions are collapsed into 1 instructions and the number of repeats is stored in the operand. Loop/Repeat instructions contain the index of the destination instruction it jumps to.
2. Because of (1), there is no advantage of storing the value of current cell in register. In fact, when I tried to do that, performance got slightly worse. That is because when the interpreter encounters Left/Right instructions, it must save the current cell to memory and load the next cell, probably causing a data dependency on the register.
3. The reason why code for Loop and Return instructions are different, is because after changing code for Loop ([ in BF) to have rare case right after cmp, I found performance increased considerably, but back fired for Return (] in BF) instruction. That seems counter intuitive to put rare case after cmp, but it seems to works here. V-Tune indicates a reduction in branch misprediction rate too.

4. Another strange example is right after label lbl_set_return_ip:, where I originally wrote:

   mov rax, r11
   sub rsi, rax
   

   but then found out that rewriting it as below noticably improved performance:

   sub rsi, r11
   

   Which is strange because I expected the mov to be pretty much free through register renaming.

5. The same data dependency problem leads to the fact that I relied on array indexing instead of increasing the pointer. This code

   movzx r10, word ptr [r13 + rsi*4]
   movzx r11, word ptr [r13 + rsi*4 + 2]
   inc rsi ; advance to the next instruction
   

   is found to be faster than

   add rsi, 4 ; rsi contains the address of current instruction
   movzx r10, word ptr [rsi]
   movzx r11, word ptr [rsi + 2]
   

• Peter Cordes: Your pointer-increment sequence has the increment before the loads? movzx r10d, word ptr [rsi+4] / movzx r11d, word ptr [rsi+4 + 2] / add rsi, 4 puts the add after the loads, instead of before, so it's not adding to the load/use latency. (And BTW, compiling to 2-byte opcode / operand bytecode sounds reasonable. Loading with movzx word ptr is good. Writing to a 64-bit dest register is redundant vs. letting implicit zero extension work, but it shouldn't matter. Code-size probably doesn't really matter here, so avoiding REX prefixes normally won't help.
• David Wohlferd: Masm does support larger alignment sizes, but you can't use a larger alignment size inside a function than you declare for the segment that contains it. Try something like _TEXT2 SEGMENT ALIGN(64) 'CODE' instead of just .code
• Ped7g: Can't you make the second argument only 16b signed value, so you can then collapse the right/left into single instruction? Also add/minus are by their nature single instruction, just adjust the byte operand for minus. The loop/return are then almost identical, just the test condition is different, hmm...
• Peter Cordes: @Ped7g: Not sure that's a good idea, but implementation-wise, movsx rcx, [rsi] / movzx eax, cl / sar rcx,8 has no extra latency for the opcode, instead of 2c extra latency. And a shorter dep chain for the operand, too. This technique would work with the current 16:16, except that movzx r10d, r11w isn't zero-latency (only byte->dword movzx is zero latency.)
• Peter Cordes: @Ethan: data-cache pressure is probably negligible, just use 16:16 if you need large operands for jump displacements. Variable-length encoding would probably hurt. To expose the offsets to C++, either use global on your code labels and declare them as extern "C" extern const char my_label[] in C++ and do pointer subtraction, or create a global offsets / offsets: dw 0, label1-base, label2-base, ... array that the C++ can read as extern "C" const short offsets[], indexed by whatever you're using now for opcodes.

Answer 1

I'd expect that most of the performance problem comes from the indirect branch (jmp qword ptr [r15 + r10 * 8]) - it's relatively unpredictable and should cause lots of branch mispredictions, bad speculations and pipeline stalls.

There's only really 2 ways to deal with this:

1) Amortise the cost. For example, if you packed 4 instructions into r10 and had a significantly larger jump table you could reduce the number of indirect branches the CPU has to do to 25% (and therefore reduce the branch mispredictions, etc). Note that BF only really has 8 instructions so you only need 3-bit opcodes, so packing 4 together could cost 12 bits and give you a 4096-entry jump table.

2) Use JIT techniques. This would probably be an order of magnitude faster, but would involve a significant "redesign and rewrite". [ADDED] For one possibility, instead of pre-compiling the BF into a "16-bit opcode + 16-bit operand" form, you could precompile BF instructions into a series of call ... 80x86 instructions and then execute the resulting series of calls. This wouldn't be "full JIT" (wouldn't be generating native code for the actual work) but it would be using "JIT techniques" (to generate code to optimise the whole "fetch and decode" part of the interpreter).

• Ethan: WRT point 1, it sounds like some code generation would be required? I don't quite understand how to armotize it that way. OTOH I'm afraid that a 4096 entry jump table is quite large, and the generated code to accompany it would be way too large, missing L1i cache every 4 BF instructions. Finally, with 3 bits, I can encode 8 opcodes, but if I would like to have additional "meta" opcodes that encode multiple BF instructions, there will be no space left. WRT to point 2, I will consider JIT at a later time, but this experiment is about pushing the basic interpreter to its limit.
• Peter Cordes: @Ethan: 1) is a much more aggressive version of my fusion suggestion from this comment. And yeah, I'd be worried about uop-cache misses and BTB misses (more different branch targets = harder to predict). L1i misses not so much. But a given BF program wouldn't always use all of those 4096 entries in a hot loop, so not all of them would have to stay hot in the uop cache. And yeah you'd probably want to macro it.
• Brendan: @Ethan: You would need to do some code generation; but you're already doing some code generation (e.g. converting to "2 byte opcode + 2 byte operand"). If you want you could think of it as a single 12-bit meta opcode (or a pair of 6-bit meta opcodes, or four separate 3-bit opcodes) - there's no practical difference.
• BeeOnRope: Yeah I'd draw the line in the sand in the same way as @PeterCordes. There's definitely a spectrum of techniques from totally vanilla interpretation to full-on JIT, but to me it crosses the JIT line when it executes code that was written at runtime by the process. I.e., exactly when it needs to use mmap or whatever to change the protections to W+X as mentioned. For example, executing a generated sequences of call instructions, one per instruction is JIT, but executing an existing sequence of unrolled call instructions with memory-source targets that you generated is not...
• BeeOnRope: ... even though the execution pattern and and performance characteristics are likely to be very similar!