Deque impl.

[Andrei Alexandrescu]

On 1/31/13 4:47 PM, bearophile wrote:
> For some usage patterns a freelist (used with an pointer carved out of
> the chunk itself) that keeps few of the last used chunks (it's usually
> not necessary to keep them all) is handy. For some other usages the
> freelist doesn't give you much, and it's just added complexity.
>
> If you keep using the structure as a queue, you keep adding from one
> side and remove from the other. In this case the circular queue of
> pointers to chunks works well, but you risk freeing and adding blocks
> all the time, for no purpose. Even keeping and reusing just one free
> chunk, "moving" it from one end to the other, avoids all/most memory
> allocations during the steady length state.

That works assuming a relatively slow allocator, which historically was 
the case with C++ and is the case with D. More recently C++ allocator 
have improved greatly and people complained that STL containers were 
hoarding memory, so many implementations abandoned freelists.

Anyhow, right now the freelist does sound like a good call for D.

DO IT!!!


Andrei