[Issue 4489] std.array.insert is slow

[d-bugmail at puremagic.com]

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


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

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


--- Comment #3 from Dmitry Olshansky <dmitry.olsh at gmail.com> 2012-09-28 11:27:53 PDT ---
Actually the culprit is the final step and not the simmingly complicated
packing of parameters into a range. I'm talking of this one:

private void insertInPlaceImpl(T, Range)(ref T[] array, size_t pos, Range
stuff)
    if(isInputRange!Range &&
       (is(ElementType!Range : T) ||
        isSomeString!(T[]) && is(ElementType!Range : dchar)))
{
    auto app = appender!(T[])();
    app.put(array[0 .. pos]);
    app.put(stuff);
    app.put(array[pos .. $]);
    array = app.data;
}

I'm actually surprized that there is no other specialization but surely there
was was one. Basically the thing above allocates an appender and does up to 3
resizes (1 per each put).

To taste waters I tried this:

    static if(hasLength!Range)
    {
        import core.stdc.string;
        immutable to_insert = stuff.length;
        immutable len = array.length;
        T* ptr = array.ptr+pos;
        array.length += to_insert;
        memmove(ptr+to_insert, ptr, (len-pos)*T.sizeof);
        //TODO: need to blit T.init over vacant places if T.__dtor exists?
        copy(stuff, array[pos..pos+to_insert]); 
    }
    else
    {// Generic implementation 
        auto app = appender!(T[])();
        app.put(array[0 .. pos]);
        app.put(stuff);
        app.put(array[pos .. $]);
        array = app.data;
    }

And for inserting at front the numbers were 
23387
23599

For inserting at i-th (last) index  I got:
58
92
These last ones were not very stable but indicate that the this packing into a
range also adds up.

I'll get myself busy with pull request since I was adding this packing thingy.

Still no idea when and how the underlying insertInPlaceImpl become 'create a
copy and return'. Sorry wasn't on my watch :)
Back when I last touched it, it looked like this:

void insertInPlaceImpl(T, Range)(ref T[] array, size_t pos, Range stuff)
    static if(hasLength!Range &&
              is(ElementEncodingType!Range : T) &&
              !is(T == const T) &&
              !is(T == immutable T))
    {
        immutable
            delta = stuff.length,
            oldLength = array.length,
            newLength = oldLength + delta;

        // Reallocate the array to make space for new content
        array = (cast(T*) core.memory.GC.realloc(array.ptr,
                        newLength * array[0].sizeof))[0 .. newLength];
        assert(array.length == newLength);

        // Move data in pos .. pos + stuff.length to the end of the array
        foreach_reverse (i; pos .. oldLength)
        {
            // This will be guaranteed to not throw
            move(array[i], array[i + delta]);
        }

        // Copy stuff into array
        copy(stuff, array[pos .. pos + stuff.length]);
    }
    else
    {
        auto app = appender!(T[])();
        app.put(array[0 .. pos]);
        app.put(stuff);
        app.put(array[pos .. $]);
        array = app.data;
    }

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