[hackathon] FreeTree is FreeList on autotune

[Timon Gehr via Digitalmars-d-announce]

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!