Fwd: Re: [Camllist] Persistence
 Jon Harrop
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20050218 (09:38) 
From:  Jon Harrop <jon@j...> 
Subject:  Fwd: Re: [Camllist] Persistence 
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" arbitrarilylarge 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.