questions about memory pool

Question

I need some clarifications for the concept & implementation on memory pool.

By memory pool on wiki, it says that

also called fixed-size-blocks allocation, ... , as those implementations suffer from fragmentation because of variable block sizes, it can be impossible to use them in a real time system due to performance.

How "variable block size causes fragmentation" happens? How fixed sized allocation can solve this? This wiki description sounds a bit misleading to me. I think fragmentation is not avoided by fixed sized allocation or caused by variable size. In memory pool context, fragmentation is avoided by specific designed memory allocators for specific application, or reduced by restrictly using an intended block of memory.

Also by several implementation samples, e.g., Code Sample 1 and Code Sample 2, it seems to me, to use memory pool, the developer has to know the data type very well, then cut, split, or organize the data into the linked memory chunks (if data is close to linked list) or hierarchical linked chunks (if data is more hierarchical organized, like files). Besides, it seems the developer has to predict in prior how much memory he needs.

Well, I could imagine this works well for an array of primitive data. What about C++ non-primitive data classes, in which the memory model is not that evident? Even for primitive data, should the developer consider the data type alignment?

Is there good memory pool library for C and C++?

Thanks for any comments!

Abscond

I think the basic idea is that you have one pool for each class of objects, so that each object requires the same space. That way, you can allocate, release and reuse memory with ease, because you can reuse freed blocks precisely. – Lovmilla

Hi, Kerrek SB, thank you for your comment. If one pool for one class type, then there would be many, many pools, or each time one class is designed, one memory pool will be designed. If this is correct, then it sounds a bit cumbersome. – Abscond

If a memory pool implementation is templated by the type of item it is allowed to allocate, then the fact that it is cumbersome is hidden by the compiler generating the bulk of the necessary boilerplate code. – Hulett

Hi, Chad, then how is pool's size predicted for a specific type T, in c++ template implemtation? would it be like: template<typename T> std::size_t my_sizeof() { return sizeof(T); } – Abscond

Modern C++ Design has a nice discussion on the topic, and I'd recommend the book as interesting outside of the topic as well. – Hawkinson

@pepero: yes, the trick is to use templates and sizeof to have only one implementation, since the management code can be the same for all. – Vierra

@Tom Kerr, thank you so much for pointing this out . It seems the Chapter 4 "Small-Object Allocation", and i find it very interesting to read. But I am quite curious, and James Johnstonwhy also points out "it is not used for larger object" in his post. What makes difference with "small" or "big"? looks like it is very heuristic statement, which i do not quite understand. – Abscond

C++ uses the C allocator by default, which is biased towards larger allocations. As I understand it, you will pay about as much for allocating 4 bytes as 64 bytes. If your app is extremely heavy on small allocations (smart pointers is the example in the book) you can see performance gains on amortizing the performance cost of using the C allocator. – Hawkinson

In any event, you probably probably won't benefit much (and possibly suffer) from equipping your classes with pool allocators. It's really important that you profile your scenario and compare. The default allocator is already pretty clever and efficient, and the advantages of rolling your own are very situational. Also do try some existing allocators like tcmalloc or nedmalloc. – Lovmilla

Answer 1

In a scenario where you always allocate fixed-size blocks, you either have enough space for one more block, or you don't. If you have, the block fits in the available space, because all free or used spaces are of the same size. Fragmentation is not a problem.

In a scenario with variable-size blocks, you can end up with multiple separate free blocks with varying sizes. A request for a block of a size that is less than the total memory that is free may be impossible to be satisfied, because there isn't one contiguous block big enough for it. For example, imagine you end up with two separate free blocks of 2KB, and need to satisfy a request for 3KB. Neither of these blocks will be enough to provide for that, even though there is enough memory available.

Vierra

Thanks, Martinho. If "what data size is required, what pool is created" is true, then I could understand the memory pool. Of course, a specific pool is preferred, rather than a generic pool for everything". The memory usage is strctly under control, no matter how many pools could be. – Abscond

Yes memory pools of fixed-size blocks are usually specific for certain data types. You can write a generic implementation with templates, but each pool has only objects of the same type, hence the fixed-size. – Vierra

Answer 2

Variable block size indeed causes fragmentation. Look at the picture that I am attaching:

The image (from here) shows a situation in which A, B, and C allocates chunks of memory, variable sized chunks.

