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
