www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Problems with GC, trees and array concatenation

reply Babele Dunnit <babele.dunnit gmail.com> writes:
Hello everybody,

I had a HELL of a day to understand what was wrong and to strip it out from my
sources, but now I got it. Run this and keep an eye on the Task Manager: your
memory will be eaten until death. Please note that:

1) the keys of it all seems to be the "recursive" Individual class (I was
playing with trees). Substitute the

class Individual
{
    Individual[20] children;
}

with a 

class Individual
{
    real[20] values;
}

and the GC will work flawlessly.

2) please note that I am using static arrays, but dynamic arrays behave in the
same way.

3) If you use array slicing and direct assignments everything is OK. Please try
both "loseMemory" and "everythingOk" versions.

4) no problem if you DON'T assign arrays (i.e, neither version is selected). GC
works OK.

5) I am playing under Windows XP, DMD version 1.014.

here he cometh da snippet:

----------------------------------------------------------------------------------------------------------


import std.stdio;

class Individual
{
    Individual[20] children;
}

class Population
{

    void grow()
    {
        foreach(inout individual; individuals)
        {
            individual = new Individual;
        }
    }

    Individual[20000] individuals;
}

version = loseMemory;

int main(char[][] args)
{

    Population testPop1 = new Population;
    Population testPop2 = new Population;

    Individual[40000] indi;

    for(int i = 0; i < 1000000; i++)
    {
        writefln("Round %d", i);

        testPop1.grow();
        testPop2.grow();

        version (loseMemory){
            indi[] = testPop1.individuals ~ testPop2.individuals;
        }

        version (everythingOk){
            indi[0..20000] = testPop1.individuals;
            indi[20000..40000] = testPop2.individuals;}
        }

    return 0;
}

-------------------------------------------------------------------------------------------------------------------

Ciao,

Bab
Jun 01 2007
next sibling parent Kirk McDonald <kirklin.mcdonald gmail.com> writes:
Babele Dunnit wrote:

 int main(char[][] args)
 {
 
     Population testPop1 = new Population;
     Population testPop2 = new Population;
 
     Individual[40000] indi;
 
     for(int i = 0; i < 1000000; i++)
     {
         writefln("Round %d", i);
 
         testPop1.grow();
         testPop2.grow();
 
         version (loseMemory){
             indi[] = testPop1.individuals ~ testPop2.individuals;
         }
 
         version (everythingOk){
             indi[0..20000] = testPop1.individuals;
             indi[20000..40000] = testPop2.individuals;
         }
     }
 
     return 0;
 }


It is worth reviewing what this line of code does:
     indi[] = testPop1.individuals ~ testPop2.individuals;
When you concatenate two static arrays, the result is a dynamic array. 
In other words, that concatenation allocates a new dynamic array of 
40,000 elements on the heap, copies the elements of the two sub-arrays 
into it. This array is then copied /again/ into the static array 'indi'.

The 'Ok' version avoids both the allocation (which is causing the GC to 
eat all that memory) and the double-copying.

-- 
Kirk McDonald
http://kirkmcdonald.blogspot.com
Pyd: Connecting D and Python
http://pyd.dsource.org
Jun 01 2007
prev sibling parent reply Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
Babele Dunnit wrote:

 Hello everybody,
 
 I had a HELL of a day to understand what was wrong and to strip it out from my
sources, but now I got it. Run this and keep an eye on the Task Manager: your
memory will be eaten until death. Please note that:
 
 1) the keys of it all seems to be the "recursive" Individual class (I was
playing with trees). Substitute the
 
 class Individual
 {
     Individual[20] children;
 }
 
 with a 
 
 class Individual
 {
     real[20] values;
 }
 
 and the GC will work flawlessly.
 
 2) please note that I am using static arrays, but dynamic arrays behave in the
same way.
 
 3) If you use array slicing and direct assignments everything is OK. Please
try both "loseMemory" and "everythingOk" versions.


