This post is the third in a series about DoomBF, a project, the goal of which is to run Doom (1993) in the esoteric programming language Brainfuck.

View all posts in the series.

JIT

Last time I ended by saying that JIT is faster, and so to increase performance, I'll add it. The JIT framework I chose to go with is GNU Lightning, as bf-li uses it, and it seems quite fast. The execution just amounts to generating an abstract RISC-like program, and then executing it.

To make execution even faster, I decided to drop memory paging and debugger support when running with JIT. This means that each instruction can be translated quite easily. Here are all of them in pseudo-assembly:

case '+':
    mov  r0, [v1]
    addi r0, r0, n
    mov  [v1], r0

case '-':
    mov  r0, [v1]
    subi r0, r0, n
    mov  [v1], r0

case '>':
    addi v1, v1, n

case '<':
    subi v1, v1, n

case '[':
    mov  r0, [v1]
    goto <forward> if r0 == 0

    label <back>

case ']':
    mov  r0, [v1]
    goto <back>    if r0 != 0

    label <forward>

case '.':
    mov  r0, [v1]
    printf("%c", r0)

case ',':
    read(stdin, v1, 1)

I found out that making more complicated macros has diminishing returns, so I left it at recognizing move and reset loops.

case '^': ; move loop macro
    mov  r0, [v1]
    mov  r1, [v1+offset]
    muli r0, r0, val
    add  r0, r0, r1
    mov  [v1+offset], r0

case '0':
    mov  [v1], 0

With just this I have overtaken tritium.

Mandelbrot-extreme.b
tritium 5m28s
ibf     4m58s
bf-li   1m42s

Loading giant programs

Right now my interpreter reads the whole source file into memory, and then processes it by rolling the addition and moving instructions, recognizing macros, etc. This wastes a lot of memory for larger programs (the doom program ended up being 3.6TiB, which is a lot more than I have memory), and also prevents me from using a pipe to provide the program (the first step if to measure the file size, which fails on pipes).

It is not as simple as just reading the file byte-by-byte, as sometimes I need to check which character comes next, but also read it properly later; I can't use fseek() to go back, because it doesn't work on pipes. Instead I added a buffer that consists of characters I've read from the file, but didn't process yet (a.k.a ones I peeked), so when I want to read a character, I first check if there is something in the buffer, and only if it's empty go to the file.

This buffer also allows me to read more than one byte from the file at a time. This is more efficient, because syscalls take a long time, so reading many bytes at a time is much faster.

Bulk-processing rolled instructions

Programs generated by RISC-BF often contains a bunch of >s or < in a row, millions of them, so by optimizing the processing of these characters I can massively speed up loading. Right now I load 128KiB at a time, but then process them one-by-one. Since I know that in many cases there will be a ton of the same instruction in a row, I can specifically optimize for this case by using x86 AVX2 to compare 32 bytes at a time, instead of just one. I can probably also use AVX-512 to compare 64 bytes, instead of 32, but my CPU doesn't have AVX-512, and with just AVX2 I'm already able to read the program at about 3GiB/s. At that pace the full program would take just 18 minutes to load, which is not a lot, but it's awful for debugging, which is why I need to compress the program.

Compression

It was discussed briefly in the previous article. To recap, any character can have a hexadecimal number withing curly brackets after it, and it will be repeated that many times. I designed this format to be as simple as possible, and also kind-of independent of brainfuck. This means that I can create a separate utility: bpk, that decompresses the program into stdout, and pipe that into my interpreter. This works, but it's much more efficient to process the compression withing the interpreter itself.

I don't actually have to decompress the program to read it. My internal representation already has instructions for repeated +, -, < and >, so I can just convert the compressed instructions into them directly, skipping the decompression. I also decided to throw an error when somebody tries to repeat any characters other than these 4, as it would be too compilcated to handle for something that's basically never used.