• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1160
  • Last Modified:

How can I deframgent memory to avoid std::bad_alloc exception?

i'm creating a tree of small objects (1-2 KB in size) but the number of elements can be more than 2 millions. After creating the tree I've to process each item and this processing require some memory buffers of 1 to 4 MB. The allocation of these buffers is failed because the memory is fragmented.
I also delete upto 100,000 elements when std::bad_alloc exception is caught but even that does not provide enough contagious memory for 1 or 2 MB buffer.
I can't preallocate the memory for future user. Is there any way to de-fragment the memory in Visual C++ on 32-bit windows?
5 Solutions
Instead of allocating small blocks for the objects in the tree, consider allocating one big block, and then using parts of that  block to use for the tree objects.

For example, if you have to store 100 objects of size 1kB in the tree, then allocate one big block of 100kB, and use that block for the 100 objects.
This is basically implementing your own (simple) heap manager on top of the Visual C++ heap manager.
Hi bali2u,

in general it's not possible to do a generic memory defragmentation in C/C++ applications since the runtime doesn't know about any pointers which point to memory locations which need to be moved while defragmenting.

You could try to implement some kind of memory management like this: Store the data in chunks of memory and in the tree only store pointers to the objects. Whenever you run into lack of memory or periodically you can try to move objects (and modify the stored pointers) between those memory chunks to generate as much empty chunks as possible - these than can be removed.

BTW, I think it's anyway not good that your application is such near on memory limits. Maybe you should think about some other possibilities, i.e. moving to 64-bit or compressing the data or writing data to files or database ...

Cloud Class® Course: Microsoft Office 2010

This course will introduce you to the interfaces and features of Microsoft Office 2010 Word, Excel, PowerPoint, Outlook, and Access. You will learn about the features that are shared between all products in the Office suite, as well as the new features that are product specific.

Instead of using normal arrays (containers) to store your entries thus having the issue that the container needed to grow by allocating always bigger contiguous buffers without ever be able to reuse freed memory, you might consider to using pointer arrays as zoppo suggested or alternatively a container that was called HAT (hashed array tree). That container manages a tree of arrays rather than one single contiguous array, what has two advantages. (1) There is no need of a huge contigous piece of memory for the final array, e. g. instead of a memory of 256 MB, it would need 16K times 16KB blocks what is much easier from heap manager to provide as the big peace. (2) When dynamically increasing the container it could reuse most of the freed buckets as the sizes are relatively small, e. g. if going from 128MB to 256MB the heap manager could reuse any contiguous pair of two former 8KB buckets to allocate a new 16KB bucket.
Sice you are apparently on Windows, one *attempt* (not guaranteed to give the expected results in all situations) might be calling 'HeapCompact()' (http://msdn.microsoft.com/en-us/library/aa909017.aspx), e.g. like

Open in new window

I suggest using "Object Pool" from boost library, it was created for such tasks exactly:

See the basic concepts explained here: http://www.boost.org/doc/libs/1_37_0/libs/pool/doc/concepts.html

Basically it allocates a large block of memory in advance, and provides allocate/delete API which works in O(1). In our projects wew usually override the new/delete operators to make it use a global pool, so you don't have to change the rest of the program, and you can always easily switch back to "normal" allocation.

>>>> If you do not respond, I may need to assume that no correct answer was provided.
Hi angelIII,

all those answers above were valid.

If there are enough points I would recommend to making an equal split among the participients.

If not, take the first.

Regards, Alex
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Cloud Class® Course: Certified Penetration Testing

This CPTE Certified Penetration Testing Engineer course covers everything you need to know about becoming a Certified Penetration Testing Engineer. Career Path: Professional roles include Ethical Hackers, Security Consultants, System Administrators, and Chief Security Officers.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now