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

[Andrei Alexandrescu via Digitalmars-d]

On 5/21/15 10:18 AM, "=?UTF-8?B?Ik3DoXJjaW8=?= Martins\" 
<marcioapm at gmail.com>\"" wrote:
> 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)

Yah, I think that's a good idea. The size of the generated code was 
getting worrisome. Thanks! -- Andrei