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?

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]

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?

On 15.12.14 01:00, "Nordlöw" wrote:
> Isn't this algorithm already encoded somewhere in Phobos?
I don't know.

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.

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).

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

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 :)

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.

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.