English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Ropes and rope-like functional extensible vectors with O(1) prepend/append.
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2007-07-28 (23:33)
From: Mauricio Fernandez <mfp@a...>
Subject: Ropes and rope-like functional extensible vectors with O(1) prepend/append.
In the aftermath of the ICFP contest, during which I used Luca de Alfaro's
Vec, I felt like implementing ropes, based on Boehm's paper and the well-known
code included in his conservative garbage collector.

I later realized that the basic implementation strategies ("dense" leaves,
bounded tree height and amortized constant time concatenation of small
strings) could be generalized to build general extensible vectors similar to

Such vectors (tentatively named "Vect" until I find a better name) have some
interesting properties:
* lower space overhead than other structures based on balanced trees such as
  Vec.  The overhead can be adjusted, allowing to make "get" faster at the
  expense of "set" and viceversa.
* appending or prepending a small vector to an arbitrarily large one in
  amortized constant time
* concat, subarray, insert, remove operations in amortized logarithmic time
* access and modification (get, set) in logarithmic time

The first one is probably the most compelling. Currently, Vec imposes a 6-word
overhead per element. Even after the obvious modification consisting in adding
a new constructor for leaves, the overhead would still be 350%... Vect uses
compact leaves with a configurable number of elements (32-64 seem good
choices, leading to worst-case overheads of 100% and 50% respectively), which
also helps with "get" due to the improved spatial locality.

You can find the code for both Rope and Vect at
It is still young and experimental, but it's maybe worth a look. Any feedback
is very welcome. 

The documentation can be found under

I've spent some time benchmarking it against Vec; you can also find the
code I used and the resulting graphs at the above address.

To summarise how it compares to Vec:
* Vec can be used when persistence is required, but Vect would probably be a
  poor choice in this case (until that is fixed using lazy rebuilding, which
  doesn't seem too hard), unless rebalancing explicitly before "taking the
  snapshot" is an option
* Vect can append/prepend single elements or small vectors very quickly, in
  amortized constant time. See
* as expected, Vec.set is faster than Vect's in general
  However, if the vector is balanced explicitly shortly before an update
  burst, Vect is somewhat surprisingly faster 
  This might be attributed to Vect's smaller memory profile and the fact that
  it allows better use of the L2 cache, but there seems to be another factor
  that I have yet to discover.
* Vect.get is considerably faster than Vec.get

The above URL is a darcs repository, so if anybody shoots me a patch I'll be
happy to apply it :)


Mauricio Fernandez  -   http://eigenclass.org