View mode: basic / threaded / horizontal-split · Log in · Help
January 08, 2007
The problem with the D GC
After having fought a while with D programs with runaway memory leaks, 
I've unfortunately had to come to the conclusion that the D GC is not 
ready for production use. The problem is what I'd call "spurious 
pointers". That is random data (strings, numbers, image data, audio or 
whatever) appearing to the GC to be full of pointers to all over the 
memory space.

Consider this simple program. It is designed to have a memory footprint 
of about 20 mb and then continuously process data.

import std.random;

void main() {
        // The real memory use, ~20 mb
        uint[] data;
        data.length = 5_000_000;
        foreach(inout x; data)
                x = rand();
        while(1) {
		// simulate reading a few kb of data
                uint[] incoming;
                incoming.length = 1000 + rand() % 5000;
                foreach(inout x; incoming)
                        x = rand();
                // do something with the data...
        }
}

The result may not be as expected. The program will use up all available 
memory (for me crashing at about 2.7 gb of memory usage) and at the same 
time run extremely slow due to the panicked GC scanning all memory over 
and over.

The reason is the 20 mb of random data and the small 32-bit memory 
address range of 4 GB. To understand how bad this is, 20 mb of random 
data will result in _each_ 4k memory page on average having 5 random 
pointers to it. Those spurious pointers are laying a dense mine-field 
effectively disabling the GC.

This means that each time you rely on the GC (array appending/resizing, 
Phobos function calls etc), you have a potential memory leak. (That is 
unless all the program data is nothing but valid pointers/references or 
all non-pointer data is hidden from the GC.)

The above program is of course just a toy illustrating the phenomena. In 
a text processing program of mine the bulk of the data is short char[] 
strings. The program still has runaway memory leaks leading to an 
inevitable crash. I have absolutely no idea how to handle text 
processing using the D recommended char[] and CoW idiom without getting 
severe memory leaks.

The definite solution has to be a GC that only scans memory containing 
pointers. Sean's patches to make the GC skip scanning memory known to 
contain elements smaller than sizeof(void*) will probably help 
tremendously. (I'd just have to make sure I'm not using dchar[] strings, 
float or double data, or the DMD associative array implementation)

-- 
/Oskar
January 08, 2007
Re: The problem with the D GC
Oskar Linde wrote:

> After having fought a while with D programs with runaway memory leaks,
> I've unfortunately had to come to the conclusion that the D GC is not
> ready for production use. The problem is what I'd call "spurious
> pointers". That is random data (strings, numbers, image data, audio or
> whatever) appearing to the GC to be full of pointers to all over the
> memory space.
> 
> Consider this simple program. It is designed to have a memory footprint
> of about 20 mb and then continuously process data.
> 
> import std.random;
> 
> void main() {
>          // The real memory use, ~20 mb
>          uint[] data;
>          data.length = 5_000_000;
>          foreach(inout x; data)
>                  x = rand();
>          while(1) {
> // simulate reading a few kb of data
>                  uint[] incoming;
>                  incoming.length = 1000 + rand() % 5000;
>                  foreach(inout x; incoming)
>                          x = rand();
>                  // do something with the data...
>          }
> }
> 
> The result may not be as expected. The program will use up all available
> memory (for me crashing at about 2.7 gb of memory usage) and at the same
> time run extremely slow due to the panicked GC scanning all memory over
> and over.
> 
> The reason is the 20 mb of random data and the small 32-bit memory
> address range of 4 GB. To understand how bad this is, 20 mb of random
> data will result in _each_ 4k memory page on average having 5 random
> pointers to it. Those spurious pointers are laying a dense mine-field
> effectively disabling the GC.
> 
> This means that each time you rely on the GC (array appending/resizing,
> Phobos function calls etc), you have a potential memory leak. (That is
> unless all the program data is nothing but valid pointers/references or
> all non-pointer data is hidden from the GC.)
> 
> The above program is of course just a toy illustrating the phenomena. In
> a text processing program of mine the bulk of the data is short char[]
> strings. The program still has runaway memory leaks leading to an
> inevitable crash. I have absolutely no idea how to handle text
> processing using the D recommended char[] and CoW idiom without getting
> severe memory leaks.
> 
> The definite solution has to be a GC that only scans memory containing
> pointers. Sean's patches to make the GC skip scanning memory known to
> contain elements smaller than sizeof(void*) will probably help
> tremendously. (I'd just have to make sure I'm not using dchar[] strings,
> float or double data, or the DMD associative array implementation)
> 

I have observed the same behavior but did not realize why it happened
(thought it was a gc bug on osx or something). Something that helped the
problem for me was to call fullCollect very often (40 times a second) this
reduced the leak from 1mb a second to almost nothing.
January 08, 2007
Re: The problem with the D GC
Oskar Linde wrote:
> After having fought a while with D programs with runaway memory leaks, 
> I've unfortunately had to come to the conclusion that the D GC is not 
> ready for production use. The problem is what I'd call "spurious 
> pointers". That is random data (strings, numbers, image data, audio or 
> whatever) appearing to the GC to be full of pointers to all over the 
> memory space.
....

