Memory allocator suggestion

Question

I have multi-threaded section where threads need to allocate several large segments of data, say ~100MB each, to use as buffers. Moreover, buffers may need to be resized at run time Several times.

The natural solution is to use realloc but it may move memory which is not needed. free/malloc pair to resize buffer i am afraid may lead to fragmentation and reserving memory before hand creates other problems.

What can I use instead, to allocate/reallocate memory?

Answer 1

Use free and malloc. This will NOT cause fragmentation problems.

Modern allocators are fairly resistant to memory fragmentation. These days, it takes a fairly pathological program to cause fragmentation problems. Fragmentation was a more severe problem when our programs addressed physical RAM directly, but with virtual memory a large "hole" in a program's heap doesn't need to consume any resources.

Furthermore, due to the size of the buffers, most allocators will request a dedicated region from the kernel for each buffer. On Linux / OS X / BSD, this means an anonymous mmap behind the scenes for each buffer. This can cause fragmentation of address space, but virtual address space is basically free on a 64-bit system, and a few hundred megs isn't a problem on 32-bit either.

So use free and malloc.

Alternative: You might find it faster to make each buffer bigger than you need. The way malloc works on a modern Unix, any pages which you don't write to don't consume memory.

So if you malloc a 500 MB buffer but only use the first 100 MB, your program doesn't actually use more memory than if you malloc a 100 MB buffer and use the whole thing. You get more address space fragmentation this way, but that's not a problem on 64-bit systems, and you can always tune the allocation size so it works on 32-bit systems too.

As for suggestions to use mmap, just think of malloc/free as a simpler interface to mmap/munmap, which is what it is for large allocations (1 MiB is a common threshold).

Answer 2

Simply use realloc. On a modern system, even if the buffer gets moved to a new address, the move will happen by manipulating the page tables (on Linux, mremap; I'm sure other systems have a similar mechanism) and not by copying data. (Note here that I'm assuming large buffers; for small buffers, usually less than a few hundred kb, actual copying will happen.)

If your target is 64-bit machines, there's absolutely no need to worry about memory fragmentation. You'll never fragment memory badly enough to run out of virtual address space. If you need to handle 32-bit machines too, you're probably safe as long as you don't have too many threads. As long as the total memory consumption is less than 1GB, it would be very hard to run out of virtual address space due to fragmentation, assuming your usage pattern. If you are worried about it, just preallocate the largest size you might possibly need.

Answer 3

Implement your solution with malloc/realloc/free and profile it. If memory allocation is a problem, you can use a better implementaion of malloc such as facebook's jemalloc, or google's tcmalloc.

See C++ memory allocation mechanism performance comparison (tcmalloc vs. jemalloc) for a comparison of the two.

They are both pretty good at handling internal/external fragmentations.