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:
- 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.
- 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.
- 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 aftercmp
, I found performance increased considerably, but back fired for Return (]
in BF) instruction. That seems counter intuitive to put rare case aftercmp
, but it seems to works here. V-Tune indicates a reduction in branch misprediction rate too. 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.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]
movzx r10d, word ptr [rsi+4]
/movzx r11d, word ptr [rsi+4 + 2]
/add rsi, 4
puts theadd
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 withmovzx 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. \$\endgroup\$_TEXT2 SEGMENT ALIGN(64) 'CODE'
instead of just.code
\$\endgroup\$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... \$\endgroup\$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 thatmovzx r10d, r11w
isn't zero-latency (only byte->dword movzx is zero latency.) \$\endgroup\$global
on your code labels and declare them asextern "C" extern const char my_label[]
in C++ and do pointer subtraction, or create aglobal offsets
/offsets: dw 0, label1-base, label2-base, ...
array that the C++ can read asextern "C" const short offsets[]
, indexed by whatever you're using now for opcodes. \$\endgroup\$