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
_______________________________________________
http://lists.parrot.org/mailman/listinfo/parrot-dev
