[hackathon] FreeTree is FreeList on autotune

[Andrei Alexandrescu via Digitalmars-d-announce]

On 5/5/15 2:23 PM, Timon Gehr wrote:
> On 05/02/2015 08:28 AM, Andrei Alexandrescu wrote:
>> I'm just done implementing a pretty cool allocator: FreeTree.
>>
>> https://github.com/andralex/phobos/blob/allocator/std/experimental/allocator/free_tree.d
>>
>>
>>
>> http://erdani.com/d/phobos-prerelease/std_experimental_allocator_free_tree.html
>>
>>
>>
>> It's similar to the classic free list allocator but instead of a
>> singly-linked list it uses a binary search tree for accommodating blocks
>> of arbitrary size. The binary search tree accommodates duplicates by
>> storing one extra pointer for each node, effectively embedding a
>> singly-linked list (a free list really) for each node.
>>
>> So a FreeTree is have a bunch of freelists organized in a binary search
>> tree. The tree is not balanced; instead, it uses an LRU heuristic - each
>> freed block is inserted as (or close to) the root. Over the lifetime of
>> a free tree, free lists naturally appear and disappear as dictated by
>> the sizes most frequently allocated by the application.
>>
>> Feedback is welcome!
>>
>>
>> Andrei
>
> - Perhaps it would make sense to splay instead of rotating to root?

As per https://en.wikipedia.org/wiki/Splay_tree? Interesting, I'll look 
into it.

> - I think the destructor only compiles if the parent allocator defines
> the 'deallocate' method.

Will fix.

> - The first static if should check for "deallocate", right?
>
>      static if (hasMember!(ParentAllocator, "deallocateAll"))
>      void deallocateAll()
>      {
>          static if (hasMember!(ParentAllocator, "deallocateAll"))

Will fix.

> - The implementation of 'allocate' appears to be buggy: If no memory
> block of a suitable size is found, the entire free tree is released.
> (There is only one occurrence of parent.allocate in the code and it
> appears right after a call to 'clear'.) If the parent allocator does not
> define the 'deallocate' method, the allocator will always return 'null'
> instead.

The idea here is that if no memory block is found in either the tree or 
the parent, the memory the tree is holding to is useless and fragments 
the parent unnecessarily. So the entire tree is thrown away, returning 
memory to the parent. Then allocation from the parent is tried again 
under the assumption that the parent might have coalesced freed memory.

If the parent doesn't define deallocate, it can't accept back the memory 
kept by the tree.

LMK if I'm missing something.


Thanks for the review!

Andrei