From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 78FC6BC75 for ; Fri, 18 Feb 2005 10:38:47 +0100 (CET) Received: from ptb-relay02.plus.net (ptb-relay02.plus.net [212.159.14.213]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j1I9ckRA018385 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Fri, 18 Feb 2005 10:38:47 +0100 Received: from [80.229.56.224] (helo=chetara) by ptb-relay02.plus.net with esmtp (Exim) id 1D24av-0008cp-63 for caml-list@yquem.inria.fr; Fri, 18 Feb 2005 09:38:41 +0000 From: Jon Harrop Organization: Flying Frog Consultancy Ltd. Subject: Fwd: Re: [Caml-list] Persistence Date: Fri, 18 Feb 2005 09:40:10 +0000 User-Agent: KMail/1.7.1 To: caml-list@yquem.inria.fr MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200502180940.11265.jon@jdh30.plus.com> X-Miltered: at nez-perce with ID 4215B7A7.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 wrote:01 stl:01 stl:01 ocaml's:01 ocaml:01 computes:01 ocaml:01 implements:01 reuse:01 memoizing:01 unions:01 ocaml's:01 reusing:01 vastly:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: Many moons ago: On Sunday 06 February 2005 22:26, Radu Grigore wrote: > I had written: > > The STL will probably take <<1ms because the STL's size() is probably > > O(1) whereas Map's fold is O(n). In contrast, forking lineages is > > probably O(n) with the STL (requiring a copy) and O(1) with ocaml's Map. > > I haven't actually tested with STL but the implementation of size() is > indeed a simple return. Do you have an example where forking lineages > is useful? I do now. :-) I've just finished converting one of my example scientific programs from OCaml to C++. The program basically computes the "n"th nearest neighbours of a vertex in a graph. The implementations are based upon sets of vertices. The OCaml version simply implements the obvious mathematical expression. The only difference is that reuse is implicit in the maths (which is purely functional) and has to be made explicit in the OCaml code by memoizing the function. My first stab at a C++ version did exactly the same thing. As you know, OCaml performance is supposed to to be within a factor of 2 of C/C++. Somewhat suprisingly, on my first timed run the C++ code turned out to be over 100 times slower than the OCaml. After some profiling it transpired that virtually all of the time was spent computing set unions which I had stupidly implemented using the STL set_union function. ;-) The reason is quite simple. Thanks to the purely functional implementation in OCaml, sets are immutable. OCaml's Set.union function exploits this by reusing pieces of tree from the input sets in the output ("copying" arbitrarily-large subsets in O(1) time), happily knowing that they cannot be altered afterwards. In contrast, the C++ implementation of set_union can make no such assumption and is forced to copy most of the elements from both of the input sets. The performance of set_union in the STL is, therefore, vastly worse than the performance of Set.union in OCaml, thanks to persistence. In summary, like me, you've probably been using persistence a lot without realising it. Every time you do set operations, for example. HTH. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd.