Fixed-Size Memory Pool

Question

I've been reading about Memory Pools since I came across them in the book Game Programming Complete 4th Edition, and I decided to try and spin my own since I didn't quite understand how the one they presented in the book worked at the time.

One thing I'm uncertain of is defining the deleter in the shared_ptr. I don't like using delegates when they aren't needed, but if I try to pass in the address to the function pointer as the deleter then the program will not compile.

Memory chunks are stored in a singly-linked list, with the first N bytes of each entry in the list being a pointer to the next entry.

While it's nifty using pointer majicks to store the pointer in the head of each chunk, it is scary to look at when you don't understand pointer-to-pointers (I know I didn't when I first tried to roll it out!).

Any suggestions on changes? Improvements? Bugs I didn't see?

#include <memory>
namespace acorn
{
 template<class Object>
 //An immutable memory pool does not grow or shrink in size.
 class ImmutableMemoryPool
 {
 typedef unsigned char byte;
 //A pointer to the block of data we will be allocating.
 byte* m_pBlock;
 //A pointer to the current chunk
 byte* m_pCurrentChunk;
 //A pointer to the last chunk
 byte* m_pLastChunk;
 unsigned int m_NumberOfChunks;
 unsigned int m_SizeOfChunk;
 unsigned int m_SizeOfChunkData;
 unsigned int m_SizeOfChunkHeader;
 unsigned int m_SizeOfBlock;
 public:
 ImmutableMemoryPool(unsigned int numberOfChunks) : m_NumberOfChunks(numberOfChunks), m_SizeOfChunkData(sizeof(Object))
 {
 //Set the size of the header of each chunk
 m_SizeOfChunkHeader = sizeof(byte*);
 //Calculate the size of a whole chunk
 m_SizeOfChunk = m_SizeOfChunkHeader + m_SizeOfChunkData;
 //Calculate the size of the block of data
 m_SizeOfBlock = m_SizeOfChunk * m_NumberOfChunks;
 //Allocate a new block of memory
 m_pBlock = new byte[m_SizeOfBlock];
 //Initialize the chunk header data
 InitializeHeaders();
 //Set the current chunk pointer to point at the start of the block
 m_pCurrentChunk = m_pBlock;
 //Set the last chunk poitner to point at the last chunk
 m_pLastChunk = m_pBlock + m_SizeOfBlock - m_SizeOfChunk;
 }
 ~ImmutableMemoryPool()
 {
 delete[] m_pBlock;
 }
 //Places a chunk of memory back into the pool
 void Dealloc(Object* pData)
 {
 byte* pConvertedData = (byte*)pData;
 //Sure, call it on a nullptr - I don't care I'll just ignore it HA
 if (pConvertedData != nullptr) {
 //Make sure this pointer belongs to this pool
 if (pConvertedData < (m_pBlock + m_SizeOfBlock) && pConvertedData > m_pBlock)
 {
 //Get the header
 byte* pHeader = (byte*)pConvertedData - m_SizeOfChunkHeader;
 //Set the tail chunk to now point to this returned chunk instead of a nullptr
 byte** ppHeaderData = (byte**)m_pLastChunk;
 ppHeaderData[0] = pHeader;
 //Set the new tail as the returned chunk
 m_pLastChunk = pHeader;
 //Set the header data to point to a nullptr
 ppHeaderData = (byte**)pHeader;
 ppHeaderData[0] = nullptr;
 //If the current chunk was pointing to a nullptr, point it to the new tail instead
 if (m_pCurrentChunk == nullptr)
 {
 m_pCurrentChunk = pHeader;
 }
 }
 else
 {
 std::cout << "This data isn't mine!" << std::endl;
 }
 }
 }
 //Returns a single chunk of memory
 std::shared_ptr<Object> Alloc()
 {
 //If there are no available chunks, return a nullptr
 if (m_pCurrentChunk == nullptr)
 {
 std::cout << "Sorry! No more chunks to be given out. Come back later, but for now have this nullptr!" << std::endl;
 return nullptr;
 }
 //Get the pointer to the next chunk and set it to pNext
 byte** ppChunkHeaderData = (byte**)m_pCurrentChunk;
 byte* pNext = ppChunkHeaderData[0];
 std::cout << (void*)m_pCurrentChunk << std::endl;
 std::cout << (void*)pNext << std::endl;
 //Get the data to return
 void* rawReturnData = m_pCurrentChunk + m_SizeOfChunkHeader;
 //Stick it into a shared pointer that automatically puts the object back into the pool when it is time.
 std::shared_ptr<Object> returnPtr((Object*)rawReturnData, [=](Object* pRawData){
 Dealloc(pRawData);
 });
 //Set the next chunk
 m_pCurrentChunk = pNext;
 return returnPtr;
 }
 protected:
 void InitializeHeaders()
 {
 byte* pHeader = nullptr;
 byte* pEnd = nullptr;
 byte* pNext = nullptr;
 byte** ppChunkHeader;
 //Set the header and end of the block
 pHeader = m_pBlock;
 pEnd = m_pBlock + m_SizeOfBlock;
 //Loop through and set the header of each chunk to point to the next chunk
 while (pHeader < pEnd)
 {
 pNext = pHeader + m_SizeOfChunk;
 ppChunkHeader = (byte**)pHeader;
 ppChunkHeader[0] = (pNext < pEnd ? pNext : nullptr);
 std::cout << "Header: " << (void*)pHeader << std::endl;
 std::cout << "Next: " << (void*)pNext << std::endl;
 pHeader = pNext;
 }
 std::cout << std::endl;
 }
 };

• glampert: By "immutable" you just mean that it doesn't change size, correct? I think the name is passing the wrong idea that the memory in itself is immutable/const. Perhaps a better name would be FixedSizePool?
• glampert: My own implementation of similar memory allocator: codereview.stackexchange.com/q/93772/39810
• Acorn: @glampert Ah! That is a better name. I knew there was something better than "Immutable", but I couldn't think of it. I'll check out your implementation as well

Answer 1

A few things complementing the other answers:

• Expanding on my previous comment, the name ImmutableMemoryPool gives the idea that the objects allocated by the pool are immutable, which is a pattern used sometimes to allow sharing of immutable instances, but that is not the case here. You meant to say that your pool has a fixed size, so why not call it FixedSizePool?

• Instead of defining a custom byte type, use the standard std::uint8_t from <cstdint>. Everyone is already familiar with it.

• m_SizeOfChunkHeader and m_SizeOfChunkData are constants, so you shouldn't have them wasting memory as class members. They are also currently mutable, which is dangerous. Either just use the sizeof() expression directly, which is fine, or make those two static consts or better static constexpr if you're aiming at C++11 and above.

• Type casting should be avoided as much as possible. C++ relies on a strong type system. But when dealing with raw memory some type casting is unavoidable. When you have to typecast, use the C++ cast operators. static_cast and reinterpret_cast are your friends. They produce better compiler diagnostics and are also very verbose and colorful on purpose, so they stand out as a clear sign that the programmer is taking matters into his/her own hands, for the better or for worse.

• The if nesting in Dealloc() is unnecessary. The first condition can just be flipped and early return. The second can also be simplified from an if-then-else to an if-then-return.

• std::cout is not meant for error logging. You can however use std::cerr if you want printed error output. cerr, or STDERR, is the standard C++ stream for error output. But you might also consider replacing the error logs by exceptions, to give more flexibility to users of your code.

• Why is InitializeHeaders() protected? You're not planning to inherit from this class, judging by the lack of a virtual destructor, so anything internal should be private. By the way, this is a bit of a personal style, but I find it more interesting to place the private section of a class right at the end. My rationale is that implementation details should not be the first thing you see when you look at a class declaration.

• Your decision of returning a shared_ptr of the allocated block is questionable. What if all I need is a unique_ptr? My opinion is that this level of memory management is much too low to be dealing with smart pointers. All the user of a memory allocator/pool cares about is a pointer to the allocated block and the block size in bytes, so perhaps your allocator should deal in terms of a Block type? But I'm stealing this idea :P, I strongly suggest watching this excellent presentation: "std::allocator Is to Allocation what std::vector Is to Vexation".

• Memory alignment is most certainly going to be an issue with your allocator. The first object pulled from the memory pool will be aligned, because operator new returns properly aligned memory, but if the size of the allocated chunk is not evenly divisible by the minimum alignment, the second allocation won't be. This might result in misaligned memory access errors. You will very likely experience that if you try using your allocator with an __m128 vector type that requires 16 bytes of alignment. Taking alignment into account is very easy. You can take advantage of std::alignment_of and std::aligned_storage. You can also allow the specification of a minimum alignment as an integer template parameter.

• Tidy up those spurious blank lines here-and-there. One blank line is more than enough to separate two distinct areas of code.

• Acorn: May I email you for more information regarding memory alignment?
• glampert: @Acorn, I'd rather discuss it publicly, so it remains available to others :) I can expand the answer if you have more specific questions, or you might even be able to find the answers yourself. Start on SO, of course: Purpose of memory alignment & How to allocate aligned memory only using the standard library?
• Acorn: Fair enough :D I understand memory alignment & why it is important, but I don't understand the concept of alignas(). Is this the same idea as adding padding bytes to a POD that is a strange number of bytes big (IE, 3,5,9,14, etc etc)? Take a look at these two code examples: ideone.com/rGsw09 and ideone.com/lpvV3x I would expect both to have the same results, but they do not. I understand that arrays do not put padding inbetween each type so they are packed tightly, so why does the first example work as expected but not the second example?
• glampert: @Acorn alignas will only specify the alignment of the starting address of a structure/block. To align each individual field of a struct, you'd have to apply it per member variable. Same thing with the array, it will only align the first memory address; To align each element, apply alignas to the type declaration, e.g.: struct alignas(N) my_type { ... }.
• glampert: alignas will work for statically declared data, that's why in your allocator you have to do the pointer adjustments by yourself for each new allocation. That was just an example, but in a real allocator the pointers returned must be evenly divisible by the alignment required.

Answer 2

Bugs:

• You forgot to include <iostream>.
• You dropped the closing brace for the namespace.
• If the size of Object and byte* aren't multiples of the others natural alignment, you get misaligned objects.
• Your calculation for the size of your allocated block can overflow.

Style:

• You have far too many empty lines sprinkled about.
• Putting a comment smack in the middle of a declaration is very curious. Had not seen that yet.
• The first type template-argument is traditionally called T.
• If nearly everything is in the same namespace (starting near the top and going to the end of the file), you normally don't indent its contents.
• Use size_t for memory-sizes and object-counts. That's what it's for, and it's potentially bigger than an unsigned int.

Member-variables:

• If something is a compile-time constant, there should be a really good reason (like binary layout) to cache it as a member-variable. You don't have such a reason for nearly all your members.

I suggest you define your own type struct element{void* header; union{Object o;};}; and allocate an array of it, with whatever allocator the user provides.

Though thinking a bit more on it, why? You never use the header at all while you are storing a payload, so unionize them (union element { element* next; Object o; };). That will also obviate the need for most of your casting.

You shouldn't use std::endl unless you need that explicit manual flush, as it destroys performance.
Anyway, I expect you will remove all printing-code before use...?

• Acorn: Thanks for the suggestions! Apparently I didn't copy the last bracket and the #include <iostream>, so I'll update that asap. On your point about Object and byte* not being multiples of the others natural alignment, what should I do to ensure that they are? Byte* is 4 bytes on my system, is there a way I can force Object to conform to a multiple of 4? I also hadn't taken into consideration that the calc for the size of the allocated block can overflow, good catch.
• Acorn: Lastly, I've never worked with unions so I'm a bit lost when you suggest to unionize the header and payload Could you provide an example, please? Oh, and I plan to remove all of the cout crap. It was just for testing purposes!
• Deduplicator: Wrote down which union to use. As an aside, putting things in a union means default-construction and destruction reverts to doing nothing.
• Acorn: Awesome! But now, won't I be using almost twice the space? Since you are supposed to only access a union however it was first accessed, I'll have a union pointing to the next "header" union, and to get the data I just move one space down in the array? If that is the case, your first suggestion of sticking the pointer and object into a single struct makes more sense IMO. I just want to make sure I am understanding your suggestion of unionizing them
• Deduplicator: @Acorn: No, you can always destruct the currently held object (only neccessary for ending the lifetime if having a non-trivial destructor), and construct a new object in-place (only neccessary for starting the new objects lifetime if it has no trivial default-constructor). And ... you already do that.