From: Jon Harrop <jon@ffconsultancy.com>
To: caml-list@yquem.inria.fr
Subject: Burrows Wheeler Transform
Date: Sun, 19 Jul 2009 07:29:45 +0100 [thread overview]
Message-ID: <200907190729.46072.jon@ffconsultancy.com> (raw)
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
reply other threads:[~2009-07-19 5:20 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=200907190729.46072.jon@ffconsultancy.com \
--to=jon@ffconsultancy.com \
--cc=caml-list@yquem.inria.fr \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).