Burrows Wheeler Transform

Burrows Wheeler Transform

[Jon Harrop]

I recently wrote an interesting blog post comparing the Burrows-Wheeler 
Transform written in OCaml and F#:

http://flyingfrogblog.blogspot.com/2009/07/ocaml-vs-f-burrows-wheeler.html

F# has a really handy "inline" feature that allows the programmer to have 
higher-order functions and their function arguments inlined and specialized 
to completely remove the performance overheads (i.e. polymorphism and closure 
invocation). Would be really nice if this were possible in OCaml too. Perhaps 
a batteries included macro is in order? :-)

Mauricio Fernandez was kind enough to optimize my simple fork-based 
parallelism into genuine shared memory parallelism, turning it into a real 
quicksort and producing much better performance (only 75% slower than F#):

http://www.reddit.com/r/programming/comments/920y4/ocaml_vs_f_burrows_wheeler_transform/c0b5u80

Matias Giovannini's minimal sorting networks can probably make it 
substantially faster still:

http://alaska-kamtchatka.blogspot.com/2008/08/family-portrait.html

I also wrote an article about QR decomposition that uses the same technique 
but the performance difference is much bigger because the functions being 
inlined are basic arithmetic ops:

http://flyingfrogblog.blogspot.com/2009/07/ocaml-vs-f-qr-decomposition.html

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e