std.allocator: FreeList uses simple statistics to control number of items

[via Digitalmars-d]

On Thursday, 21 May 2015 at 15:17:03 UTC, Andrei Alexandrescu 
wrote:
> [snip]

Could something like this work for the statistics part?

enum AdaptabilityWindow	= 256;
enum AdaptabilitySpeed	= 2; // log2 of rescaling divisor


	if (hit) ++hitCount;
	else ++missCount;

	if ((hitCount + missCount) >= Adaptability) {
		hitCount >>= AdaptabilitySpeed;
		missCount >>= AdaptabilitySpeed;
	}
	
	// hitCount/(hitCount + missCount) and missCount / (hitCount + 
missCount) are a decent approximation of p(hit) and p(miss) given 
recent history
	// if you can make decisions just by comparing them then you 
don't have to perform expensive divisions

This is based on re-scaling frequencies, similar to what you'd 
find in model-based compression algorithms.

With it you could try to always keep a minimum reserve of blocks 
just in case, and when freeing a block of fit size make the 
decision about keeping it in the free-list if the tendency or 
returning it to the parent if the tendency is to allocate bad 
sizes.

To incrementally reduce the big free-list, you could just reduce 
the free-list size by a factor proportional to p(miss) - p(hit)