11 ms·

Brainfuck Optimization Strategies

103 points by nirvanis 12y ago

sp332 12y ago
As a comparison, what does it look like if you enable GCC optimization?
- matslina 12y ago
  Here's the no-vs-all optimizations graph for gcc with -O3: http://imgur.com/Q6yycrT http://imgur.com/Q6yycrT
Gurkenmaster 12y ago
There's of course also a optimized brainfuck compiler written in sed: https://github.com/stedolan/bf.sed https://github.com/stedolan/bf.sed
- Exuma 12y ago
  Ugh
  - musername 12y ago
    Is that the sound of your chin hitting the floor or air escaping as you tense up, trying to decipher the code? :)
- yellowapple 12y ago
  That is incredibly beautiful.
- throwaway_99837 12y ago
  64 Kb should be enough for anyone!
blt 12y ago
Beautiful insanity.
JetSpiegel 12y ago
http://calmerthanyouare.org/2014/09/30/brainfuck-java.html http://calmerthanyouare.org/2014/09/30/brainfuck-java.html some of the issues encountered when writing a brainfuck-to-java compiler in brainfuck Yo dawg, etc
- JetSpiegel 12y ago
  It gets better http://awib.googlecode.com/svn/builds/awib-0.4.b http://awib.googlecode.com/svn/builds/awib-0.4.b Awib is a brainfuck compiler written in brainfuck. It is also polyglot in bash, Tcl and C For instance, using gcc, the following will build an executable file called awib from awib-0.2.b. $ cp awib-0.2.b awib-0.2.c $ gcc awib-0.2.c -o awib.tmp $ ./awib.tmp < awib-0.2.b > awib-0.2.c $ gcc -O2 awib-0.2.c -o awib Using bash works fine, but is very very very slow: $ (echo "@386_linux"; cat awib.b) | bash awib.b > awib $ chmod +x awib And tcl: $ (echo "@386_linux"; cat awib.b) | tclsh awib.b > awib $ chmod +x awib
