[Issue 2313] New: Poor array ~= append performance

[d-bugmail at puremagic.com]

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

           Summary: Poor array ~= append performance
           Product: D
           Version: unspecified
          Platform: PC
               URL: http://www.digitalmars.com/webnews/newsgroups.php?art_gr
                    oup=digitalmars.D&article_id=75410
        OS/Version: Windows
            Status: NEW
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: bugzilla at digitalmars.com
        ReportedBy: lio+bugzilla at lunesu.com


See original thread.

Appending an element to an array is very slow. There are three reasons:

1) __d_arrayappendcT is used for all types of arrays, resulting in less than
optimal performance when sizeof(item) > 1;

2) std.gc.capacity calls sizeOfNoSync which in turn calls findPool. Complexity
of this call is O(m+n), n = number of pools, m = size of block;

3) sizeOfNoSync records the last result in a (global) cache to improve the
performance of the case "for() ar~=item;" When appending to two arrays, this
cache is useless, resulting in the O(m+n) code path described above.

A possible solution to 1) might be to create custom append routines for each
array type (similar to the custom routines for the array operations,
comparison, hashing, etc.) This way, an array of int[] can simply add an int.
Or, the __d_arrayappendcT code should check the size of the item and invoke
different code (possibly using mmx/sse when applicable.)

2) might be solved by using the fact that pooltable is always sorted; this
would bring the complexity down to O(m + log n). Ideally the size for each
allocation is recorded, either in a separate array (per pool) or right before
the allocation itself. This would result in a complexity of O(log n) resp.
O(1), minimizing the impact of the cache miss as mentioned in 3).


--