I tried both with GDC 0.23 on OSX, and neither of them leaked any 
memory, so I can only speculate about what is causing this. The D GC is 
not precise (although it has become much better since 1.001). There will 
almost always be some spurious pointers. Allocating large arrays (such 
as what happens behind the scenes when doing array concatenation) will 
always carry a risk of allocated memory being hit by a spurious pointer. 
The risk of your application having runaway or contained memory leaks 
depend on the allocation patterns you have, but in general, the larger 
your objects (like arrays) are, the larger the chance that you need to 
handle their memory manually. The problem is increased if you have many 
objects containing mixed pointer and non-pointer, but apparantly random 
data.

So in conclusion, I am quite sure the following line:

              indi[] = testPop1.individuals ~ testPop2.individuals;

Is the cause of the memory leak, because it allocates a huge chunk of 
memory that is left to the GC to free. The chance of those huge chunks 
being hit by a spurious pointer seems quite high.

I have no idea why the Individual->real substitution above would make 
any difference, if not by pure chance.

/Oskar
Jun 01 2007
next sibling parent reply BCS <ao pathlink.com> writes:
Reply to Oskar,

 

 I have no idea why the Individual->real substitution above would make
 any difference, if not by pure chance.
 


Would not real[] allocations be tagged as "does not contain pointers"?


 /Oskar
Jun 01 2007
parent Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
BCS skrev:

 Reply to Oskar,
 
 

 I have no idea why the Individual->real substitution above would make
 any difference, if not by pure chance.


 
 Would not real[] allocations be tagged as "does not contain pointers"?
 


Yes, but I don't see how that would make any difference. There will, as 
far as I can tell, never be any dangling pointers or otherwise spurious 
pointers generated by the Individual class, unless the array 
concatenation code somehow generates non-zero-initialized data.

/Oskar
Jun 01 2007
prev sibling next sibling parent Regan Heath <regan netmail.co.nz> writes:
Oskar Linde Wrote:

 I have no idea why the Individual->real substitution above would make 
 any difference, if not by pure chance.


In D1.001 a new type aware GC was implemented:

http://www.digitalmars.com/d/changelog.html#new1_001

Is it possible that this is why substituting 'Individual' for 'real' makes a
difference.  When you use 'real' your memory consists of mainly 'real's which
are non-pointer types, greatly reducing the risk of spurious pointer collisions.

Regan Heath
Jun 01 2007
prev sibling parent reply Paolo Invernizzi <arathorn NO_SPAMfastwebnet.it> writes:
Oskar Linde wrote:


 There will 
 almost always be some spurious pointers. Allocating large arrays (such 
 as what happens behind the scenes when doing array concatenation) will 
 always carry a risk of allocated memory being hit by a spurious pointer.


I don't understand. Where are the spurious pointers coming in the above 
example?


 The risk of your application having runaway or contained memory leaks 
 depend on the allocation patterns you have, but in general, the larger 
 your objects (like arrays) are, the larger the chance that you need to 
 handle their memory manually. The problem is increased if you have many 
 objects containing mixed pointer and non-pointer, but apparantly random 
 data.


Again, I don't understand. I don't see any random data.



 So in conclusion, I am quite sure the following line:
 
              indi[] = testPop1.individuals ~ testPop2.individuals;
 
 Is the cause of the memory leak, because it allocates a huge chunk of 
 memory that is left to the GC to free. The chance of those huge chunks 
 being hit by a spurious pointer seems quite high.


This is a nonsense. What's the meaning of having a garbage collector if, 
huge or not huge, it cannot free a block of memory is a so pretty linear 
example? For sure, I'm missing something...

Walter?

Cheers, Paolo.
Jun 03 2007
parent reply Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
Paolo Invernizzi skrev:

 Oskar Linde wrote:
 

 There will almost always be some spurious pointers. Allocating large 
 arrays (such as what happens behind the scenes when doing array 
 concatenation) will always carry a risk of allocated memory being hit 
 by a spurious pointer.


 
 I don't understand. Where are the spurious pointers coming in the above 
 example?


