What Collection Types to Use?

[stephengtuggy]

I am trying to decide which STL, Boost, or other collection types to use in the Vega Strike Game Engine, for storing Units and Orders, among other things. Could use some help figuring out the best approach.

Here are the C++ STL container types: https://en.cppreference.com/w/cpp/container

And the Boost container types: https://www.boost.org/doc/libs/1_80_0/?view=category_containers

The existing code has some custom collection types, as well as collection types that inherit from, and override, STL container types. Examples include vsUMap and LeakVector.

[stephengtuggy]

Here's an interesting one: https://www.boost.org/doc/libs/1_80_0/doc/html/boost/container/static_vector.html You can add and remove elements from it, but its memory storage is statically allocated, with a size specified at compile time. The memory just remains uninitialized until you actually add enough elements to fill it.

We could perhaps use static_vector for Particles, of which there is only supposed to be a maximum of 500 at any given time, if I'm not mistaken.

Perhaps we could even use it for Units. The comment at the top of the existing UnitCollection implementation says that it's designed to be "robust up to 20,000 Units." What if we made it a static_vector of boost::smart_ptr<Unit>, and preallocated space for all 20,000 Units right from the start?

That sounds like a lot, but if I'm calculating correctly, those 20,000 Unit pointers would only require something like 80,000 or 160,000 bytes to store in memory. The actual Units could be allocated as they are needed.

What do you guys think?

[stephengtuggy]

OK, I miscalculated. On the 64-bit platforms we are generally targeting, a pointer takes up 8 bytes. 8 x 20,000 = 160,000. So that's the minimum size it would take in memory. Plus there might be some overhead.

[stephengtuggy]

Perhaps a better choice to hold Unit pointers is std::set: https://en.cppreference.com/w/cpp/container/set We would probably use a custom comparer that compares the Units pointed to, by getFgId(), or something like that.

[stephengtuggy]

Nope. You can't update an item in-place in a std::set. You have to remove the item, modify it, and then reinsert it. That would not perform well at runtime if we were constantly removing and reinserting items. Not to mention it would be a major pain to code.

[stephengtuggy]

After further reading, it seems that an item can be efficiently removed and reinserted in a set or map if you provide a hint as to what position to reinsert it into. For now, I am going with an std::map<std::string, boost::shared_ptr<UnitBaseClass>> implementation for UnitCollection. Units will only need to be removed and reinserted when their key (getFgID()) changes. For other changes, they can remain in place in the map.

I think this data structure should provide a reasonable balance of performance on inserts, deletes, random access, and iteration. The proof is in the pudding, though, so let's see how it goes.

[stephengtuggy]

Here's another interesting one: https://www.boost.org/doc/libs/1_80_0/doc/html/circular_buffer.html Sounds like this one performs much better on deletes.

[stephengtuggy]

For the Unit delete queue, I'm actually considering using a boost::lockfree::spsc_queue of smart pointers to Units. This data structure should perform extremely fast, even if a different thread pops items off the queue from the one that's pushing them onto the queue. I am excited to try it.