Wow that is so bad. I thought it has been mentioned this will not be a 
problem in practice but it apparently is.
January 08, 2007
Re: The problem with the D GC
Oskar Linde wrote:
> After having fought a while with D programs with runaway memory leaks, 
> I've unfortunately had to come to the conclusion that the D GC is not 
> ready for production use. The problem is what I'd call "spurious 
> pointers". That is random data (strings, numbers, image data, audio or 
> whatever) appearing to the GC to be full of pointers to all over the 
> memory space.
> 
> Consider this simple program. It is designed to have a memory footprint 
> of about 20 mb and then continuously process data.
> 
> import std.random;
> 
> void main() {
>         // The real memory use, ~20 mb
>         uint[] data;
>         data.length = 5_000_000;
>         foreach(inout x; data)
>                 x = rand();
>         while(1) {
>         // simulate reading a few kb of data
>                 uint[] incoming;
>                 incoming.length = 1000 + rand() % 5000;
>                 foreach(inout x; incoming)
>                         x = rand();
>                 // do something with the data...
>         }
> }
> 
> The result may not be as expected. The program will use up all available 
> memory (for me crashing at about 2.7 gb of memory usage) and at the same 
> time run extremely slow due to the panicked GC scanning all memory over 
> and over.
> 
> The reason is the 20 mb of random data and the small 32-bit memory 
> address range of 4 GB. To understand how bad this is, 20 mb of random 
> data will result in _each_ 4k memory page on average having 5 random 
> pointers to it. Those spurious pointers are laying a dense mine-field 
> effectively disabling the GC.
> 
> This means that each time you rely on the GC (array appending/resizing, 
> Phobos function calls etc), you have a potential memory leak. (That is 
> unless all the program data is nothing but valid pointers/references or 
> all non-pointer data is hidden from the GC.)
> 
> The above program is of course just a toy illustrating the phenomena. In 
> a text processing program of mine the bulk of the data is short char[] 
> strings. The program still has runaway memory leaks leading to an 
> inevitable crash. I have absolutely no idea how to handle text 
> processing using the D recommended char[] and CoW idiom without getting 
> severe memory leaks.
> 
> The definite solution has to be a GC that only scans memory containing 
> pointers. Sean's patches to make the GC skip scanning memory known to 
> contain elements smaller than sizeof(void*) will probably help 
> tremendously. (I'd just have to make sure I'm not using dchar[] strings, 
> float or double data, or the DMD associative array implementation)

I've run into similar problems back when I was messing around with the 
Universal Machine for that programing contest. It would run slower and 
slower. Skipping GC checks on arrays without pointers is a must, if you 
ask me.

L.
January 08, 2007
Re: The problem with the D GC
Oskar Linde wrote:
> (...) gc hell (...)

I've experienced pretty much the same while doing memory-intensive 
computations. Since then I've been using lots of malloc/realloc/free and 
both my memory footprint and execution speed have improved. The GC needs 
a fix. Badly.


--
Tomasz Stachowiak
January 08, 2007
Re: The problem with the D GC
I also have experienced bad GC performance. I found it to be because of 
the ~ operator on strings. The program is a daemon, and after it had 
been running for a while, memory usage gets truly horrific, and 
performance degrades very bad.

This was back on 0.140, so things may have changed since then...

I solved two ways. First, I wrote a function which accepts variadic 
arguments, and separated everything by a comma instead of appending the 
strings and the performance difference was stunning. it was also nice to 
be able to write:

prt("string", my_int, " ", my_float, "string2");

instead of

"string"~std.string.toString(my_int)~" 
"~std.string.toString(my_float)~"string2"

Second, like someone else in this thread I also called fullCollect every 
second.

I used to use gdc-0.08 with boehm-gc too. I can't honestly remember if 
that had the same problem.

