Does the D garbage collector work?

Question

So I tried to test whether the D garbage collector works properly by running this program on Windows.

DMD 2.057 and 2.058 beta both give the same result, whether or not I specify -release, -inline, -O, etc.

The code:

import core.memory, std.stdio;

extern(Windows) int GlobalMemoryStatusEx(ref MEMORYSTATUSEX lpBuffer);

struct MEMORYSTATUSEX
{
    uint Length, MemoryLoad;
    ulong TotalPhys, AvailPhys, TotalPageFile, AvailPageFile;
    ulong TotalVirtual, AvailVirtual, AvailExtendedVirtual;
}

void testA(size_t count)
{
    size_t[] a;
    foreach (i; 0 .. count)
        a ~= i;
    //delete a;
}

void main()
{
    MEMORYSTATUSEX ms;
    ms.Length = ms.sizeof;

    foreach (i; 0 .. 32)
    {
        testA(16 << 20);
        GlobalMemoryStatusEx(ms);
        stderr.writefln("AvailPhys: %s MiB", ms.AvailPhys >>> 20);
    }
}

The output was:

AvailPhys: 3711 MiB
AvailPhys: 3365 MiB
AvailPhys: 3061 MiB
AvailPhys: 2747 MiB
AvailPhys: 2458 MiB
core.exception.OutOfMemoryError

When I uncommented the delete a; statement, the output was

AvailPhys: 3714 MiB
AvailPhys: 3702 MiB
AvailPhys: 3701 MiB
AvailPhys: 3702 MiB
AvailPhys: 3702 MiB
...

So I guess the question is obvious... does the GC actually work?

Answer 1

The problem here is false pointers. D's garbage collector is conservative, meaning it doesn't always know what's a pointer and what isn't. It sometimes has to assume that bit patterns that would point into GC-allocated memory if interpreted as pointers, are pointers. This is mostly a problem for large allocations, since large blocks are a bigger target for false pointers.

You're allocating about 48 MB each time you call testA(). In my experience this is enough to almost guarantee there will be a false pointer into the block on a 32-bit system. You'll probably get better results if you compile your code in 64-bit mode (supported on Linux, OSX and FreeBSD but not Windows yet) since 64-bit address space is much more sparse.

As far as my GC optimizations (I'm the David Simcha that CyberShadow mentions) there were two batches. One's been in for >6 months and hasn't caused any problems. The other is still in review as a pull request and isn't in the main druntime tree yet. These probably aren't the problem.

Short term, the solution is to manually free these huge blocks. Long term, we need to add precise scanning, at least for the heap. (Precise stack scanning is a much harder problem.) I wrote a patch to do this a couple years ago but it was rejected because it relied on templates and compile time function evaluation to generate pointer offset information for each datatype. Hopefully this information will eventually be generated directly by the compiler and I can re-create my precise heap scanning patch for the garbage collector.