SeeWebsiteForEmail at erdani.org
Thu May 27 10:54:08 PDT 2010
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.
>> 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.
More information about the Digitalmars-d