Ropes and rope-like functional extensible vectors with O(1) prepend/append.

Ropes and rope-like functional extensible vectors with O(1) prepend/append.

[Mauricio Fernandez]

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.

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

Re: [Caml-list] Ropes and rope-like functional extensible vectors with O(1) prepend/append.

[Jon Harrop]

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?

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

Re: [Caml-list] Ropes and rope-like functional extensible vectors with O(1) prepend/append.

[Mauricio Fernandez]

On Mon, Jul 30, 2007 at 01:46:20AM +0100, Jon Harrop wrote:
> 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

Re: [Caml-list] Ropes and rope-like functional extensible vectors with O(1) prepend/append.

[Jon Harrop]

On Monday 30 July 2007 12:51:29 Mauricio Fernandez wrote:
> 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

Re: [Caml-list] Ropes and rope-like functional extensible vectors with O(1) prepend/append.

[Mauricio Fernandez]

On Mon, Jul 30, 2007 at 02:47:23PM +0100, Jon Harrop wrote:
> 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

Re: [Caml-list] Ropes and rope-like functional extensible vectors with O(1) prepend/append.

[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

Re: [Caml-list] Ropes and rope-like functional extensible vectors with O(1) prepend/append.

[Nathaniel Gray]

On 7/28/07, Mauricio Fernandez <mfp@acm.org> wrote:
> 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 -->

Re: [Caml-list] Ropes and rope-like functional extensible vectors with O(1) prepend/append.

[Luca de Alfaro]

[-- Attachment #1: Type: text/plain, Size: 3839 bytes --]

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?

All the best,

Luca

On 7/28/07, Mauricio Fernandez <mfp@acm.org> wrote:
>
> 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.
>
> 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
>

[-- Attachment #2: Type: text/html, Size: 5118 bytes --]

Re: [Caml-list] Ropes and rope-like functional extensible vectors with O(1) prepend/append.

[skaller]

On Tue, 2007-08-21 at 14:39 -0700, Luca de Alfaro wrote:
> 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