[Issue 4489] New: std.array.insert is slow

[d-bugmail at puremagic.com]

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

           Summary: std.array.insert is slow
           Product: D
           Version: D2
          Platform: Other
        OS/Version: Windows
            Status: NEW
          Keywords: performance
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody at puremagic.com
        ReportedBy: torhu at yahoo.com


--- Comment #0 from torhu at yahoo.com 2010-07-20 10:14:18 PDT ---
DMD 2.046.

std.array.insert seemed slow when I tried it, so I made a simple benchmark
comparing it to a simple alternative using memmove.

When compiled with -O -release -inline, the lowest numbers I got where 127 ms
for myInsert and 254 ms for std.array.insert.  That's a 100% speedup just from
using the most obvious implementation.

---
import std.array;
import std.perf;
import std.stdio;
import std.c.string;


enum COUNT = 100_000;


void myInsert(T)(ref T[] arr, size_t where, T value)
{
    assert(where <= arr.length);

    size_t oldLen = arr.length;
    arr.length = arr.length + 1;

    T* ptr = arr.ptr + where;
    memmove(ptr + 1, ptr, (oldLen - where) * T.sizeof);
    arr[where] = value;
}


void bench(alias insert)(ref int[] arr)
{
    auto pc = new PerformanceCounter;
    pc.start();
    foreach (_; 0..10) {
        arr.length = 0;
        foreach (i; 0..COUNT)
            insert(arr, i, i);
    }
    pc.stop();
    writeln(pc.milliseconds);
}


void main()
{
    int[] arr = new int[COUNT];

    bench!(myInsert)(arr);
    bench!(std.array.insert)(arr);
}
---

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