View mode: basic / threaded / horizontal-split · Log in · Help
November 06, 2012
How do you remove/insert elements in a dynamic array without allocating?
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
November 06, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
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
November 06, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
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
November 06, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
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
November 06, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
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
November 06, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
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
November 06, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
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.
November 06, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
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
November 06, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
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>>.
November 06, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
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
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home