Implementing brainfuck, part 2

Update: Faster binaries posted. Source coming shortly.

In Part 1, I presented some benchmarks (see here) for my brainfuck implementation against some of the best.  I'll now lay out the reference interpreter, the optimized interpreter, and source code.

(I'm slower posting all this than I meant to be:  apologies --- dayjob and all...)

To start, the reference interpreter looks like this:

The source code is here: bffsree_ref.c and bfsree.h.
[updated: fixed missing header]
Executables for Windows and Linux.

Its pretty basic --- pretty much add/subtract, move left/right, get/put, and then loop begin/end. It basically is as basic as you can get, though it include three things that are, only in the loosest sense, "optimizations":

1. Although the interpreter will ignore non-valid characters at runtime, they are actually stripped at parse time.
2. I accumulate operations into a counter at parse time (e.g. ++++ becomes +4)
3. I parse the jump locations for loops at parse time.

These are so simple to do inline that it feels like they hardly qualify, and you'll see all 3 in pretty much every implementation (I'd guess).

And presented below is the optimized implementation that I presented in Part 1:

Note that it is NOT materially different.
The main differences are:

• The collapse of the command and "helper" arrays
• Double-instructioning -- whereby it is assumed that to do anything interesting in brainfuck, you always have to move the pointer, so every instruction has a move-the-pointer offset (saves on instruction decodes)
• The inclusion of the "super instructions" that perform the following common tasks:
1. Pointer shifting in a loop
2. Multiplication of a cell by a constant
3. Setting a cell to a value
4. Multiplication of a cell by a constant, then zeroing
5. Multiplying two cells

The first 2 are pretty straighforward -- most of the work is in the third item: collapsing the existing instructions into the optimized "super" instructions without breaking any contracts.  The primary optimizations are around loop invariance.

There are a LOT more optimizations I didn't yet finish tackling -- dead code elimination and constant propagation, in particular -- that should yield materially better performance.

I'll post the details and source to the optimizing implementation in a future post.  

(Oh, btw, forget to mention -- if you use the "-c" option with the optimized implementation from part 1, it will convert your brainfuck program to somewhat performant C code.)

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.

Redux: WebGL Random Pixel Toy

Fun: Check out WebGL Sand Toy.

John Robinson, at his storminthecastle blog, posted a 'cloud' version (i.e. a webpage :P) of a toy app I did 5 years ago.  His version is pretty cool, all the more so because it runs in the browser, using WebGL.

Two things strike me about this (other than general fun/goodness):

1. 5 years(-ish) feels about right on the Moore's law curve, and is probably the target for 'native' smartphones apps making the transition to browser based (if the W3C can get its act together)
2. On the other hand, "runs like native" still seems like the highest compliment one can pay a browser based thing... so there's that.

By way of example for both points, consider:

Viewpoint Media Player 3D, in a browser, circa 2002 using 'SreeD'

WebGL racer, in a browser, circa 2011 using OpenGL

In any case, enjoy.

Kindle Fire: Return of the Desktop?

Much has been written about the Amazon Kindle Fire (Amazon's new Android based touchscreen Kindle e-reader/media player).

Is it a game changer? Maybe. We'll see.

I've certainly ordered one, and though many say its no threat to the iPad, given its media capabilities... I dunno --- people might be surprised. If its reasonably performant (and compatible) for browsing, and given its e-commerce, e-book, and media capabilities... well, we'll see.

Certainly its going to make it tough for other Android tablet vendors; Jeff Bezos is right in asserting that devices alone don't sell (and this is old news) -- it's devices+services, as Apple has amply demonstrated again and again.

All that said, there's another interesting thing about the Kindle Fire that distinguishes its market approach from Apple's.

It's about content.

Apple sells activities -- a lifestyle; Amazon sells content.

Contrast Amazon's pitch with Apple's:

Disagree if you want, but its a philosophy difference that extends to the VERY FIRST SCREEN: Amazon hilights the content, not the application(s) -- go watch the Amazon video at the top of the post again.

Sure, you can by music, movies, and books with your iOS device, and there's no question that's a big part of the appeal -- but Apple's metaphor is about the task (books-->'Winnie the Pooh', videos-->'Inception'), and Amazon's is the reverse.

Interesting.

And here I thought "document-centric" computing, and the desktop metaphor it implies, was dead (I even wrote a eulogy).

Is it going to work? Maybe. We'll see.

But, either way, I have to give props to Amazon, and Bezos, for, well, trying to Think Different... :P

#ihatewhengirlssay "that didn't take long"

Interesting to watch "tweetalanches" happen... and where/when they get started. For example, today at 10am, "#ihatewhengirlssay" was not a hashtag with any tweets. At the moment .... a few hundred. It should be interesting to see how much "damage" it causes before the dust settles. The whole things reminds of Scott Adams' "Avatar" concept/character in his most excellent books: God's Debris and Religion War (no relation to James Cameron's upcoming movie).

Also of recent note: Twitter's going to start making money.

#ihatewhengirlsay "Twitter's going to make tons of money."

Comcast, Time Warner, and TVEverywhere

Comcast and Time Warner jointly announced the "TV Everywhere" initiative - much to the very vocal derision of blogs, pundits, and digital heads everywhere :)

The root of the announcement is, of course, that premium programming content will be available online, at no incremental cost to consumers (what marketers like to call "free" :)).

Hard to see why this is a bad thing - but there are lots of big words, like "anti-competitive" and "anti-consumer", being bandied about, so let's try to deconstruct the questions being asked a bit. Note that opinions expressed here, as always, are strictly my own.

1) Should content producers allowed to charge for access to their content?

I think the answer to that is "yes". There are some fair questions about who they charge, and how, and is there pricing collusion, etc. - but I don't think anyone means to imply that advertising is the ONLY model that content producers should be able to use?

2) Doesn't "TV Everywhere" depart from the Hulu model?

So... broadcasters (NBC, ABC, Fox, et al) ALREADY make the content available for free (over-the-air) - and they monetize with advertising. The "Hulu model" was to take the same business model, and make it available online. I don't mean to parse semantics here, but... kinda sounds like the same idea here: make content available wherever consumers are, using a model that is already working for consumers. Like Hulu, this isn't a new business - its a new distribution channel.

3) Doesn't this "violate the open nature of the Internet"?

Hmm - not sure I follow this one. "TV Everywhere" is not exclusive in any way - its simply a way for premium TV producers to get their content to consumers online, and helps identify those who are already paying for the content offline. If the content producers want to make their stuff free - well, it is their content; they're welcome to do so - not sure how this initiative impedes that idea. Yes, NBC, Fox, et al, already make their content available free to consumers (for a limited time window) - but also did so before Hulu.

The Internet is an "all bits are equal" data pipe into the home - and nothing about offering subscription video over the Internet with "TV Everywhere" changes that?

The irony, to me, of posts like Om Malik's (about the "inefficent business model" being propagated here, etc.) is that it sits on the site the same day as a post that reads "Is there a future for original web video shows?"....

There is a fair question here - will the price to consumers of content trend towards zero? And if it does, how will that impact quality (i.e. who's going to want to pay to make the good stuff)?

This program doesn't purport to answer that - mostly its just trying to get more people more convenient access to something they're already paying for.

How horrible! :)