* Burrows Wheeler Transform
@ 2009-07-19 6:29 Jon Harrop
0 siblings, 0 replies; only message in thread
From: Jon Harrop @ 2009-07-19 6:29 UTC (permalink / raw)
To: caml-list
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
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2009-07-19 5:20 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2009-07-19 6:29 Burrows Wheeler Transform Jon Harrop
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).