On 05/02/2015 08:28 AM, Andrei Alexandrescu wrote:
I'm just done implementing a pretty cool allocator: FreeTree.



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!


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

Reply via email to