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

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

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.

On 5/2/15 4:11 AM, Meta wrote:
> 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.

All members except alignment and allocate are optional. There are allocators that can't deallocate, such as Region. -- Andrei

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.

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

On 5/5/15 2:23 PM, Timon Gehr wrote:
> - Perhaps it would make sense to splay instead of rotating to root?

Just read the wikipedia article... haven't done anything related to splay trees since college!

Looks like my code effectively implements a splay tree for the simple reason that all successful find operations are followed by remove, and all insertions are at root.

Per Wikipedia:

* Insertion
To insert a value x into a splay tree:

Insert x as with a normal binary search tree.
Splay the newly inserted node x to the top of the tree.

(my note: that's what I do, and I suspect for a leaf rotating to the root is identical to splaying to the root)

ALTERNATIVE:

Use the split operation to split the tree at the value of x to two sub-trees: S and T.
Create a new tree in which x is the root, S is its left sub-tree and T its right sub-tree.

* Deletion

To delete a node x, use the same method as with a binary search tree: if x has two children, swap its value with that of either the rightmost node of its left sub tree (its in-order predecessor) or the leftmost node of its right subtree (its in-order successor). Then remove that node instead. In this way, deletion is reduced to the problem of removing a node with 0 or 1 children. Unlike a binary search tree, in a splay tree after deletion, we splay the parent of the removed node to the top of the tree.

(my note: that's what I do except the splaying the parent part, which I need to think whether it's useful)

(Another note: I need to optimize for the pattern remove node/reinsert same node, perhaps with a quick test upon insertion whether I can just make the new node the root.)


Andrei

On 05/07/2015 04:49 PM, Andrei Alexandrescu wrote:
>
>> - 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.
>

The comment says:

"Allocates $(D n) bytes of memory. First consults the free tree, and returns from it if a suitably sized block is found. Otherwise, the parent allocator is tried. If allocation from the parent succeeds, the allocated block is returned. Otherwise, the free tree tries an alternate strategy: If $(D ParentAllocator) defines $(D deallocate), $(D FreeTree) releases all of its contents and tries again."


Unless I am the one missing something, the implementation does the following instead:

"Allocates $(D n) bytes of memory. First consults the free tree, and returns from it if a suitably sized block is found. Otherwise, the free tree tries an alternate strategy: If $(D ParentAllocator) defines $(D deallocate), $(D FreeTree) releases all of its contents and tries again."

(findAndRemove never allocates new memory from the parent, it just gets you memory already stored in the tree, if the right allocation size is present.)


>
> Thanks for the review!

My pleasure!