Why region based memory allocation help with fragmentation

November 26, 2021

Recently, I read an advocacy article on Go's garbage collection as compared to Java (via, which has important criticisms of the technical content, also). One of the things it mentioned is that Go's region based memory allocation reduces memory fragmentation. This struck me as both correct and not entirely obvious, so I want to talk about why region allocation helps.

A classical simple memory allocator maintains a pool of blocks of unallocated memory of various sizes. When you ask to allocate some amount of memory, in the ideal case there is a free block of exactly the right size and you get it. If there isn't, the allocator breaks up an existing free block that is larger than you need, handing you the now-allocated part and putting the remaining smaller block of free memory back in the pool. When you free memory again, the allocator adds it to the pool and then attempts to merge it with adjacent blocks to make a larger block of free memory. If you ask the allocator for a larger amount of memory than it has in a free block (for example, you ask for 64 Kb when the largest free blocks are 32 Kb), the allocator gets more memory from the operating system and returns some or all of it to you as your allocation.

(The simple but often slow way to maintain the pool of free memory blocks is as an ordered linked list.)

This simple memory allocator is vulnerable to fragmenting memory over time, because it starts out with large blocks, breaks them up as you ask for various amounts of memory, and can only merge freed allocations back into the original large blocks if everything in the block is free. If you start with a 64 Kb block, allocate all of it in various sized chunks, and then free most of it, you might be unlucky and wind up with small remaining allocated pieces that prevent you from having any large contiguous runs of free memory (you could also be lucky). This mixture is quite possible because consecutive chunks of memory are often allocated in roughly time order, and programs ofter intermix small and large allocations (first they want a small chunk, then a big chunk, then a few small chunks again, and so on).

Region allocators (such as Go has) break up (free) memory into regions where each region is dedicated to a single (rounded) size of object allocation, and these fixed size objects are arranged so that none of them cross page boundaries or always occupy a fixed number of pages (usually people assume 4 Kb pages). This makes allocating and freeing objects easier, automatically groups similar objects together, and allows relatively flexible reuse of free memory pages (a free page can be allocated to any small object size class).

Because region allocation never repeatedly breaks up a large block of memory for different allocations (especially different sized ones), you can't wind up in the original situation of a large amount of free memory that can't be merged together into a large block because there are a few allocated spots in the middle. Those allocated spots would be in their own regions, not in the middle of a valuable large block of a different (large sized) region. Region allocators do especially well at keeping small allocations from interfering with the free memory used for larger ones, even (or especially) when the program intermixed the allocation of the various sizes. The program may intermix its requests for various sizes, but the region allocator separates them out again.

Because programs often allocate a lot of objects that are page sized or less, region allocators can often usefully reuse even relatively modest chunks of free memory. If the region allocator works at the level of single pages (instead of larger blocks of them), a free page can be recycled for any size of small objects that happens to be in demand at the moment.

Overall, I think we can say that region allocation reduces fragmentation by making the order of allocating and freeing memory less important. If you intermix allocating a bunch of different sized objects and then don't free all of them (or delay freeing them for a long time), in a simple allocator you wind up with allocated holes in your free ranges. In a region allocator, those different sized allocations go to different regions, and failing to free all of the objects of one size (in one region) doesn't cause problems for other regions of other sizes.

(Region allocators have their own forms of fragmentation, but it's often harder to have happen. A discussion of region allocator fragmentation is beyond the scope of this entry.)


Comments on this page:

By Rick Hudson at 2021-12-06 07:36:34:

Allocation in these segregated size schemes is also very fast. A simple bit map can indicate where an object can be allocated and there is usually an NSA instruction like ctz laying around to locate the free bit. This makes the cost of finding the a free slot negligible when compared to zeroing the object.

Nice article.

- Rick

Written on 26 November 2021.
« Computation that needs to be "secure" is everywhere in practice
How we use the SLURM job scheduler system on our compute servers »

Page tools: View Source, View Normal.
Search:
Login: Password:

Last modified: Fri Nov 26 00:54:44 2021
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.