From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id CF950BB83 for ; Thu, 17 Aug 2006 20:49:05 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id k7HIn42U007990 for ; Thu, 17 Aug 2006 20:49:05 +0200 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id UAA29724 for ; Thu, 17 Aug 2006 20:49:04 +0200 (MET DST) Received: from mta.conjury.org (grymling.conjury.org [69.12.155.90]) by nez-perce.inria.fr (8.13.6/8.13.6) with ESMTP id k7HGQBF4021542 for ; Thu, 17 Aug 2006 18:26:11 +0200 Received: from localhost (localhost [127.0.0.1]) by mta.conjury.org (Postfix) with ESMTP id A5C2D15743B for ; Thu, 17 Aug 2006 09:26:06 -0700 (PDT) Received: from mta.conjury.org ([127.0.0.1]) by localhost (localhost [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 11831-03 for ; Thu, 17 Aug 2006 09:25:56 -0700 (PDT) Received: from [10.0.1.200] (station.conjury.org [69.12.155.91]) by mta.conjury.org (Postfix) with ESMTP id 0E69115741C for ; Thu, 17 Aug 2006 09:25:56 -0700 (PDT) Mime-Version: 1.0 (Apple Message framework v752.2) In-Reply-To: <44E454F5.2040406@inria.fr> References: <44D3A944.3060907@janestcapital.com> <44E454F5.2040406@inria.fr> Content-Type: text/plain; charset=WINDOWS-1252; delsp=yes; format=flowed Message-Id: Content-Transfer-Encoding: quoted-printable From: j h woodyatt Subject: Re: [Caml-list] map implementation question Date: Thu, 17 Aug 2006 09:25:52 -0700 To: The Caml Trade X-Mailer: Apple Mail (2.752.2) X-Virus-Scanned: by amavisd-new at conjury.org X-Miltered: at concorde with ID 44E4BA20.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; woodyatt:01 jhw:01 red-black:01 tweak:01 red-black:01 ocaml:01 binary:01 binary:01 seq:01 hypothetical:01 node:01 woodyatt:01 jhw:01 2006,:98 smoke:98 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 On Aug 17, 2006, at 4:37 AM, Xavier Leroy wrote: > > This said, red-black trees would probably work faster anyway, but I'll > let the algorithm experts on this list comment. My experience trying to tweak the red-black trees in the Cf library =20 of OCaml NAE so they perform globally better than the height-balanced =20= trees in the standard library has been mixed. Some functions perform =20= marginally better, but others are worse-- sometimes substantially =20 worse, and I don't think there's any way around it. (It doesn't help =20= that a lot of my exercises reveal that my binary set operations need =20 improvement, but there are other places where there's simply nothing =20 to do. I'll get around to fixing the binary set operators someday, =20 before my next release.) By the way, Xavier is very correct: that "imbalance <=3D 2" thing is =20 utterly brilliant. I'm pretty sure my red-black trees would smoke =20 the standard library if it weren't for that. The result is that I recommend using my red-black trees only when you =20= are either 1) using the other facilities in the Cf library that are =20 integrated well with them, e.g. Cf_seq and such, or 2) using them in =20 a [currently hypothetical] case where you have compared the =20 performance with the standard library and it makes a valuable =20 difference to get 15% more CPU (or one less field per tree node) out =20 of your tree algorithm. =97 j h woodyatt san francisco, ca