Removing Large number of objects from vector immediately.

This topic is 1771 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hello, I've been experimenting with STD::Vector, And I've been trying to find the most efficient way to delete a large number of items from an Std::Vector, In the fastest way possible.

This Is the program I have been writing:

#include<iostream>
#include <memory>
#include <vector>

using namespace std;

struct SmallObject1
{
int a[256];
};

int main()
{
char a;
typedef vector<shared_ptr<SmallObject1>> ObjectList;
ObjectList * list1 = new ObjectList();
cout << "Allocate 65536, objects Lol!" << "\n";

for(unsigned int i = 0; i < 65536; i++)
{
SmallObject1 * smallObject1 = new SmallObject1;
shared_ptr<SmallObject1> a(smallObject1);
list1->push_back(a);
}

cout << "Allocated! Try Again?" << "\n";
/*while(list1.size() != 0)
{
list1.pop_back();
}*/
//list1->clear();
delete list1;
list1 = new ObjectList;
cout << "Deleted....";

for(unsigned int i = 0; i < 65536; i++)
{
SmallObject1 * smallObject1 = new SmallObject1;
shared_ptr<SmallObject1> a(smallObject1);
list1->push_back(a);
}

cout << "COMPLETE!!!1!!!";
while(1)
{
}

return 0;

}

If I were Writing a video game, and I was transitioning to another level, I Would want to remove the objects for Level 1 from the list as Fast As Possible. However, All the methods I've tried seemed to result into waiting a couple of seconds for the objects to be deleted.

