Performance considerations of Vector (hurts performance)

[simpleyo]

Vector is used everywhere in Godot. A push_back operation allways do a resize (alloc or realloc, allways), WTF?. This hurts performance a lot. Why Vector is implemented that way?.

[RebelliousX]

I didn't look at the code for a long time. But I always wondered about the reasons of using custom Vector class template instead of using std::vector. For me (at least) this is nonsensical, if there is a custom behavior needed, std vector should have been used as a base and expand its functionality, not reinventing the wheel.

Some people hate the standard library just for the heck of it, I just hope this is not the main reason for not using it here, since it is really fast, faster than any half baked implementation that is error prone. VS2015 for example in its Update 3, std::vector's pushing operation's speed was increased about 10 times and std::string was also accelerated roughly 15 times for concatenating strings or adding chars to strings, according to VS changelog IIRC.

According to my rusty knowledge about std vectors, (if memory serves me right) there are two different aspects about memory allocations, one is size and the other is capacity. Not every resize will change capacity (in case of shrinking, for example, the size will shrink, but memory allocation (capacity) will remain just in case it will be needed later).

[Zireael07]

IIRC the reason for avoiding std is to do with c++ 03 vs c++ 11 or some such.

[simpleyo]

An example of how Vector hurts performance is in servers/visual/rasterizer. It uses a Vector<Command*> commands; to store commands of each CanvasItem. That means that, each frame, there is a lot of Vector::push_back and Vector::clear operations (that, allways, require an alloc or realloc). And that hurts performance a lot.

[RandomShaper]

When Godot was first written probably you couldn't rely too much on all the STL implementations for all the platforms supported (don't forget they even got it built for consoles).

Now I think all the main compiler/library vendors provide a good STL, but in any case you'd want here to have the very same library for every platform. You could grab STLport or any other and use it, but Godot's custom containers are so tightly integrated that they have an advantage over them, at least in that regard.

Anyway, this point would be better discussed on #9694, leaving this issue only for discussing improvements on the custom container.

I played a lot in the past with the Visual Server and the rasterizer trying to optimize it and I can tell you that the list of commands only changes when the CanvasItem's update() is called. That is, for almost everything it will be called only at startup.

And, just a guess, having the data blocks sized on demand may provide a higher chance of cache hits on every frame, which is of greater interest.

[simpleyo]

Yes, it is not so much, do not hurts on every frame, only at startup.

A problem with Vector is that can be easily confused with std::vector and they are very different things. And using Vector, believing it to be the same (or similar) as a std :: vector, may imply bad surprises in terms of performance.

[volzhs]

I guess it's related #9506 also.

[Zylann]

@volzhs it's about Vector, not Vector2 or Vector3 types.

I guess Vector just needs a capacity then? (if not done already internally by memory allocs?) No need to bring in the STL I think.

[volzhs]

@Zylann oh. misread...

[m4nu3lf]

Isn't the fix as simple as going with an exponential capacity increase/decrease?

[reduz]

Did no one bother to read the code?
Vector<> already has exponential capacity increase/decrease so push_back() is fast for the most part.
https://github.com/godotengine/godot/blob/master/core/vector.h#L74

Also Vector<> in Godot uses copy on write with an atomic counter, making the passing around of these very fast and thread safe.
std::vector<> does not support any of these functions, so the entire memory needs to be reallocated when passed around.

[reduz]

I suggest we do a programming faq to avoid these questions from being asked again and again.

[m4nu3lf]

@reduz I think I've read it, but long ago, it sounded weird to me indeed to have a so trivial implementation. I wonder how the OP came to the conclusion that Vector does a realloc for each push_back().
If he managed to do that by profiling the code, then this would mean there is a bug, otherwise he/she just misread the code.

[Zylann]

I read this part a while ago too, but didn't realized it actually was a capacity implementation. It's not mentionned or commented so I guess if you read this too fast you won't realize it actually does that^^"