Tom S wrote:
> Oskar Linde wrote:
>> (...) gc hell (...)
> 
> I've experienced pretty much the same while doing memory-intensive 
> computations. Since then I've been using lots of malloc/realloc/free and 
> both my memory footprint and execution speed have improved. The GC needs 
> a fix. Badly.
> 
> 
> -- 
> Tomasz Stachowiak
January 08, 2007
Re: The problem with the D GC
Oskar Linde wrote:
> After having fought a while with D programs with runaway memory leaks, 
> I've unfortunately had to come to the conclusion that the D GC is not 
> ready for production use. The problem is what I'd call "spurious 
> pointers". That is random data (strings, numbers, image data, audio or 
> whatever) appearing to the GC to be full of pointers to all over the 
> memory space.
> 
> Consider this simple program. It is designed to have a memory footprint 
> of about 20 mb and then continuously process data.
> 
> import std.random;
> 
> void main() {
>         // The real memory use, ~20 mb
>         uint[] data;
>         data.length = 5_000_000;
>         foreach(inout x; data)
>                 x = rand();
>         while(1) {
>         // simulate reading a few kb of data
>                 uint[] incoming;
>                 incoming.length = 1000 + rand() % 5000;
>                 foreach(inout x; incoming)
>                         x = rand();
>                 // do something with the data...
>         }
> }
> 
> The result may not be as expected. The program will use up all available 
> memory (for me crashing at about 2.7 gb of memory usage) and at the same 
> time run extremely slow due to the panicked GC scanning all memory over 
> and over.
> 
> The reason is the 20 mb of random data and the small 32-bit memory 
> address range of 4 GB. To understand how bad this is, 20 mb of random 
> data will result in _each_ 4k memory page on average having 5 random 
> pointers to it. Those spurious pointers are laying a dense mine-field 
> effectively disabling the GC.
> 
> This means that each time you rely on the GC (array appending/resizing, 
> Phobos function calls etc), you have a potential memory leak. (That is 
> unless all the program data is nothing but valid pointers/references or 
> all non-pointer data is hidden from the GC.)
> 
> The above program is of course just a toy illustrating the phenomena. In 
> a text processing program of mine the bulk of the data is short char[] 
> strings. The program still has runaway memory leaks leading to an 
> inevitable crash. I have absolutely no idea how to handle text 
> processing using the D recommended char[] and CoW idiom without getting 
> severe memory leaks.
> 
> The definite solution has to be a GC that only scans memory containing 
> pointers. Sean's patches to make the GC skip scanning memory known to 
> contain elements smaller than sizeof(void*) will probably help 
> tremendously. (I'd just have to make sure I'm not using dchar[] strings, 
> float or double data, or the DMD associative array implementation)

Since the patch keys on element size, the above code would still leak 
horribly by default.  However, the user can set/clear this "no scan" 
flag explicitly, so if there are any memory blocks that are still 
scanned by default, you can indicate that the GC should not scan them. 
I think between the two, we should be in pretty good shape.


Sean
January 08, 2007
Re: The problem with the D GC
kenny wrote:
> I also have experienced bad GC performance. I found it to be because of 
> the ~ operator on strings. The program is a daemon, and after it had 
> been running for a while, memory usage gets truly horrific, and 
> performance degrades very bad.
> 
> This was back on 0.140, so things may have changed since then...

Probably not.  Assuming this is a multithreaded app, you have to pay for 
two mutex locks for every concat operation.  So an expression like:

a = b ~ c ~ d;

would result in six locks of the mutex protecting the GC to perform 
allocations (I think anyway--I don't believe chained concats have 
special handling).  I think this would also result in two discarded 
temporary buffers for the GC to clean up later.  And since the Phobos GC 
scans all such blocks by default...

My patch will address the scanning issue, but it won't address the mutex 
issue--there's really no easy way to avoid that one.


Sean
January 08, 2007
Re: The problem with the D GC
kenny wrote:
> Second, like someone else in this thread I also called fullCollect every 
> second.

This is not always an option. With a few hundred megs of memory 
allocated, collections can last seconds. Resorting to malloc was the 
only rescue for me...


Anyway, thanks for sharing your experiences guys. Now I know I'm not the 
only one around having difficult relationships with the GC.


--
Tomasz Stachowiak
January 08, 2007
Re: The problem with the D GC
Sean Kelly wrote:
> Assuming this is a multithreaded app, you have to pay for 
> two mutex locks for every concat operation.  So an expression like:
> 
> a = b ~ c ~ d;
> 
> would result in six locks of the mutex protecting the GC to perform 
> allocations (I think anyway--I don't believe chained concats have 
> special handling).  I think this would also result in two discarded 
> temporary buffers for the GC to clean up later.  And since the Phobos GC 
> scans all such blocks by default...

Chained concats *do* have special handling. See 
phobos/internal/arraycat.d, _d_arraycatn() (first function in the file, 
can't miss it).
This function takes element size and number of arrays, followed by 
C-style vararg arrays.
And yes, it only allocates once :).

By the way, how do you figure six locks? At two locks per concat, that 
code only has two concats so even without above special handling 
wouldn't it still only lock four times?

Also: Why two locks per concat at all? A concat only requires one 
allocation, so does a single alloc require two locks?
(I haven't looked much into the GC code, so this is just curiosity)

> My patch will address the scanning issue, but it won't address the mutex 
> issue--there's really no easy way to avoid that one.

What exactly do you mean by "the mutex issue"? Is using mutexes at all 
the problem, or is it locking them too often per operation (i.e. more 
than once per alloc)?

If you don't want to use them at all, I think the closest you'd get 
would involve implementing thread-local heaps.
But that would still require a mutex if you want to allow deleting an 
object from a different thread than it was allocated in...
« First   ‹ Prev
1 2 3 4 5
Top | Discussion index | About this forum | D home