On 05/27/2010 11:01 AM, Pillsy wrote:
== Quote from Andrei Alexandrescu
([email protected])'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