bquinlan 12y ago
I while ago I wrote a simple Brainfuck interpreter, JIT and compiler (https://github.com/brianquinlan/brainfuck-jit https://github.com/brianquinlan/brainfuck-jit). The compiler implements the "Operation offsets" optimization as described in the article. It is actually pretty straightforward. This function converts a map of offset => delta to x86-64 instructions: https://github.com/brianquinlan/brainfuck-jit/blob/master/bf_compile_and_go.cpp#L175 https://github.com/brianquinlan/brainfuck-jit/blob/master/bf... and the function following it generates that table.
- icefox 12y ago
  A silly Brainfuck interpreter I wrote one evening converts BF to JavaScript and runs eval() on it. The result was that I got for free all of the compiler optimizations and JIT capabilities in the Javascript engines for a trivial amount of effort. I found the resulting execution faster than the various hand rolled C interpreters I found online. The best part was that I spent probably less than an hour implementing and testing my "interpreter".
debacle 12y ago
Brainfuck is a really beautiful language. It was the first language I wrote a parser for, and it's incredibly beautiful in its simplicity.
- SCHiM 12y ago
  What always strikes me (I also wrote a bf parser a while back) is the pay-off in how simple it is to implement vs how hard it is to write in it. This seems a very obvious and simple thing to notice: the less tokens/rules your language uses the easier it is to write a parser for it, but the harder it is to write a program in that language. The implications seem more subtle and are more interesting. The very simple phenomenon implies that application development time later can be saved by compiler development time now. If so then what is the most optimal language/compiler? What is the best distribution of time? Is it perhaps so that there exists a language that is trivial to implement, yet also super powerful and expressive to program in (don't say lisp here, though it does almost satisfy the second constraint imo).
  - debacle 12y ago
    That's kind of just Greenspun's rule as applied to programming languages.
  - jnbiche 12y ago
    >Is it perhaps so that there exists a language that is trivial to implement, yet also super powerful and expressive to program in (don't say lisp here, though it does almost satisfy the second constraint imo). Lisp. Satisfies both constraints. But seriously, Forth is another interesting language that strikes a good balance between ease of implementation vs ease of use and expressive power. But even more than Lisp, it takes some serious getting used to.
  - z3t4 12y ago
    Interesting observation. I think, the more abstraction, the more productive you can be.
  - rdc12 12y ago
    The language IO has a very simple grammar[1] and ignoring libraries is a pretty productive language. I suspect that you are on to something, but instead of the grammer being the guide instead the abstraction that the language gives you, but with a correlation between abstraction and the complexity of the grammar. [1] http://iolanguage.org/scm/io/docs/IoGuide.html http://iolanguage.org/scm/io/docs/IoGuide.html exp ::= { message | terminator } message ::= symbol [arguments] arguments ::= "(" [exp [ { "," exp } ]] ")" symbol ::= identifier | number | string terminator ::= "\n" | ";"
huhtenberg 12y ago
Now peg it against http://mazonka.com/brainf/ http://mazonka.com/brainf/, the bff4lnr version :)
- matslina 12y ago
  Since bff4lnr is an interpreter, this really becomes apples and oranges. But for fun, dbfi.b on bff4lnr (at -O3) vs all at -O0 and -O3: http://imgur.com/uEEgVr0 http://imgur.com/uEEgVr0 Conclusion: if you want speed then compile.
  - huhtenberg 12y ago
    Ah, my bad. I didn't realize yours was a compiler.
Yadi 12y ago
This sounds cool, but I was not sure till halfway through the post if it's like an Onion article or not.
primaryobjects 12y ago
Is there an implementation of this that converts any BF code into C/C# code? Might make a handy web-based tool. It would be interesting to apply this to AI generated programs (http://www.primaryobjects.com/CMS/Article163 http://www.primaryobjects.com/CMS/Article163)
- matslina 12y ago
  Implementations are available in the repository linked to from the article. Not quite "ready for production", but hopefully a useful starting point. https://github.com/matslina/bfoptimization https://github.com/matslina/bfoptimization
  - primaryobjects 12y ago
    Thanks, I see it. The translation code is inside ir.py. So you can call ir_to_c(bf_to_ir("+++.")) to do the conversion. Here is the code to convert BF to C, in case anyone else is interested https://gist.github.com/primaryobjects/0ba06f1f6f0d3e984d89 https://gist.github.com/primaryobjects/0ba06f1f6f0d3e984d89 Here it is running the converted C code https://ideone.com/z16KPJ https://ideone.com/z16KPJ Very cool.
- rdc12 12y ago
  It is pretty trival to write a BF compiler to C, each instruction has a clear C equivilant and the parser is dead simple to write as well. It is less then an hours work to write a naive BF->C compiler
- shultays 12y ago
  BF operators can be matched C code easily. http://en.wikipedia.org/wiki/Brainfuck#Commands http://en.wikipedia.org/wiki/Brainfuck#Commands
ninjakeyboard 12y ago
I'm working on implementing the JVM in Brainfuck
lifthrasiir 12y ago
I have a (at the initial release, and possibly still) "state-of-the-art" Brainfuck compiler to C [1], which can compile a "Hello, world" program into a single `puts` call. Some ProTip(tm): JITing Brainfuck doesn't fare a lot; for example, resetting the cell is an O(n) operation in BF, so JIT alone doesn't reduce this into O(1). Some kind of scalar evolution has to be implemented to reduce this O(n) factor. More sophiscated liveness and range analysis might be required to go further (esotope-bfc didn't get there, anyway). [1] https://bitbucket.org/lifthrasiir/esotope-bfc https://bitbucket.org/lifthrasiir/esotope-bfc
nemo 12y ago
Kudos, I guess...
Fede_V 12y ago
How long until someone makes a homoiconic version of brainfuck?
abandonliberty 12y ago
Though rather juvenile I appreciated this interpreter that maps instructions to offensive four letter words. NSFW text. ff/feckfeck/f* ckf* ck. http://web.archive.org/web/20050318095341/http://www.chilliwilli.co.uk/ff/ http://web.archive.org/web/20050318095341/http://www.chilliw... http://web.archive.org/web/20050311055852/http://www.chilliwilli.co.uk/ff/hwcommented.ff http://web.archive.org/web/20050311055852/http://www.chilliw...
chucksmart 12y ago
Who is hiring brainfuck developers these days?
- shultays 12y ago
  I always keep it on my CV, hopefully one day.

103 points by nirvanis 12y ago

sp332 12y ago

As a comparison, what does it look like if you enable GCC optimization?

matslina 12y ago
Here's the no-vs-all optimizations graph for gcc with -O3: http://imgur.com/Q6yycrT http://imgur.com/Q6yycrT

Gurkenmaster 12y ago

There's of course also a optimized brainfuck compiler written in sed: https://github.com/stedolan/bf.sed https://github.com/stedolan/bf.sed

Exuma 12y ago
Ugh
- musername 12y ago
  Is that the sound of your chin hitting the floor or air escaping as you tense up, trying to decipher the code? :)
yellowapple 12y ago
That is incredibly beautiful.
throwaway_99837 12y ago
64 Kb should be enough for anyone!

blt 12y ago

Beautiful insanity.

JetSpiegel 12y ago

http://calmerthanyouare.org/2014/09/30/brainfuck-java.html http://calmerthanyouare.org/2014/09/30/brainfuck-java.html some of the issues encountered when writing a brainfuck-to-java compiler in brainfuck Yo dawg, etc

JetSpiegel 12y ago
It gets better http://awib.googlecode.com/svn/builds/awib-0.4.b http://awib.googlecode.com/svn/builds/awib-0.4.b Awib is a brainfuck compiler written in brainfuck. It is also polyglot in bash, Tcl and C For instance, using gcc, the following will build an executable file called awib from awib-0.2.b. $ cp awib-0.2.b awib-0.2.c $ gcc awib-0.2.c -o awib.tmp $ ./awib.tmp < awib-0.2.b > awib-0.2.c $ gcc -O2 awib-0.2.c -o awib Using bash works fine, but is very very very slow: $ (echo "@386_linux"; cat awib.b) | bash awib.b > awib $ chmod +x awib And tcl: $ (echo "@386_linux"; cat awib.b) | tclsh awib.b > awib $ chmod +x awib

bquinlan 12y ago

I while ago I wrote a simple Brainfuck interpreter, JIT and compiler (https://github.com/brianquinlan/brainfuck-jit https://github.com/brianquinlan/brainfuck-jit). The compiler implements the "Operation offsets" optimization as described in the article. It is actually pretty straightforward. This function converts a map of offset => delta to x86-64 instructions: https://github.com/brianquinlan/brainfuck-jit/blob/master/bf_compile_and_go.cpp#L175 https://github.com/brianquinlan/brainfuck-jit/blob/master/bf... and the function following it generates that table.

icefox 12y ago
A silly Brainfuck interpreter I wrote one evening converts BF to JavaScript and runs eval() on it. The result was that I got for free all of the compiler optimizations and JIT capabilities in the Javascript engines for a trivial amount of effort. I found the resulting execution faster than the various hand rolled C interpreters I found online. The best part was that I spent probably less than an hour implementing and testing my "interpreter".

debacle 12y ago

Brainfuck is a really beautiful language. It was the first language I wrote a parser for, and it's incredibly beautiful in its simplicity.

SCHiM 12y ago
What always strikes me (I also wrote a bf parser a while back) is the pay-off in how simple it is to implement vs how hard it is to write in it. This seems a very obvious and simple thing to notice: the less tokens/rules your language uses the easier it is to write a parser for it, but the harder it is to write a program in that language. The implications seem more subtle and are more interesting. The very simple phenomenon implies that application development time later can be saved by compiler development time now. If so then what is the most optimal language/compiler? What is the best distribution of time? Is it perhaps so that there exists a language that is trivial to implement, yet also super powerful and expressive to program in (don't say lisp here, though it does almost satisfy the second constraint imo).
- debacle 12y ago
  That's kind of just Greenspun's rule as applied to programming languages.
- jnbiche 12y ago
  >Is it perhaps so that there exists a language that is trivial to implement, yet also super powerful and expressive to program in (don't say lisp here, though it does almost satisfy the second constraint imo). Lisp. Satisfies both constraints. But seriously, Forth is another interesting language that strikes a good balance between ease of implementation vs ease of use and expressive power. But even more than Lisp, it takes some serious getting used to.
- z3t4 12y ago
  Interesting observation. I think, the more abstraction, the more productive you can be.
- rdc12 12y ago
  The language IO has a very simple grammar[1] and ignoring libraries is a pretty productive language. I suspect that you are on to something, but instead of the grammer being the guide instead the abstraction that the language gives you, but with a correlation between abstraction and the complexity of the grammar. [1] http://iolanguage.org/scm/io/docs/IoGuide.html http://iolanguage.org/scm/io/docs/IoGuide.html exp ::= { message | terminator } message ::= symbol [arguments] arguments ::= "(" [exp [ { "," exp } ]] ")" symbol ::= identifier | number | string terminator ::= "\n" | ";"

huhtenberg 12y ago

Now peg it against http://mazonka.com/brainf/ http://mazonka.com/brainf/, the bff4lnr version :)

matslina 12y ago
Since bff4lnr is an interpreter, this really becomes apples and oranges. But for fun, dbfi.b on bff4lnr (at -O3) vs all at -O0 and -O3: http://imgur.com/uEEgVr0 http://imgur.com/uEEgVr0 Conclusion: if you want speed then compile.
- huhtenberg 12y ago
  Ah, my bad. I didn't realize yours was a compiler.

Yadi 12y ago

This sounds cool, but I was not sure till halfway through the post if it's like an Onion article or not.

primaryobjects 12y ago

Is there an implementation of this that converts any BF code into C/C# code? Might make a handy web-based tool. It would be interesting to apply this to AI generated programs (http://www.primaryobjects.com/CMS/Article163 http://www.primaryobjects.com/CMS/Article163)

matslina 12y ago
Implementations are available in the repository linked to from the article. Not quite "ready for production", but hopefully a useful starting point. https://github.com/matslina/bfoptimization https://github.com/matslina/bfoptimization
- primaryobjects 12y ago
  Thanks, I see it. The translation code is inside ir.py. So you can call ir_to_c(bf_to_ir("+++.")) to do the conversion. Here is the code to convert BF to C, in case anyone else is interested https://gist.github.com/primaryobjects/0ba06f1f6f0d3e984d89 https://gist.github.com/primaryobjects/0ba06f1f6f0d3e984d89 Here it is running the converted C code https://ideone.com/z16KPJ https://ideone.com/z16KPJ Very cool.
rdc12 12y ago
It is pretty trival to write a BF compiler to C, each instruction has a clear C equivilant and the parser is dead simple to write as well. It is less then an hours work to write a naive BF->C compiler
shultays 12y ago
BF operators can be matched C code easily. http://en.wikipedia.org/wiki/Brainfuck#Commands http://en.wikipedia.org/wiki/Brainfuck#Commands

ninjakeyboard 12y ago

I'm working on implementing the JVM in Brainfuck

lifthrasiir 12y ago

I have a (at the initial release, and possibly still) "state-of-the-art" Brainfuck compiler to C [1], which can compile a "Hello, world" program into a single `puts` call. Some ProTip(tm): JITing Brainfuck doesn't fare a lot; for example, resetting the cell is an O(n) operation in BF, so JIT alone doesn't reduce this into O(1). Some kind of scalar evolution has to be implemented to reduce this O(n) factor. More sophiscated liveness and range analysis might be required to go further (esotope-bfc didn't get there, anyway). [1] https://bitbucket.org/lifthrasiir/esotope-bfc https://bitbucket.org/lifthrasiir/esotope-bfc

nemo 12y ago

Kudos, I guess...

Fede_V 12y ago

How long until someone makes a homoiconic version of brainfuck?

abandonliberty 12y ago

Though rather juvenile I appreciated this interpreter that maps instructions to offensive four letter words. NSFW text. ff/feckfeck/f* ckf* ck. http://web.archive.org/web/20050318095341/http://www.chilliwilli.co.uk/ff/ http://web.archive.org/web/20050318095341/http://www.chilliw... http://web.archive.org/web/20050311055852/http://www.chilliwilli.co.uk/ff/hwcommented.ff http://web.archive.org/web/20050311055852/http://www.chilliw...

chucksmart 12y ago

Who is hiring brainfuck developers these days?

shultays 12y ago
I always keep it on my CV, hopefully one day.