Padding and rearranging structure members - Embedded.com

Padding and rearranging structure members

A couple of months ago, I showed how a C++ delete-expression is actually a two-step process: (1) apply a destructor to the object in the allocated storage, and (2) deallocate the storage.1 In an array-delete-expression, the first step is actually a loop, which applies the destructor to each array element.

When I described the implementation of the loop, I omitted the details of how a delete-expression determines the array dimension. I promised to present those details–and I will–but not just yet. The details draw upon an understanding of memory alignment and the use of padding in structures, which are my topics this month.

Alignment
Many of today's processors can address memory one 8-bit byte at a time. They can also access memory as larger objects such as 2- or 4-byte integers, 4-byte pointers, or 8-byte floating-point numbers.

Multibyte objects often have an alignment. The C Standard defines alignment as a “requirement that objects of a particular type be located on storage boundaries with addresses that are particular multiples of a byte address”.2 The Standard leaves it up to each target processor to specify its alignment requirements. That is, a processor might require that a 4-byte integer or pointer referenced as a single object be word aligned–at an address that's a multiple of four. A processor also might require that an 8-byte floating-point number be word aligned, or maybe even double-word aligned–at an address that's a multiple of eight.

According to the C Standard, a program that attempts to access an improperly aligned object produces undefined behavior . This means that the program is in error, but the exact consequences of that error are platform-dependent. With many processors, an instruction that attempts to access improperly aligned data issues a trap. With other processors, an instruction that accesses misaligned data executes properly but uses up more cycles to fetch the data than if the data were properly aligned.

An object whose address requirement is a higher multiple than another is said to have a stricter alignment . For example, an object that must be double-word aligned (at an address that's a multiple of eight) has a stricter alignment than an object that must be only word aligned (at an address that's a multiple of four). Character objects always have a size of one (by definition) and can reside at any boundary. They have no alignment requirement.

Machines with 4-byte words and 8-byte double words are very common but hardly universal. The following discussion uses these common sizes for illustrative purposes only. Please bear in mind that machines with other word sizes and alignment requirements do exist.

Structure padding in C
C compilers may insert unused bytes called padding bytes after structure members to ensure that each member is appropriately aligned. For example, given:

typedef struct widget widget;struct widget{    char m1;    int m2;    char m3;};   

