The Problems On Free List Allocator in phobos and My Improve Ideas

[xiaoyu]

I recently tried to use the free-list allocator in the standard 
library, but encountered some problems during use.Then I 
inspected this part of the code and found some other problems.

The pronlems are below:

1. When allocations are frequent and the size fluctuates greatly, 
it is easy to degenerate into only a proxy of the parent 
allocator and cannot make good use of free memory blocks.

2. When the memory size to be allocated is not in the `[min, 
max]` range, it instead requests the parent allocator to 
allocate, but this is unreasonable. This unreasonable request 
should be rejected and `null` should be returned.

3. The `allocateZeroed` method does not necessarily depend on the 
parent allocator's `allocateZeroed`.

4. It is not reasonable to directly forward the `expand` and 
`reallocate` methods of parent allocator.In fact, `expand` does 
not depend on the `expand` of parent allocator, and this also 
isolates the possibility of `alignedExpand` and 
`alignedReallocate`.

5. It cannot perfectly cope with situations where it does not 
exclusively onws the parent allocator.For example, when the 
free-list allocator does not exclusively onws the parent 
allocator, method `owns` may regard blocks allocated by other 
allocators that rely on the same parent allocator as being 
allocated by itself. Allocator's `deallocate` and `deallocateAll` 
have the same problem.


My ideas for improvement are as follows:

1. Add a field called `volum` for `Node`, indicating the memory 
size allocated by this block excluding `Node`, and the memory 
occupied by `Node` will not be overwritten. That is to say, when 
the block where `Node` is located is allocated, the memory 
occupied by `Node` itself will not be overwritten.

2. The free-list allocator maintains two linked lists internally, 
one representing the free memory block linked list, and the other 
representing the allocated memory block linked list. The free 
memory block linked list is sorted and inserted according to the 
size of the corresponding `volum` from small to large.

3. When an allocation request occurs, it will first try to search 
in the free memory block linked list. Because this linked list is 
sorted, it can allocate the memory block with the most suitable 
size relatively quickly. If a suitable memory block is found, it 
will be allocated and put the `Node` corresponding to this memory 
block at the beginning of the allocated-list, otherwise forward 
the request to the parent, construct a `Node`, and put this 
`Node` at the beginning of the allocated-list. If the adaptive 
mode is turned on, there will be some additional optimization 
operations during this period.

4. When choosing to `deallocate` a memory block, it will first 
check whether the block is being managed on the allocated-list 
(this is also the implementation logic of `owns`). If it is 
`true`, the block will be removed and inserted into the 
free-list. This operation It does not really return the memory 
block to the parent. The same is true for deallocateAll. This 
method inserts all memory blocks managed by allocated-list into 
free-list for future allocation requests.

5. When this allocator is destroyed, the memory blocks managed by 
the two linked lists will be returned to the parent. Of course, 
you can also manually reduce the length of the free-list.

6. Then based on the above ideas, I provide `alignedAllocate`, 
`alignedExpand` and `alignedRellocate`, `resolveInternalPointer`.


This is just a general idea. For details, you can check out the 
code I improved on `https://github.com/malyjacob/free-list`. 
There are comments and explanations in it. Of course, I only 
improved the non-thread safe parts. If possible, the thread safe 
version can also adopt this improvement idea.