Vectors vs Lists, Efficiency when dealing with rapid resizing and deletion

This is a more general c++ question I guess, but I am at the point in my project that I need to start thinking of efficiency.

Right now, I have a custom class, oscThread, which extends of3dPrimitives. Each thread goes into one braid, which is vector<oscThread>, and finally, each braid is organized in space, becoming vector< vector<oscThread> >. My “braids” are a collection of meshes that go between two points, and when the reach their destination point, they need to be removed from memory.

I have been pointed in the direction of using lists over vectors. I know this will take some effort to convert the whole system from utilizing vectors to lists, so I was wondering, does this sound like it would be worth it? The ability to remove and add at any point in the collection makes me feel like lists would be appropriate, but I have dealt with vectors much more often.

It’s difficult to say without seeing your exact code and profiling it, but this article has been helpful to me in the past when making the same decision. The rule of thumb seems to be prefer vectors. But of course, that may not apply for your case :smile:.

Before you go too far down that path, have you determined exactly where you bottleneck is? Could it be eliminated with the use of (smart) pointers, move semantics, etc? A lot of times the in my experience the bottleneck was copy operations rather than list / vector reorganization and access, etc.

If you determine that creating and destroying meshes is your bottleneck rather than moving them around, you might consider creating a “pool” of meshes with a vector of pointers to the active meshes. When you need to “revive” a mesh, you re-set its parameters and add its pointer from the pool (which “owns” the actual mesh in memory) and go from there.

Anyway … have fun! And follow the profiling data! I’ve been doing this for a while and my “intuition” for what takes a lot of cycles and what doesn’t is still not all that great … things that were slow last year or in C++98 are blazing fast in C++11, and on newer compilers.

1 Like

a vector is usually faster to access, mostly for small objects that are completely allocated in every position of the vector as opposed to complex objects that point to memory in the heap (as seems to be your case), for example for particle systems. when deleting objects, though, a vector can become slow since it’ll start to copy memory around if it needs more memory than it already has allocated at any time. Also a 2d vector can be even worse because when you delete positions they need to be completely reallocated again.

a lsit can help slightly since it doens’t need to copy memory when reallocating.

in any case the same name of your object, oscThread that also contains an of3dPrimitive which has a relatively complex geometry in both ram and the gpu memory sound more like the real problem. you have objects which seem to be doing network communication through osc, which internally starts it’s own thread, but you are also creating one more thread and mixing that with a highh use of memory in both ram and gpu. destroying and reallocating an object like that is going to be really slow no matter in which memory structure it’s stored. i would try to simplify that object for example by moving the osc communication to 1 object which updates all your vector and it’s never destroyed. such an object can work in a different thread if you are careful but it’s probably not even necessary. if that’s not enough i would try putting all the geometry somehow in one object or using instanced drawing but trying to optimize the memory structure is probably not going to give you much speed gains if you are still going to need to allocate and destroy objects so expensive as the ones you seem to be using

1 Like

Both of these replies are hugely helpful, and send me off towards plenty of places to learn more about. I tend to be afraid of too much premature optimization, but I know what I will need later can’t be handled in it’s current form. The suggestion about creating a separate object to update my vector seems like it could really help, it will just take some restructuring of things. Thank you both!

1 Like