From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.4 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id B66FFBBAF for ; Sun, 19 Jul 2009 07:20:15 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Au0CAFlKYkrUnwdkdWdsb2JhbACCIJc7AQwKCQkTBLFRhAwF X-IronPort-AV: E=Sophos;i="4.43,228,1246831200"; d="scan'208";a="43625368" Received: from relay.pcl-ipout02.plus.net ([212.159.7.100]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 19 Jul 2009 07:20:15 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ApsEAFlKYkrUnw4R/2dsb2JhbACCIMlMhAwF Received: from pih-relay04.plus.net ([212.159.14.17]) by relay.pcl-ipout02.plus.net with ESMTP; 19 Jul 2009 06:20:14 +0100 Received: from [87.115.75.10] (helo=leper.local) by pih-relay04.plus.net with esmtp (Exim) id 1MSOon-0006et-MH for caml-list@yquem.inria.fr; Sun, 19 Jul 2009 06:20:14 +0100 From: Jon Harrop Organization: Flying Frog Consultancy Ltd. To: caml-list@yquem.inria.fr Subject: Burrows Wheeler Transform Date: Sun, 19 Jul 2009 07:29:45 +0100 User-Agent: KMail/1.9.9 MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200907190729.46072.jon@ffconsultancy.com> X-Plusnet-Relay: 4c2623b7dfb38a7ddac45f20a69260dc X-Spam: no; 0.00; wheeler:01 ocaml:01 higher-order:01 inlined:01 polymorphism:01 invocation:01 ocaml:01 parallelism:01 parallelism:01 wheeler:01 inlined:01 blog:98 2009:98 920:98 2009:98 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