Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
RE: Re: [Caml-list] Persistence
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2005-02-21 (20:17)
From: Don Syme <dsyme@m...>
Subject: RE: Re: [Caml-list] Persistence

Hi Jon,

Could you send around the source code to this?  I intuitively knew that
such performance results were likely, but had never had such a
convincing example to wave at people.  

It would also be interesting to ask some C++ programmers how they would
go about optimizing this code, for a couple of reasons

(a) to see if they come up with anything faster; and 

(b) to see if they would ever even think of using
sharing-of-complex-immutable-internal-data-structure-nodes as an
optimization technique.


-----Original Message-----
[] On Behalf Of Jon Harrop
Sent: 18 February 2005 09:40
Subject: Fwd: Re: [Caml-list] 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
> > 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
> 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

The OCaml version simply implements the obvious mathematical expression.
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

My first stab at a C++ version did exactly the same thing. As you know,
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
times slower than the OCaml. After some profiling it transpired that
virtually all of the time was spent computing set unions which I had
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
no such assumption and is forced to copy most of the elements from both
the input sets. The performance of set_union in the STL is, therefore,
worse than the performance of Set.union in OCaml, thanks to persistence.

In summary, like me, you've probably been using persistence a lot
realising it. Every time you do set operations, for example.


Dr Jon D Harrop, Flying Frog Consultancy Ltd.

Caml-list mailing list. Subscription management:
Beginner's list:
Bug reports: