Jump to content
  • Advertisement
Sign in to follow this  
Haytil

Cleaning Up - Stalling When Deleting Huge Arrays

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello,

I have written some numerical simulation code in C++, which runs in a Win32 console. Nothing fancy.

My code deals with huge amounts of randomly-generated numerical data, but even so, it runs pretty fast and smoothly.

However, I have found that - once the simulation is complete - the program appears to stall at the end, when deleting all of the program objects and allocated memory. So the simulation runs fine, except at the end, during cleanup.

My simulation, at the beginning, essentially allocates a huge array of objects (each object representing an agent in my agent-based simulation). This allocation occurs all at once, though each individual object will have to allocate memory as well (see below). I am currently dealing with 10,000 agents (so allocating a dynamic array of 10,000 instances of this class).

Each object, upon initialization, allocates something on the order of 40 kB of memory. Each object also has 2 STL deques, which increase in size during run-time, but peak at around 2 kB of memory.

So all-told, the program initially allocates 400 MB of memory, and increases to a peak of about 500 MB during run-time.

Again, the program runs fine. But when cleaning up these 500 MB of memory, the program slows down. As the program continues to clean up, the program continues to run slower and slower.

I investigated the cleanup behavior by stepping through with the debugger. I said there are 10,000 agents. When deleting the array, the destructors of the agents are called in reverse order. So the 10,000th agent's destructor is called first (where the 40-50 kB of memory that agent had allocated is released). Then the 9,999th agent's destructor is called. And so forth.

The total time it takes to delete the first 1000 agents (so Agents 9000-9999) is at most a second. But the next 1000 agents (Agents 8000-8999) take something like twice as long. The next 1000 after that take twice as long as the previous thousand. And so forth.

So by the time I'm trying to clean up Agents 500-1000, I'm waiting 30 seconds. I can't even get down to the last agent, because the cleanup time per agent ramps up so high - i.e., as I said, the progam appears to stall. While it's running this cleanup code, of course, much of the allocated RAM remains allocated, and the CPU usage remains as high as ever.

Though I don't think it would cause this issue, I have checked my code for memory leaks, dangling pointers, and so forth, and my code looks fine.

Can anyone provide any insight to this behavior?

Though the "stall" doesn't seem to last forever, and is quite manageable, with far fewer numbers of agents, such a workaround is undesirable, as my program really needs to be able to handle something like 10,000 agents. Additionally, the code may eventually be run on a grid computing kind of service with multiple instances (testing different parameters in the simulation), and so a program that appears to stall - but still eats up CPU time and RAM - won't be accepted

Thank you.

Share this post


Link to post
Share on other sites
Advertisement
What most programs do when freeing data on exit is touch lots of memory that's not in the CPU cache, and is quite possibly paged out to disc. Also note that programs that are launched from the debugger automatically use the Windows debug heap which is much slower than the non-debug one, try testing performance when starting without debugging too. A good profiler should be able to give you more detail on what's going on.

There's a simple solution for both of those issues - exit without deleting anything. The operating system will free the memory for you on exit, and do it much quicker than you can any other way. Note that the C++ runtime will call the destructors of all globals when it's shut down, so make sure your globals aren't actual objects - pointers are fine.

http://blogs.msdn.co...5/10253268.aspx

The only downside is that you need to make sure that destructors that you are avoiding calling don't do anything vital, like flushing file output buffers.

You may also want to leave the deletion code in there in debug builds to aid leak checking.

Share this post


Link to post
Share on other sites
If this is at program exit, you can leak it as described. Leak everything and let the OS clean it up for you.

If for some reason you cannot do that, or leaking memory like that offends you, an option is to spawn a delete thread. You can use a single small function that deletes the objects. Just create the thread, swap the thread's empty version with the main app's full version, and let the new thread do the work.

It sounds like a lot of work, but isn't too bad. It's a small static function, a static data member that you can swap if it is empty, and about twenty lines of code to spawn, swap, and clean up. If the target member is not empty you just delete and clean up in your main thread. I'm sure Google can find some examples.

Share this post


Link to post
Share on other sites
Thanks for the replies. It sounds like the most pragmatic solution is indeed to avoid cleanup entirely, and trust the OS to handle it.

