Prevent memory fragmentation

Question

Can anyone point me to a source or outline how the algorithm for the low-fragmentation heap works?

It sounds like most people are reading the question as, "How does one create and allocator that has minimal fragmentation?". But I think the author means, "Which algorithm does Windows's Low-Fragmentation Heap use?" The answer to that question doesn't turn up with a simple search. — Adrian McCarthy, Feb 16 '10 at 21:38

score 1 · Accepted Answer · edited May 23 '17 at 12:30

First decide which 'multiples' you want to use for the allocated memory chunks. I typically use 8 bytes.

At startup of the application, make a vector where each element in the vector points to a 'pool' of memory chunks. The first index in the vector will be for memory allocations of 8 bytes or less. The second index in the vector will be for memory allocations from 9-16 bytes, and so on.

Within every pool, allocate memory in bigger chunks. E.g. in the pool for allocations of 8 bytes (or less), don't allocate 8 bytes, but allocate N times 8 bytes. Within the pool remember which parts are really allocated in the application and which parts are just waiting to be allocated.

When freeing memory, don't free it immediately, but keep some chunks ready for the next allocation of that size. Only if you have a lot of subsequent free chunks, return the free memory to the operating system.

That's the basic idea. The rest is implementing the pools (typically linked lists of chunks).

The difficult part is integrating the heap implementation into the application.

If you are still using malloc/free, use #define's to redefine malloc and free
If you use new/delete, define global new and delete operators

Also take a look at How to solve Memory Fragmentation, and my comment at Memory management in memory intensive application

score 1 · Answer 2 · answered Sep 10 '11 at 14:50

From MSDN:

The LFH is not a separate heap. Instead, it is a policy that applications can enable for their heaps. When the LFH is enabled, the system allocates memory in certain predetermined sizes. When an application requests a memory allocation from a heap that has the LFH enabled, the system allocates the smallest block of memory that is large enough to contain the requested size.

This strategy is used by many memory managers, though the details can vary.

Prevent memory fragmentation

2 Answers2