Structure Alignment and Padding

Structure Alignment and Padding is used to make CPU memory access faster. The compiler lays out data members within a struct so that the CPU can read/write data using a single instruction. Without the alignment, the CPU might end up doing more work than necessary. The goal of the compiler is to align the members to their natural alignment. Let us see what that means. What do you think is the size of the following struct?

struct FooBar {
    int *p;
    char c1;
    int i;
    char c2;
};

If you add up individual members in the struct, the total accumulates to 14 (This depends on your architecture. On my machine, p = 8 bytes; c1 = 1 byte; i = 4 bytes; c2 = 1 byte). But this is not the actual size of the struct FooBar. sizeof(FooBar) returns 24. This is because the compiler aligns the members to their natural alignment. To do this, it introduces holes in the struct. The size of the hole/padding depends on the members in the struct. Let us look at this in more detail.

The members inside a struct does not start at some arbitrary address. The size of the type, in bytes, determines the starting address of each of the member. This alignment requirement needs to be satisfied by each of the member within the struct. A type, of size 1 byte, can start at any address. A type, of size 2 bytes, needs to start at address divisible by 2. A type, of size 4 bytes, needs to start at address divisible by 4 and so on. To satisfy this requirement, the variables are stored as below:

And hence the total size of the struct is - 8 bytes + 1 byte + 3 bytes + 4 bytes + 1 byte + 7 bytes. Also, importantly, the struct instance will have the alignment of its widest member. In the above, an instance of FooBar will be aligned to an address divisible by 8, since this is the size of the widest member. For example, the below struct will be aligned to an address divisible by 4 - the size of the largest member:

struct Align4 {
    int i;
    char c;
    int j;
}

Compilers do this to ensure all members are self-aligned for fast read/write.

What does it mean when we say that read/write is faster — when accessing members naturally aligned? Most processors can only read/write properly aligned data. If a program requests a 8-byte data at 0x7ffc6870ae60, a single request is enough to read/write this data. This is because the address 0x7ffc6870ae60 is divisible by 8. Now, in a mis-aligned world, the program requests the same 8-byte data but which now starts at 0x7ffc6870ae55. Now, the CPU needs to issue two instructions to read the data. The first access is done at 0x7ffc6870ae50 (Previous naturally aligned access for the data size) and the second access is done at 0x7ffc6870ae58 (Next naturally aligned access for the data size). The data from both the address needs to be masked and shifted to get the final value. This is shown below:

The order in which we declare the members within the struct can result in totally different sizes. For example, in the above FooBar struct, if we were to declare them as below:

struct FooBar {
    int *p;
    char c1;
    char c2;
    int i;
};

The sizeof(FooBar) now returns 16 instead of the earlier 24. The reason is because now, this results in a hole/padding of only size 2 and the integer following it is naturally aligned after adding the hole in the struct. Although, this saving might not be much, but when dealing with thousands of such objects in a long running program, the savings become substantial.

What if we do not want the compiler to introduce padding for us? You can use the pragma pack directive to let your compiler know. More details can be found here. Note, that in some architecture unaligned read/write will result in an error or a wrong value.

The natural alignment requirements comes into play on structs using bitfields too. Consider the below struct:

struct FooBar {
    int i:1;
    int j:1;
};

This struct will be packed to the size of the longest member. Although, we have specified to take only 2 bits, the sizeof(FooBar) will return 4.

To check the layout of your structure, you can use gdb to print it out to the console. For example, for the above FooBar:

$ gdb --quiet a.out
Reading symbols from a.out...done.
(gdb) break main
Breakpoint 1 at 0xdca: file main.cpp, line 6.
(gdb) r
Starting program: /home/vagrant/Projects/Linux/a.out

Breakpoint 1, main (argc=1, argv=0x7fffffffe4d8) at main.cpp:6
6	{
(gdb) ptype /o struct FooBar
/* offset    |  size */  type = struct FooBar {
/*    0      |     8 */    int *p;
/*    8      |     1 */    char c1;
/*    9      |     1 */    char c2;
/* XXX  2-byte hole  */
/*   12      |     4 */    int i;

                           /* total size (bytes):   16 */
                         }

You can also use the -Wpadded option on clang to print out messages about holes present in your structs. You can also use offsetof to print out the offset of your member, including the padding, if any. More details can be seen here.

Usually, it is advised to pad the struct manually so as not to trip other developers working on it. For example, the above FooBar struct can be rewritten as:

struct FooBar {
    int *p;
    char c1;
    char c2;
    char _pad[2];
    int i;
};

The sizeof(FooBar) is still 16. But now, you have explicitly marked the padding and other developers working on this piece of code are not tripped by the compiler. To further strengthen the walls, you can use static_assert() to let the developers know to tread carefully:

static_assert(sizeof(struct FooBar) == 16, "Tread carefully!!!")

This makes your intentions clear and any changes take into account the padding in the struct.

Structure alignment and padding are somewhat common across major compiled languages. There might be some differences in how each compiler aligns the data members within a struct. For more details on the differences between compilers, see here.

That’s it. For any discussion, tweet here.

[1] http://www.catb.org/esr/structure-packing/ - Goto reference on the topic
[2] https://en.wikipedia.org/wiki/Data_structure_alignment