on a machine where int must be word aligned (on an address that's a multiple of four), the compiler will insert 3 bytes of padding after m1 , and also after m3 , as if the structure had been defined as:

typedef struct widget widget;struct widget{    char m1;    char padding_after_m1[3];     int m2;    char m3;    char padding_after_m3[3]; };   

except that the added members don't actually have names. The C Standard gives compilers the freedom to add more padding, but I don't know why a compiler would add more than necessary.

(The typedef definition immediately before the structure definition elevates the name widget from a tag to a full-fledged type name.3 This lets C code refer to the type as just widget , rather than as struct widget . For brevity, I'll omit the typedefs from now on, but you should assume that they are there.)

Padding between adjacent structure members is called internal padding . Padding after the last member is called trailing padding . The C Standard doesn't allow leading padding. It specifically states that “A pointer to a structure object, suitably converted, points to its initial member and vice versa. There may be unnamed padding within a structure object, but not at its beginning.”2

Each structure object must be at least as a strictly aligned as its most strictly aligned member. For example, the most strictly aligned member in widget is integer m2 , which is word aligned. However, the m2 member of an actual widget object won't be word aligned unless that widget object is also word aligned. Thus each widget must be at least word aligned. A compiler could decide to make widget double-word aligned, which it might do if the stricter alignment yielded faster memory access. (I'm just speculating here. I don't know of a compiler that actually does this.)

Padding and sizeof
For any type T, an object of type “pointer to T” can point to any T object, whether that object is an individual object, a structure member, or an array element. For example, given:

widget w;widget x[10];widget *p = &w;widget *q = &x[2];   

the assignment:

*q = *p;   

copies the value of a standalone widget object into a widget that's an array element. For such assignments to work, all widget objects must have the same size and alignment.

The size of each structure must be a multiple of its alignment. Compilers add trailing padding to each structure if necessary to make this so. For example, since widget must be word aligned, the compiler adds trailing padding to bring the size of a widget up to the next multiple of the word size, which in my examples, is four.

The sizeof operator applied to a structure such as widget yields the total number of bytes in the object, including any padding. In the case of widget compiled for a target processor where sizeof(int) equals four, the cumulative size of widget 's three members would be six:

sizeof(char) + sizeof(int) + sizeof(char) = 6   

However, the padding adds six more bytes, so for our hypothetical target processor, sizeof(widget) would be 12. Type widget has an alignment of four, and 12 is a multiple of four.

Why must the size of a structure be a multiple of its alignment? Well, suppose it weren't. Suppose that widget had no trailing padding so that sizeof(widget) were nine. However, each element in an array of widget s would still have to be word aligned, so each array element would have to be padded with three bytes. That padding just wouldn't be counted in the size of each element. What's wrong with that?

According to both the C and C++ Standards, “When applied to an array, the result [of the sizeof operator] is the total number of bytes in the array.”2,4 The C++ Standard adds that “This implies that the size of an array of n elements is n times the size of an element.” If the padding after each array weren't counted in the size of each element, then the size of an array of n elements would in fact be greater than n times the size of each element. Various common programming techniques would cease to work.

For example, the common C idiom for allocating storage for an array of n widget s is to call malloc in an expression of the form:

pw = malloc(n * sizeof(widget));   

If sizeof(widget) didn't account for the trailing padding after each widget , then this expressions could easily allocate too little storage for the entire array.

As another example, suppose that gadget is a structure defined as:

struct gadget{    char m1;    double m2;    char m3;};   

and that objects of type double must be double-word aligned. The compiler will add 7 bytes of padding after member m1 and also after member m3 , as if the structure had been defined as:

struct gadget{    char m1;    char padding_after_m1[7];     double m2;    char m3;    char padding_after_m3[7]; };   

The most strictly aligned member of gadget is m2 , which is double-word aligned. Thus, each gadget must also be double-word aligned. The padding after m1 ensures that member m2 is double-word aligned relative to the beginning of each gadget . The padding after m3 ensures that the next gadget in an array of gadget s is also double-word aligned.

Rearranging members to reduce padding
You can reduce the size of each widget by rearranging the members to reduce the number of padding bytes. Specifically, you can rearrange the member declarations so that the char members m1 and m3 are adjacent to each other, as in:

struct widget{    char m1;    char m3;    int m2;};   

In this case, the compiler will add only two padding bytes, as if you had declared widget as:

struct widget{    char m1;    char m3;    char padding[2];     int m2;    };   

Consequently, sizeof(widget) would be only eight, rather than 12. (Again, I'm calculating these sizes assuming an int is a 4-byte object aligned to an address that's a multiple of four. The sizes could be different on a machine with different object sizes and alignment requirements.)

You can rearrange widget 's members in other ways to reduce the number of padding bytes. For example, defining widget as:

struct widget{    int m2;    char m1;    char m3;};   

also reduces the number of padding bytes to two and sizeof(widget) to eight.

A Standard C compiler won't rearrange the members of a structure automatically to reduce the structure's size. According to the Standard: “Within a structure object, the non-bit-field members … have addresses that increase in the order in which they are declared.” This effectively prohibits compilers from rearranging structure members from the order in which they're declared.

Class padding in C++
A C++ class is a generalization of a C structure. For the most part, C code that defines and uses structures behaves the same when compiled and executed as C++.

A C++ class can have elements that a C structure cannot, such as access specifiers (public, protected, and private), member functions, static data members, and base classes. Some of these elements alter the physical layout of class objects and complicate the rules for padding. Those rules will be the subject of my next column.

Thanks to Joel Saks for all his help.

Dan Saks is president of Saks & Associates, a C/C++ training and consulting company. For more information about Dan Saks, visit his website at www.dansaks.com. Dan also welcomes your feedback: e-mail him at . For more information about Dan .

Endnotes:

1. Saks, Dan, “Deallocating objects vs. deallocating storage,” Embedded Systems Design, March 2009, p. 9.

2. ISO/IEC Standard 9899:1999, Programming languages–C.

3. Saks, Dan, “Tag vs. Type Names,” Embedded Systems Programming, October 2002, p. 7.

4. ISO/IEC Standard 14882:2003(E), Programming languages–C++.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.