[Caml-list] Ropes and rope-like functional extensible vectors with O(1) prepend/append.
Mauricio Fernandez
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
Vec.
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
http://eigenclass.org/repos/oropes/head/
It is still young and experimental, but it's maybe worth a look. Any feedback
is very welcome.
The documentation can be found under
http://eigenclass.org/repos/oropes/head/doc/
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
http://eigenclass.org/repos/oropes/head/append.png
* as expected, Vec.set is faster than Vect's in general
http://eigenclass.org/repos/oropes/head/set.png
However, if the vector is balanced explicitly shortly before an update
burst, Vect is somewhat surprisingly faster
http://eigenclass.org/repos/oropes/head/set-balanced.png
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
http://eigenclass.org/repos/oropes/head/get.png
The above URL is a darcs repository, so if anybody shoots me a patch I'll be
happy to apply it :)
Regards,
--
Mauricio Fernandez - http://eigenclass.org
_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
Jon Harrop
> It is still young and experimental, but it's maybe worth a look. Any
> feedback is very welcome.
Looks awesome!
It seems to use mutation internally. Is it not thread safe?
I have some suggestions:
I'd like metadata in every node, so I can provide a constructor that combines
the metadata of child nodes and a cull function to accelerate searches.
The usual HOFs, like map.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e
Mauricio Fernandez
> On Sunday 29 July 2007 00:33:05 Mauricio Fernandez wrote:
> > It is still young and experimental, but it's maybe worth a look. Any
> > feedback is very welcome.
>
> Looks awesome!
>
> It seems to use mutation internally. Is it not thread safe?
The structure is persistent and all operations are non-destructive.
Mutation is used only in the rebalancing operation and in set, but they affect
an ephemeral forest of ropes/vects and a new string/array respectively, so the
original structure is never modified and in principle all operations should be
thread-safe.
Ropes/vects being functional doesn't mean that they will perform well in a
persistent setting however, see the clarification at
http://eigenclass.org/repos/oropes/head/doc/Vect.html
> I have some suggestions:
>
> I'd like metadata in every node, so I can provide a constructor that combines
> the metadata of child nodes and a cull function to accelerate searches.
If I understand it correctly, that scheme could in the limit turn some O(n)
searches into O(log n)?), right?
Unlike Vec, Vect uses "compact" leaves (Leaf of 'a array) of bounded size
(leaf_size, typically 16-64), which might not fit very well.
Vect would need to know how to combine the metadata, wouldn't it? I was
thinking about something like
Leaf of ('meta -> 'meta -> 'meta) * 'meta * 'a array
but I've realized that this wouldn't suffice. So, given that Vect.t is
currently
type 'a t =
Empty
| Concat of 'a t * int * 'a t * int * int
| Leaf of 'a array
something like this maybe?
type ('a, 'meta) t =
Empty of ('meta -> 'meta -> 'meta)
| Concat of ('meta -> 'meta -> 'meta) * 'meta *
('a, 'meta) t * int *
('a, 'meta) t * int *
int
| Leaf of ('meta -> 'meta -> meta) * 'meta array * 'a array
(* maybe also * 'meta to cache the last computation? *)
or even without the ('meta -> 'meta -> 'meta) part, forcing the user to pass
the function on each modification? Just thinking out loud.
At any rate, it'd be better to provide it as a separate structure, any
suggestions for the name?.
> The usual HOFs, like map.
I just pushed a patch with filter and map. The former is trivially implemented
with fold + append (thanks to the O(1) append). I was going to code map the
same way but I ended up making one that returns an isomorphic vect and is
faster (since there's no need to rebalance).
So Vect currently has iter, iteri, rangeiter, fold, map and filter. I'm
considering renaming fold to fold_left and providing fold_right too.
--
Mauricio Fernandez - http://eigenclass.org
_______________________________________________
Jon Harrop
> The structure is persistent and all operations are non-destructive.
> Mutation is used only in the rebalancing operation and in set, but they
> affect an ephemeral forest of ropes/vects and a new string/array
> respectively, so the original structure is never modified and in principle
> all operations should be thread-safe.
>
> Ropes/vects being functional doesn't mean that they will perform well in a
> persistent setting however, see the clarification at
>
> http://eigenclass.org/repos/oropes/head/doc/Vect.html
Ok.
> > I have some suggestions:
> >
> > I'd like metadata in every node, so I can provide a constructor that
> > combines the metadata of child nodes and a cull function to accelerate
> > searches.
>
> If I understand it correctly, that scheme could in the limit turn some O(n)
> searches into O(log n)?), right?
Something like that, yes.
> Unlike Vec, Vect uses "compact" leaves (Leaf of 'a array) of bounded size
> (leaf_size, typically 16-64), which might not fit very well.
I can think of two solutions:
1. Linear search.
2. Store an array of metadata corresponding to a binary search of the array of
elements in a leaf.
The latter sounds sexy but the former would probably suffice. :-)
> Vect would need to know how to combine the metadata, wouldn't it?
Users would have to provide a function to do that, yes.
> I was
> thinking about something like
> Leaf of ('meta -> 'meta -> 'meta) * 'meta * 'a array
> but I've realized that this wouldn't suffice. So, given that Vect.t is
> currently
>
> type 'a t =
> Empty
>
> | Concat of 'a t * int * 'a t * int * int
> | Leaf of 'a array
>
> something like this maybe?
>
> type ('a, 'meta) t =
> Empty of ('meta -> 'meta -> 'meta)
>
> | Concat of ('meta -> 'meta -> 'meta) * 'meta *
>
> ('a, 'meta) t * int *
> ('a, 'meta) t * int *
> int
>
> | Leaf of ('meta -> 'meta -> meta) * 'meta array * 'a array
>
> (* maybe also * 'meta to cache the last computation? *)
>
> or even without the ('meta -> 'meta -> 'meta) part, forcing the user to
> pass the function on each modification? Just thinking out loud.
I would use a functor to pass it the "combine" and "cull" functions, rather
than putting them in the tree itself. This is analogous to the Set.Make
functor accepting a comparison function.
> At any rate, it'd be better to provide it as a separate structure, any
> suggestions for the name?.
You could just call it Tree and try to make it as generic as possible.
You could then reimplement the Set module on top of your data structure by
searching for the index of the given element and inserting it if it is new.
Hmm, maybe a function that combines a search with an update (to avoid two
traversals) would be a good idea...
> > The usual HOFs, like map.
>
> I just pushed a patch with filter and map. The former is trivially
> implemented with fold + append (thanks to the O(1) append). I was going to
> code map the same way but I ended up making one that returns an isomorphic
> vect and is faster (since there's no need to rebalance).
Yes. You could also use recursive subdivision to create a perfectly balanced
result.
> So Vect currently has iter, iteri, rangeiter, fold, map and filter. I'm
> considering renaming fold to fold_left and providing fold_right too.
I'd definitely provide both folds, yes.
I'd also like specialized rewrite functions that avoid allocations when the
outputs are the same as the inputs. So I'd make the set function bail via an
exception when the element is left unchanged, returning the original Vect and
doing no allocation in this case. I'd also like an id_map function that did a
map but reused old branches whenever they were left unchanged.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e
_______________________________________________
Mauricio Fernandez
> On Monday 30 July 2007 12:51:29 Mauricio Fernandez wrote:
> > > I'd like metadata in every node, so I can provide a constructor that
> > > combines the metadata of child nodes and a cull function to accelerate
> > > searches.
> >
> > If I understand it correctly, that scheme could in the limit turn some O(n)
> > searches into O(log n)?), right?
>
> Something like that, yes.
>
> > Unlike Vec, Vect uses "compact" leaves (Leaf of 'a array) of bounded size
> > (leaf_size, typically 16-64), which might not fit very well.
>
> I can think of two solutions:
>
> 1. Linear search.
>
> 2. Store an array of metadata corresponding to a binary search of the array of
> elements in a leaf.
>
> The latter sounds sexy but the former would probably suffice. :-)
Yes, linear search over <100 elements should be acceptable if the
structure is to hold several orders of magnitude more...
> > something like this maybe?
> >
[...]
> > | Leaf of ('meta -> 'meta -> meta) * 'meta array * 'a array
> >
> > (* maybe also * 'meta to cache the last computation? *)
> >
> > or even without the ('meta -> 'meta -> 'meta) part, forcing the user to
> > pass the function on each modification? Just thinking out loud.
>
> I would use a functor to pass it the "combine" and "cull" functions, rather
> than putting them in the tree itself. This is analogous to the Set.Make
> functor accepting a comparison function.
You're very right, a functor makes so much more sense here: it saves one word
per node and allows stronger typing (the alternative would be ugly, lots
of if mycombine != hiscombine then invalid_arg "operation" and errors found at
run-time).
So combine would be combine : 'meta -> 'meta -> 'meta; commutative and
associative, so that it can be used in leaves as
Array.fold_left combine arr default
which shows that a default value for the metadata would have to be provided
too.
What about cull? a control_cull : 'meta -> bool that tells the vect whether
the search goes on recursively for each node (so the search is carried out by
a function in Vect) , or a function that handles recursion itself, using some
get_metadata : ('a, 'meta) t -> 'meta ? It seems the latter could lead to a
leaky abstraction though. Which type would it have anyway? Both
('a, 'meta) t -> 'a and say ('a, 'meta) t -> 'a list could be useful (the
former can be used for find and the latter e.g. for select).
> > At any rate, it'd be better to provide it as a separate structure, any
> > suggestions for the name?.
>
> You could just call it Tree and try to make it as generic as possible.
>
> You could then reimplement the Set module on top of your data structure by
> searching for the index of the given element and inserting it if it is new.
For the sake of better space efficiency? Set uses 5 words per element, but it
could be brought down to 3.5 words by adding a new constructor. Still, Vect's
~1.125 to ~2.0 would remain considerably better.
It'd be great to find a way to make good use of the O(1) append to improve
on Set's logarithmic bounds, but I can't see how right now (again, it's late :)
> > > The usual HOFs, like map.
> >
> > I just pushed a patch with filter and map. The former is trivially
> > implemented with fold + append (thanks to the O(1) append). I was going to
> > code map the same way but I ended up making one that returns an isomorphic
> > vect and is faster (since there's no need to rebalance).
>
> Yes. You could also use recursive subdivision to create a perfectly balanced
> result.
The problem is that the obvious implementation, using Array, would run against
the max_array_length limit. Avoiding it is pretty easy but there are still
a few more interesting things to be done :)
> > So Vect currently has iter, iteri, rangeiter, fold, map and filter. I'm
> > considering renaming fold to fold_left and providing fold_right too.
>
> I'd definitely provide both folds, yes.
>
> I'd also like specialized rewrite functions that avoid allocations when the
> outputs are the same as the inputs. So I'd make the set function bail via an
> exception when the element is left unchanged, returning the original Vect and
> doing no allocation in this case. I'd also like an id_map function that did a
> map but reused old branches whenever they were left unchanged.
I've renamed fold to fold_left and added fold_right as well as
id_map : ('a -> 'a) -> 'a t -> 'a t.
Last but not least, I've added destructive_set : int -> 'a -> 'a t -> unit.
It's evil but so much faster...
http://eigenclass.org/repos/oropes/head/set-balanced.png
It brings Vect one order of magnitude closer to Array for ephemeral usage.
--
Mauricio Fernandez - http://eigenclass.org
_______________________________________________
Jon Harrop
Incidentally, this data structure is a completely generic sequence. I think it
would be extremely valuable to provide pattern matching over such a sequence.
This could be done either using the active patterns macro or by adding a new
macro (that could also allow sequence literals). I did something similar for
the original Vec data structure (independently).
On Wednesday 01 August 2007 00:55:14 Mauricio Fernandez wrote:
> Yes, linear search over <100 elements should be acceptable if the
> structure is to hold several orders of magnitude more...
Yes. After all, this optimization is replacing linear search anyway...
> You're very right, a functor makes so much more sense here: it saves one
> word per node and allows stronger typing (the alternative would be ugly,
> lots of if mycombine != hiscombine then invalid_arg "operation" and errors
> found at run-time).
Exactly.
> So combine would be combine : 'meta -> 'meta -> 'meta; commutative and
> associative, so that it can be used in leaves as
> Array.fold_left combine arr default
> which shows that a default value for the metadata would have to be provided
> too.
Sounds good.
> What about cull? a control_cull : 'meta -> bool that tells the vect
> whether the search goes on recursively for each node (so the search is
> carried out by a function in Vect) , or a function that handles recursion
> itself, using some get_metadata : ('a, 'meta) t -> 'meta ? It seems the
> latter could lead to a leaky abstraction though. Which type would it have
> anyway? Both
> ('a, 'meta) t -> 'a and say ('a, 'meta) t -> 'a list could be useful
> (the former can be used for find and the latter e.g. for select).
What about writing the search in continuation passing style. So the search
function calls a continuation with a left, current and right just like the
recursive call within "Set.find".
On a related note, I think the Set module would be much more powerful if the
choose function chose a roughly central element by extracting from the root.
Not only is this faster, it allows many more algorithmic optimizations to be
performance from outside Set by recursively choosing and splitting. I think
the set-theoretic operations could then be implemented from outside the AVL
tree.
> > You could then reimplement the Set module on top of your data structure
> > by searching for the index of the given element and inserting it if it is
> > new.
>
> For the sake of better space efficiency?
And performance. The current Set implementation performs huge amount of
unnecessary allocations and is an order of magnitude slower than hashset as a
consequence. Your rope-based implementation could close that gap considerably
without sacrificing the purely functional style.
> Set uses 5 words per element, but
> it could be brought down to 3.5 words by adding a new constructor. Still,
> Vect's ~1.125 to ~2.0 would remain considerably better.
> It'd be great to find a way to make good use of the O(1) append to improve
> on Set's logarithmic bounds, but I can't see how right now (again, it's
> late :)
There are lots more potential improvements, like adding a set_of_array
function that avoids repeated insertion.
> > Yes. You could also use recursive subdivision to create a perfectly
> > balanced result.
>
> The problem is that the obvious implementation, using Array, would run
> against the max_array_length limit. Avoiding it is pretty easy but there
> are still a few more interesting things to be done :)
I'd forget about it to be honest. In 2 years, most desktops will be 64-bit...
> Last but not least, I've added destructive_set : int -> 'a -> 'a t -> unit.
> It's evil but so much faster...
> http://eigenclass.org/repos/oropes/head/set-balanced.png
> It brings Vect one order of magnitude closer to Array for ephemeral usage.
Cool.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e
_______________________________________________
Nathaniel Gray
> 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
> Vec.
>
>
> You can find the code for both Rope and Vect at
> http://eigenclass.org/repos/oropes/head/
> It is still young and experimental, but it's maybe worth a look. Any feedback
> is very welcome.
>
> The documentation can be found under
> http://eigenclass.org/repos/oropes/head/doc/
This looks pretty nice! I don't have an immediate need for it but
it's a good thing to have in the toolbox.
Thanks,
-n8
--
>>>-- Nathaniel Gray -- Caltech Computer Science ------>
>>>-- Mojave Project -- http://mojave.cs.caltech.edu -->
Luca de Alfaro
One small question: someone suggested me to rewrite Vec to add a Leaf
(Node_without_children) construct, to cut down on the number of Empty
instances I use. I have so far not done that (no reason in particular, but
I was busy with other things). In light of your experiments, would you also
advise me to do it?
All the best,
Luca
On 7/28/07, Mauricio Fernandez <m...@acm.org> wrote:
>
skaller
> Great work!
>
> One small question: someone suggested me to rewrite Vec to add a Leaf
> (Node_without_children) construct, to cut down on the number of Empty
> instances I use. I have so far not done that (no reason in
> particular, but I was busy with other things). In light of your
> experiments, would you also advise me to do it?
You should look at Judy arrays. They don't require rebalancing.
The current implementation is mutable -- it would be very interesting
to see a functional version.
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net