On Saturday, 2 May 2015 at 06:28:01 UTC, 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!


From the doc:

If ParentAllocator defines (deallocate|allocate), ...

I forget what the rules are for allocators exactly, but isn't something only an allocator if it defines allocate, deallocate, owns, etc.? It just seems weird that you mentioned something that I thought was implicit.

Reply via email to