www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - FreeTree eviction strategy

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
May 04 2015
next sibling parent Rikki Cattermole <alphaglosined gmail.com> writes:
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.
May 04 2015
prev sibling parent "Chris" <wendlec tcd.ie> writes:
On Monday, 4 May 2015 at 17:56:23 UTC, 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


Taking the tree analogy further, would it be possible to have 
autumn (fall) for the leaves. Either the tree gets rid of old 
leaves (as in nature) or the leaves have some self-destruction 
mechanism like cells in the body.
May 05 2015