www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Fastest Way to Append Multiple Elements to an Array

reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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
next sibling parent reply zeljkog <zeljkog home.com> writes:
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
next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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
next sibling parent zeljkog <zeljkog home.com> writes:
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
prev sibling parent reply zeljkog <zeljkog home.com> writes:
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
next sibling parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
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.
Dec 17 2014
next sibling parent zeljkog <zeljkog home.com> writes:
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
prev sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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
Dec 18 2014
parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
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.
Dec 18 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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
next sibling parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
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.
Dec 26 2014
parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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/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?
Dec 30 2014
prev sibling parent reply "Damian" <damianday hotmail.co.uk> writes:
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 :)
Dec 30 2014
parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
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
Dec 18 2014
parent reply zeljkog <zeljkog home.com> writes:
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
next sibling parent reply "Anonymous" <Anonymous nowhere.fr> writes:
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
Dec 19 2014
parent "anonymous" <anonymous example.com> writes:
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.
Dec 19 2014
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
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
Dec 19 2014
next sibling parent reply zeljkog <zeljkog home.com> writes:
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
next sibling parent Steven Schveighoffer <schveiguy yahoo.com> writes:
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
Dec 19 2014
prev sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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
Dec 19 2014
parent reply zeljkog <zeljkog home.com> writes:
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); }
Dec 19 2014
parent reply "MarcelDuchamp" <emeric nowhere.ut> writes:
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.
Dec 19 2014
next sibling parent reply "MarcelDuchamp" <emeric nowhere.ut> writes:
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...
Dec 19 2014
parent reply zeljkog <zeljkog home.com> writes:
If you wish run this just add:

struct S{
    int n1, n2, n3, n4, n5 ...;
}
Dec 19 2014
parent "MarcelDuchamp" <emeric nowhere.ut> writes:
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
prev sibling parent "anonymous" <anonymous example.com> writes:
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
prev sibling parent reply "Anonymous" <Anonymous nowhere.fr> writes:
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...
Dec 19 2014
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
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
Dec 19 2014
parent reply "Anonymous" <Anonymous nowhere.fr> writes:
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.
Dec 19 2014
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
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
Dec 19 2014
prev sibling parent "anonymous" <anonymous nowhere.ut> writes:
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.
Dec 14 2014
prev sibling next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
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
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
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
parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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 :)
Dec 15 2014