www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Difference between DList and SList from garbage collector point of

reply Alexandr Druzhinin <drug2004 bk.ru> writes:
I used in my application DList (code is large and I couldn't reduce it) 
and the application allocates memory always. I can not realize why and 
don't know it now. But when I replaced DList by SList (and even dynamic 
array) memory leaks disappeared at all and all works as expected. I know 
it is hard to help me without code but what may be reason of this? May 
be I don't know some simple things I should and just misuse DList?

About code causing memory leaks - it is trivial loop:

	class DataChunk {
	...
	}

	DList!DataChunk patch;
	(RedBlackTree!DataChunk)[uint] _container_map;

	...	

	foreach(datachunk; find!isNewer(_container_map[source][])) {
	    patch.insertFront(datachunk);
	}

if I replace DList by SList all works fine - size of used memory is the 
same all the time. But with DList the application uses memory more and more.
Feb 24 2013
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Sunday, 24 February 2013 at 20:16:26 UTC, Alexandr Druzhinin 
wrote:

 I used in my application DList (code is large and I couldn't 
 reduce it) and the application allocates memory always. I can 
 not realize why and don't know it now. But when I replaced 
 DList by SList (and even dynamic array) memory leaks 
 disappeared at all and all works as expected. I know it is hard 
 to help me without code but what may be reason of this? May be 
 I don't know some simple things I should and just misuse DList?

 About code causing memory leaks - it is trivial loop:

 	class DataChunk {
 	...
 	}

 	DList!DataChunk patch;
 	(RedBlackTree!DataChunk)[uint] _container_map;

 	...	

 	foreach(datachunk; find!isNewer(_container_map[source][])) {
 	    patch.insertFront(datachunk);
 	}

 if I replace DList by SList all works fine - size of used 
 memory is the same all the time. But with DList the application 
 uses memory more and more.


I don't see any any calls to remove, so I'm not sure what the 
algorithm is. Wouldn't patch just grow and grow and grow?

Regardless, the design of DList is currently flawed (but a pull 
is open to fix it), in the sense that a DList is just a "handle" 
on a chain of nodes.

The problem with this approach is that calls to things such as 
"removeFront()" or "removeFront(n)" merelly reposition the 
"first" pointer. However, the nodes are never actually un-linked. 
I'd say there are good chances this is what you are seeing.

Seeing a DList doesn't have splice either, I'm unsure what to 
tell you in regards to working around it.

I'd say once you are done with a list, you can try to "dup" it: 
This will allocate *more*, but will allow the GC to collect 
everything that was previously removed.

...Or just SList. It's "less" bugged.

See this:
http://forum.dlang.org/thread/gjhclwsuqyhrimdeoaec forum.dlang.org
Feb 24 2013
parent Alexandr Druzhinin <drug2004 bk.ru> writes:
25.02.2013 3:59, monarch_dodra пишет:

 I don't see any any calls to remove, so I'm not sure what the algorithm
 is. Wouldn't patch just grow and grow and grow?

 Regardless, the design of DList is currently flawed (but a pull is open
 to fix it), in the sense that a DList is just a "handle" on a chain of
 nodes.

 The problem with this approach is that calls to things such as
 "removeFront()" or "removeFront(n)" merelly reposition the "first"
 pointer. However, the nodes are never actually un-linked. I'd say there
 are good chances this is what you are seeing.

 Seeing a DList doesn't have splice either, I'm unsure what to tell you
 in regards to working around it.

 I'd say once you are done with a list, you can try to "dup" it: This
 will allocate *more*, but will allow the GC to collect everything that
 was previously removed.

 ...Or just SList. It's "less" bugged.

 See this:
 http://forum.dlang.org/thread/gjhclwsuqyhrimdeoaec forum.dlang.org


After some research I think that this situation is due to several 
reasons set and DList isn't single cause.
patch is local var:
      class DataChunk {
	uint source_id;
	uint id;
      ...
      }

      class DataStorage {
          DList!DataChunk patch;
          (RedBlackTree!DataChunk)[uint] _container_map;

      ...

	auto getPatch(uint source, long last) {

	    bool isNewer(DataChunk dc) {
		if(dc.source_id == source && dc.id > last)
		    return true;
		else
		    return false;	
	    }

             Patch patch;
             foreach(datachunk; find!isNewer(_container_map[source][])) {
                 patch.insertFront(datachunk);
             }
	}
     }	
so it doesn't grow.
Feb 25 2013