In the general case a rope is a tree, in the common "append string to
the end of rope" case it degenerates to a list.
Concatenation of ropes results in a tree.
I would just do it in core.
Kevin
Will Coleda wrote:
How would this PMC differ from the ResizableStringArray?
I'd hate to have to go out of core to get fast string manipulation.
On Thu, Apr 22, 2010 at 12:34 PM, Jonathan Leto <[email protected]> wrote:
Howdy,
A Rope PMC sounds like a great idea. Should it be developed in core,
or perhaps in Parrot-Data-Structures [0] ? That way a few different
implementations of the Rope PMC can be written and benchmarked, and
the most versatile implementation can be pushed back to core. I would
be willing to help with this.
Duke
[0] - http://github.com/Whiteknight/parrot-data-structures
On Thu, Apr 22, 2010 at 6:56 AM, Kevin Tew <[email protected]> wrote:
This is really a simple data structure problem, with a well known solution.
Theses use cases should be using ropes not strings.
http://en.wikipedia.org/wiki/Rope_(computer_science)
Ropes really are just a generalization of a StringBuffer or chromatics RSA
trick.
If you eventually output a rope to a stream (say a file stream) there is no
need to ever flatten or allocate space for the entire stream.
Apache's buckets is another well know example of where this idea is used.
We should add a rope PMC that has a flatten to string and write to stream
operations.
Kevin
Patrick R. Michaud wrote:
On Thu, Apr 22, 2010 at 08:04:39AM -0400, Andy Dougherty wrote:
This does bring up another question, however. The old concatenation
scheme used to work; now it doesn't. (Or, more precisely, it works on small
files, but not on large ones.) Should I open a separate ticket on the
inefficiency of concatenation in the new immutable strings era, or was
pbc_to_exe's use so pathological that it's not worth worrying about?
The compiler toolkit does a lot of concatenation in order to generate
the PIR that ultimately gets compiled.
The POST compiler converts each POST::Op node into the appropriate
PIR statement (a string), and concatenates these strings together
to produce the final PIR output. So I suspect it's worth looking into.
Pm
_______________________________________________
http://lists.parrot.org/mailman/listinfo/parrot-dev
_______________________________________________
http://lists.parrot.org/mailman/listinfo/parrot-dev
--
Jonathan "Duke" Leto
[email protected]
http://leto.net
_______________________________________________
http://lists.parrot.org/mailman/listinfo/parrot-dev
_______________________________________________
http://lists.parrot.org/mailman/listinfo/parrot-dev
