Rope PMC (was Re: Why has pbc_to_exe become unusable?)

Will Coleda will at coleda.com
Thu Apr 22 16:44:36 UTC 2010


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 <jaleto at gmail.com> 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 <tewk at tewk.com> 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
> jonathan at leto.net
> http://leto.net
> _______________________________________________
> http://lists.parrot.org/mailman/listinfo/parrot-dev
>



-- 
Will "Coke" Coleda


More information about the parrot-dev mailing list