Data Alignment and Padding

Usually we use structures in C to combine data relevant to an object or a problem. If we intend to create many objects of this structure, we have an array of structures. But how are these structures stored in memory? Let’s take a simple structure defined as below

struct abc
{
    int i;
    char c;
};

Now assuming a 32 bit architecture, we know an integer occupies 4 bytes and a char occupies 1 byte. So the instantaneous answer as to what is the size of struct abc would be 5. But the actual size occupied by a variable of the above struct is 8. This is because of the concept of Padding.

http://www.geeksforgeeks.org/structure-member-alignment-padding-and-data-packing/

The above link provides an excellent reference of how the memory is organized in today’s computers. We can see that memory is usually divided into four banks, each of 1 byte width. It so happens that the CPU can access all the four banks of 1 byte each in a single read instruction cycle which is the case with modern CPU architectures. So reading 4 bytes of data needs a single instruction and not four. In a 64 bit architecture, the CPU is capable of reading 8 bytes in a single instruction!

So, we learn that the CPU architecture decides how many bytes can be read at a time and this is referred as word length, which is 4 bytes or 8 bytes depending on the architecture. Let’s stick to 32 bit architecture or 4 byte word length for the rest of the article.

Now it does not mean that the CPU is not capable of reading one byte at a time. Just that reading one byte and four bytes would require equal CPU processing. Hence if we have a char and an int in a structure, the compiler would pad 3 bytes after the char. This is called Data Alignment.

So as a general rule of thumb, the starting address of a variable would depend on its type. A char can start at any address. However, a short, int, long, float or double will start at even memory addresses. Further, short will start at addresses divisible by 2, int and float would start at addresses divisible by 4, long and double would begin at addresses divisible by 8. Confused? Have a look at the diagram in the above link to clear things up.

So let’s consider the following structure.

struct xyz
{
    double a;    
    int b;
    double c;
};

Now would the size of the above structure be 20 bytes (8+4+8) ? Nope! It would be 24 bytes! This is because apart from word alignment, the compiler follows a natural alignment for the structure. It means that the padding is with respect to the largest data member of the structure. Hence there would be a 4 byte padding after variable b in the above structure. But why is this required? Now let’s say we have an array of the above structure and for simplicity, the start of address is 1000. If it were to occupy 20 bytes, then second element of the address would begin at address 1021, which is not a multiple of 8. So padding 4 bytes after b will begin the second element of the array at 1024 which is a multiple of 8. But why, you ask! This is because the emphasis is on performance. Since the cost of physical memory has reduced over time, the compiler would rather waste 4 bytes and ensure the CPU can read the next variable of the array quickly than to save 4 bytes. So in the above case, if the padding has happened, assuming the memory bank model mentioned in the above link, the CPU has to read every 7th memory bank when the structure array is accessed by index, which means it has to skip an even number of memory rows, which is more efficient for the CPU!

References:

http://www.geeksforgeeks.org/structure-member-alignment-padding-and-data-packing/

http://www.catb.org/esr/structure-packing/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s