Jonathan Worthington jonathan at
Sun Sep 4 14:38:39 UTC 2011

On 04/09/2011 11:18, Nicholas Clark wrote:
> On Sun, Sep 04, 2011 at 01:06:47AM +0200, Jonathan Worthington wrote:
>> One obvious fix would be to just keep an extent list: an array of
>> (start,end) pairs, hanging off the pool header, which we can very
>> cheaply scan through (since it's just a bunch of values laid out
>> contiguously in memory). That way, we don't go chasing all over RAM, and
> I think you can binary search it, as it's effectively an inversion list.
> O(log n) will beat O(n) for any non-trivial size :-)
Yeah, that would probably be an additional win. Takers wanted. :-)

That said, it turns out even the naive O(n) way is very than worth doing 
- tadzik++ reported a somewhat scary 25% improvement in compiling the 
rakudo/nom setting after this, and the function in question has fallen 
way down my profiler output.



More information about the parrot-dev mailing list