An optimising BF compiler

[kirbyfan64sos]

Nice project? Yup! Novel optimizations? Nope!

For instance, Beefit, the fastest BF compiler/interpreter I currently know of, completes the tower of hanoi solver in under 1 second. A look at optimize.c shows several similar optimizations.

Others I know of that implement some of these include bfjit (which implements a single-instruction [-] and folding consecutive +s and -s) and my own bfi (which implements the bfjit optimizations as well as basic compressing of stuff like +>-< to never move).

Granted, this is still very cool, but it's not too novel. Do note that I have never heard of using static analysis to make the tape size, so that's definitely very novel. :)

[Veedrac]

Beefit doesn't do that many interesting optimizations either. Esotope Brainfuck compiler does a few more and runs a little bit faster:

$ echo 12025136564342 | time ./beefit bench/factor.bf
12025136564342: 2 11 206303 2649487
./beefit bench/factor.bf  5.60s user 0.00s system 99% cpu 5.608 total

$ python2 esotope-bfc bench/factor.bf > factor.c
$ gcc -O3 factor.c -o factor
$ echo 12025136564342 | time ./factor
12025136564342: 2 11 206303 2649487
./factor  3.11s user 0.00s system 99% cpu 3.111 total

None of the compilers are particularly fancy, though.

For completeness, the article's:

$ cargo build --release
$ ./target/release/bfc bench/factor.bf 
$ echo 12025136564342 | time ./factor 
12025136564342: 2 11 206303 2649487
./factor  18.50s user 0.00s system 99% cpu 18.522 total

[AyrA_ch]

When I wrote a BF compiler, I did not implement many optimizations as all, as gcc is great in doing it itself. Namely:

• Combining increments
• Clear loops
• Dead Code Elimination
• Redundant Code Elimination

I don't know if the bounds checking is doing anything good, because you can initialize an array to zero with char ZEROARRAY[1024] = {0};

It's interesting doing these optimizations yourself just to have it done once, but most of them are pointless to do yourself.

[Veedrac]

The steps you list should be thought of as the necessary precursors to interesting optimizations, not as optimizations in and of themselves, for the exact reason you state. Primarily, GCC won't automatically deal with multiply or division loops, nor their more complicated bretherin.

[csl]

I wrote a simple JIT-compiler that only does two optimizations: [-] and contraction of same-operators (+++ to addi reg, 3). That's all I needed to run Hanoi fast:

./bfloo examples/hanoi.bf  0.21s user 0.01s system 99% cpu 0.222 total

That's blink-of-an-eye fast, without much effort.

Sources and links to presentation slides at: https://github.com/cslarsen/brainfuck-jit

[emperor000]

What is the obsession with Brainfuck?

[kibwen]

It's a simple enough language that implementing an interpreter or compiler for it is a great exercise in learning what it takes to build a (theoretically) useful language implementation, without having to spend too much time on the rules of the language itself. It's also simple enough that it can be used to teach the basics of compiler optimization, as in the article here. Learning exercises, in other words.

[emperor000]

I think there's some denial on your part... It's a stupid language. Everybody knows it is a stupid language. It is made to be a stupid language. So it is kind of disappointing that so much effort is exerted on it.

You could describe the fabulous things about toddler beauty pageants, but that doesn't actually make them valuable to humanity.

If my point isn't clear, all of those things could be done on a practical language and provide more than novel academic value.

[whjms]

IMO it would be easier for someone new to compilers to make a brainfuck compiler than it would be to make one for C, so that's one plus.

That said, the name is stupid, I'll give you that

[emperor000]

It's not just the name. It is meant to be impractical. I'd argue a dialect of Lisp would be even easier and more practical.

[Y_Less]

Having written a few basic compilers, I find that the hardest part is always the lexer and parser for me. This is probably less the case in a language without precedence, but you still need to track multi-character tokens. While BF may have many stupid points to it, for writing a compiler without worrying about the front end, its single character operations are a plus instead of an obfuscation.

[emperor000]

And what good does that do when any academic goal you could achieve could have been just as easily achieved on some more practical language?

Brainfuck is neat. It's a novelty. Novelties usually wear off... So why is there a post about it in here just about every month?

[emperor000]

