Thread overview
[Issue 2900] New: Array appending slowed drastically since integration of druntime
Apr 25, 2009
d-bugmail
Apr 26, 2009
d-bugmail
Apr 26, 2009
d-bugmail
Apr 29, 2009
d-bugmail
Apr 29, 2009
d-bugmail
Apr 30, 2009
d-bugmail
May 06, 2009
d-bugmail
May 06, 2009
d-bugmail
May 06, 2009
d-bugmail
Jul 09, 2009
Walter Bright
April 25, 2009
http://d.puremagic.com/issues/show_bug.cgi?id=2900

           Summary: Array appending slowed drastically since integration of
                    druntime
           Product: D
           Version: 2.020
          Platform: PC
        OS/Version: Windows
            Status: NEW
          Severity: regression
          Priority: P2
         Component: DMD
        AssignedTo: bugzilla@digitalmars.com
        ReportedBy: dsimcha@yahoo.com


Test program:

import std.stdio, std.perf;

void main() {
    scope pc = new PerformanceCounter;
    pc.start;
    uint[] foo;
    foreach(i; 0..1_000_000) {
        foo ~= i;
    }
    pc.stop;
    writeln(pc.milliseconds);
}

Timings:

DMD 2.019 (Last release before druntime):  42 milliseconds.
DMD 2.020 (First release with druntime):  ~1000 milliseconds.
DMD 2.029 (Current version):  ~1000 milliseconds.
DMD 2.029 (Replacing ~= with the Appender struct):  18 milliseconds.
DMD 2.029 (Replacing builtin array with rangeextra.TNew):  19 milliseconds.

This looks to be related to the block size caching scheme used by gcx.d.  When appending to two arrays simultaneously, the difference between 2.019 and 2.029 is much smaller, both in absolute and especially in relative terms:

Program:

import std.stdio, std.perf;

void main() {
    scope pc = new PerformanceCounter;
    pc.start;
    uint[] foo, bar;
    foreach(i; 0..1_000_000) {
        foo ~= i;
                bar ~= i;
    }
    pc.stop;
    writeln(pc.milliseconds);
}

Timings:
DMD 2.019:  ~1800 ms
DMD 2.029:  ~2300 ms (Note:  Still slower but not by as much even in absolute
terms)
DMD 2.029 (Using Appender instead of ~=):  49 ms


-- 

April 26, 2009
http://d.puremagic.com/issues/show_bug.cgi?id=2900





------- Comment #1 from dsimcha@yahoo.com  2009-04-25 23:09 -------
Created an attachment (id=340)
 --> (http://d.puremagic.com/issues/attachment.cgi?id=340&action=view)
Fix by adding BlkInfo caching to druntime GC.

I've figured out the problem.  In lifetime.d, the druntime devs tried to improve the allocation model in a way that required the whole BlkInfo struct from the GC, so the caching of size info wasn't used.  This patch addresses this by adding caching of BlkInfo similar to caching of size to the GC.

It also fixes a subtle bug in the size caching that I found while reading the code:  When free() is called on the block whose size is currently being cached, that cache information is not cleared.


-- 

April 26, 2009
http://d.puremagic.com/issues/show_bug.cgi?id=2900





------- Comment #2 from dsimcha@yahoo.com  2009-04-25 23:35 -------
Created an attachment (id=341)
 --> (http://d.puremagic.com/issues/attachment.cgi?id=341&action=view)
Another possible fix:  query just size first in lifetime.

Here's another possible fix.  This patch simply queries only the size of the block in lifetime.d and, if the array does not need to be reallocated, skips the querying of the full block info.


-- 

April 29, 2009
http://d.puremagic.com/issues/show_bug.cgi?id=2900


sean@invisibleduck.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED




------- Comment #3 from sean@invisibleduck.org  2009-04-29 11:42 -------
Thanks for doing this research.  The reason gc_query() is currently used is because it provides a means of determining explicitly whether the array is an interior slice.  However, I've begun thinking that it would make more sense just to require that gc_sizeOf() always return zero for interior pointers (I'd left the door open for it to return a positive value).  That would bring performance in line with Phobos pre-Druntime.  Either way though, the caching of BlkInfo is a valuable change.  I'll see about at least getting these patches applied before the next release.


-- 

April 29, 2009
http://d.puremagic.com/issues/show_bug.cgi?id=2900


sean@invisibleduck.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|bugzilla@digitalmars.com    |sean@invisibleduck.org
             Status|ASSIGNED                    |NEW




-- 

April 30, 2009
http://d.puremagic.com/issues/show_bug.cgi?id=2900





------- Comment #4 from dsimcha@yahoo.com  2009-04-30 18:20 -------
Been thinking about this some more.  It might be a good thing, even with the full BlkInfo caching, to make array appending only need size.  In multithreaded programs, this might allow for the size to be queried atomically if it's cached, rather than requiring locking on every array append.  Then again, this caching is somewhat of a kludge, and if you're doing a lot of appends, the better answer is probably to use an ArrayBuilder/Appender/TNew anyhow.


-- 

May 06, 2009
http://d.puremagic.com/issues/show_bug.cgi?id=2900





------- Comment #5 from sean@invisibleduck.org  2009-05-06 13:12 -------
I'm afraid the source locations where most of this code is inserted by the patches is wrong.  Could you update them?


-- 

May 06, 2009
http://d.puremagic.com/issues/show_bug.cgi?id=2900





------- Comment #6 from dsimcha@yahoo.com  2009-05-06 14:53 -------
Sure, but could you please specify what's wrong with it and/or give me hints as to how to fix it?  It seems right to me, though I'm pretty new to submitting patches.  Also, while looking at it, I found a small error in my BlkInfo caching patch that needs fixing anyhow.  I initially misunderstood how setAttr works.

if(gcx.infoCache.base is p) {
     gcx.infoCache.attr = mask;
}

should be something like:

if(gcx.infoCache.base is p) {
     gcx.infoCache.attr = mask & oldb;
}


-- 

May 06, 2009
http://d.puremagic.com/issues/show_bug.cgi?id=2900


dsimcha@yahoo.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
 Attachment #340 is|0                           |1
           obsolete|                            |




------- Comment #7 from dsimcha@yahoo.com  2009-05-06 15:20 -------
Created an attachment (id=353)
 --> (http://d.puremagic.com/issues/attachment.cgi?id=353&action=view)
New BlkInfo caching

On second thought, it does look like some weird things were going on.  First of all, Cygwin diff's omit whitespace option seems to do weird things.  Here's another attempt, also with a subtle bug or two in the orig. patch fixed.  I think this is the much better solution than the other patch, but if you disagree, let me know and I'll fix the other one too.


-- 

July 09, 2009
http://d.puremagic.com/issues/show_bug.cgi?id=2900


Walter Bright <bugzilla@digitalmars.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |bugzilla@digitalmars.com
         Resolution|                            |FIXED




--- Comment #8 from Walter Bright <bugzilla@digitalmars.com>  2009-07-09 02:55:48 PDT ---
Fixed dmd 2.031

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