www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - [hackathon] FreeTree is FreeList on autotune

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
May 01 2015
next sibling parent reply "Meta" <jared771 gmail.com> writes:
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.
May 02 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
May 02 2015
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.
May 05 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
May 07 2015
parent Timon Gehr <timon.gehr gmx.ch> writes:
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!
May 09 2015
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
May 07 2015