I'm thinking of removing all the objects on a separate thread, And allocating the New objects on the main thread, in a Separate list, and then after the objects are removed, then append the list to the main list. But I'm not sure if it will work, and I know next to nothing about Multi-Threading :( .

Anyways, I was wondering if anyone has any alternative solutions to this dillema, as I can't seem to find a faster method.

Share on other sites

Why all the pointers? Why is your vector not simply of type std::vector<SmallObject1>'? And why is the vector itself a pointer?

Share on other sites

Why all the pointers? Why is your vector not simply of type std::vector<SmallObject1>'? And why is the vector itself a pointer?

They Are all pointers so that way I can share the objects with multiple lists (Display Lists, Collision lists, etc...), and the vector being a pointer so I can reference it to multiple objects that need the list.

Share on other sites

Well, isn't there one of the vectors that naturally owns all those objects? The other vectors can store indices into the owner.

EDIT: The part about the vector being a pointer I didn't understand at all.

Edited by Álvaro

Share on other sites

Well, isn't there one of the vectors that naturally owns all those objects? The other vectors can store indices into the owner.

EDIT: The part about the vector being a pointer I didn't understand at all.

Ah, well I guess it doesn't need to be a Pointer vector, however If I had a Physics Class, or a Rendering Class, I might want each class to have an empty ObjectList * objectList variable to hold a reference to the list if it needs it.

Nyways, I tried converting the list to one Without smart pointers, and now it is much much faster, It works almost immediately. But,  I need to use pointers, because if I have a base class of GameObject, that inherits to multiple different Classes, I will need a Vector of Pointers instead of just a GameObject Vector.

Edited by Solid_Spy

Share on other sites

How have you profiled this code? I suspect that the "delete list1;" call might be pretty quick compared to the allocations and push_back() calls (which will dynamically resize your vector). First step is to verify that the slow part is actually what you think it is.

Second step is to be sure you are using a non-debug build, as allocations and deletes can be significantly slower with debug builds.

If you are using Visual Studio, be sure to turn off the STL debugging stuff, too, as that can be frightfully slow.

OK, if all of that doesn't help (and I think it will), the big optimization I can think of is to move away from std::vector and use the C-style array allocation mechanism directly. Then you can allocate and free a while bunch of objects at once. This is not nearly as maintainable, though, so be sure to exhaust other possibilities first.

Hmm... an object pool could work too. Also to be avoided if possible.

Good luck!

Geoff

Share on other sites

How have you profiled this code? I suspect that the "delete list1;" call might be pretty quick compared to the allocations and push_back() calls (which will dynamically resize your vector). First step is to verify that the slow part is actually what you think it is.

Second step is to be sure you are using a non-debug build, as allocations and deletes can be significantly slower with debug builds.

If you are using Visual Studio, be sure to turn off the STL debugging stuff, too, as that can be frightfully slow.

OK, if all of that doesn't help (and I think it will), the big optimization I can think of is to move away from std::vector and use the C-style array allocation mechanism directly. Then you can allocate and free a while bunch of objects at once. This is not nearly as maintainable, though, so be sure to exhaust other possibilities first.

Hmm... an object pool could work too. Also to be avoided if possible.

Good luck!

Geoff

Well, Every time I allocate all 65,536 Objects to the list, it happens very quickly, however deleting the list actually takes around 5 seconds, and I don't know why .

I switched to release mode and disables Secure Scl, and it improved, but not by much. I don't want to switch to the c-Style array until I have run out of options.

I know that games like minecraft have to allocate and deallocate Hundreds of Thousands of blocks and game objects at runtime, so there HAS to be a solution to this..

Edited by Solid_Spy

Share on other sites

Every time I allocate all 65,536 Objects to the list

Why on earth are you allocating and deleting 2^16 objects? That seems like an awful lot of items...

Share on other sites

Are you deleting things one at a time?

Whenever you delete an item from a vector that's not the last thing, all the elements afterwards get copied one space forward to fill the gap, and if you delete many items one at a time, at some point a re-allocation might occur to save memory space. So, for example, if you were to loop through the vector front-to-back deleting individual items, you're pretty much guaranteeing a pathologically-bad use-case. Doing the same back to front is a little better, but not by much (fewer iterations, but I don't think even enough to change the Big-O order).

The right way to delete many items from a vector is to first partition the vector into things you will keep, and things you will delete, and then you delete the things you want to get rid of after that. The way to do that is to call remove_if on your vector with a predicate that sorts the things you want to keep from those you don't. Then, it returns an iterator to the first thing that's removed, and you can use that iterator to call delete over the range from that iterator to the end of the container. This is better because only individual items are copied, and at most once. Also the memory re-allocation can only happen once, if it needs to.

Also, in regards to your using pointers, someone mentioned that one container could own the resource directly, and other vectors could reference them by index. If you frequently add/remove items from the owning list, the indexes will change every time you add or delete and item. This makes using indexes troublesome, unless you can build-up those indices in the other lists anew -- this is fairly common for a list of drawable objects, but might not be common for other uses. It depends on your use-case. Pointers of some type might be perfectly valid, but I'd look into the standard smart pointers like shared_ptr, weak_ptr, and unique_ptr. From your brief description, it sounds like you might want to do shared_ptr in the owning list, and weak_ptr in the other lists (unless you can build up those lists each frame, between delete/insert cycles).

Share on other sites
You might be describing the problem of running all those destructors. Some have described it as taking time to empty the trash bins while tearing down a building.

C++ provides a lot of great functionality. One very useful thing the standard library guarantees is that when you start destroying objects their destructors and other cleanup code gets called.

The problem with that: Sometimes you don't want their destructors and other cleanup code to be called.

Many systems (frequently game, but also many business apps) will replace the default memory managers for containers to provide a method to just wipe everything out. No destructors, no cleanup, just release the memory.

This is one of many reasons why professional games tend to throw away the built-in memory manager and use their own. The standard library guarantees are nice, but with insufficient features. Pulling from a global pool can be time consuming, fragmentation of a global pool can be problematic, game-specific alignment needs are more nuanced than the standard specifies, and cleaning up memory when cleanup is unnecessary can be uselessly slow.

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 9
• 11
• 9
• 9
• Forum Statistics

• Total Topics
634135
• Total Posts
3015753
×