Re: [hackathon] FreeTree is FreeList on autotune
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!
Re: [hackathon] FreeTree is FreeList on autotune
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
Re: [hackathon] FreeTree is FreeList on autotune
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
Re: [hackathon] FreeTree is FreeList on autotune
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.
Re: [hackathon] FreeTree is FreeList on autotune
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
Re: [hackathon] FreeTree is FreeList on autotune
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.
[hackathon] FreeTree is FreeList on autotune
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
