rt_finalize WTFs?

[Martin Nowak]

On Tue, 06 Dec 2011 00:16:01 +0100, dsimcha <dsimcha at yahoo.com> wrote:

> == Quote from Martin Nowak (dawg at dawgfoto.de)'s article
>> > More promising is to put pool addresses ranges in a trie.
>> >
>> > addr[7]          [...      .     ...]
>> >                       /     |    \
>> > addr[6]     [...   .   ...]    [...   .   ...]
>> >                 /   |    \         /   |   \
>> > addr[5]     pool:8             [...   .  ...]
>> >                                /   |   \
>> > addr[4]                  pool:8 [....] pool:5
>> >
>> Actually 64-bit should use a hashtable for the upper 32-bit and then
>> the the 32-bit trie for lower.
>
> Why do you expect this to be faster than a binary search?  I'm not  
> saying it won't
> be, just that it's not a home run that deserves a high priority as an
> optimization.  You still have a whole bunch of indirections, probably  
> more than
> you would ever have for binary search.

It's the tightest loop in the garbage collector.
It will end with few array accesses and the locality of
memory being pointed too is paired by tree locality,
thus you'd have good chances to finding them in the cache.

What this gives you is that it scales very good to many pools/regions.
Thus you can better tweak the pool granularity against pool sizes.

Also:
for (p < pend)
   if (*p in lastPool)
can be:
for (p < pend)
   if (*p in lastNode)

It is definitely no home run, but I'll try it
out when I find some time.