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