When should I worry about alignment?

Question

I've learned a little about alignment recently but I am not certain in which situations it will be an issue or not. There are two cases that I wonder about:

The first one is when using arrays:

struct Foo {
    char data[3]; // size is 3, my arch is 64-bit (8 bytes)
};

Foo array[4]; // total memory is 3 * 4 = 12 bytes. 
              // will this be padded to 16?

void testArray() {
    Foo foo1 = array[0];
    Foo foo2 = array[1]; // is foo2 pointing to a non-aligned location?
                           // should one expect issues here?
}

The second case is when using a memory pool:

struct Pool {
    Pool(std::size_t size = 256) : data(size), used(0), freed(0) { }

    template<class T>
    T * allocate() {
        T * result = reinterpret_cast<T*>(&data[used]);
        used += sizeof(T);
        return result;
    }

    template<class T>
    void deallocate(T * ptr) {
        freed += sizeof(T);
        if (freed == used) {
            used = freed = 0;
        }
    }

    std::vector<char> data;
    std::size_t used;
    std::size_t freed;
};

void testPool() {
    Pool pool;
    Foo * foo1 = pool.allocate<Foo>(); // points to data[0]
    Foo * foo2 = pool.allocate<Foo>(); // points to data[3],
                                       // alignment issue here?
    pool.deallocate(foo2);
    pool.deallocate(foo1);
}

My questions are:

• Are there any alignment issues in the two code samples?
• If yes, then how can they be fixed?
• Where can I learn more about this?

Update

I am using a 64-bit Intel i7 processor with Darwin GCC. But I also use Linux, Windows (VC2008) for 32-bit and 64-bit systems.

Update 2

Pool now uses a vector instead of array.

Answer 1

struct Foo {
    char data[3]; // size is 3, my arch is 64-bit (8 bytes)
};

Padding is allowed here, in the struct after the data member--but not before it, and not between the elements of data.

Foo array[4]; // total memory is 3 * 4 = 12 bytes. 

No padding is allowed between elements in the array here. Arrays are required to be contiguous. But, as noted above, padding is allowed inside of a Foo, following its data member. So, sizeof(someFoo.data) must be 3, but sizeof(someFoo) could be (and often will be 4).

void testArray() {
    Foo * foo1 = array[0];
    Foo * foo2 = array[1]; // is foo2 pointing to a non-aligned location?
                           // should I expect issues here?
}

Again, perfectly fine -- the compiler must allow this¹.

For your memory pool, the prognosis isn't nearly as good though. You've allocated an array of char, which has to be sufficiently aligned to be accessed as char, but accessing it as any other type is not guaranteed to work. The implementation isn't allowed to impose any alignment limits on accessing data as char in any case though.

Typically for a situation like this, you create a union of all the types you care about, and allocate an array of that. This guarantees that the data is aligned to be used as an object of any type in the union.

Alternatively, you can allocate your block dynamically -- both malloc and operator ::new guarantee that any block of memory is aligned to be used as any type.

Edit: changing the pool to use vector<char> improves the situation, but only slightly. It means the first object you allocate will work because the block of memory held by the vector will be allocated (indirectly) with operator ::new (since you haven't specified otherwise). Unfortunately, that doesn't help much -- the second allocation may be completely misaligned.

For example, let's assume each type requires "natural" alignment -- i.e., alignment to a boundary equal to its own size. A char can be allocated at any address. We'll assume short is 2 bytes, and requires an even address and int and long are 4 bytes and require 4-byte alignment.

In this case, consider what happens if you do:

char *a = Foo.Allocate<char>();
long *b = Foo.Allocate<long>();

The block we started with had to be aligned for any type, so it was definitely an even address. When we allocate the char, we use up only one byte, so the next available address is odd. We then allocate enough space for a long, but it's at an odd address, so attempting to dereference it gives UB.

---

¹ Mostly anyway -- ultimately, a compiler can reject just about anything under the guise of an implementation limit having been exceeded. I'd be surprised to see a real compiler have a problem with this though.

Answer 2

Nobody has mentioned the memory pool yet. This has huge alignment problems.

T * result = reinterpret_cast<T*>(&data[used]);

That is no good. When you take over memory management, you need to take over all of the aspects of memory management, not just allocation. While you may have allocated the right amount of memory, you have not addressed alignment at all.

Suppose you use new or malloc to allocate one byte. Print it's address. Do this again, and print this new address:

char * addr1 = new char;
std::cout << "Address #1 = " << (void*) addr1 << "\n";
char * addr2 = new char;
std::cout << "Address #2 = " << (void*) addr2 << "\n";

On a 64 bit machine such as your Mac you will see that both of the printed addresses end with a zero and they are typically 16 bytes apart. You haven't allocated two bytes here. You have allocated 32! That's because malloc always returns a pointer that is aligned such that it can be used for any data type.

Put a double or a long long int on an address that does not end with 8 or 0 when printed in hex and you are likely to get a core dump. Doubles and long long ints need to be aligned to 8 byte boundaries. Similar constraints apply to plain old vanilla integers (int32_t); these need to be aligned on 4 byte boundaries. Your memory pool is not doing this.

Answer 3

Generally—that is, for most data structures—don't worry about alignment in advance. The compiler will generally do the right thing. The days of sweating time penalties for unaligned data are at least 20 years behind us.

The only issues remaining are illegal unaligned data access which occur only on a minority of CPU architectures. Write the code so it makes sense. Test it. If an unaligned data exception occurs, then it is time to figure out how to avoid it. Most cases are easily fixed by adding a command line option. A few require altering the structure: reordering elements, or explicitly inserting unused padding elements.

Answer 4

The alignment is handled transparently by the compiler - sizeof and array accesses always account for any alignment and you don't have to care about it.

There's a bug in the memory pool example though - if you call deallocate(), it always deallocates the last allocated pointer instead of the given pointer.