Stack data (and registers) for instance. Possibly other sections of data 
from the runtime or libraries.


 Is the cause of the memory leak, because it allocates a huge chunk of 
 memory that is left to the GC to free. The chance of those huge chunks 
 being hit by a spurious pointer seems quite high.


 
 This is a nonsense. What's the meaning of having a garbage collector if, 
 huge or not huge, it cannot free a block of memory is a so pretty linear 
 example? For sure, I'm missing something...


The GC is not guaranteed to free all blocks of memory, but the usage 
patterns in most applications make the amount of noncollectable memory 
bound by a constant factor.

I was not able to reproduce the unbounded memory growth in the original 
example, and if it is really there, it seems to me it may very likely be 
a bug, as the program, as you say, never should produce any considerable 
amount of "random" data.

Unbounded growth should normally only appear if the noncollected memory 
blocks themselves contain spurious pointers. I am not too familiar with 
the D GC and allocator, but as far as I know, care is taken to make sure 
no uninitialized (random) data is introduced to the GC.

I'd be interested to hear on what platform the original sample gives 
unbounded memory leakage.

/Oskar
Jun 03 2007
next sibling parent Lutger <lutger.blijdestijn gmail.com> writes:
Oskar Linde wrote:
...

 I'd be interested to hear on what platform the original sample gives 
 unbounded memory leakage.
 
 /Oskar


I can confirm this leak on windows XP with latest DMD. It just keeps 
growing until it runs out of memory. Not so if used with array of reals, 
or when you tell the gc that Individual hasNoPointers.
Jun 03 2007
prev sibling next sibling parent Paolo Invernizzi <arathorn NO_SPAMfastwebnet.it> writes:
Oskar Linde wrote:

 Paolo Invernizzi skrev:

 Oskar Linde wrote:


 There will almost always be some spurious pointers. Allocating large 
 arrays (such as what happens behind the scenes when doing array 
 concatenation) will always carry a risk of allocated memory being hit 
 by a spurious pointer.


 I don't understand. Where are the spurious pointers coming in the 
 above example?


 
 Stack data (and registers) for instance. Possibly other sections of data 
 from the runtime or libraries.


