[Issue 4489] std.array.insert is slow
d-bugmail at puremagic.com
d-bugmail at puremagic.com
Wed Aug 1 16:46:39 PDT 2012
http://d.puremagic.com/issues/show_bug.cgi?id=4489
--- Comment #2 from Andrei Alexandrescu <andrei at metalanguage.com> 2012-08-01 16:46:38 PDT ---
Brought the code to date with:
----
import std.array;
import std.datetime;
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 sw = StopWatch(AutoStart.yes);
foreach (_; 0..10) {
arr.length = 0;
foreach (i; 0..COUNT)
insert(arr, i, i);
}
writeln(sw.peek.msecs);
}
void main()
{
int[] arr = new int[COUNT];
bench!(myInsert)(arr);
bench!(std.array.insertInPlace)(arr);
}
----
I was able to measure a notable the performance mismatch. The culprit is:
----
void insertInPlace(T, U...)(ref T[] array, size_t pos, U stuff)
if(!isSomeString!(T[]) && allSatisfy!(isInputRangeOrConvertible!T, U))
{
T[staticConvertible!(T, U)] stackSpace = void;
auto range = chain(makeRangeTuple(stackSpace[], stuff).expand);
insertInPlaceImpl(array, pos, range);
}
----
I replaced that with:
----
void insertInPlace(T, U...)(ref T[] array, size_t pos, U stuff)
if(!isSomeString!(T[]) && allSatisfy!(isInputRangeOrConvertible!T, U))
{
immutable oldLen = array.length;
array.length += stuff.length;
auto ptr = array.ptr + pos;
import core.stdc.string;
memmove(ptr + stuff.length, ptr, (oldLen - pos) * T.sizeof);
ptr = array.ptr + pos;
foreach (i, Unused; U)
{
emplace(ptr + i, stuff[i]);
}
}
----
and was able to measure similar performance.
Clearly the code once approved belongs to the entire team, not only to its
author, and I should be a better man than this, but I can't stop noticing the
irony of this given
http://forum.dlang.org/thread/mailman.811.1343564241.31962.digitalmars-d@puremagic.com
I'll make a pull request soon.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
More information about the Digitalmars-d-bugs
mailing list