I know that D slices are set up so you can successively append to them and it only has to re-allocate infrequently, but what about with prepending?

ie, does D have a way to handle

int[] x;
for(int i=0; i < 1000; i++) {
  x = [i] ~ x;
}

efficiently, or is it better to avoid this sort of thing?

dnspies:

> efficiently, or is it better to avoid this sort of thing?

D arrays are dynamic on the right. So appending on their left is not efficient (also here you are not prepending, you are concatenating. Array concatenation creates a new array). In some cases you can append on the right many items and then use std.algorithm.reverse (don't forget the () if you use UFCS) to reverse them. In case of doubt write little benchmarks.

Bye,
bearophile

On Wednesday, 9 April 2014 at 23:43:27 UTC, bearophile wrote:
> dnspies:
>
>> efficiently, or is it better to avoid this sort of thing?
>
> D arrays are dynamic on the right. So appending on their left is not efficient (also here you are not prepending, you are concatenating. Array concatenation creates a new array). In some cases you can append on the right many items and then use std.algorithm.reverse (don't forget the () if you use UFCS) to reverse them. In case of doubt write little benchmarks.
>
> Bye,
> bearophile

Does concatenation always create a new array?  What if the type of the original is immutable (or even const)?  In that case, wouldn't it be worthwhile to check first if rhs can be copied to the right of lhs?

dnspies:

> Does concatenation always create a new array?

Concatenation allocated a new array (unless some compiler is able to optimize away something in some cases, but I think this is not yet happening).

Bye,
bearophile

On Wednesday, 9 April 2014 at 23:53:04 UTC, dnspies wrote:
> Does concatenation always create a new array?  What if the type of the original is immutable (or even const)?  In that case, wouldn't it be worthwhile to check first if rhs can be copied to the right of lhs?

Yes, it *always* creates a new array. First:
The resulting array is guaranteed new. Consider:
1. If "rhs" was copied to the right of "lhs", then "lhs" and "result" would be aliasing data:
a = [1];
b = [1];
c = a ~ b;
c[0] = 2;
assert(a[0] == 1); //Could fail! A got clobbered!

2. If "lhs" has some capacity, then it is guaranteed its next concatenation will be non allocating.
a = [1];
a.reserve(2);
p = a.ptr;
b =a ~ 2; //Uses a's capacity;
a ~= 2; //relocates.
assert(a.ptr == p); //Fails!

If you *really* wanted to "make concatenation maybe append", you can do it this way:
a = [1, 2, 3];
b = [...];
c = a; c ~= b; //c has the same contents as "a ~ b", but may actually contain a part of "a".

On Wednesday, 9 April 2014 at 23:18:27 UTC, dnspies wrote:
> I know that D slices are set up so you can successively append to them and it only has to re-allocate infrequently, but what about with prepending?
>
> ie, does D have a way to handle
>
> int[] x;
> for(int i=0; i < 1000; i++) {
>   x = [i] ~ x;
> }
>
> efficiently, or is it better to avoid this sort of thing?

Yeah, that's going to re-allocate every time. At the very least, use std.array.insertInPlace, which will do what it can to avoid re-allocating, as well as calling un-needed postblits (when applicable):

int[] x;
for(int i=0; i < 1000; i++)
    insertInPlace(x, 0, i);

But even then, insertInPlace has a complexity of O(N), so while this is "better", it is still far from optimal.

You should try to avoid prepending in a loop altogether if you can. Try to prefer a solution where:
- you foreach_reverse and you always append.
- you foreach, but assign to the final location (requires setting length first).
- you foreach, but append, and then std.algorithm.reverse once done.
Just some ideas.

On Wednesday, 9 April 2014 at 23:18:27 UTC, dnspies wrote:
> I know that D slices are set up so you can successively append to them and it only has to re-allocate infrequently, but what about with prepending?
>
> ie, does D have a way to handle
>
> int[] x;
> for(int i=0; i < 1000; i++) {
>   x = [i] ~ x;
> }
>
> efficiently, or is it better to avoid this sort of thing?

Definitely better to avoid. What's the use-case? There is almost certainly a better way of achieving what you want.

On Wed, 09 Apr 2014 19:18:25 -0400, dnspies <dspies@ualberta.ca> wrote:

> I know that D slices are set up so you can successively append to them and it only has to re-allocate infrequently, but what about with prepending?
>
> ie, does D have a way to handle
>
> int[] x;
> for(int i=0; i < 1000; i++) {
>    x = [i] ~ x;
> }
>
> efficiently, or is it better to avoid this sort of thing?

I would recommend appending, and then using std.range.retro to access, or reversing the array afterwards.

Another possibility, if you know the final array size, is to reserve and then fill the array:

int[] x;
x.length = 1000;
for(int i = 0; i < 1000; ++i)
{
   x[$-1-i] = i;
   // or (I think this works)
   retro(x)[i] = i;
}

I don't know the use case (how do you use it after creation?)

Note, I create a deque class in dcollections which maintains 2 arrays, one for prepending (and is in reverse order), and one for appending. The class handles the indexing so that it looks like a standard array. But prepending is also amortized O(1)

Also note, [i] ~ x will first allocate on the heap an array with a single element value of i, then allocate ANOTHER array on the heap which can contain all the elements in x + 1, and copy i and x to it.

The code is extremely inefficient, and should be avoided.

-Steve

On Thursday, 10 April 2014 at 05:54:52 UTC, monarch_dodra wrote:
> On Wednesday, 9 April 2014 at 23:53:04 UTC, dnspies wrote:
>> Does concatenation always create a new array?  What if the type of the original is immutable (or even const)?  In that case, wouldn't it be worthwhile to check first if rhs can be copied to the right of lhs?
>
> Yes, it *always* creates a new array. First:
> The resulting array is guaranteed new. Consider:
> 1. If "rhs" was copied to the right of "lhs", then "lhs" and "result" would be aliasing data:
> a = [1];
> b = [1];
> c = a ~ b;
> c[0] = 2;
> assert(a[0] == 1); //Could fail! A got clobbered!
>
> 2. If "lhs" has some capacity, then it is guaranteed its next concatenation will be non allocating.
> a = [1];
> a.reserve(2);
> p = a.ptr;
> b =a ~ 2; //Uses a's capacity;
> a ~= 2; //relocates.
> assert(a.ptr == p); //Fails!
>
> If you *really* wanted to "make concatenation maybe append", you can do it this way:
> a = [1, 2, 3];
> b = [...];
> c = a; c ~= b; //c has the same contents as "a ~ b", but may actually contain a part of "a".

The aliasing thing isn't a problem if the data-type is const or immutable, because you can't change it any way. (Your "A got clobbered" example doesn't apply)

It depends on your use-case, I think. How often will you be prepending? Will you be appending as well?

On Thursday, 10 April 2014 at 16:10:04 UTC, Steven Schveighoffer wrote:
> Note, I create a deque class in dcollections which maintains 2 arrays, one for prepending (and is in reverse order), and one for appending. The class handles the indexing so that it looks like a standard array. But prepending is also amortized O(1)

I like this one. If you're only ever prepending you would only need the reverse one, appending values in .retro to it as you wish, and then .retro.dup when you want a copy.

In my NewlineBufferThingy struct, I sometimes need to move a slice at an arbitrary point of an array to the very beginning of it, like a poor man's circular buffer. I ended up using std.algorithm.copy for that, but in your case -- once more, depending on your use-case -- that could end up in a *lot* of copying.