Again, I don't understand. The only library imported in the example is 
the std.stdio, but I guess that the leak are not coming from that 
(Babele, can you confirm? I'm on OS X...).

And, as I don't see how the above program can put on the stack something 
  similar to a pointer (everything it's null, or IT'S a pointer), it 
remains only the runtime... *sigh*

Are really the registers to be considered as a possible font of leaks?


 Is the cause of the memory leak, because it allocates a huge chunk of 
 memory that is left to the GC to free. The chance of those huge 
 chunks being hit by a spurious pointer seems quite high.


 This is a nonsense. What's the meaning of having a garbage collector 
 if, huge or not huge, it cannot free a block of memory is a so pretty 
 linear example? For sure, I'm missing something...


 
 The GC is not guaranteed to free all blocks of memory, but the usage 
 patterns in most applications make the amount of noncollectable memory 
 bound by a constant factor.


I simply cannot see how the usage pattern above can produce leak.
Must we avoid dynamic array concatenation?


 I was not able to reproduce the unbounded memory growth in the original 
 example, and if it is really there, it seems to me it may very likely be 
 a bug, as the program, as you say, never should produce any considerable 
 amount of "random" data.
 
 Unbounded growth should normally only appear if the noncollected memory 
 blocks themselves contain spurious pointers. I am not too familiar with 
 the D GC and allocator, but as far as I know, care is taken to make sure 
 no uninitialized (random) data is introduced to the GC.


Yep, that's the point! I can understand it's better to keep under 
control big chunks of data full of random values, but  it seems to me 
that the fact nobody can understand in an easy way that Babele example 
WILL leaks it's a little frightening.


 I'd be interested to hear on what platform the original sample gives 
 unbounded memory leakage.


DMD 1.014 on XP, I guess..

Cheers, Paolo
Jun 04 2007
prev sibling parent reply Babele Dunnit <babele.dunnit gmail.com> writes:
Oskar Linde Wrote:


 The GC is not guaranteed to free all blocks of memory, but the usage 
 patterns in most applications make the amount of noncollectable memory 
 bound by a constant factor.


That is good theory, but this means that this version of DMD is unuseful for
production software. HOW MUCH is that upper bound? Will it be enough to have 2
GB of RAM? or 4 GB? I am running a genetic algorithm, which ideally should run
"forever"... nonetheless, I wrote some Java SW (which I basically dont like)
which is running server-side since last 3 years... OK, OK, we all know how Java
works, and the Java GC is more mature, and Sun has a lot of money, blah blah.. 

Thinking at it again, a 10-children individual and two 200-individual
population will amount to 1.480KB when properly garbage collected, but will
raise to a (relatively) impressive 31MB when using array concatenation (I
stopped it after 700.000 iterations). Try It Yourself. And it seems to me that
these are not *big* arrays. And all pointers are null. And GC works OK when you
do *NOT* use concatenation (even on "real" trees, I can assure you... I got
some 300-nodes, 20-level-deep trees in my program here, and when not using
concatenation everything gets collected smoothly)

So, I should say, there is a bug in ARRAYS CONCATENATION, not in GARBAGE
COLLECTION... Array concatenation introduces something in memory layout so
that, later, the garbage collection cannot reclaim that memory zone...


 I'd be interested to hear on what platform the original sample gives 
 unbounded memory leakage.


Windows XP, DMD 1.014 (point 5 of my original post)

From another post:


So in conclusion, I am quite sure the following line:
              indi[] = testPop1.individuals ~ testPop2.individuals;
Is the cause of the memory leak, because it allocates a huge chunk of
memory that is left to the GC to free. The chance of those huge chunks
being hit by a spurious pointer seems quite high.


again: if you DO NOT concatenate those two arrays, everything is properly
garbage collected. So, why on earth the GC should be able to collect the
"original" arrays and not the "copied" ones?? And it happens also with very
small vectors (see above), and still I do not see from where those spurious
pointer should come from (holy smoke, Walter was so kind to make D initialize
everything...)

Seems to me that DEFINITELY there is something in array concatenation code
which fools the GC - the Windows version of it, I mean...

Ciao,
Babele
Jun 04 2007
parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Babele Dunnit wrote:

 Oskar Linde Wrote:
 

 The GC is not guaranteed to free all blocks of memory, but the usage 
 patterns in most applications make the amount of noncollectable memory 
 bound by a constant factor.


 


[snip]

 
 So, I should say, there is a bug in ARRAYS CONCATENATION, not in GARBAGE
COLLECTION... Array concatenation introduces something in memory layout so
that, later, the garbage collection cannot reclaim that memory zone...
 

 I'd be interested to hear on what platform the original sample gives 
 unbounded memory leakage.


 
 Windows XP, DMD 1.014 (point 5 of my original post)
 
 From another post:
 

 So in conclusion, I am quite sure the following line:
              indi[] = testPop1.individuals ~ testPop2.individuals;
 Is the cause of the memory leak, because it allocates a huge chunk of
 memory that is left to the GC to free. The chance of those huge chunks
 being hit by a spurious pointer seems quite high.


 
 again: if you DO NOT concatenate those two arrays, everything is properly
garbage collected. So, why on earth the GC should be able to collect the
"original" arrays and not the "copied" ones?? And it happens also with very
small vectors (see above), and still I do not see from where those spurious
pointer should come from (holy smoke, Walter was so kind to make D initialize
everything...)
 
 Seems to me that DEFINITELY there is something in array concatenation code
which fools the GC - the Windows version of it, I mean...


Looking at the GC code I can't seem to find any place where arr[length 
.. _gc.cap(arr)] (the unused part of the array allocation) is 
initialized. This could explain the issue if your arrays have different 
lengths (since the data from an longer old array may be present after a 
shorter new array, and is considered as "live" pointers by the GC 
because it's within the same allocation block).

However, this seems to be the case for straight allocation as well, not 
just concatenation.
If this is the cause, you probably have the same issue if you replace
     indi[] = testPop1.individuals ~ testPop2.individuals;
by
     auto tmp = new Individual[](testPop1.length + testPop2.length);
     tmp[0 .. testPop1.length] = testPop1;
     tmp[testPop1.length .. $] = testPop2;
     indi[] = tmp;
Is this the case?
Jun 04 2007
next sibling parent Babele Dunnit <babele.dunnit gmail.com> writes:
Frits van Bommel Wrote:



 Looking at the GC code I can't seem to find any place where arr[length 
 .. _gc.cap(arr)] (the unused part of the array allocation) is 
 initialized. This could explain the issue if your arrays have different 
 lengths (since the data from an longer old array may be present after a 
 shorter new array, and is considered as "live" pointers by the GC 
 because it's within the same allocation block).
 
 However, this seems to be the case for straight allocation as well, not 
 just concatenation.
 If this is the cause, you probably have the same issue if you replace
      indi[] = testPop1.individuals ~ testPop2.individuals;
 by
      auto tmp = new Individual[](testPop1.length + testPop2.length);
      tmp[0 .. testPop1.length] = testPop1;
      tmp[testPop1.length .. $] = testPop2;
      indi[] = tmp;
 Is this the case?



Woagh!

You got it, man! Actually, the Population is not an array itself but a
container, so the correct code is:

        auto tmp = new Individual[](testPop1.individuals.length +
testPop2.individuals.length);
             tmp[0 .. testPop1.individuals.length] = testPop1.individuals;
             tmp[testPop1.individuals.length .. $] = testPop2.individuals;
             indi[] = tmp;

but the leak is there!

I still do not understand one thing, though: you say "if your arrays have
different lengths", but my arrays are fixed in size... they are even static!
Shouldn't  GC try to allocate and recycle always the same fixed-size chunk of
memory?

and why the leak does not shows up under OsX??

anyway, thx!

Babele
Jun 04 2007
prev sibling parent reply Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
Frits van Bommel skrev:

 Babele Dunnit wrote:

 Seems to me that DEFINITELY there is something in array concatenation 
 code which fools the GC - the Windows version of it, I mean...


 
 Looking at the GC code I can't seem to find any place where arr[length 
 .. _gc.cap(arr)] (the unused part of the array allocation) is 
 initialized. This could explain the issue if your arrays have different 
 lengths (since the data from an longer old array may be present after a 
 shorter new array, and is considered as "live" pointers by the GC 
 because it's within the same allocation block).


The code that clears arr[length.._gc.cap(arr)] lies in gcx.d. Search for 
the phrase "inline"

The code is actually commented out on DMD:
//foreach(inout byte b; cast(byte[])(p + size)[0..binsize[bin] - size]) 
{ b = 0; }

A patch that reverses that comment:

--- gcx.d       2007-06-04 16:47:02.354590379 +0200
+++ gcx.d.new   2007-06-04 16:46:53.331933006 +0200
   -297,7 +297,7   
                 gcx.bucket[bin] = (cast(List *)p).next;
                 //memset(p + size, 0, binsize[bin] - size);
                 // 'inline' memset - Dave Fladebo.
-               //foreach(inout byte b; cast(byte[])(p + 
size)[0..binsize[bin] - size]) { b = 0; }
+               foreach(inout byte b; cast(byte[])(p + 
size)[0..binsize[bin] - size]) { b = 0; }
                 //debug(PRINTF) printf("\tmalloc => %x\n", p);
                 debug (MEMSTOMP) memset(p, 0xF0, size);
             }


