Jump to content

  • Log In with Google      Sign In   
  • Create Account

Removing Large number of objects from vector immediately.


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
20 replies to this topic

#1 Solid_Spy   Members   -  Reputation: 452

Like
0Likes
Like

Posted 17 March 2014 - 11:54 AM

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.

 



Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13907

Like
1Likes
Like

Posted 17 March 2014 - 12:00 PM

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



#3 Solid_Spy   Members   -  Reputation: 452

Like
0Likes
Like

Posted 17 March 2014 - 12:10 PM

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.



#4 Álvaro   Crossbones+   -  Reputation: 13907

Like
1Likes
Like

Posted 17 March 2014 - 12:21 PM

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, 17 March 2014 - 12:23 PM.


#5 Solid_Spy   Members   -  Reputation: 452

Like
0Likes
Like

Posted 17 March 2014 - 12:25 PM

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, 17 March 2014 - 12:41 PM.


#6 gdunbar   Crossbones+   -  Reputation: 1013

Like
1Likes
Like

Posted 17 March 2014 - 12:39 PM

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



#7 Solid_Spy   Members   -  Reputation: 452

Like
0Likes
Like

Posted 17 March 2014 - 12:55 PM

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 sad.png.

 

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, 17 March 2014 - 12:56 PM.


#8 swiftcoder   Senior Moderators   -  Reputation: 10364

Like
2Likes
Like

Posted 17 March 2014 - 01:25 PM


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...


Tristam MacDonald - Software Engineer @Amazon - [swiftcoding]


#9 Ravyne   GDNet+   -  Reputation: 8154

Like
3Likes
Like

Posted 17 March 2014 - 01:26 PM

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).



#10 frob   Moderators   -  Reputation: 22718

Like
3Likes
Like

Posted 17 March 2014 - 02:15 PM

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.

Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I write about assorted stuff.


#11 Solid_Spy   Members   -  Reputation: 452

Like
0Likes
Like

Posted 17 March 2014 - 07:00 PM

 


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...

 

 

Games Like Minecraft will allocate hundreds of thousands of blocks at runtime to RAM, I'm trying to do something similar. 65,536, Objects., Is the total number of blocks in an Chunk in the Minecraft World. I'm Just experimenting with trying to create as many objects as fast as I can, to no avail :/.


Edited by Solid_Spy, 17 March 2014 - 07:04 PM.


#12 Solid_Spy   Members   -  Reputation: 452

Like
0Likes
Like

Posted 17 March 2014 - 07:04 PM

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.

But Then how would one build their own memory manager? That Sounds like It May be a lot Of Work. As a Sole independent game developer, Idk if I would go that far, but If you know any resources that could help me learn the basics, do you know of any websites that could help me out?

 

Oh, and Thnx everyone for the help :3 .


Edited by Solid_Spy, 17 March 2014 - 07:09 PM.


#13 Ravyne   GDNet+   -  Reputation: 8154

Like
2Likes
Like

Posted 17 March 2014 - 07:38 PM

I'll say again, your problems likely stem from your *pattern* of deletion, rather than the outright number of things being deleted. Depending on what makes up your other objects, though, the deletions themselves might be taking up a significant amount of time. What's in each object? Does it own other memory or resources that need to be freed?

 

On the topic of custom memory management routines, its not actually all that much work if one knows what they're doing. Its hours or days of work for one developer, depending on the features you want, not weeks or months. Typically what it involves is block allocation, wherein a single object is never allocated, but instead several object's worth at a time are allocated, and some additional book-keeping tracks objects-worth of memory that are unused. These spaces are re-used when "empty" but never deleted unless the entire chunk is freed.

 

But again, even though custom memory management doesn't need to be complex or scary, all signs point towards poor usage patterns IMO (or perhaps unrealistic expectations, depending on what destructors do), not to the kinds of problems that a custom memory manager would solve.



#14 swiftcoder   Senior Moderators   -  Reputation: 10364

Like
2Likes
Like

Posted 17 March 2014 - 07:49 PM

Games Like Minecraft will allocate hundreds of thousands of blocks at runtime to RAM, I'm trying to do something similar. 65,536, Objects., Is the total number of blocks in an Chunk in the Minecraft World. I'm Just experimenting with trying to create as many objects as fast as I can, to no avail :/.

I highly doubt that minecraft allocates 2^16 separate objects to represent a single 16*16*256 chunk of cubes.

It would generally be stored as a single 2^16 element array of bytes, where each byte represents the type of a single block (or zero for an empty block). For rendering you would walk over this structure and generate a suitable vertex buffer - which again, is a flat array of vertices.

Moral of the story: allocating many thousands of small objects is almost always something which should be avoided.

Tristam MacDonald - Software Engineer @Amazon - [swiftcoding]


#15 Ravyne   GDNet+   -  Reputation: 8154

Like
3Likes
Like

Posted 17 March 2014 - 07:58 PM

I suppose next time I should read your code :)

 

So, I see you're not explicitly deleting individual elements in a loop, however, you still need to understand that the destructor is being called for each object when you delete the list. For these particular objects, the destructor is simple since you've just got a POD type. But the problem is that you're hitting the built-in memory manager's deallocator 65k times -- since memory is a shared resource, taking or returning memory to the pool can be non-trivial.

 

So, I take it back. This probably is the kind of problem that a pooled memory manager would benefit you. Conceptually, think of it as allocating a raw array of 65k objects, and then creating shared-pointers to those objects within it. Now, if the destructor for those items does work you still need to call them but you don't need to deallocate the memory -- but if they do no work, then you can just reuse those element-spaces that are dis-used, and deallocate that huge array when you're done with all of them. If you abstract that, and throw in a little book-keeping you end up with a pooled memory manager, though usually you will use smaller chunks.

 

