The problem I see with an array approach from an api perspective is simply when a bucket
is free'd, in order to have efficient memory usage, we'd need a second level array scan
for every ALLOC_ZVAL().
Perhaps a linked list would be a better choice for this, as we can just be smart about bucket
access, and eliminate the need for a scan (could be possible I'm missing something?)
A number of memory allocators use a multi-tiered page table for this. basically for each object type you have a array of N pointers to level 1 objects and a freelist for them, basically tier one has N elements that each contain a freelist bitmask value and an array of pointers to level 2 objects. Level 2 objects have a freelist of N allocations for the desired object type and pointers to each of them. This may be what Andi was talking about, but it wasn't clear to me from his description.
So you get N^3 aloocations you can track, and a freelist search involves looking at 3 bitmasks. Significantly faster than a linked list implementation. By keeping a separate tree for each allocation type (or at least allocation size), you also end up with basically no fragmentation.
-Sterling
-- PHP Development Mailing List <http://www.php.net/>
To unsubscribe, visit: http://www.php.net/unsub.php