Fastest Way to Append Multiple Elements to an Array
https://forum.dlang.org/post/rkxnfxsjvkffxufok...@forum.dlang.org On Thursday, 1 January 2015 at 19:18:34 UTC, Nordlöw wrote: Do we really need Append and Prepend (along with append and prepend) here? Doesn't [cC]hain already fulfill the needs of a lazy range in this case inplace of Append? Is there still a place for `append` in Phobos? What about reusing `chain(args)` for realizing append(Args...)(lhs, args)?
Re: Fastest Way to Append Multiple Elements to an Array
On Wednesday, 31 December 2014 at 00:36:36 UTC, Damian wrote: Append and Prepend would be very useful additions to Phobos it's quite surprising there not already there? In any case would love to see some pull requests :) Do we really need Append and Prepend (along with append and prepend) here? Doesn't [cC]hain already fulfill the needs of a lazy range in this case inplace of Append? /Per
Re: Fastest Way to Append Multiple Elements to an Array
On Friday, 26 December 2014 at 16:31:48 UTC, Nordlöw wrote: On Friday, 26 December 2014 at 16:29:56 UTC, Nordlöw wrote: See my update at https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L1602 which tries to merge all the ideas into one adapting algorithm :) Destroy! BTW: 1. Is is relevant to extend `append` to data being a non-Random-Access range? 2. I guess a corresponding `prepend` is motivated aswell, right? Append and Prepend would be very useful additions to Phobos it's quite surprising there not already there? In any case would love to see some pull requests :)
Re: Fastest Way to Append Multiple Elements to an Array
On Saturday, 27 December 2014 at 07:34:43 UTC, Tobias Pankrath wrote: On Friday, 26 December 2014 at 16:31:48 UTC, Nordlöw wrote: On Friday, 26 December 2014 at 16:29:56 UTC, Nordlöw wrote: See my update at https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L1602 which tries to merge all the ideas into one adapting algorithm :) Destroy! BTW: writeln(estimateLength([1,2,3],[1,2,3])); If appending to an int[] this must print 6, if appending to an int[][] it should print 2. Do you have a suitable proposal for a CT-expression that checks if an argument of type E to estimateLength() will be treated as T[] in the append? My current suggestion is isArray!A && is(T == ElementType!(A)) && hasLength!A in use at https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L1602 with the hope of being compatible with static arrays. However uncommenting https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L1680 gives compilation error as algorithm_ex.d(1658,20): Error: template std.array.Appender!(int[]).Appender.put cannot deduce function from argument types !()(int[3]), candidates are: /home/per/opt/x86_64-unknown-linux-gnu/dmd/linux/bin64/src/phobos/std/array.d(2518,10): std.array.Appender!(int[]).Appender.put(U)(U item) if (canPutItem!U) /home/per/opt/x86_64-unknown-linux-gnu/dmd/linux/bin64/src/phobos/std/array.d(2554,10): std.array.Appender!(int[]).Appender.put(Range)(Range items) if (canPutConstRange!Range) /home/per/opt/x86_64-unknown-linux-gnu/dmd/linux/bin64/src/phobos/std/array.d(2563,10): std.array.Appender!(int[]).Appender.put(Range)(Range items) if (canPutRange!Range) algorithm_ex.d(1658,20): Error: template std.array.Appender!(int[]).Appender.put cannot deduce function from argument types !()(int[3]), candidates are: /home/per/opt/x86_64-unknown-linux-gnu/dmd/linux/bin64/src/phobos/std/array.d(2518,10): std.array.Appender!(int[]).Appender.put(U)(U item) if (canPutItem!U) /home/per/opt/x86_64-unknown-linux-gnu/dmd/linux/bin64/src/phobos/std/array.d(2554,10): std.array.Appender!(int[]).Appender.put(Range)(Range items) if (canPutConstRange!Range) /home/per/opt/x86_64-unknown-linux-gnu/dmd/linux/bin64/src/phobos/std/array.d(2563,10): std.array.Appender!(int[]).Appender.put(Range)(Range items) if (canPutRange!Range) algorithm_ex.d(1681,16): Error: template instance algorithm_ex.append!(int, int[3], int[3]) error instantiating Comint exited abnormally with code 1 at Tue Dec 30 23:55:33 Isn't appender compatible with static arrays?
Re: Fastest Way to Append Multiple Elements to an Array
On Friday, 26 December 2014 at 16:31:48 UTC, Nordlöw wrote: On Friday, 26 December 2014 at 16:29:56 UTC, Nordlöw wrote: See my update at https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L1602 which tries to merge all the ideas into one adapting algorithm :) Destroy! BTW: writeln(estimateLength([1,2,3],[1,2,3])); If appending to an int[] this must print 6, if appending to an int[][] it should print 2. 1. Is is relevant to extend `append` to data being a non-Random-Access range? Currently it does not work for RA ranges, only for arrays. RA ranges cannot grow and std.container.Array is no RA range. 2. I guess a corresponding `prepend` is motivated aswell, right? Maybe not, since you cannot efficiently prepend to an array, so having users call bringToFront explicitly might be more inline with how e.g. std.container handles complexities.
Re: Fastest Way to Append Multiple Elements to an Array
On Friday, 26 December 2014 at 16:29:56 UTC, Nordlöw wrote: See my update at https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L1602 which tries to merge all the ideas into one adapting algorithm :) Destroy! BTW: 1. Is is relevant to extend `append` to data being a non-Random-Access range? 2. I guess a corresponding `prepend` is motivated aswell, right?
Re: Fastest Way to Append Multiple Elements to an Array
On Thursday, 18 December 2014 at 20:12:01 UTC, Tobias Pankrath wrote: You shouldn't use my code verbatim though. For example, you should only use x.length, if x is of element type of data. Otherwise if you have e.g. an array of array you'd get totally wrong numbers. What role does `x` play here? Does it mean the range `data` or the `args` to be appended? See my update at https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L1602 which tries to merge all the ideas into one adapting algorithm :) Destroy!
Re: Fastest Way to Append Multiple Elements to an Array
On Saturday, 20 December 2014 at 00:15:21 UTC, MarcelDuchamp wrote: You've forget the array of ref version. (append the address of the first data) What "array of ref" version? Sounds like it would be a different data structure, which would be beyond the scope the topic. And adding S to an array is biased. S is fucking only >>8<< bytes. add more data to your struct. Adding a hundred more bytes to S didn't change the relative outcome for me. At a thousand more bytes the second version (appending an array literal) faints, and the others are closer together, but the relative order stays the same.
Re: Fastest Way to Append Multiple Elements to an Array
On Friday, 19 December 2014 at 14:41:07 UTC, Anonymous wrote:
What a big surprise. If you make an array of struct, each item
of your array has the length of the struct. structs a values.
If you want to append a struct to an array just append a
pointer to the struct:
--
struct arg{uint a,r,g,h;};
arg * [] argh;
arg [] argv;
foreach(immutable i; 0..1000)
argh ~= new arg;
--
so in argh, each item is a size_t pointer. damn.
In argv, the delta between each item is
(a.sizeof+r.sizeof+g.sizeof+h.sizeof)
In argh, the delta between each item is (arg *).sizeof
The two versions which zeljkog compared both deal with values,
not pointers. You're barking up the wrong tree.
Re: Fastest Way to Append Multiple Elements to an Array
On Saturday, 20 December 2014 at 00:44:54 UTC, zeljkog wrote:
If you wish run this just add:
struct S{
int n1, n2, n3, n4, n5 ...;
}
I wish. And I also wish you to get that to append in an array or
a in a list some ptr its not the same as appending structs,
particularly when the structs are bigger than a ptr.
Thank for hearing me. Your measures will be better.
ОПА!
Re: Fastest Way to Append Multiple Elements to an Array
If you wish run this just add:
struct S{
int n1, n2, n3, n4, n5 ...;
}
Re: Fastest Way to Append Multiple Elements to an Array
On Saturday, 20 December 2014 at 00:15:21 UTC, MarcelDuchamp
wrote:
On Friday, 19 December 2014 at 23:24:13 UTC, zeljkog wrote:
On 19.12.14 23:56, Ali Çehreli wrote:
Can we see the test code please.
Ali
import std.stdio, std.datetime, std.random;
int N = 10_000;
int len = 1000;
int k = 4;
struct S{
int n1, n2;
//~ this(this){
//~ writeln("this(this)");
//~ }
}
ref T[] append(T, Args...)(ref T[] arr, auto ref Args args)
{
static if (args.length == 1)
return arr ~= args[0];
else{
arr.length += args.length;
foreach(i, ref e; args)
arr[$ - args.length + i] = e;
return arr;
}
}
void append1(T)(ref T[] arr, T[] args...)
{
arr ~= args;
}
void main() {
S[] arr1 = new S[len];
S[] arr2, arr3, arr4, arr5;
foreach (i; 0..len)
arr1[i] = S(uniform(0, 100), uniform(0, 100));
auto sw = new StopWatch;
sw.start();
foreach(n; 0..N){
for (int i = 0; i < len; i += k){
arr2 ~= arr1[i];
arr2 ~= arr1[i+1];
arr2 ~= arr1[i+2];
arr2 ~= arr1[i+3];
//~ arr2 ~= arr1[i+4];
//~ arr2 ~= arr1[i+5];
}
delete arr2;
}
sw.stop();
long tm = sw.peek.msecs;
writeln(tm);
sw.reset();
sw.start();
foreach(n; 0..N){
for (int i = 0; i < len; i += k){
arr3 ~= [arr1[i], arr1[i+1], arr1[i+2], arr1[i+3]/+ ,
arr1[i+4], arr1[i+5] +/];
}
delete arr3;
}
sw.stop();
tm = sw.peek.msecs;
writeln(tm);
sw.reset();
sw.start();
foreach(n; 0..N){
for (int i = 0; i < len; i += k){
arr4.append(arr1[i], arr1[i+1], arr1[i+2], arr1[i+3]/+
, arr1[i+4], arr1[i+5] +/);
}
delete arr4;
}
sw.stop();
tm = sw.peek.msecs;
writeln(tm);
sw.reset();
sw.start();
foreach(n; 0..N){
for (int i = 0; i < len; i += k){
arr5.append1(arr1[i], arr1[i+1], arr1[i+2],
arr1[i+3]/+ , arr1[i+4], arr1[i+5] +/);
}
delete arr5;
}
sw.stop();
tm = sw.peek.msecs;
writeln(tm);
}
You've forget the array of ref version. (append the address of
the first data)
And adding S to an array is biased. S is fucking only >>8<<
bytes. add more data to your struct.
Seriously, do you get what I mean: 'roger this'/'copy that' ?
on an 64 bit OS, to append a 8 bytes struct is the same as
appending a pointer. It Becommes more interesting to make an
array of pointer when the struct is bigger.
When I've read your test I just thought: buy a rope man, you
don't get the thing...
You want to add things but what ? a pointer or full stack of
values ? 8 bytes it's nothing...
Re: Fastest Way to Append Multiple Elements to an Array
On Friday, 19 December 2014 at 23:24:13 UTC, zeljkog wrote:
On 19.12.14 23:56, Ali Çehreli wrote:
Can we see the test code please.
Ali
import std.stdio, std.datetime, std.random;
int N = 10_000;
int len = 1000;
int k = 4;
struct S{
int n1, n2;
//~ this(this){
//~ writeln("this(this)");
//~ }
}
ref T[] append(T, Args...)(ref T[] arr, auto ref Args args)
{
static if (args.length == 1)
return arr ~= args[0];
else{
arr.length += args.length;
foreach(i, ref e; args)
arr[$ - args.length + i] = e;
return arr;
}
}
void append1(T)(ref T[] arr, T[] args...)
{
arr ~= args;
}
void main() {
S[] arr1 = new S[len];
S[] arr2, arr3, arr4, arr5;
foreach (i; 0..len)
arr1[i] = S(uniform(0, 100), uniform(0, 100));
auto sw = new StopWatch;
sw.start();
foreach(n; 0..N){
for (int i = 0; i < len; i += k){
arr2 ~= arr1[i];
arr2 ~= arr1[i+1];
arr2 ~= arr1[i+2];
arr2 ~= arr1[i+3];
//~ arr2 ~= arr1[i+4];
//~ arr2 ~= arr1[i+5];
}
delete arr2;
}
sw.stop();
long tm = sw.peek.msecs;
writeln(tm);
sw.reset();
sw.start();
foreach(n; 0..N){
for (int i = 0; i < len; i += k){
arr3 ~= [arr1[i], arr1[i+1], arr1[i+2], arr1[i+3]/+ ,
arr1[i+4], arr1[i+5] +/];
}
delete arr3;
}
sw.stop();
tm = sw.peek.msecs;
writeln(tm);
sw.reset();
sw.start();
foreach(n; 0..N){
for (int i = 0; i < len; i += k){
arr4.append(arr1[i], arr1[i+1], arr1[i+2], arr1[i+3]/+
, arr1[i+4], arr1[i+5] +/);
}
delete arr4;
}
sw.stop();
tm = sw.peek.msecs;
writeln(tm);
sw.reset();
sw.start();
foreach(n; 0..N){
for (int i = 0; i < len; i += k){
arr5.append1(arr1[i], arr1[i+1], arr1[i+2],
arr1[i+3]/+ , arr1[i+4], arr1[i+5] +/);
}
delete arr5;
}
sw.stop();
tm = sw.peek.msecs;
writeln(tm);
}
You've forget the array of ref version. (append the address of
the first data)
And adding S to an array is biased. S is fucking only >>8<<
bytes. add more data to your struct.
Re: Fastest Way to Append Multiple Elements to an Array
On 19.12.14 23:56, Ali Çehreli wrote:
> Can we see the test code please.
>
> Ali
import std.stdio, std.datetime, std.random;
int N = 10_000;
int len = 1000;
int k = 4;
struct S{
int n1, n2;
//~ this(this){
//~ writeln("this(this)");
//~ }
}
ref T[] append(T, Args...)(ref T[] arr, auto ref Args args)
{
static if (args.length == 1)
return arr ~= args[0];
else{
arr.length += args.length;
foreach(i, ref e; args)
arr[$ - args.length + i] = e;
return arr;
}
}
void append1(T)(ref T[] arr, T[] args...)
{
arr ~= args;
}
void main() {
S[] arr1 = new S[len];
S[] arr2, arr3, arr4, arr5;
foreach (i; 0..len)
arr1[i] = S(uniform(0, 100), uniform(0, 100));
auto sw = new StopWatch;
sw.start();
foreach(n; 0..N){
for (int i = 0; i < len; i += k){
arr2 ~= arr1[i];
arr2 ~= arr1[i+1];
arr2 ~= arr1[i+2];
arr2 ~= arr1[i+3];
//~ arr2 ~= arr1[i+4];
//~ arr2 ~= arr1[i+5];
}
delete arr2;
}
sw.stop();
long tm = sw.peek.msecs;
writeln(tm);
sw.reset();
sw.start();
foreach(n; 0..N){
for (int i = 0; i < len; i += k){
arr3 ~= [arr1[i], arr1[i+1], arr1[i+2], arr1[i+3]/+ , arr1[i+4],
arr1[i+5] +/];
}
delete arr3;
}
sw.stop();
tm = sw.peek.msecs;
writeln(tm);
sw.reset();
sw.start();
foreach(n; 0..N){
for (int i = 0; i < len; i += k){
arr4.append(arr1[i], arr1[i+1], arr1[i+2], arr1[i+3]/+ , arr1[i+4],
arr1[i+5] +/);
}
delete arr4;
}
sw.stop();
tm = sw.peek.msecs;
writeln(tm);
sw.reset();
sw.start();
foreach(n; 0..N){
for (int i = 0; i < len; i += k){
arr5.append1(arr1[i], arr1[i+1], arr1[i+2], arr1[i+3]/+ , arr1[i+4],
arr1[i+5] +/);
}
delete arr5;
}
sw.stop();
tm = sw.peek.msecs;
writeln(tm);
}
Re: Fastest Way to Append Multiple Elements to an Array
On 12/19/2014 07:42 AM, zeljkog wrote: On 19.12.14 16:25, Steven Schveighoffer wrote: Did you compile both tests with the same command line parameters? Yes. Can we see the test code please. Ali
Re: Fastest Way to Append Multiple Elements to an Array
On 12/19/14 5:28 PM, Anonymous wrote:
What a big surprise. If you make an array of struct, each item of your
array has the length of the struct. structs a values.
If you want to append a struct to an array just append a pointer to
the struct:
--
struct arg{uint a,r,g,h;};
arg * [] argh;
arg [] argv;
foreach(immutable i; 0..1000)
argh ~= new arg;
--
so in argh, each item is a size_t pointer. damn.
In argv, the delta between each item is
(a.sizeof+r.sizeof+g.sizeof+h.sizeof)
In argh, the delta between each item is (arg *).sizeof
argv needs to be a contiguous thing so it's slower to append because
it's not just storing a reference but the whole thing. There is
consequently more realloc().
argh is faster because it stores the addresses of the items.
argv appends maybe 33 bytes, 33 bytes and so on.
argh always appens 4 4 4... (32 bits OS) or 8 8 8...(64 bits OS). It's
faster , always aligned...page-aware.that's all.
Oh Oh oh.
I'm not sure what you are saying here, sorry.
-Steve
Re: Fastest Way to Append Multiple Elements to an Array
On Friday, 19 December 2014 at 18:38:32 UTC, Steven Schveighoffer
wrote:
On 12/19/14 12:15 PM, Anonymous wrote:
On Friday, 19 December 2014 at 15:25:46 UTC, Steven
Schveighoffer wrote:
This is surprising to me.
Ho ho ho, this year he has brought your surprise sooner than
expected...
It would be nice if this was the only time this year I was
surprised because I didn't fully understand something ;)
-Steve
It's because of this:
On Friday, 19 December 2014 at 14:41:07 UTC, Anonymous wrote:
On Thursday, 18 December 2014 at 22:27:06 UTC, zeljkog wrote:
On 18.12.14 14:50, Steven Schveighoffer wrote:
I wonder how your code compares to this:
void append(T)(ref T[] arr, T[] args...)
{
arr ~= args;
}
This is ~20% slower for ints, but it difference increases for
bigger structs.
What a big surprise. If you make an array of struct, each item
of your array has the length of the struct. structs a values.
If you want to append a struct to an array just append a
pointer to the struct:
--
struct arg{uint a,r,g,h;};
arg * [] argh;
arg [] argv;
foreach(immutable i; 0..1000)
argh ~= new arg;
--
so in argh, each item is a size_t pointer. damn.
In argv, the delta between each item is
(a.sizeof+r.sizeof+g.sizeof+h.sizeof)
In argh, the delta between each item is (arg *).sizeof
argv needs to be a contiguous thing so it's slower to append
because it's not just storing a reference but the whole thing.
There is consequently more realloc().
argh is faster because it stores the addresses of the items.
argv appends maybe 33 bytes, 33 bytes and so on.
argh always appens 4 4 4... (32 bits OS) or 8 8 8...(64 bits OS).
It's faster , always aligned...page-aware.that's all.
Oh Oh oh.
Re: Fastest Way to Append Multiple Elements to an Array
On 12/19/14 12:15 PM, Anonymous wrote: On Friday, 19 December 2014 at 15:25:46 UTC, Steven Schveighoffer wrote: This is surprising to me. Ho ho ho, this year he has brought your surprise sooner than expected... It would be nice if this was the only time this year I was surprised because I didn't fully understand something ;) -Steve
Re: Fastest Way to Append Multiple Elements to an Array
On Friday, 19 December 2014 at 15:25:46 UTC, Steven Schveighoffer
wrote:
On 12/18/14 5:27 PM, zeljkog wrote:
On 18.12.14 14:50, Steven Schveighoffer wrote:
I wonder how your code compares to this:
void append(T)(ref T[] arr, T[] args...)
{
arr ~= args;
}
This is ~20% slower for ints, but it difference increases for
bigger structs.
This is surprising to me.
-Steve
Ho ho ho, this year he has brought your surprise sooner than
expected...
Re: Fastest Way to Append Multiple Elements to an Array
On 12/19/14 10:42 AM, zeljkog wrote: On 19.12.14 16:25, Steven Schveighoffer wrote: This is surprising to me. I would expect especially ints to be faster. In reality, there is no difference between arr ~= args and arr.length += args.length, and then copying, it's just how you do the copying. Perhaps it's the call to memcpy in the runtime that is slower than looping. I think it's compile time looping, it's unrolled. Ah, good point. Your solution is definitely preferable then, and I hope at some point the compiler can make that the result of appending an array literal. -Steve
Re: Fastest Way to Append Multiple Elements to an Array
On 19.12.14 16:25, Steven Schveighoffer wrote: This is surprising to me. I would expect especially ints to be faster. In reality, there is no difference between arr ~= args and arr.length += args.length, and then copying, it's just how you do the copying. Perhaps it's the call to memcpy in the runtime that is slower than looping. I think it's compile time looping, it's unrolled. Did you compile both tests with the same command line parameters? Yes.
Re: Fastest Way to Append Multiple Elements to an Array
On 12/18/14 5:27 PM, zeljkog wrote:
On 18.12.14 14:50, Steven Schveighoffer wrote:
I wonder how your code compares to this:
void append(T)(ref T[] arr, T[] args...)
{
arr ~= args;
}
This is ~20% slower for ints, but it difference increases for bigger structs.
This is surprising to me. I would expect especially ints to be faster.
In reality, there is no difference between arr ~= args and arr.length +=
args.length, and then copying, it's just how you do the copying. Perhaps
it's the call to memcpy in the runtime that is slower than looping.
Did you compile both tests with the same command line parameters?
-Steve
Re: Fastest Way to Append Multiple Elements to an Array
On Thursday, 18 December 2014 at 22:27:06 UTC, zeljkog wrote:
On 18.12.14 14:50, Steven Schveighoffer wrote:
I wonder how your code compares to this:
void append(T)(ref T[] arr, T[] args...)
{
arr ~= args;
}
This is ~20% slower for ints, but it difference increases for
bigger structs.
What a big surprise. If you make an array of struct, each item of
your array has the length of the struct. structs a values.
If you want to append a struct to an array just append a pointer
to the struct:
--
struct arg{uint a,r,g,h;};
arg * [] argh;
arg [] argv;
foreach(immutable i; 0..1000)
argh ~= new arg;
--
so in argh, each item is a size_t pointer. damn.
In argv, the delta between each item is
(a.sizeof+r.sizeof+g.sizeof+h.sizeof)
In argh, the delta between each item is (arg *).sizeof
Re: Fastest Way to Append Multiple Elements to an Array
On 18.12.14 14:50, Steven Schveighoffer wrote:
> I wonder how your code compares to this:
>
> void append(T)(ref T[] arr, T[] args...)
> {
> arr ~= args;
> }
This is ~20% slower for ints, but it difference increases for bigger structs.
Re: Fastest Way to Append Multiple Elements to an Array
On Thursday, 18 December 2014 at 15:12:39 UTC, Nordlöw wrote:
On Wednesday, 17 December 2014 at 12:30:37 UTC, Tobias Pankrath
wrote:
void append(T, Args...)(ref T[] arr, auto ref Args args){
{
static if (args.length == 1)
arr ~= args[0]; // inlined
else{
arr.length += args.length;
foreach(i, e; args)
arr[$ - args.length + i] = e;
}
}
Is it un-Phobos-like to make append return a reference to data
like at
https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L1605
I don't now, returning it at least allows chaining, which is nice.
You shouldn't use my code verbatim though. For example, you
should only use x.length, if x is of element type of data.
Otherwise if you have e.g. an array of array you'd get totally
wrong numbers.
Re: Fastest Way to Append Multiple Elements to an Array
On Wednesday, 17 December 2014 at 12:30:37 UTC, Tobias Pankrath
wrote:
void append(T, Args...)(ref T[] arr, auto ref Args args){
{
static if (args.length == 1)
arr ~= args[0]; // inlined
else{
arr.length += args.length;
foreach(i, e; args)
arr[$ - args.length + i] = e;
}
}
Is it un-Phobos-like to make append return a reference to data
like at
https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L1605
Re: Fastest Way to Append Multiple Elements to an Array
On 12/17/14 6:15 AM, zeljkog wrote:
On 15.12.14 01:00, "Nordlöw" wrote:
Isn't this algorithm already encoded somewhere in Phobos?
void append(T, Args...)(ref T[] arr, auto ref Args args){
{
static if (args.length == 1)
arr ~= args[0]; // inlined
else{
arr.length += args.length;
foreach(i, e; args)
arr[$ - args.length + i] = e;
}
}
I've just tested, this looks usable.
Equal for 1 item, considerably (~40%) faster for 2, and much (100+%) faster for
more.
Also more convenient.
This makes sense. The cost of calling a function is much much higher
than copying a single element.
Maybe samthing like that should go to Fobos.
Definitely. I would love to see the improvement, however, of having arr
~= [a, b, c] do this automatically by the compiler.
I wonder how your code compares to this:
void append(T)(ref T[] arr, T[] args...)
{
arr ~= args;
}
Which is how I would have approached it. Your solution is more general,
but mine has the benefit of avoiding the double-initialization of the data.
-Steve
Re: Fastest Way to Append Multiple Elements to an Array
On 17.12.14 13:30, Tobias Pankrath wrote:
void append(T, Args...)(ref T[] data, Args args)
{
static size_t estimateLength(Args args)
{
size_t result;
foreach(e; args)
static if(hasLength!(typeof(e)))
result += e.length;
else
result += 1;
return result;
}
auto app = appender!(T[])(data);
app.reserve(data.length + estimateLength(args));
foreach(e; args)
app.put(e);
data = app.data;
}
void main()
{
import std.stdio;
int[] data;
append(data, 1, 2, only(1, 2, 3), iota(4, 9));
writeln(data);
}
---
Maybe appender.put should get an overload that does the same, though I
didn't had the need for it yet.
It's for convenient one line: arr.append(e1, e2, ...);
I said "something like that" :)
Re: Fastest Way to Append Multiple Elements to an Array
On Wednesday, 17 December 2014 at 11:15:30 UTC, zeljkog wrote:
On 15.12.14 01:00, "Nordlöw" wrote:
Isn't this algorithm already encoded somewhere in Phobos?
void append(T, Args...)(ref T[] arr, auto ref Args args){
{
static if (args.length == 1)
arr ~= args[0]; // inlined
else{
arr.length += args.length;
foreach(i, e; args)
arr[$ - args.length + i] = e;
}
}
I've just tested, this looks usable.
Equal for 1 item, considerably (~40%) faster for 2, and much
(100+%) faster for more.
Also more convenient.
Maybe samthing like that should go to Fobos.
I don't think you can beat appender. And your function does not
accept ranges, only elements. I would write it like this:
---
void append(T, Args...)(ref T[] data, Args args)
{
static size_t estimateLength(Args args)
{
size_t result;
foreach(e; args)
static if(hasLength!(typeof(e)))
result += e.length;
else
result += 1;
return result;
}
auto app = appender!(T[])(data);
app.reserve(data.length + estimateLength(args));
foreach(e; args)
app.put(e);
data = app.data;
}
void main()
{
import std.stdio;
int[] data;
append(data, 1, 2, only(1, 2, 3), iota(4, 9));
writeln(data);
}
---
Maybe appender.put should get an overload that does the same,
though I didn't had the need for it yet.
Re: Fastest Way to Append Multiple Elements to an Array
On 15.12.14 01:00, "Nordlöw" wrote:
> Isn't this algorithm already encoded somewhere in Phobos?
void append(T, Args...)(ref T[] arr, auto ref Args args){
{
static if (args.length == 1)
arr ~= args[0]; // inlined
else{
arr.length += args.length;
foreach(i, e; args)
arr[$ - args.length + i] = e;
}
}
I've just tested, this looks usable.
Equal for 1 item, considerably (~40%) faster for 2, and much (100+%) faster for
more.
Also more convenient.
Maybe samthing like that should go to Fobos.
Re: Fastest Way to Append Multiple Elements to an Array
On Monday, 15 December 2014 at 15:55:22 UTC, Steven Schveighoffer wrote: What's the fastest way to append multiple elements to an array?: Before appending, call reserve to avoid the possibility of reallocating multiple times: arr.reserve(arr.length + n); // about to append n elements. Thanks! Either arr ~= e1; arr ~= e2; arr ~= e3; or arr ~= [e1,e2,e3]; I wish this would be fastest, but it's not, because this allocates an array on the heap with elements e1, e2, e3 before appending. It would be a superb addition to D if this would simply allocate a stack array (if the array never escapes the expression). That's what I thought :)
Re: Fastest Way to Append Multiple Elements to an Array
On 12/14/14 6:16 PM, "Nordlöw" wrote: What's the fastest way to append multiple elements to an array?: Before appending, call reserve to avoid the possibility of reallocating multiple times: arr.reserve(arr.length + n); // about to append n elements. Either arr ~= e1; arr ~= e2; arr ~= e3; or arr ~= [e1,e2,e3]; I wish this would be fastest, but it's not, because this allocates an array on the heap with elements e1, e2, e3 before appending. It would be a superb addition to D if this would simply allocate a stack array (if the array never escapes the expression). -Steve
Re: Fastest Way to Append Multiple Elements to an Array
On Sunday, 14 December 2014 at 23:16:12 UTC, Nordlöw wrote: What's the fastest way to append multiple elements to an array?: Either arr ~= e1; arr ~= e2; arr ~= e3; or arr ~= [e1,e2,e3]; or some other trick? It does somewhat depend on context but std.array.appender is generally a good choice. It supports appending elements individually, appending a range of elements and manually reserving extra space. E.g. auto app = appender(somePreExistingArray); app ~= e0; app ~= [e1, e2]; app.reserve(3); //eagerly ensures that there's 3 elements capacity, //guaranteeing at most one re-allocation for adding the following 3 elements app ~= e3; app ~= e4; app ~= e5; or my personal favourite: app ~= only(e6, e7, e8, e9); When you append a range to an appender it will use the length of the range (if available) to reserve space ahead-of-time. There is a (small) cost to creating an appender, so you ideally don't want to make a new one every time you add a couple of elements (this isn't a deficiency in appender, it's just how GC slices are in D).
Re: Fastest Way to Append Multiple Elements to an Array
On Sunday, 14 December 2014 at 23:52:15 UTC, zeljkog wrote:
On 15.12.14 00:16, "Nordlöw" wrote:
or some other trick?
void append(T, Args...)(ref T[] arr, Args args){
arr.length += args.length;
foreach(i, e; args)
arr[$ - args.length + i] = args[i];
}
void main()
{
int[] arr = [1, 2, 3, 4, 5];
arr.append(3, 10, 14);
writeln(arr);
}
output:
[1, 2, 3, 4, 5, 3, 10, 14]
Maybe *std.array.Appender* should be used in append().
(http://dlang.org/phobos/std_array.html#.Appender)
Even if i often myself feel too lazy to use it and use only the
concat. op instead.
Re: Fastest Way to Append Multiple Elements to an Array
On 15.12.14 01:00, "Nordlöw" wrote: Isn't this algorithm already encoded somewhere in Phobos? I don't know.
Re: Fastest Way to Append Multiple Elements to an Array
On Sunday, 14 December 2014 at 23:52:15 UTC, zeljkog wrote:
void append(T, Args...)(ref T[] arr, Args args){
arr.length += args.length;
foreach(i, e; args)
arr[$ - args.length + i] = args[i];
}
Isn't this algorithm already encoded somewhere in Phobos?
Re: Fastest Way to Append Multiple Elements to an Array
On 15.12.14 00:16, "Nordlöw" wrote:
> or some other trick?
void append(T, Args...)(ref T[] arr, Args args){
arr.length += args.length;
foreach(i, e; args)
arr[$ - args.length + i] = args[i];
}
void main()
{
int[] arr = [1, 2, 3, 4, 5];
arr.append(3, 10, 14);
writeln(arr);
}
output:
[1, 2, 3, 4, 5, 3, 10, 14]
Fastest Way to Append Multiple Elements to an Array
What's the fastest way to append multiple elements to an array?: Either arr ~= e1; arr ~= e2; arr ~= e3; or arr ~= [e1,e2,e3]; or some other trick?