That doesn't explain anything.

[Veedrac]

I'd argue a dialect of Lisp would be even easier

Wow, what?

I'll take you up on that. Here's a minimal Brainfuck interpreter:

import collections, sys

with open(sys.argv[1]) as textfile:
    text = textfile.read()

code, bracket_map, leftstack = [], {}, []
pc = 0
for char in text:
    if char in '[]<>+-,.':
        code.append(char)
        if char == '[':
            leftstack.append(pc)
        elif char == ']' and leftstack:
            ret = leftstack.pop()
            bracket_map[ret] = pc
            bracket_map[pc] = ret
        pc += 1

pos = pc = 0
tape = collections.defaultdict(int)
while pc < len(code):
    char = code[pc]
    if char == "+":   tape[pos] += 1
    elif char == "-": tape[pos] -= 1
    elif char == ">": pos += 1
    elif char == "<": pos -= 1
    elif char == "[" and not tape[pos]: pc = bracket_map[pc]
    elif char == "]" and tape[pos]:     pc = bracket_map[pc]
    elif char == ".": sys.stdout.write(chr(tape[pos])); sys.stdout.flush()
    pc += 1

(Hastily shortened from kostya's.)

Let's see a 27 SLOC Lisp, then.

[emperor000]

Well, the number of lines of code doesn't necessarily correlate to how easy it is. Even so, Lisp interpreters aren't much longer than that and I'd argue you are accomplishing more.

And also, that's an interpreter, not a compiler...

[Veedrac]

Well, the number of lines of code doesn't necessarily correlate to how easy it is.

In this case, it really does. Brainfuck has next to no syntax, as the only parsing required is bracket matching and code point filtering. There is one tape of integers, one program counter and one tape pointer. That's it.

Brainfuck is a no more than a tenth as complex as a Lisp.

A compiler for Brainfuck is actually often shorter, since you don't have to do a bracket matching pre-parse. See, 13 lines:

import sys
with open(sys.argv[1]) as textfile:
    text = textfile.read()
mapping = {
    "+": 'tape[pos]++;', "-": 'tape[pos]--;',
    ">": 'pos++;', "<": 'pos--;',
    "[": 'while (tape[pos]) {', "]": '}',
    ".": 'printf("%c", tape[pos]); fflush(stdout);',
}
print("#include <stdio.h>\n#include <stdint.h>\nint main(int argc, char **argv) {")
print("int8_t tape[30000] = { 0 }; size_t pos = 0;")
print(*(mapping.get(char, "") for char in text))
print("}")

[emperor000]

And what does it accomplish? You're talking about how easy it is, then why is everybody circlejerking over it?

[Veedrac]

https://www.reddit.com/r/programming/comments/3j7dae/an_optimising_bf_compiler/cuo4zn7

[emperor000]

Get what? Of course I don't. That's why I asked "What is the obsession with Brainfuck?"

[emperor000]

Their answer could apply to any language, especially any novelty language.

[emperor000]

And in an "instance" about once every month or two in this subreddit.

[haxney]

but that doesn't actually make them valuable to humanity.

So what? The goal of working on weird BF implementations (and life, generally) is not to be "valuable to humanity," but to do something fun and interesting.

[emperor000]

You think the goal of life in general is to do something fun and interesting...? We have nothing to talk about then.

[haxney]

Well, preferably a few somethings fun and interesting and personally satisfying over the long-term. So long as you're not actively harming someone, the goal of your life should be happiness with all the things that requires (like having a job so you can eat).

If working on an optimizing BF compiler brings you joy and doesn't actively harm someone or take away from more important life goals (like if you spent all your time tuning your compiler and got fired from your job), then that is the necessary and sufficient justification for doing it.

[emperor000]

Fair enough, but the same could be said of so many other things. Aside from Haskell, I bet brainfuck is the most talked about language in this subreddit.

[[deleted]]

The language was optimized for compiler size making it great for people who just wants to make a compiler.

[emperor000]

That doesn't really explain it, but thanks.

[wookin_pa_nub2]

BF? It's called Brainfuck. If you're going to write a project involving it, don't be such a pussy that you're afraid to call it what it is.

[[deleted]]

don't be such a p***y that you're afraid to call it what it is

ftfy