Jimmy Zhuo jimmy.zhuo at
Mon Sep 5 13:19:19 UTC 2011

I don't know how to binary search it, it's not an ordered array.

On Sep 4, 10:38 pm, Jonathan Worthington <jonat... at> wrote:
> 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.
> Thanks,
> Jonathan
> _______________________________________________

More information about the parrot-dev mailing list