We help IT Professionals succeed at work.

We've partnered with Certified Experts, Carl Webster and Richard Faulkner, to bring you a podcast all about Citrix Workspace, moving to the cloud, and analytics & intelligence. Episode 2 coming soon!Listen Now

x

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

bali2u
bali2u asked
on
Medium Priority
1,249 Views
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?
Comment
Watch Question

CERTIFIED EXPERT
Top Expert 2009
Commented:
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.

Not the solution you were looking for? Getting a personalized solution is easy.

Ask the Experts
CERTIFIED EXPERT
Top Expert 2009

Commented:
This is basically implementing your own (simple) heap manager on top of the Visual C++ heap manager.
CERTIFIED EXPERT
Commented:
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 ...

ZOPPO
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.
jkr
CERTIFIED EXPERT
Top Expert 2012
Commented:
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
HeapCompact(GetProcessHeap(),0);

Open in new window

Commented:
I suggest using "Object Pool" from boost library, it was created for such tasks exactly:
http://www.boost.org/doc/libs/1_37_0/libs/pool/doc/index.html

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.

Michael
>>>> 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
Access more of Experts Exchange with a free account
Thanks for using Experts Exchange.

Create a free account to continue.

Limited access with a free account allows you to:

  • View three pieces of content (articles, solutions, posts, and videos)
  • Ask the experts questions (counted toward content limit)
  • Customize your dashboard and profile

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.