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

Kevin Tew tewk at tewk.com
Thu Apr 22 16:50:51 UTC 2010


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 <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
>>
>>     
>
>
>
>   



More information about the parrot-dev mailing list