Structure Packing

Run the following piece of C++ code and observe the output:

#include <iostream>

struct something {

        char c;

        int i;

        short s;

};

int main()

{

        std::cout << sizeof(something) << endl;

}

The output will be 12.

Now run the following program:

#include <iostream>

struct something {

        int i;

        short s;

        char c;

};

int main()

{

        std::cout << sizeof(something) << endl;

}

The output will be 8.

Now that you have run both versions of the same program on a computer, run them in your head. Both programs are doing the same thing. They are printing the size of a struct. The struct contains the same type of variable in both cases. And yet the size of the struct comes out to be different. The structs are almost identical with the only difference being the order in which the variables are declared inside the struct. So the moral of the story is that the order in which variables are declared in a struct determine what the size of struct is going to be. But you should ask your self that why in God's good name should the declaration order matter to size, after all the same number and type of variables are used and hence the size of memory they occupy should also be the same. Well clearly this is not the case. To understand why, you need to learn this first. 

Data alignment! It was fun wasn't it? A direct consequence of this sort of alignment of data in C (and C++) is the way in which compound data types like structs are given memory. Remember how C likes its variables to be stored at memory addresses that are a multiple of their size? Well C doesn't discriminate, the same rule applies to structs. So if a struct is of size S, then any instance of this struct will be stored at an address that is a multiple of S. This is very intuitive as you already know why this is required. The issue is the fact that since a struct is a compound data type, its size can be any arbitrary number of bytes depending on what variables it holds as members. The whole alignment thing works only because the data types were allowed to have certain convenient sizes i.e. 2, 4, 8 ... This means that if structs are allowed to have any arbitrary size then aligning them according to their size will make arbitrary sense (i.e. it will work well sometimes and sometimes it will seem stupid).

Hence it is imperative that the compiler do something to make sure that the structs also end up getting convenient sizes i.e. multiples of 4. The rule that C has to ensure this is rather simple, The size of the struct is always made to be a multiple of the size of the biggest member of the struct. In the example above, the struct something has int i as its biggest member with size 4, so the struct size will also be a multiple of that. How does the compiler achieve this? By using structure packing.

To understand this, you need to be introduced with some nomenclature. X from now on is the size of the biggest member of the struct. Boundary refers to any multiple of X following the address where the struct memory begins. So some struct object begins its memory at 20 and X is 8 for that struct, then the boundaries are: 28, 36, 44, and so on.

Structure packing is a technique (or a policy) in which if adding a new member of the structure to memory crosses any boundary in the struct, then before adding that member, the leading (proceeding) bits are left as padding and the new member is made to start immediately after the said boundary ends. Finally if after allocating memory to all members in this way, the struct is shy of the next boundary by a few bytes, then those bytes are also used as padding just to make the structure a direct multiple of X and end always end up on the boundary exactly.

Consider the first example of the struct something. The value of X is 4 (size of int i, the biggest member of the struct). Adding the first member of the struct, char c crosses no boundaries and the size of struct reaches 1 (which is the size of char). Then comes the turn of int i. int i is 4 bytes in size, adding it to the memory of struct will make the sum 5. This is problematic, int i is crossing the boundary of the first multiple of 4 i.e. 4. In this case the compiler will decide to allocate 4 bytes to int i starting from byte number 5 only and the bytes in between (2, 3, 4) will be used as padding. So int i will start from 5 and will go till 8. The variable left to be added now is short s which is 2 bytes in size. Adding it to 8 does not cross any boundaries so no proceeding padding is needed. But since the final outcome comes at the total of 10, an extra two bytes are padded just to make the size be 12 i.e. a multiple of 4. This way the final size comes out to be 12 bytes, out which 7 bytes are the variables and 5 bytes are just padding. That is some extravagant wastage don't you think?

Now moving onto the second example. The value of X is still 4. The first variable to be added is int i, adding it gets the total to 4. This covers the first boundary entirely. Then comes short s. Adding this takes the total to 6. So far no addition has cost the total to cross any boundaries. Lastly it is required to add char c. c is 1 byte in size. Adding it to the struct makes the total memory equal to 7, which as you may notice still does not cross the next multiple of 4 i.e. 8. Hence so far we are golden, no padding is needed. The only thing left to do is to add one byte of padding in the end to take the total to an even 8. And vola, that is the final size of this struct, with 7 bytes of actual data and a frugal byte for padding.

You see now, how rearranging members can make a difference in size of the struct. One might say that okay saving a few bytes is cool but it isn't very significant. That may be true for moderate size programs on moderate size computers, but if either the program is very big or the computer on which it is to be run is low on memory, then these little alterations can add up to amazing benefits.

The next time you are writing a struct, may be keep in mind to arrange the members in such a way that the small ones come together so that they can be fit inside a single chunk and padding is needed to the least.

Another important thing to know here is that the standard does not guarantee that the padded bytes are to be zeroed, they can be anything, from zero to any arbitrary value. It is the programmer's duty to play around with these carefully. Assuming that the members in a struct are all packed together continuously is plain foolish.