digitalmars.D.learn - Fastest Way to Append Multiple Elements to an Array
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (8/8) Dec 14 2014 What's the fastest way to append multiple elements to an array?:
- zeljkog (14/15) Dec 14 2014 void append(T, Args...)(ref T[] arr, Args args){
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (2/7) Dec 14 2014 Isn't this algorithm already encoded somewhere in Phobos?
- zeljkog (2/3) Dec 14 2014 I don't know.
- zeljkog (15/16) Dec 17 2014 void append(T, Args...)(ref T[] arr, auto ref Args args){
- Tobias Pankrath (32/49) Dec 17 2014 I don't think you can beat appender. And your function does not
- zeljkog (3/31) Dec 17 2014 It's for convenient one line: arr.append(e1, e2, ...);
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (5/15) Dec 18 2014 Is it un-Phobos-like to make append return a reference to data
- Tobias Pankrath (6/21) Dec 18 2014 I don't now, returning it at least allows chaining, which is nice.
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (8/12) Dec 26 2014 What role does `x` play here? Does it mean the range `data` or
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (5/10) Dec 26 2014 BTW:
- Tobias Pankrath (10/23) Dec 26 2014 writeln(estimateLength([1,2,3],[1,2,3]));
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (41/57) Dec 30 2014 Do you have a suitable proposal for a CT-expression that checks
- Damian (4/17) Dec 30 2014 Append and Prepend would be very useful additions to Phobos it's
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (5/8) Jan 01 2015 Do we really need Append and Prepend (along with append and
- Steven Schveighoffer (13/29) Dec 18 2014 This makes sense. The cost of calling a function is much much higher
- zeljkog (2/8) Dec 18 2014 This is ~20% slower for ints, but it difference increases for bigger st...
- Anonymous (16/25) Dec 19 2014 What a big surprise. If you make an array of struct, each item of
- anonymous (3/18) Dec 19 2014 The two versions which zeljkog compared both deal with values,
- Steven Schveighoffer (7/15) Dec 19 2014 This is surprising to me. I would expect especially ints to be faster.
- zeljkog (3/8) Dec 19 2014 Yes.
- Steven Schveighoffer (5/12) Dec 19 2014 Ah, good point. Your solution is definitely preferable then, and I hope
- =?UTF-8?B?QWxpIMOHZWhyZWxp?= (3/6) Dec 19 2014 Can we see the test code please.
- zeljkog (81/84) Dec 19 2014 import std.stdio, std.datetime, std.random;
- MarcelDuchamp (5/92) Dec 19 2014 You've forget the array of ref version. (append the address of
- MarcelDuchamp (10/113) Dec 19 2014 Seriously, do you get what I mean: 'roger this'/'copy that' ?
- zeljkog (4/4) Dec 19 2014 If you wish run this just add:
- MarcelDuchamp (6/10) Dec 19 2014 I wish. And I also wish you to get that to append in an array or
- anonymous (8/12) Dec 19 2014 What "array of ref" version? Sounds like it would be a different
- Anonymous (4/18) Dec 19 2014 Ho ho ho, this year he has brought your surprise sooner than
- Steven Schveighoffer (4/9) Dec 19 2014 It would be nice if this was the only time this year I was surprised
- Anonymous (12/51) Dec 19 2014 It's because of this:
- Steven Schveighoffer (3/31) Dec 19 2014 I'm not sure what you are saying here, sorry.
- anonymous (5/20) Dec 14 2014 Maybe *std.array.Appender* should be used in append().
- John Colvin (24/32) Dec 15 2014 It does somewhat depend on context but std.array.appender is
- Steven Schveighoffer (9/16) Dec 15 2014 Before appending, call reserve to avoid the possibility of reallocating
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (4/23) Dec 15 2014 Thanks!
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?
Dec 14 2014
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]
Dec 14 2014
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?
Dec 14 2014
On 15.12.14 01:00, "Nordlöw" wrote:Isn't this algorithm already encoded somewhere in Phobos?I don't know.
Dec 14 2014
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.
Dec 17 2014
On Wednesday, 17 December 2014 at 11:15:30 UTC, zeljkog wrote:On 15.12.14 01:00, "Nordlöw" wrote: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.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.
Dec 17 2014
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" :)
Dec 17 2014
On Wednesday, 17 December 2014 at 12:30:37 UTC, Tobias Pankrath wrote: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#L1605void 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; } }
Dec 18 2014
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: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.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#L1605void 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; } }
Dec 18 2014
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!
Dec 26 2014
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?
Dec 26 2014
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: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.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?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.
Dec 26 2014
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: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/s d/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/s d/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/s d/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/s d/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/s d/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/s d/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?On Friday, 26 December 2014 at 16:29:56 UTC, Nordlöw wrote: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.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:
Dec 30 2014
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: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 :)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?
Dec 30 2014
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
Jan 01 2015
On 12/17/14 6:15 AM, zeljkog wrote:On 15.12.14 01:00, "Nordlöw" wrote:This makes sense. The cost of calling a function is much much higher than copying a single element.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.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
Dec 18 2014
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.
Dec 18 2014
On Thursday, 18 December 2014 at 22:27:06 UTC, zeljkog wrote:On 18.12.14 14:50, Steven Schveighoffer 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 *).sizeofI 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.
Dec 19 2014
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 *).sizeofThe two versions which zeljkog compared both deal with values, not pointers. You're barking up the wrong tree.
Dec 19 2014
On 12/18/14 5:27 PM, zeljkog wrote:On 18.12.14 14:50, 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. Did you compile both tests with the same command line parameters? -SteveI 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.
Dec 19 2014
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.
Dec 19 2014
On 12/19/14 10:42 AM, zeljkog wrote:On 19.12.14 16:25, Steven Schveighoffer wrote: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. -SteveThis 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.
Dec 19 2014
On 12/19/2014 07:42 AM, zeljkog wrote:On 19.12.14 16:25, Steven Schveighoffer wrote:Can we see the test code please. AliDid you compile both tests with the same command line parameters?Yes.
Dec 19 2014
On 19.12.14 23:56, Ali Çehreli wrote:Can we see the test code please. Aliimport 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); }
Dec 19 2014
On Friday, 19 December 2014 at 23:24:13 UTC, zeljkog wrote:On 19.12.14 23:56, Ali Çehreli wrote: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.Can we see the test code please. Aliimport 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); }
Dec 19 2014
On Saturday, 20 December 2014 at 00:15:21 UTC, MarcelDuchamp wrote:On Friday, 19 December 2014 at 23:24:13 UTC, zeljkog wrote: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...On 19.12.14 23:56, Ali Çehreli wrote: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.Can we see the test code please. Aliimport 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); }
Dec 19 2014
If you wish run this just add: struct S{ int n1, n2, n3, n4, n5 ...; }
Dec 19 2014
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. ОПА!
Dec 19 2014
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.
Dec 19 2014
On Friday, 19 December 2014 at 15:25:46 UTC, Steven Schveighoffer wrote:On 12/18/14 5:27 PM, zeljkog wrote:Ho ho ho, this year he has brought your surprise sooner than expected...On 18.12.14 14:50, Steven Schveighoffer wrote:This is surprising to me. -SteveI 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.
Dec 19 2014
On 12/19/14 12:15 PM, Anonymous wrote:On Friday, 19 December 2014 at 15:25:46 UTC, Steven Schveighoffer wrote:It would be nice if this was the only time this year I was surprised because I didn't fully understand something ;) -SteveThis is surprising to me.Ho ho ho, this year he has brought your surprise sooner than expected...
Dec 19 2014
On Friday, 19 December 2014 at 18:38:32 UTC, Steven Schveighoffer wrote:On 12/19/14 12:15 PM, Anonymous wrote:It's because of this: On Friday, 19 December 2014 at 14:41:07 UTC, Anonymous wrote:On Friday, 19 December 2014 at 15:25:46 UTC, Steven Schveighoffer wrote:It would be nice if this was the only time this year I was surprised because I didn't fully understand something ;) -SteveThis is surprising to me.Ho ho ho, this year he has brought your surprise sooner than expected...On Thursday, 18 December 2014 at 22:27:06 UTC, zeljkog wrote: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.On 18.12.14 14:50, Steven Schveighoffer 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 *).sizeofI 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.
Dec 19 2014
On 12/19/14 5:28 PM, Anonymous wrote:I'm not sure what you are saying here, sorry. -SteveWhat 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 *).sizeofargv 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.
Dec 19 2014
On Sunday, 14 December 2014 at 23:52:15 UTC, zeljkog wrote:On 15.12.14 00:16, "Nordlöw" wrote:Maybe *std.array.Appender* should be used in append(). Even if i often myself feel too lazy to use it and use only the concat. op instead.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]
Dec 14 2014
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).
Dec 15 2014
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
Dec 15 2014
On Monday, 15 December 2014 at 15:55:22 UTC, Steven Schveighoffer wrote:Thanks!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.That's what I thought :)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).
Dec 15 2014