[Haskell-cafe] Need for speed: the Burrows-Wheeler Transform

[Jon Harrop]

On Saturday 23 June 2007 13:02:54 Andrew Coppin wrote:
> Well, I altered the code, and it's *still* very short and very readable,
> and it's just as fast as the (3 pages long) C++ version. >:-D

Indeed. The performance of modern functional programming languages never 
ceases to amaze me. INRIA typically claim performance within 2x of C for 
OCaml but there are very few programs where OCaml isn't within 50% now, at 
least on AMDs.

Most of the pedagogical examples of functional programming (e.g. n-queens) are 
too academic for general consumption but there are plenty of excellent 
examples. Burrows-Wheeler is a great one. Ray tracing is another. Sudoku 
solving is fairy good, albeit unusually well suited to arrays.

I also like to compare the performance of term-level interpreters or rewriters 
implemented in different languages. I think it would be interesting to 
compare Scheme/Mathematica interpreters written in OCaml, SML (MLton) and 
Haskell, for example. I've benchmarked some interpreters in OCaml and SML 
(MLton) and MLton's whole-program optimizations are a huge benefit here, 
making it several times faster than OCaml. I'd like to know how well Haskell 
would do.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?e