January 08, 2007
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
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
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
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
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
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
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
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
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
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 6
Top | Discussion index | About this forum | D home