All that being said, understand that you're allocating 64 MB of data here, in small chunks, and this is what causes you to hit the standard deallocator so much-- and its probably taking locks and crossing into kernel-space every time. That's not cheap.



#16 Javier Meseguer de Paz   Members   -  Reputation: 371

Like
6Likes
Like

Posted 18 March 2014 - 06:38 AM

 

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 sad.png.

 

I switched to release mode and disables Secure Scl, and it improved, but not by much.

 

Since you mention SCL I assume you are using Visual Studio. Are you running your program with F5 or with Ctrl+F5? It is not the same. 

 

When you run your program with Visual Studio hooked to your process memory allocation / deallocation is far slower. (EVEN if you are in Release mode). This is thanks to the so-called DEBUG HEAP smile.png

 

I have a ~15 seconds delay (Visual Studio 2012, Release Mode, Win64) when running with F5, but the code runs instantaneously when using Ctrl+F5 (AKA: running the program process independently of VS).

 

Look at this question of Stack Overflow for more information: http://stackoverflow.com/questions/6486282/set-no-debug-heap (it is tagged as C#... but it is not a C# question).

 

PS: Regardless, using a custom stack memory allocator (http://molecularmusings.wordpress.com/2012/08/27/memory-allocation-strategies-a-stack-like-lifo-allocator/) might be a good optimization is you see that you have a bottleneck here. But as always, MEASURE before optimizing. Remember that "optimization is the root of all evil (Donnald Knuth)" ;) 


Edited by Javier Meseguer de Paz, 18 March 2014 - 06:42 AM.

“We should forget about small efficiencies, say about 97% of the time; premature optimization is the root of all evil” -  Donald E. Knuth, Structured Programming with go to Statements

 

"First you learn the value of abstraction, then you learn the cost of abstraction, then you're ready to engineer" - Ken Beck, Twitter


#17 gdunbar   Crossbones+   -  Reputation: 1013

Like
0Likes
Like

Posted 18 March 2014 - 07:25 AM

Well, I tried out what the OP said, and I'll be damned if he wasn't correct. Calling delete 65000 times does indeed take about 5 seconds on my system. I'm actually somewhat surprised, but when reality differs from your thoughts, I find reality is usually correct.

 

However, calling delete[] on a 65000 long array is near instantaneous. Also, calling std::vector::resize( 0 ) on a vector of objects (not pointers!) is also super fast. So, for the OP, I would advise storing objects directly in a std::vector, rather than pointers. Only if that is impossible should you look into the more complicated allocation pooling solutions.

 

Geoff

 

Code:

 

// ConsoleApplication1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>

#define FOONUM 65000

static int iConstructor = 0;
static int iDestructor = 0;
class CFoo
{
public:
    CFoo() { iConstructor++; }
    ~CFoo() { iDestructor++; }

    char chFoo[ 256 ];
};

int _tmain(int argc, _TCHAR* argv[])
{
    CFoo *fooArray[ FOONUM ];

    int i;
    for( i = 0; i < FOONUM; i++ )
    {
        fooArray[ i ] = new CFoo;
    }

    for( i = 0; i < FOONUM; i++ )
    {
        delete fooArray[ i ];
    }

    CFoo *fooArray2;
    fooArray2 = new CFoo[ FOONUM ];

    delete[] fooArray2;

    std::vector< CFoo > fooArray3;
    fooArray3.resize( FOONUM );

    fooArray3.resize( 0 );

return 0;
}

 



#18 gdunbar   Crossbones+   -  Reputation: 1013

Like
0Likes
Like

Posted 18 March 2014 - 07:30 AM

Well, I tried out what the OP said, and I'll be damned if he wasn't correct. Calling delete 65000 times does indeed take about 5 seconds on my system. I'm actually somewhat surprised, but when reality differs from your thoughts, I find reality is usually correct.
 
However, calling delete[] on a 65000 long array is near instantaneous. Also, calling std::vector::resize( 0 ) on a vector of objects (not pointers!) is also super fast. So, for the OP, I would advise storing objects directly in a std::vector, rather than pointers. Only if that is impossible should you look into the more complicated allocation pooling solutions.

 

Well, today is my day for not believing people! Someone else said "run without debugging, and it will be much faster". Sounded like hogwash to me. But, when I did that exact experiment, it was correct! So, OP, you may not have a "real world" issue at all. And, Javier Meseguer de Paz, apologies for not believing you at first!

 

Geoff


Edited by gdunbar, 18 March 2014 - 07:31 AM.


#19 jHaskell   Members   -  Reputation: 1087

Like
1Likes
Like

Posted 18 March 2014 - 07:31 AM


Since you mention SCL I assume you are using Visual Studio. Are you running your program with F5 or with Ctrl+F5?

 

This.  I run the OPs code in debug mode, and it does take several seconds to delete the vector.  Run it without debugging and everything is apparently instantaneous.  Would have to add in some timing code to see how long everything takes.



#20 osmanb   Crossbones+   -  Reputation: 1628

Like
3Likes
Like

Posted 18 March 2014 - 10:32 AM

No, you really don't need to time anything. (As a rule, yes - you should). But in this case, Javier is right. The calls to free memory underlying the delete calls are what's taking forever, and it's because the debug heap is enabled. The debug heap verifies the integrity of the entire heap (by ensuring that every allocation's bookkeeping information is still correct) on EVERY free call. Programs that thrash the system (win32) heap run incredibly slowly with the debug heap enabled, period.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS