Re: Ann: Natools.Chunked_Strings, beta 1

[Natasha Kerensikova <lithiumcat@gmail.com>]

On 2011-11-29, Georg Bauhaus <rm.dash-bauhaus@futureapps.de> wrote:
> The package GNAT.Spitbol.Patterns uses Unbounded_String extensively.
> Last time I checked it seemed possible to replace the dependence
> on Ada.Strings.Unbounded with one on a compatible package.
> The very first definition in GNAT.Spitbol is
>
>    subtype VString is Ada.Strings.Unbounded.Unbounded_String;
>
> It should be sufficient to change this definition and
>
>    Nul : VString renames Ada.Strings.Unbounded.Null_Unbounded_String;
>
> to use your strings, in local copies of the sources of the
> GNAT.Spitbol hierarchy.

Also To_Unbounded_String has to be replaced by To_Chunked_String, but
this is also conveniently renamed at the same place.

> Of particular interest might be, I think, anything that can improve
> replacement in objects of type Unbounded_String.

It seems we are talking about the transformation of
Prefix & Old & Suffix into Prefix & Replacement & Suffix, with
Old'Length /= Replacement'Length. In that case, Chunked_String is
probably not an improvement over Unbounded_String, since in both cases
the whole Suffix has to be moved, so they should be of similar speed
with a slight advantage for Unbounded_String because the contiguous
memory is more cache-friendly.

However it seems to be the kind of use-cases for which ropes were
designed. So it leads to the question, is there already an Ada
implementation of ropes somewhere?

Assuming there isn't, I wouldn't mind starting one. It seems to be an
interesting toy problem.

When thinking about it, the first tricky part I identified is dealing
with reference-counted object in a thread-safe way (the original paper
assumed a garbage collector). It will probably involve writing tree
algorithms from scratch (to efficiently preserve the rope invariant when
rebalancing or rotating), so I will end up with accesses to reference
counted nodes. I guess using a protected type for nodes will take care
of the thread safety, but I will need to somehow indicate whether I'm
dereferencing the access for reading or for read/write. I might be an
interesting concurrency exercise, but I don't really know how to
properly test it.



Thanks for your interest,
Natasha