FreeTree eviction strategy

Rikki Cattermole via Digitalmars-d digitalmars-d at puremagic.com
Mon May 4 18:38:41 PDT 2015


On 5/05/2015 5:56 a.m., Andrei Alexandrescu wrote:
> 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

This may sound crazy BUT:

struct MyPointer {
	void* ptr;
	alias ptr this;
}

void* allocate() {
	// do the actual allocation
	MyPointer* ret = new MyPointer(thePtr);// something better?
	// store ret
	return ret;
}

void cleaner() {
	MyPointer*[] toMerge;
	foreach(pointer; pointers) {
		// detect small but mergable items
	}
	foreach(toM; toMerge) {
		// re assign the ptr
	}
}

In essence make small allocations big by reallocating them to be bigger.


More information about the Digitalmars-d mailing list