[hackathon] FreeTree is FreeList on autotune

[Andrei Alexandrescu via Digitalmars-d-announce]

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