std.container update

[Andrei Alexandrescu]

On 05/27/2010 11:01 AM, Pillsy wrote:
> == Quote from Andrei Alexandrescu
> (SeeWebsiteForEmail at erdani.org)'s article:
>> I just implemented a singly-linked list type to illustrate
>> the container abstraction.
>> http://erdani.com/d/phobos/std_container.html
>> http://erdani.com/d/phobos/container.d
> [...]
>> Please let me know of how you find it.
>
> One thing worries me a bit, but may be based on a misunderstanding
> of how D's GC works. In dup, you allocate all the nodes at once as
> an array and then go through them one by one setting their payload_
> and next_ values to make the list.
>
> My worry is that the array is allocated as a single block and
> (presumably) GC'd as a single block. If I copy a 1000 element list
> and then remove 999 elements from the front using removeFront(),
> won't I end up leaking memory for the first 999 nodes?

There are indeed tradeoffs associated with allocation of nodes that way. 
Technically that's not a leak, but indeed the entire block will stay put 
for as long as at least one node in it it's used.

One improvement would be to put removed nodes in a static freelist to be 
used by all SLists of the same type in the current thread. In that case, 
remove becomes unstable.

I think I hastened a bit with that optimization, it's debatable and 
detracts from the main point of the discussion.


Andrei