Actually seems to remove the memory leak on Linux 1.014...

I am unable to test this on windows.

Note that on GDC, the above code is replaced by a memset(...,0,...) that 
is run conditional to a version(GNU), so that may be the reason the leak 
  doesn't exist on OSX.

/Oskar
Jun 04 2007
next sibling parent "David B. Held" <dheld codelogicconsulting.com> writes:
Oskar Linde wrote:

 [...]
 The code is actually commented out on DMD:
 //foreach(inout byte b; cast(byte[])(p + size)[0..binsize[bin] - size]) 
 { b = 0; }
 
 A patch that reverses that comment:
 
 --- gcx.d       2007-06-04 16:47:02.354590379 +0200
 +++ gcx.d.new   2007-06-04 16:46:53.331933006 +0200
    -297,7 +297,7   
                 gcx.bucket[bin] = (cast(List *)p).next;
                 //memset(p + size, 0, binsize[bin] - size);
                 // 'inline' memset - Dave Fladebo.
 -               //foreach(inout byte b; cast(byte[])(p + 
 size)[0..binsize[bin] - size]) { b = 0; }
 +               foreach(inout byte b; cast(byte[])(p + 
 size)[0..binsize[bin] - size]) { b = 0; }
                 //debug(PRINTF) printf("\tmalloc => %x\n", p);
                 debug (MEMSTOMP) memset(p, 0xF0, size);
             }
 [...]


