Arrays and vectors always resize after a push or a remove

[Daw11]

Godot version:
3.0.6.stable.mono

OS/device including version:
Linux, Ubuntu 18.04, g++

Issue description:
I'm writing a library in C++ with GDNative and running it in Godot with C#.
The library is returning an Array of Vector2.
The problem is that every time I push an element, it always trigger a resize of the corresponding Vector.

Steps to reproduce:
If I write this code:

Array result;

for( int i = 0; i < 1000; i++ )
  result.push_back( Vector2( 0.0f, 0.0f ) );

return result;

Valgrind shows that it's triggering resize every time instead of once every power of two.

[akien-mga]

CC @karroffel

[karroffel]

The same should happen when you do it from GDScript or VisualScript or any other language. As you can see it's going through the Array::push_back() call and there's nothing that GDNative does extra, it just forwards. So this is a core issue, not a GDNative one.

[Zylann]

Having it call resize sounds legit, isnt it supposed to resize the capacity instead at every power of two?

[voithos]

Taking a look at this, and indeed, it seems like array.h, darray.h, and cowdata.h all basically assume that capacity == size, and will resize by +1 when inserting and -1 when removing. As far as I can tell, the code doesn't currently keep track of "capacity" separately, in addition to current size.

Regarding the growth factor, I'm personally leaning away from 2 (and instead, towards something like 1.5) based on info from the Dynamic array wiki page and this StackOverflow discussion. Specifically, a growth factor of 2 has the following disadvantages:

• Assuming memory is allocated sequentially, there is never a time where previously de-allocated memory can be re-used during a growth operation. With growth == 1.5, there is.
• Since 2 is fairly rapid growth, it's easier to "run out" of memory even though significant free space is still available. With growth == 1.5, this is less of an issue (albeit still present).

Thoughts / suggestions are welcome!

[profan]

Any movement here?

I'm currently writing a grid based A* implementation following up on a bunch of people in the community using A* in that way anyways and it being possible to optimize it quite a bit with that in mind, but I'm finding that the final limit I'm hitting is the same as was found in #28925, namely that the constant reallocs occurring due to the arrays resizing when the open list is pushed to/removed from has a fairly big performance impact.

So I also did a quick experiment with the new grid based A* (called our here), the default graph-sort A* implementation godot has (called default here) and the new grid based A* but with std::vector in place of the open list instead of godot's Vector as the only change (our_std_vector here):

As you can see just replacing the open list alone leads to > 2x improvement, so I'd love to see some movement in this issue!

I imagine mitigating the issue here would lead to improvements across the entire Godot codebase (I also ran a similar test with the previously improved default A* and also saw a nearly 2x improvement just by replacing the open list with std::vector which doesn't reallocate on every modification).

[Zylann]

Is it actually similar to #24731 ?

[profan]

@Zylann Ah yes, you're quite right, it is indeed, I'd missed that one existed!

The only thing here is the resize by power of two does not occur on removing elements so that always causes a realloc right now afaik. ... But it's the very same issue at the root anyways, the lack of a capacity in the container.