Following code:

void main()
{
    import core.memory;
    GC.disable();
    scope(exit) GC.enable();

    int[] a = [1, 2, 3, 4, 5];
    foreach(i; 0 .. 1000000000)
    {
        --a.length;
        a ~= i;
    }
}

That loop will keep on allocating in every iteration until your memory is full.

Is there a way to do something similar to this without allocating? I have also tried slicing:
a = a[0 .. $ - 1]; // instead of (--a.length;)

But neither one works.

How do you work with the dynamic array without having to rely on the GC all the time? I want something similar to the stl vector, which only re-allocates once your array grows past a certain size, not on every append.

Thanks!

Malte

On 11/05/2012 05:11 PM, Malte Skarupke wrote:
> Following code:
>
> void main()
> {
> import core.memory;
> GC.disable();
> scope(exit) GC.enable();
>
> int[] a = [1, 2, 3, 4, 5];
> foreach(i; 0 .. 1000000000)
> {
> --a.length;
> a ~= i;
> }
> }
>
> That loop will keep on allocating in every iteration until your memory
> is full.
>
> Is there a way to do something similar to this without allocating? I
> have also tried slicing:
> a = a[0 .. $ - 1]; // instead of (--a.length;)
>
> But neither one works.
>
> How do you work with the dynamic array without having to rely on the GC
> all the time? I want something similar to the stl vector, which only
> re-allocates once your array grows past a certain size, not on every
> append.
>
> Thanks!
>
> Malte

I think you want assumeSafeAppend() as explained here:

  http://www.dsource.org/projects/dcollections/wiki/ArrayArticle

Ali

On Tuesday, November 06, 2012 02:11:06 Malte Skarupke wrote:
> Following code:
> 
> void main()
> {
> import core.memory;
> GC.disable();
> scope(exit) GC.enable();
> 
> int[] a = [1, 2, 3, 4, 5];
> foreach(i; 0 .. 1000000000)
> {
> --a.length;
> a ~= i;
> }
> }
> 
> That loop will keep on allocating in every iteration until your memory is full.
> 
> Is there a way to do something similar to this without
> allocating? I have also tried slicing:
> a = a[0 .. $ - 1]; // instead of (--a.length;)

There's no real difference between those two.

> But neither one works.
> 
> How do you work with the dynamic array without having to rely on the GC all the time? I want something similar to the stl vector, which only re-allocates once your array grows past a certain size, not on every append.

Arrays do work that way. They have capacity, and they have reserve. They only append when they don't have enough memory or they're not the last slice in the block. The problem is that if you remove elements, the runtime doesn't know if there's another slice pointing to the element which was just removed, so it has to assume that that there is, and it'll be forced to reallocate when appending.

If you _know_ that there are no slices of anything beyond the end of the array, then you can call assumeSafeAppend on the array, and then the runtime will mark it as the last slice in the block, and appending won't reallocate unless it actually runs out of space in the block (or you end up removing another element without calling assumeSafeAppend or you end up with a slice which contains elements beyond the end of that array - e.g. if you slice the array and then append to the slice). So, in this particular case, assumeSafeAppend would solve your problem. Whether it works in your program in general depends on what your program is doing. And if you want to make sure that the array has enough space before appending to it a bunch, then you can use reserve. However, if you're specifically building an array, you should probably look at std.array.Appender. Don't remove elements from that though. It's just for making appending more efficient, not for being used once the array has been fully constructed.

If you haven't read it yet, I'd strongly advise reading this article on arrays in D:

http://dlang.org/d-array-article.html

- Jonathan M Davis

Malte Skarupke:

> void main()
> {
>     import core.memory;
>     GC.disable();
>     scope(exit) GC.enable();
>
>     int[] a = [1, 2, 3, 4, 5];
>     foreach(i; 0 .. 1000000000)
>     {
>         --a.length;
>         a ~= i;
>     }
> }
>
> That loop will keep on allocating in every iteration until your memory is full.
>
> Is there a way to do something similar to this without allocating?

void main() {
    auto array = [1, 2, 3, 4, 5];
    array.assumeSafeAppend();
    foreach (i; 0 .. 10_000_000) {
        array.length--;
        array ~= i;
    }
}



> But neither one works.

And that's good, it was designed that way on purpose :-)


> How do you work with the dynamic array without having to rely on the GC all the time?

There are various ways to do it...


> I want something similar to the stl vector, which only re-allocates once your array grows past a certain size, not on every append.

D arrays already work like this.

Bye,
bearophile