The programmer in me really doesn't like that, as it goes against everything I know about "best practices." But perhaps the reality of the situation prevents me from being able to stick to my ideals 100% of the time. I guess that's life.


If for some reason you cannot do that, or leaking memory like that offends you, an option is to spawn a delete thread. You can use a single small function that deletes the objects. Just create the thread, swap the thread's empty version with the main app's full version, and let the new thread do the work.


But won't the new thread still be churning the CPU along at full throttle, just as the original thread was doing during cleanup? I don't see how handing off the main thread's problems to a new thread will mean the machine isn't dealing with the same issues.

I guess it would mean the main thread would be free to do other stuff in the meantime, so there is that benefit. But the only thing that would come next would be either a new simulation or a different program entirely, both of which would require the system resources that seem to be endlessly stuck in the "cleanup thread."

Share this post


Link to post
Share on other sites
(De)Allocation is symmetric. On allocation, constructors initialize the memory. On destruction, memory isn't even overwritten.

If destruction time grows, there's something else going on. 30 seconds for 400MB, even with ~50k objects is a bit much for an O(n) problem.

What do destructors look like? Are they updating membership perhaps? Such as, when an agent is destroyed, does it remove itself from some list? This can easily lead to described behavior.

If all destructors are empty, then at least use a custom allocator, especially for queues.

as it goes against everything I know about "best practices."[/quote]

It's the "best practices" that is wrong. See here, for example.

As the article explains - the building is being demolished and you're worried about emptying the trash cans.

Share this post


Link to post
Share on other sites

But won't the new thread still be churning the CPU along at full throttle, just as the original thread was doing during cleanup? I don't see how handing off the main thread's problems to a new thread will mean the machine isn't dealing with the same issues.

I guess it would mean the main thread would be free to do other stuff in the meantime, so there is that benefit.

But the only thing that would come next would be either a new simulation or a different program entirely, both of which would require the system resources that seem to be endlessly stuck in the "cleanup thread."


The biggest thing is it frees up the application to do other things. That can include destruction of the UI and otherwise making the program appear dead. You will notice that when you close many large programs, the application and a huge chunk of memory remain present in your task manager for quite some time with gradually decreasing memory requirements, even though it looks like the app is gone.

From the user's perspective there is very little stuff going on at that point. It is done, and the user can move on. Memory dealllocation in a background thread will have a negligable impact from the human perspective, although you are right it will continue to consume resources.





If destruction time grows, there's something else going on. 30 seconds for 400MB, even with ~50k objects is a bit much for an O(n) problem.

What do destructors look like? Are they updating membership perhaps? Such as, when an agent is destroyed, does it remove itself from some list? This can easily lead to described behavior.

...

It's the "best practices" that is wrong. See here, for example.

As the article explains - the building is being demolished and you're worried about emptying the trash cans.



I have seen this type of thing in practice on game tools. One notorious tool effectively cached the parsed file tree. Caching the computed details itself was a good thing for the tool; cache on load when certain assets can potentially be reused thousands of times can dramatically improve running performance. Before the cache each run could take hours for a full rebuild, dropped to minutes with parse cache enabled.

At shutdown, though, not so much of a performance improvement. smile.png They are not contiguous memory blocks, but std::list of objects, and most objects contained std::list of objects, ultimately these containing std::string, std::vector, and other destructor-required objects. After a few days of use, the tool could require over 20 minutes within the cache destructor.

Because there a few things in the cache were persisted they didn't just leak the whole thing. Instead it was moved to a new thread and the main thread was allowed to complete while the cleanup took place in the background.


I agree about the empty-the-trash-cans description and link. Usually that is correct. Many objects are best leaked at application shutdown.

Share this post


Link to post
Share on other sites
Are you using Visual Studio and execute your program from inside of MSVS (F5), even if it is compiled in release mode ? I could be wrong, but MSVS does some memory checking, even in release mode, so try to run your program from outside of MSVS and look if it gets faster.

Share this post


Link to post
Share on other sites
I've been through the same problem as you already. The problem isn't the amount of memory you use but actually the number of allocations and frees that you do because these are slow operations. A solution to that problem is to use a memory pool that is shared among your agents, i.e. a pre-allocated large chunk of memory that you use to store your agents data.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!