Whitespace is ignored in Brainfuck, so just write the compiler in brainfuck and then strip all but 6 newlines.

I think lines should be hard wrapped at around 100 or 120. Linus prefers 100 for example.

This is such a Brainfuck answer

This is correct. A players rank will typically differ between both server and go association. Sensei's Library holds more information: http://senseis.xmp.net/?RankWorldwideComparison

Glibc falls back to quicksort from merge sort (its default algorithm) when there's to little free memory available to accommodate merge sort's O(n) requirement. Quicksort only uses O(log n) additional memory, making it a good option in that sense. O(1) would of course be better, but even for huge inputs that logarithm makes the memory consumption a non-issue in most cases. Heapsort does give you O(1) memory, but also comes with poorer cache locality and overall performance than quicksort, making it a not so compelling option.

Well, the worst case is still there. You're just going to have a very hard time crafting an input that triggers it.

Could be. You can have a look at the headline data here: https://gist.github.com/matslina/64601f39ef12bd653be6

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

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

Here it is running the converted C code https://ideone.com/z16KPJ

Very cool.

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 Conclusion: if you want speed then compile.

Ah, my bad. I didn't realize yours was a compiler.

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

Mergesort would be a poor choice for qsort() due to the linear space complexity. With N bytes of RAM, you'd only be able to sort (a bit less than) N/2 bytes of data. An in-place algorithm is preferable.

Glibc is the only libc I'm aware of that implements mergesort. It still falls back to quicksort for large inputs though.

I just heard about smoothsort: http://code.google.com/p/combsortcs2p-and-other-sorting-algo...

Also, nice little write-up, thanks. I also dig the extracted sort implementations you dug-out: https://github.com/matslina/qsort

All BSD derived libcs contains mergesort(), and heapsort() as well.

True, but parent meant used in the qsort and qsort_r implementations.

Oh, of course. reading fail.