[hackathon] FreeTree is FreeList on autotune

[Timon Gehr via Digitalmars-d-announce]

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?

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

- The first static if should check for "deallocate", right?

     static if (hasMember!(ParentAllocator, "deallocateAll"))
     void deallocateAll()
     {
         static if (hasMember!(ParentAllocator, "deallocateAll"))

- 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.