FreeTree eviction strategy

Andrei Alexandrescu via Digitalmars-d digitalmars-d at puremagic.com
Mon May 4 10:56:36 PDT 2015


So I'm toying around with a promising structure that I call "free tree" 
for std.allocator. There's some detail with code and docs here: 
http://forum.dlang.org/thread/mi1qph$cgr$1@digitalmars.com.

A free tree allocator is akin to a free list. Instead of just a singly 
linked list, it also maintains a binary search tree sorted by size. So 
each free chunk contains the size, the "next" node, and "left"/"right" 
children.

Insertion in the free tree is done to the root, i.e. the newly inserted 
block becomes the root. Just like the free list. So we got nice locality 
etc. and no need to worry about rebalancing. Code came in really small 
and clean, textbook-like.

All in all free tree is like an adaptive battery of freelists - it just 
adapts to whichever sizes you allocate the most.

And herein lies the danger. As allocation patterns come and go, chunks 
of less-frequently-used lengths get pushed toward the leaves of the tree 
and there's nothing to limit growth. So we have fragmentation because 
the free tree is holding onto all those old chunks etc.

What's needed is a good eviction strategy that's cheap (e.g. doesn't 
require me to hold age info or run complex algos) and effective. One 
hamfisted solution is to just blow away the tree once in a while (e.g. 
when it gets to a specific size or after some time/number of 
allocations) but I feel there's something more principled out there.

I'd love to hear your thoughts.


Thanks,

Andrei


More information about the Digitalmars-d mailing list