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

           Summary: [CTFE] Absurd memory usage (still) on building array
           Product: D
           Version: unspecified
          Platform: Other
        OS/Version: Windows
            Status: NEW
          Keywords: performance
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: nobody@puremagic.com
        ReportedBy: dsimcha@yahoo.com


--- Comment #0 from David Simcha <dsimcha@yahoo.com> 2011-08-06 13:34:11 PDT ---
The following program uses over a gigabyte of memory at compile time.  I thought these kinds of issues were fixed by the rewrite of CTFE in the last release.

enum staticFacTableLen = 1000;
immutable table = makeLogFacTable();

immutable(double[staticFacTableLen]) makeLogFacTable() pure nothrow {

    static real log(real x) pure nothrow @safe
    {
        immutable xMinusPlus = (x - 1) / (x + 1);
        immutable xMinusPlusSquared = xMinusPlus * xMinusPlus;
        real xMinusPlusPow = xMinusPlus * xMinusPlusSquared;

        real ret = xMinusPlus;
        real power = 3;

        while(true)
        {
            immutable toAdd = xMinusPlusPow / power;
            immutable oldRet = ret;
            ret += toAdd;

            if(ret == oldRet || ret != ret)
            {
                return 2 * ret;
            }

            power += 2;
            xMinusPlusPow *= xMinusPlusSquared;
        }

        assert(0);
    }

    double[staticFacTableLen] ret;

    ret[0] = 0;
    foreach(i; 1..staticFacTableLen) {
        ret[i] = ret[i - 1] + log(i);
    }

    return cast(immutable) ret;
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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


Jonathan M Davis <jmdavisProg@gmx.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jmdavisProg@gmx.com


--- Comment #1 from Jonathan M Davis <jmdavisProg@gmx.com> 2011-08-06 13:49:50 PDT ---
CTFE was definitely improved such that it should generally use less memory (e.g. arrays aren't always copied anymore - which not only used too much memory but was semantically incorrect anyway). However, I don't think that the core problem that dmd _never_ releases memory while compiling was fixed. So, even if there's memory that should have been reclaimed and reused, it isn't, and more memory is allocated. So, it should still be pretty easy to use too much memory with CTFE. My guess would be that that's why you're using so much memory here.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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


Don <clugdbug@yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |clugdbug@yahoo.com.au


--- Comment #2 from Don <clugdbug@yahoo.com.au> 2011-08-06 23:45:24 PDT ---
(In reply to comment #0)
> The following program uses over a gigabyte of memory at compile time.  I thought these kinds of issues were fixed by the rewrite of CTFE in the last release.

No, bug 1382 is still open. Some cases of it have been fixed (eg, the one in
comment 4). I'm not sure why this particular case is so bad, I'll take a look
at it when I get a chance.
Note that CTFE still uses copy-on-write for values, and no memory is ever
released (this is more general than bug 1382). My guess is that the code below
just runs for a very long time.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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


Dmitry Olshansky <dmitry.olsh@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dmitry.olsh@gmail.com


--- Comment #3 from Dmitry Olshansky <dmitry.olsh@gmail.com> 2011-08-07 03:02:09 PDT ---
I've hitted the dmd's "Out of Memory"  with constructing bit-Trie form a set of [a,b) intervals at compile time. I haven't been able to reduce it significantly, but I think it's the same bug.

The main loop in my cases sets a lot of separate bits in an array, and if array gets copied on each write I think it explains the enormous memory usage.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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



--- Comment #4 from David Simcha <dsimcha@yahoo.com> 2011-08-07 13:41:31 PDT ---
(In reply to comment #2)
> (In reply to comment #0)
> > The following program uses over a gigabyte of memory at compile time.  I thought these kinds of issues were fixed by the rewrite of CTFE in the last release.
> 
> No, bug 1382 is still open. Some cases of it have been fixed (eg, the one in
> comment 4). I'm not sure why this particular case is so bad, I'll take a look
> at it when I get a chance.
> Note that CTFE still uses copy-on-write for values, and no memory is ever
> released (this is more general than bug 1382). My guess is that the code below
> just runs for a very long time.

Values == ints, floats, other primitives?  What about static arrays?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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


Don <clugdbug@yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |INVALID


--- Comment #5 from Don <clugdbug@yahoo.com.au> 2011-08-15 00:48:37 PDT ---
(In reply to comment #4)
> (In reply to comment #2)
> > (In reply to comment #0)
> > > The following program uses over a gigabyte of memory at compile time.  I thought these kinds of issues were fixed by the rewrite of CTFE in the last release.
> > 
> > No, bug 1382 is still open. Some cases of it have been fixed (eg, the one in
> > comment 4). I'm not sure why this particular case is so bad, I'll take a look
> > at it when I get a chance.
> > Note that CTFE still uses copy-on-write for values, and no memory is ever
> > released (this is more general than bug 1382). My guess is that the code below
> > just runs for a very long time.
> 
> Values == ints, floats, other primitives?  What about static arrays?

Just integers (includes int, bool, char types) and floats. Static arrays aren't
duplicated.

This one just uses a lot of memory because it performs so many assignments, as
you can see if you count the number of iterations, as in the code below.
It's O(n^^2), so with n=1000, it loops about 4 million times.

It's nothing to do with arrays, and the memory usage is only linear with number
of assignments, so I'm marking this as invalid.
I'll create a new bug for the general memory usage issue.

-----------
enum staticFacTableLen = 10;
//  10 -->     436 iterations
// 100 -->   45598 iterations
// 200 -->  179242
// 400 -->  704609
// 600 --> 1568674
// 800 --> out of memory

int makeLogFacTable() pure nothrow {

    static int logCount(real x) pure nothrow @safe
    {
        immutable xMinusPlus = (x - 1) / (x + 1);
        immutable xMinusPlusSquared = xMinusPlus * xMinusPlus;
        real xMinusPlusPow = xMinusPlus * xMinusPlusSquared;
        int kkk = 0;

        real ret = xMinusPlus;
        real power = 3;

        while(true)
        {
            ++kkk;
            immutable toAdd = xMinusPlusPow / power;
            immutable oldRet = ret;
            ret += toAdd;

            if(ret == oldRet || ret != ret)
            {
                return kkk;
            }

            power += 2;
            xMinusPlusPow *= xMinusPlusSquared;
        }

        assert(0);
    }
    int totalcount = 0;
    foreach(i; 1..staticFacTableLen) {
        totalcount +=logCount(i);
    }
    return totalcount;
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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


downs <default_357-line@yahoo.de> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |default_357-line@yahoo.de


--- Comment #6 from downs <default_357-line@yahoo.de> 2012-03-04 14:17:45 PST ---
Note that you can alleviate this under Linux by replacing your /usr/libexec/gcc/i686-pc-linux-gnu/4.5.3/cc1d (adapt as appropriate, do gdc -v hello.d to see which backend it uses) with a stub that preloads Boehm like so:

LD_PRELOAD="/usr/lib/libgc.so" $(dirname $(realpath $0))/real_cc1d $@

Note that Boehm has to be built with malloc/calloc/free stubs enabled. Doing this brought my GDC memory usage down by a factor of six. I can make -j5 again!

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------