On Tuesday, November 06, 2012 02:27:24 bearophile wrote:
> void main() {
> auto array = [1, 2, 3, 4, 5];
> array.assumeSafeAppend();
> foreach (i; 0 .. 10_000_000) {
> array.length--;
> array ~= i;
> }
> }

assumeSafeAppend needs to be called every time that length is decremented. It does nothing in this example, because when it's called, array is already marked as the last slice in its block.

- Jonathan M Davis

Jonathan M Davis:

> assumeSafeAppend needs to be called every time that length is decremented.

Right. (But adding one such call inside a critical loop...).

Bye,
bearophile

On Tuesday, 6 November 2012 at 01:25:39 UTC, Jonathan M Davis wrote:
> On Tuesday, November 06, 2012 02:11:06 Malte Skarupke wrote:
>> Following code:
>> 
>> void main()
>> {
>> import core.memory;
>> GC.disable();
>> scope(exit) GC.enable();
>> 
>> int[] a = [1, 2, 3, 4, 5];
>> foreach(i; 0 .. 1000000000)
>> {
>> --a.length;
>> a ~= i;
>> }
>> }
>> 
>> That loop will keep on allocating in every iteration until your
>> memory is full.
>> 
>> Is there a way to do something similar to this without
>> allocating? I have also tried slicing:
>> a = a[0 .. $ - 1]; // instead of (--a.length;)
>
> There's no real difference between those two.
>
>> But neither one works.
>> 
>> How do you work with the dynamic array without having to rely on
>> the GC all the time? I want something similar to the stl vector,
>> which only re-allocates once your array grows past a certain
>> size, not on every append.
>
> Arrays do work that way. They have capacity, and they have reserve. They only
> append when they don't have enough memory or they're not the last slice in the
> block. The problem is that if you remove elements, the runtime doesn't know if
> there's another slice pointing to the element which was just removed, so it
> has to assume that that there is, and it'll be forced to reallocate when
> appending.
>
> If you _know_ that there are no slices of anything beyond the end of the
> array, then you can call assumeSafeAppend on the array, and then the runtime
> will mark it as the last slice in the block, and appending won't reallocate
> unless it actually runs out of space in the block (or you end up removing
> another element without calling assumeSafeAppend or you end up with a slice
> which contains elements beyond the end of that array - e.g. if you slice the
> array and then append to the slice). So, in this particular case,
> assumeSafeAppend would solve your problem. Whether it works in your program in
> general depends on what your program is doing. And if you want to make sure
> that the array has enough space before appending to it a bunch, then you can
> use reserve. However, if you're specifically building an array, you should
> probably look at std.array.Appender. Don't remove elements from that though.
> It's just for making appending more efficient, not for being used once the
> array has been fully constructed.
>
> If you haven't read it yet, I'd strongly advise reading this article on arrays
> in D:
>
> http://dlang.org/d-array-article.html
>
> - Jonathan M Davis

Thanks, that explains it well. I must admit that I didn't fully understand slices before. I've read the linked article and am baffled that this is seen as acceptable behavior. I will most certainly never use dynamic arrays or slices again for anything that needs to grow or shrink dynamically.

On Tuesday, November 06, 2012 03:28:09 Malte Skarupke wrote:
> Thanks, that explains it well. I must admit that I didn't fully understand slices before. I've read the linked article and am baffled that this is seen as acceptable behavior. I will most certainly never use dynamic arrays or slices again for anything that needs to grow or shrink dynamically.

It has to work this way, or it would totally screw up slices. You can't append to a slice which is not the last slice in the block without affecting the slices after it, so a reallocation must occur. And it would create too much overhead for the runtime to try to figure out whether it's safe for a slice to be considered the last slice in the block when you decrement its length. So, if you want it to be considered the last one, you have to keep track of it and tell the runtime yourself.

This sort of thing wouldn't be a problem if you couldn't slice arrays, but not being able to do that would be a huge loss. So, you either need to manage it yourself or create a type which will do that for you (e.g. std.container.Array should do that, though unfortunately, it looks like it doesn't currently call assumeSafeAppend like it should).

- Jonathan M Davis

On Tuesday, 6 November 2012 at 01:11:08 UTC, Malte Skarupke wrote:
> I want something similar to the stl vector, which only re-allocates once your array grows past a certain size, not on every append.

std.container.Array is similar to a shared_ptr<std::vector<T>>.

Malte Skarupke:

> I will most certainly never use dynamic arrays or slices again for anything that needs to grow or shrink dynamically.

And doing so you will miss an important and handy part of D :-/

Bye,
bearophile