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

Posted on 2009-02-16
Last Modified: 2012-05-06
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?
Question by:bali2u
    LVL 53

    Accepted Solution

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

    Expert Comment

    This is basically implementing your own (simple) heap manager on top of the Visual C++ heap manager.
    LVL 30

    Assisted Solution

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

    LVL 39

    Assisted Solution

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

    Assisted Solution

    Sice you are apparently on Windows, one *attempt* (not guaranteed to give the expected results in all situations) might be calling 'HeapCompact()' (, e.g. like

    Open in new window

    LVL 5

    Assisted Solution

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

    See the basic concepts explained here:

    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.

    LVL 39

    Expert Comment

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

    Featured Post

    Are end users causing IT problems again?

    You’ve taken the time to design and update all your end user’s email signatures, only to find out they’re messing up the HTML, changing the font and ruining the imagery. What can you do to prevent this? Find out how you can save your signatures from end users today.

    Join & Write a Comment

    Several part series to implement Internet Explorer 11 Enterprise Mode
    NTFS file system has been developed by Microsoft that is widely used by Windows NT operating system and its advanced versions. It is the mostly used over FAT file system as it provides superior features like reliability, security, storage, efficienc…
    The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
    Get a first impression of how PRTG looks and learn how it works.   This video is a short introduction to PRTG, as an initial overview or as a quick start for new PRTG users.

    755 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    23 Experts available now in Live!

    Get 1:1 Help Now