I keep hearing that memory pools can signficantly improve performance when allocating memory.. so why aren't they used in some way by traditional malloc implementations?
I know part of it is that memory pools use fixed sized blocks of memory but seems like some don't and the only thing they require is grabbing a little extra memory in advance. Is there a way they could be sufficiently generalized for such purposes?
Memory pools can be more efficient than generalised memory allocation, but usually only because you have extra information about the allocation patterns. Perhaps their most important property is that they are deterministic in their run time, especially important in, for example, real-time operating systems.
As an example, I once coded up an embedded system where I knew the largest allocation needed was 128 bytes (called a chunk hereafter). To that end, I maintained a contiguous set of chunks and used a map for deciding whether one was free or not.
It was originally a bitmap but we ended up getting more performance simply by storing each used/unused flag in a separate byte. Eight times as much memory usage for the map but, since the pool size was known and reasonably limited (a thousand or so), that wasn't too bad. And it gave us even more speed by not having to do bit twiddling to do pool management.
And there were other optimisations we added like storing the first free block so we could quickly find it. It was easy to maintain since:
Then, if you asked for more than the chunk size, it returned NULL (this never happened in that system but, being paranoid, I coded for it just in case). If you asked for something that would fit in a chunk, you got a full chunk regardless (but, of course, you should still only use the memory you asked for, just in case I wanted to later change the chunk size or allocate from separate pools with differing chunk sizes).
This turned out to be much faster than the generalised allocators that were around at the time, since they had to handle differing request sizes and worry about things like coalescing contiguous free blocks when freeing memory.
But it required that extra knowledge, the fact that no allocation would ever be more than the chunk size.
Another model is to have a pool for requests below a certain size but to revert to general allocation if either:
That allows you the extra efficiency in most cases (depending on your allocation patterns, of course) but allowing for allocation beyond that. It introduces a little extra effort in every allocation in that you need to evaluate request size and pool exhaustion, but it still may out-perform the general case.
As an aside, I recall something similar in Java strings (not sure if this is still the case, I haven't used Java for quite a while). The string object allocation had a buffer inside it for storing small strings but could also use that space to store a pointer for a separately allocated chunk of characters (if it was bigger than the internal buffer). This reduced fragmentation (and dereferencing) for what was possibly a large number of small strings, but still allowed for larger strings if needed.
Interestingly, I once tried an experiment in the CPython source code to see if a memory pool could improve performance, especially given the quantity of memory allocations that goes on in there. It used a strategy similar to the one given above, allocating from the pool in preference, but reverting to the original strategy if the requested size was beyond the chunk size or if the pool was exhausted.
Again, it had optimisations as discussed, and then some. For example, the last block freed was cached so it could be handed out immediately without any searching of the pool, in an attempt to speed up the many-times(single-free-then-allocate) pattern.
However, even with a variety of optimisations, pool and chunk sizes, it appeared to make no substantial difference to the performance of some test code I wrote to exercise it, leading me to believe that the actual allocator used in CPython is already pretty good.
And, just having finished reading the excellent book I purchased a couple of weeks ago(a), I now know why I didn't make any headway.
Turns out CPython is already heavily optimised, including the use of memory pools. The "Memory Management" chapter goes into a lot more detail but it basically only uses the normal allocator (raw domain) for getting large blocks (> 256K) or specific non-object-related memory.
All objects, and Python is pretty much all objects :-), come from the object domain (other than a few legacy things).
For this domain, it maintains its own heap and allocates arenas sized to match the system page size, using mmap if supported to reduce fragmentation. All the used arenas are held in a doubly-linked list, the empty ones are maintained in a singly-linked free list.
Within each arena, 4K pools are created (so 64 per arena) and a pool can only serve one size of allocation, locked in when the first allocation is requested from that pool. For example, requests for 1-16 bytes will get a 16-byte block from a pool serving 16-byte blocks, 33-48 byte requests will come from a pool serving 48-byte blocks.
Note this is for a 64-bit system where the block sizes are {16, 32, 48, ..., 512}. 32-bit systems have a slightly different set of block sizes, {8, 16, 24, 32, ..., 512}.
For pools within an arena, they are either:
Keep in mind that transitions between those three states all result in pools moving from list to list.
I won't go into any more detail since your head may explode, like mine almost did :-)
In short, CPython object allocations are always for a specific block size, the smallest one larger or equal to what you need. These come from pools that serve a single block size (once locked in). These pools exist in arenas heavily optimised for preventing fragmentation. And arenas can be created as needed.
Suffice to say, this is why my little experiment didn't improve CPython: it already does memory pooling in a quite complex, yet efficient, way and my attempt to intercept malloc did no good at all.
And my opening statement that pooled memory can be more efficient "but usually only because you have extra information about the allocation patterns" is supported by a comment from that book:
Most of the memory allocation requests are small and of a fixed size. because
PyObjectis 16 bytes,PyASCIIObjectis 42 bytes,PyCompactUnicodeObjectis 72 bytes, andPyLongObjectis 32 bytes.
(a) CPython Internals if you're interested, I have no affiliation other than the fact I like good tech books about how things work.
I've written memory pools, with multiple approaches and tradeoffs. I believe malloc() doesn't use them under the covers (if that's true) because:
12 bytes, you may secretly get 64 bytes (assuming that's the nearest block size >= 12 bytes, and with proper alignment padding), depending on the memory pool implementation. Maybe malloc(), however, would give you 16 bytes, which is the nearest alignment requirement alone, and therefore wastes fewer bytes.n bytes requested, whereas malloc() just allocates to the nearest alignment requirement (generally alignas(max_align_t), which is usually 8 or 16 byte alignment, depending on architecture) >= n bytes requested.n bytes you want allocated to a free list linked list (for the next block size >= n bytes) that you can pull from.In other words, as is the case with most things, there are tradeoffs. I suspect malloc() has chosen to be slower and nondeterministic in order to:
Memory pools are frequently customized in speed, RAM usage, block size, and max number of blocks, for your specific requirement and application at-hand. malloc(), on the other hand, must be universally-applicable and universally-functional for all quantities of bytes possible for your given size RAM. It has much different constraints and requirements.
Having said all that, I'm considering writing some drop-in replacements called fast_malloc() and fast_free() for general-purpose usage. They would either have O(1) allocate and free time complexity by using a huge mapping array to map from n bytes to a block size, or I coud choose an option which uses less program space and/or RAM but uses binary search to map from n bytes to a block size, and therefore has O(log m) time complexity, where m is the number of possible block sizes you can allocate. I could even make it use malloc() under the hood to expand the memory pool at run-time whenever the memory pool runs out, if desired--but that shouldn't be done on microcontrollers or in real-time, safety-critical, deterministic applications, in which case I'd disable that feature and only allocate statically at compile-time, or once at initialization during run-time.
Speed note:
malloc() (ie: my implementation took ~33% to ~100% as much time), depending on the block sizes allowed and the number of bytes being allocated. See my comment below this answer for details.n bytes (when calling fast_malloc(n)) to an index into a mapping array containing structs of {block_size and ptr_to_free_list}. This 1:1 O(N_MAX) in size mapping array used to map into another O(m) in size mapping array would perform much faster, but at the cost of a ton more memory usage in program space/flash, and possibly RAM, depending on the hardware you're running on: microcontroller vs PC.Anyway, it is indeed possible to write a fast_malloc() implementation which does use memory pools under the hood, and has O(1) allocate and free time complexity, and which reverts to regular malloc() if necessary for block sizes too big to allocate in O(1) time (ie: for allocating n bytes where n > N_MAX), in which case it'd just pass the call to regular malloc().
fast_malloc() speed test results:Preliminary results indicate my single-threaded version of
fast_malloc()is ~36 clock_cycles/14 clock_cycles = 2.6x faster than glibc'smalloc().
fast_malloc(), however, currently is waaaay slower. Apparently mutexes are insanely slow. But, I have some ideas to fix it. I have a lot of work to do, and I am still convinced I can make a faster implementation than anything currently out there, including for multi-threaded applications. It has tradeoffs, of course, though--namely: less-efficient usage of memory space.malloc() implementationsas system malloc() What system were you using/comparing to (windows, glibc, musl) ? –
Prune -Wall -Wextra -Werror -O3 -std=c11. ldd --version shows ldd (Ubuntu GLIBC 2.31-0ubuntu9.2) 2.31, so it looks like I'm using glibc 2.31. Source where I learned the ldd --version cmd.. I also ran Profile-Guided Optimization (PGO) and saw no real improvement with it. Using -O3, however, was very important over -O0, of course. –
Wardieu As usual, it all depends.
In this case it depends mainly on what you mean by performance.
As others already said, memory pools are usually faster than standard malloc and free implementations, but the speed is not the only factor one must consider in general case. A general allocator should not allocate too much data in advance, until necessary (which pools usually do) and it should allocate blocks of arbitrary size (which pools usually not do).
Memory pools are more efficient in allocating large amounts of small blocks, especially of the same size, because they can be allocated as an array, so a bunch of blocks has a single common header instead of a separate header for each block.
On the other hand, not the whole bunch will be used up usually, which may be seen as a loss of memory efficiency.
Pools can be faster in malloc/new because they can almost instantly give you a block of data from a pre-allocated array of blocks of a fitting size, instead of searching for a fitting block to slice from. However, you can't have a pool for every possible size, so usually you get blocks a bit longer than needed, which again is some memory loss.
They can also be faster in free/delete, because they just mark a block in a pool as freed and don't need to seek for adjacent blocks to see if they're free, too, and 'glue' the newly freed block to them.
Pretty much every malloc implementation today does use memory pools for ages. Only when requesting large amounts of memory, malloc will directly request virtual memory from the kernel and return that memory back to the system once freed.
In all other cases, malloc requests memory from the system in larger blocks. E.g. if you request 4 bytes of memory, malloc may request 4 KB from the system and then only assign the first 4 bytes from that block to you. The reason why malloc does that is because requesting memory from the system is expensive and that way the next time you request 4 byte malloc doesn't have to request memory from the system at all but can just assign you some more memory from that block.
This also means, that if you free an allocation, malloc cannot return that block to the system, unless all allocations from that block have been freed. And even then malloc will always keep some spare blocks around. Also note that you cannot request arbitrary amounts of virtual memory from the system, usually only a multiple of page sizes, so without an internal memory pool every allocation would in fact be 4 KB of RAM, no matter how small the allocation is. So malloc will always request one or more pages, split those up into chuncks and allocations are in fact taken from these chunks.
Here's a pretty good article how that works: https://levelup.gitconnected.com/understand-heap-memory-allocation-a-hands-on-approach-775151caf2ea
Those blocks basically form a memory pool. However, not a specialized one. malloc cannot know in advance how often you will require blocks or of what size. It has to deal with arbitrary memory allocations in arbitrary order. Also there is some management overhead, finding a free spot in the allocated blocks for your allocation and remembering that this spot is now in use, as well as marking it free again once it isn't in use anymore.
When people say a memory pool is faster, they mean a specialized memory pool. E.g. one where all blocks have the same size (e.g. matching the size of memory allocations you will need) and are stored in a single linked list, so finding a free block is just removing the first block from the list (all have the same size, so any block will do) and freeing it again is just adding it back to the list; nothing could be simpler and faster than that. And as you never return the memory to the system, you never have to request it again from the system, which is the slowest part of memory management.
The downside of such an approach is that your code constantly reserves more memory than it may currently need (and that memory is not available to other processes or can cause the system to swap) and all allocations have a fixed size, which wastes a lot of memory for nothing. Memory pools are specialized, malloc must be general and conservative with resources. So it won't use a pool approach for large allocation and even for small ones where it does use a pool, it cannot compete with a simple specialized pool tailored to your memory needs.
© 2022 - 2024 — McMap. All rights reserved.
mallocand similar need to be good in general, and they use strategies for that (including memory pools). – Herrickmalloc()at runtime -- it might run fine for 6 weeks, and then fail due to memory exhaustion because some other process grabbed almost all the RAM; not what embedded programmers like to deal with – Raspberry