Could one of you guys file a bug report for this?  Looks pretty important.

Dave
Jun 04 2007
prev sibling parent reply Babele Dunnit <babele.dunnit gmail.com> writes:
Oskar Linde Wrote:


 The code is actually commented out on DMD:
 //foreach(inout byte b; cast(byte[])(p + size)[0..binsize[bin] - size]) 
 { b = 0; }
 
 A patch that reverses that comment:
 
 --- gcx.d       2007-06-04 16:47:02.354590379 +0200
 +++ gcx.d.new   2007-06-04 16:46:53.331933006 +0200
    -297,7 +297,7   
                  gcx.bucket[bin] = (cast(List *)p).next;
                  //memset(p + size, 0, binsize[bin] - size);
                  // 'inline' memset - Dave Fladebo.
 -               //foreach(inout byte b; cast(byte[])(p + 
 size)[0..binsize[bin] - size]) { b = 0; }
 +               foreach(inout byte b; cast(byte[])(p + 
 size)[0..binsize[bin] - size]) { b = 0; }
                  //debug(PRINTF) printf("\tmalloc => %x\n", p);
                  debug (MEMSTOMP) memset(p, 0xF0, size);
              }
 
 
 Actually seems to remove the memory leak on Linux 1.014...
 
 I am unable to test this on windows.


My test case seems to run rock-steady now under Windows. BTW, much faster (it
does not reallocate!! :))

I'll let run the WHOLE BEAST tonight and tell you if it is still alive
tomorrow...

great!

Grazie,
Bab

PS: Ok, but WHY is it commented out in actual Phobos distribution??
Jun 04 2007
parent reply Babele Dunnit <babele.dunnit gmail.com> writes:
Babele Dunnit Wrote:


 I'll let run the WHOLE BEAST tonight and tell you if it is still alive
tomorrow...


the BEAST died anyway, but for some other problem. I believe this patch is OK
and proceed to file a bug report


 PS: Ok, but WHY is it commented out in actual Phobos distribution??


This question is still open...

ciao
Jun 05 2007
parent Babele Dunnit <babele.dunnit gmail.com> writes:
Hi all,

D 1.015, just released (thx Walter), fixes some GC problem, as in 

http://www.digitalmars.com/d/changelog.html#new1_015

but the array concatenation bug is still present (just tried!) and I proceeded
to file it on Bugzilla (and patch it again in Phobos):

http://d.puremagic.com/issues/show_bug.cgi?id=1258

ciao,
Babele
Jun 06 2007