What to consider with regards to alignment when designing a memory pool?

Question

I'm working on a memory pool for a small game engine.

The main use will be as a segregated storage; a pool contains object of a specific type and size. Currently the pools can be used to store anything, but allocations will be done in blocks of a specific size. Most of the memory need will be allocated at once, but "overgrowth" can be enabled if needed to assist in tuning (almost fixed size).

Problem is, I started to get somewhat paranoid when contemplating about memory alignment. I'm only used to raw memory management on 8 bit processors where everything is byte aligned.

I'm letting the user (me) specify the desired size of the blocks, which in the segregated storage case would be the size of the objects that I'm going to store in it.

The current approach is to allocate a chunk of memory blocks * (desired_size + header_size) big and place the objects in it, with a header for each block; objects would obviously be positioned directly behind this header.

What do I need to consider with regards to memory alignment in my scenario?

The answer I've come up with so far is that as long as desired_size represents n-byte aligned data; the header is correctly aligned and packed by the compiler as well as the actual data, everything stored in the block will be n-byte aligned.

n is whatever boundary required by the platform. I'm targeting x86 for the moment but I don't like to make any assumptions about the platform in my code.

Some of the resources I've used:

• http://www.ibm.com/developerworks/library/pa-dalign/
• http://en.wikipedia.org/wiki/Data_structure_alignment
• Memory alignment on a 32-bit Intel processor
• Boost Pool docs for inspiration on the general design. I would like to avoid dragging boost into this project; and I'm seeing this as a learning opportunity as well.

Edit

Uploaded small sample code which may helpful anybody as confused as me in the future here.

Answer 1

Allocations with malloc are guaranteed to be aligned for any type provided by the compiler and hence any object[*].

The danger is when your header has a smaller alignment requirement than the maximum alignment requirement for your implementation. Then its size might not be a multiple of the max. alignment, and so when you try to cast/use buf + header_size as a pointer to something that does have the max. alignment, it's misaligned. As far a C is concerned, that's undefined behaviour. On Intel it works but is slower. On some ARMs it causes a hardware exception. On some ARMs it silently gives the wrong answer. So if you don't want to make assumptions about platform in your code, you must deal with it.

There are basically three tricks that I'm aware of to ensure that your header doesn't cause misalignment:

• Use an implementation-specific alignment pragma to force the issue.
• Use platform-specific knowledge of struct layout and alignment to make sure that its size just so happens to be a multiple of the max alignment requirement on the system. Typically this means, "stick an extra int in as padding if necessary to make it an 8-multiple rather than just a 4-multiple".
• Make the header a union of every standard type, together with the struct that you actually want to use. Works well in C, but you'd have problems in C++ if your header isn't valid for membership of unions.

Alternatively, you can just define header_size not to be sizeof(header), but to be that size rounded up to a multiple of some chunky power of 2 that's "good enough". If you waste a bit of memory, so be it, and you can always have a "portability header" that defines this kind of thing in a way that isn't purely platform-independent, but makes it easy to adjust to new platforms.

[*] with a common exception being over-sized SIMD types. Since they're non-standard, and it would be wasteful to 16-align every allocation just because of them, they get hand-waved aside, and you need special allocation functions for them.

Answer 2

Your compiler will already align the members of objects and structures that will be stored in the pool. Using the default packing that's appropriate for your architecture, usually 8 for a 32-bit core. You just need to make sure that the address you generate from your pool is aligned accordingly. Which on a 32-bit operating system ought to be a multiple of 8 bytes.

Mis-aligning the objects can be very expensive when they cross a CPU cache line boundary. A double that straddles two cache lines takes as much as three times as long to be read or written.

Answer 3

I've fiddled with memory alignment too. The first thing to understand is that each object has its own memory alignment requirements, which is (at most) the size of the object itself. Fortunately it's often smaller.

There are facilities of two types to help writing correct memory allocators (C++0x, they can be found in std::tr1 in most STL):

• std::alignment_of gives the alignment as a compile-time value
• std::aligned_storage gives an aligned storage according to its parameters

Working with the two of them, you'll get what you need.

However your design is slightly off-base, not by much mind, because your header won't have the same alignment requirement (in general) than the objects stored.

template <class T, size_t N>
struct Block
{
  // Header bits

  typedef std::aligned_storage<
      N*sizeof(T),
      std::alignment_of<T>::value
  >::type buffer_type;
  buffer_type mBuffer;
};

Two notes:

• Block itself might have a different alignment, but it doesn't matter
• You could use sizeof for the alignment, it's guaranteed to work, even if a bit wasteful

Finally, you can also succeed without all these, and some pointer arithmetic, but since it's offered....

Answer 4

Use http://msdn.microsoft.com/en-us/library/bb982233.aspx - std::alignment_of. This ensures that for every T you allocate into your pool, you will know the alignment and can ensure that it fits. I'm not going to pretend to know/understand the actual logic you would use to make this information into alignment guarantees, but it does exist and is available for use.

Answer 5

As far as I know boost::pool is based on alexandrescu's 'allocator of small objects' explained in his book "modern c++ design". I is must read book (since you are writing this stuff for learning too)