Implementing brainfuck

Updated:  Part 2 is now available.

For those not aware, brainfuck is a small programming language whose sole existence is to amuse programmers. It has certainly been amusing.

In that vein, I got myself a nice X1 Carbon Touch with Windows 8 a few weeks ago, and as always with a new laptop, I play with a few projects to "break it in". I have a fun little image viewer that I upgraded to touch (a few more things to clean up - may post it), and one of the other toys I thought I'd play with was a brainfuck interpreter and debugger. The debugger part is important, as I've done a few language implementations before, but not all the way through the tool chain, and thought it'd be informative. Sadly, I'm not through the whole tool chain yet -- still have to finish the editor/debugger, but the basic mechanics for the implementation are in place.

Because I'm competitive, I wanted to also try some interpreter optimization ideas. I'd been kicking them around with a Javascript interpreter I did over the holidays (*cough* 2011 --- will get back to it at some point). Brainfuck seemed simple enough that it would be a nice testbed.

Anyway, I'll post some more details and source code, but thought I'd start with some results and executables to "whet the appetite" as it were.

For those who are unfamiliar, brainfuck has only 8 operators: "<>[]+-,." ... and "Hello World" looks like this:

>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]
>++++++++[<++++>-] <.>+++++++++++[<++++++++>-]<-.--------.+++
.------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.

I first built a reference interpreter, and then found a few fast online intepreters: Alex Pankatrov's moderately optimizing implementation (bff) and Oleg Mazonka's "fastest in class" interpreter (bff4) (according to Wikipedia). They both crushed my reference interpreter, which lead to my optimized implementation. Compiled versions are included here:

• Alex's bff for Windows and Linux.
• Oleg's bff4 for Windows and Linux.
• My bffsree for Windows and Linux.

Some brainfuck sample programs are here.

UPDATE: Linux binaries updated; had uploaded in text mode (d'oh!).

UPDATE 02.27.13: Slightly faster binaries updated again.

Performance is as follows:
Linux:

program:	mandel.b	hanoi.b	sisihi.b	long.b
bff	6.0s	12.3s	n/a	14.4s
bff4	6.8s	0.5s	5.9s	3.1s
bffsree	2.7s	0.05s	1.4s	0.2s

Windows:

program:	mandel.b	hanoi.b	sisihi.b	long.b
bff	7.6s	16.2s	n/a	17.1s
bff4	6.8s	1.3s	4.1s	3.1s
bffsree	3.4s	0.8s	1.2s	0.16s

Some notes:

• GCC 4.7 for Windows and 4.6 for Linux were used.
• bffsree and bff can read from a file or stdin.  bff4 reads from stdin.
• "sisihi.b" is a brainfuck self interpreter running itself running "hi123.b" -- basically the executable you pick runs a brainfuck program that is a self intepreter running a self interpreter (itself) that runs a simple brainfuck program.  Which is why they call it brainfuck.
• The difference between Linux speed and Windows speed appears to be gcc version and console speed (Windows console is slow).
• Both bff and bff4 seem to fail with "bench.b" (or are crazy slow) --- not sure what that's about.
• Oleg's bff4 appears to have been the fastest since 2009 -- which is quite impressive.

I'll discussion implementation notes in a follow-up post shortly.
Continued here.