At some point, B frees all its chunks of memory, and suddenly you have fragmentation. E.g., if C needed to allocate a large chunk of memory, that still would fit into available memory, it could not do because available memory is split in two blocks.

Now, if you think about the case where each chunk of memory would be of the same size, this situation would clearly not arise.

Memory pools, of course, have their own drawbacks, as you yourself point out. So you should not think that a memory pool is a magical wand. It has a cost and it makes sense to pay it under specific circumstances (i.e., embedded system with limited memory, real time constraints and so on).

As to which memory pool is good in C++, I would say that it depends. I have used one under VxWorks that was provided by the OS; in a sense, a good memory pool is effective when it is tightly integrated with the OS. Actually each RTOS offers an implementation of memory pools, I guess.

If you are looking for a generic memory pool implementation, look at this.

EDIT:

From you last comment, it seems to me that possibly you are thinking of memory pools as "the" solution to the problem of fragmentation. Unfortunately, this is not the case. If you want, fragmentation is the manifestation of entropy at the memory level, i.e., it is inevitable. On the other hand, memory pools are a way to manage memory in such a way as to effectively reduce the impact of fragmentation (as I said, and as wikipedia mentioned, mostly on specific systems like real time systems). This comes to a cost, since a memory pool can be less efficient than a "normal" memory allocation technique in that you have a minimum block size. In other words, the entropy reappears under disguise.

Furthermore, that are many parameters that affect the efficiency of a memory pool system, like block size, block allocation policy, or whether you have just one memory pool or you have several memory pools with different block sizes, different lifetimes or different policies.

Memory management is really a complex matter and memory pools are just a technique that, like any other, improves things in comparison to other techniques and exact a cost of its own.

Milden

thanks sergio, "if you think about the case where each chunk of memory would be of the same size, this situation would clearly not arise." How could be possible for each chunk of the same size, unless you only have a single data type? – Abscond

HI, sergio, i read the image link. Unfortunately, that is a typical sample introduction about external fragmentation, like what Martinho Fernandesand explains in his post. I think this does not clarifies my question. e.g., they could also have the same size but not contiguous too, and c still cannot request a memory. – Abscond

Answer 3

Both fix-size and variable size memory pools will feature fragmentation, i.e. there will be some free memory chunks between used ones.

For variable size, this might cause problems, since there might not be a free chunk that is big enough for a certain requested size.

For fixed-size pools, on the other hand, this is not a problem, since only portions of the pre-defined size can be requested. If there is free space, it is guaranteed to be large enough for (a multiple of) one portion.

Hax

Answer 4

If you do a hard real time system, you might need to know in advance that you can allocate memory within the maximum time allowed. That can be "solved" with fixed size memory pools.

I once worked on a military system, where we had to calculate the maximum possible number of memory blocks of each size that the system could ever possibly use. Then those numbers were added to a grand total, and the system was configured with that amount of memory.

Crazily expensive, but worked for the defence.

---

When you have several fixed size pools, you can get a secondary fragmentation where your pool is out of blocks even though there is plenty of space in some other pool. How do you share that?

Chateau

that is also a question i want to ask, after I learn "one pool for one type", what happens? – Abscond

Answer 5

With a memory pool, operations might work like this:

1. Store a global variable that is a list of available objects (initially empty).
2. To get a new object, try to return one from the global list of available. If there isn't one, then call operator new to allocate a new object on the heap. Allocation is extremely fast which is important for some applications that might currently be spending a lot of CPU time on memory allocations.
3. To free an object, simply add it to the global list of available objects. You might place a cap on the number of items allowed in the global list; if the cap is reached then the object would be freed instead of returned to the list. The cap prevents the appearance of a massive memory leak.

Note that this is always done for a single data type of the same size; it doesn't work for larger ones and then you probably need to use the heap as usual.

It's very easy to implement; we use this strategy in our application. This causes a bunch of memory allocations at the beginning of the program, but no more memory freeing/allocating occurs which incurs significant overhead.

Ebby

Hi, James, if "memory pool is always done for a single data type of the same size", then what kind of data type shoul we choose for memory pool, and what not? – Abscond

It depends on the data type you are trying to store. In our example we were processing images that were all of the same dimensions. So it was a two-dimensional array / matrix representing the image's pixels. The global variable was an array of pointers. – Ebby