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.7 required=5.0 tests=AWL,SPF_SOFTFAIL autolearn=disabled version=3.1.3 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 69B38BC6B for ; Fri, 25 Jan 2008 03:34:04 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Aq4HAP3YmEfUnw6Flmdsb2JhbACCNY1vAQEBAQcEBgcKEQeBFJ07 X-IronPort-AV: E=Sophos;i="4.25,247,1199660400"; d="scan'208";a="21776215" Received: from pih-relay06.plus.net ([212.159.14.133]) by mail4-smtp-sop.national.inria.fr with ESMTP; 25 Jan 2008 03:34:04 +0100 Received: from [80.229.56.224] (helo=beast.local) by pih-relay06.plus.net with esmtp (Exim) id 1JIEOJ-0004mx-3d for caml-list@yquem.inria.fr; Fri, 25 Jan 2008 02:34:03 +0000 From: Jon Harrop Organization: Flying Frog Consultancy Ltd. To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] strange timing between search trees Date: Fri, 25 Jan 2008 02:28:07 +0000 User-Agent: KMail/1.9.7 References: <47993C41.1050900@univ-savoie.fr> In-Reply-To: <47993C41.1050900@univ-savoie.fr> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-15" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200801250228.07262.jon@ffconsultancy.com> X-Plusnet-Relay: b37a31d44c9ac2c628a1dc9c2ac324ff X-Spam: no; 0.00; christophe:01 raffalli:01 wikipedia:01 indirections:01 ocamlopt:01 cmxa:01 locality:01 ocaml:01 ocaml:01 inlined:01 functor:01 node:01 frog:98 wrote:01 unix:01 On Friday 25 January 2008 01:32:49 Christophe Raffalli wrote: > Dear list members, > > I wanted to compare 2-3-4 trees (look in wikipedia if you do not know > them) with the balanced trees of the standard library. > I expected the 2-3-4 to be much faster for search because they use much > less indirections. However, I thought > that construction should make little difference ... > > I was wrong : > Construction is arround 20% faster for 2-3-4 trees > Search is slower arround 5-10% for 2-3-4 trees (the diff gets smaller > when the trees are larger which is expected) > > I wonder if the difference in code size is the explanation (the search > function for balanced trees is really small and fits better > in cache) ? I doubt it. You can make the built-in Set module much faster by increasing the code size. > I attach my code with two files (the code and the test, compile with > ocamlopt unix.cmxa set234.ml test234tree.ml) > > Any remarks or comments ? I get quantitatively similar performance results. You're missing a lot of information in your benchmarking though: What happens if the sets are constructed in-order (affects locality)? What happens if you iterate the benchmark over an array of preallocated sets? I did lots of benchmarking along these lines for the optimization chapter in OCaml for Scientists (including benchmarking sets). I found that there are several alternative set implementations out there but they all give almost identical performance (as you're observing). However, the AVL trees of the built-in sets provide asymptotically more efficient set-theoretic operations (union, diff, inter) than most other implementations. I also found that the benchmarking strategy more representative of the real code that I had was to iterate over preallocate sets, i.e. more cache misses. Ultimately, I found it much more productive to simply optimize the Set module that comes with OCaml. I'll describe how in a later OCaml Journal article but the main ideas are to get the comparison function inlined (OCaml doesn't inline across functor boundaries) and add a new node type for leaves. The latter greatly reduces the stress on the GC, which is the main performance bottleneck of the current implementation, and I found it to be up to 30% faster. We've also discussed this in detail before here so you might find more information in the caml-list archives. HTH. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/products/?e