STRUCTURE PADDING

1:Data structure alignment is the way data is arranged and accessed in computer memory. It consists of two separate but related issues: data alignment and data structure padding. When a modern computer reads from or writes to a memory address, it will do this in word sized chunks (e.g. 4 byte chunks on a 32-bit system). Data alignment means putting the data at a memory offset equal to some multiple of the word size, which increases the system's performance due to the way the CPU handles memory. To align the data, it may be necessary to insert some meaningless bytes between the end of the last data structure and the start of the next, which is data structure padding.
For example, when the computer's word size is 4 bytes, the data to be read should be at a memory offset which is some multiple of 4. When this is not the case, e.g. the data starts at the 14th byte instead of the 16th byte, then the computer has to read two 4-byte chunks and do some calculation before the requested data has been read, or it may generate an alignment fault. Even though the previous data structure ends at the 14th byte, the next data structure should start at the 16th byte. Two padding bytes are inserted between the two data structures to align the next data structure to the 16th byte.

2:

Data structure padding

Although the compiler (or interpreter) normally allocates individual data items on aligned boundaries, data structures often have members with different alignment requirements. To maintain proper alignment the translator normally inserts additional unnamed data members so that each member is properly aligned. In addition the data structure as a whole may be padded with a final unnamed member. This allows each member of an array of structures to be properly aligned.

Padding is only inserted when a structure member is followed by a member with a larger alignment requirement or at the end of the structure. By changing the ordering of members in a structure, it is possible to change the amount of padding required to maintain alignment. For example, if members are sorted by ascending or descending alignment requirements a minimal amount of padding is required. The minimal amount of padding required is always less than the largest alignment in the structure. Computing the maximum amount of padding required is more complicated, but is always less than the sum of the alignment requirements for all members minus twice the sum of the alignment requirements for the least aligned half of the structure members.

Although C and C++ do not allow the compiler to reorder structure members to save space, other languages might. It is also possible to tell most C and C++ compilers to "pack" the members of a structure to a certain level of alignment, e.g. "pack(2)" means align data members larger than a byte to a two-byte boundary so that any padding members are at most one byte long.

One use for such "packed" structures is to conserve memory. For example, a structure containing a single byte and a four-byte integer would require three additional bytes of padding. A large array of such structures would use 37.5% less memory if they are packed, although accessing each structure might take longer. This compromise may be considered a form of space-time tradeoff.

Although use of "packed" structures is most frequently used to conserve memory space, it may also be used to format a data structure for transmission using a standard protocol. However in this usage, care must also be taken to ensure that the values of the struct members are stored with the endianness required by the protocol (often network byte order), which may be different from the endianness used natively by the host machine.

[edit] Computing padding

The following formulas provide the number of padding bytes required to align the start of a data structure (where mod is the modulo operator):

padding = align - (offset mod align)
new offset = offset + padding = offset + align - (offset mod align)

For example, the padding to add to offset 0x59d for a structure aligned to every 4 bytes is 3. The structure will then start at 0x5a0, which is a multiple of 4. Note that when offset already is a multiple of align, taking the modulo of align - (offset mod align) is required to get a padding of 0.

Or alternatively when the alignment is a power of two, the following formulas provides the new offset (where & is a bitwise AND and ~ a bitwise NOT):

new offset = align + ((offset - 1) & ~(align - 1))
padding = (align + ((offset - 1) & ~(align - 1))) - offset

[edit] Typical alignment of C structs on x86

Data structure members are stored sequentially in a memory so that in the structure below the member Data1 will always precede Data2 and Data2 will always precede Data3:

struct MyData
{
 short Data1;
 short Data2;
 short Data3;
};

If the type "short" is stored in two bytes of memory then each member of the data structure depicted above would be 2-byte aligned. Data1 would be at offset 0, Data2 at offset 2 and Data3 at offset 4. The size of this structure would be 6 bytes.

The type of each member of the structure usually has a default alignment, meaning that it will, unless otherwise requested by the programmer, be aligned on a pre-determined boundary. The following typical alignments are valid for compilers from Microsoft, Borland, and GNU when compiling for 32-bit x86:

• A char (one byte) will be 1-byte aligned.
• A short (two bytes) will be 2-byte aligned.
• An int (four bytes) will be 4-byte aligned.
• A float (four bytes) will be 4-byte aligned.
• A double (eight bytes) will be 8-byte aligned on Windows and 4-byte aligned on Linux.
• A long double (twelve bytes) will be 4-byte aligned on Linux.
• Any pointer (four bytes) will be 4-byte aligned on Linux. (e.g.: char*, int*)

The only notable difference in alignment for a 64-bit Linux system when compared to a 32 bit is:

• A double (eight bytes) will be 8-byte aligned.
• A long double (Sixteen bytes) will be 16-byte aligned.
• Any pointer (eight bytes) will be 8-byte aligned.

Here is a structure with members of various types, totaling 8 bytes before compilation:

struct MixedData
{
 char Data1;
 short Data2;
 int Data3;
 char Data4;
};

After compilation the data structure will be supplemented with padding bytes to ensure a proper alignment for each of its members:

struct MixedData  /* after compilation */
{
 char Data1;
 char Padding1[1]; /* For the following 'short' to be aligned on a 2 byte boundary */
 short Data2;
 int Data3;
 char Data4;
 char Padding2[3];
};

The compiled size of the structure is now 12 bytes. It is important to note that the last member is padded with the number of bytes required to conform to the largest type of the structure. In this case 3 bytes are added to the last member to pad the structure to the size of a long word.

It is possible to change the alignment of structures to reduce the memory they require (or to conform to an existing format) by reordering structure members or changing the compiler’s alignment (or “packing”) of structure members.

struct MixedData  /* after reordering */
{
 char Data1;
 char Data4;   /* reordered */
 short Data2;
 int Data3;
};

The compiled size of the structure now matches the pre-compiled size of 8 bytes. Note that Padding1[1] has been replaced (and thus eliminated) by Data4 and Padding2[3] is no longer necessary as the structure is already aligned to the size of a long word.

The alternative method of enforcing the MixedData structure to be aligned to a one byte boundary will cause the pre-processor to discard the pre-determined alignment of the structure members and thus no padding bytes would be inserted.

While there is no standard way of defining the alignment of structure members, some compilers use #pragma directives to specify packing inside source files. Here is an example:

#pragma pack(push)  /* push current alignment to stack */
#pragma pack(1)     /* set alignment to 1 byte boundary */

struct MyPackedData
{
 char Data1;
 long Data2;
 char Data3;
};

#pragma pack(pop)   /* restore original alignment from stack */

This structure would have a compiled size of 6 bytes. The above directives are available in compilers from Microsoft, Borland, GNU and many others.

[edit] Default packing and #pragma pack

On some MS compilers, particularly for the RISC processor, there is a relationship between project default packing (the /Zp directive) and the #pragma pack directive which is unexpected for most people.

The #pragma pack directive can only be used to reduce the packing size of a structure from the project default packing. This leads to interoperability problems with library headers which use for example #pragma pack(8) if you set a project packing to smaller than this. The MSDN documentation^[1] states that if the #pragma pack packing is larger than or equal to the project packing, it will be ignored.

For this reason, one should never set a project packing to any value other than the default of 8 bytes, as it would break the #pragma pack directives used in library headers and result in binary incompatibilities between structures.

In particular, setting /Zp1 breaks all #pragma pack directives other than #pragma pack(1).

However, this limitation is not present when compiling for desktop processors, such as the x86 architecture.

[edit] Allocating memory aligned to cache lines

It would be beneficial to allocate memory aligned to cache lines. If an array is partitioned for more than one thread to operate on, having the sub-array boundaries unaligned to cache lines could lead to performance degradation. Here is an example to allocate memory (double array of size 8) aligned to cache line of 64 bytes.

#include 
double *foo(void) {
   double *var;
   int     ok;
 
   ok = posix_memalign(&var, 64, 8);
 
   if(ok != 0)
     return NULL;
 
   return var;
}

4:Structure Padding
 

Most processors require specific memory alignment on variables certain
types. Normally the minimum alignment is the size of the basic type in
question, fo instance this is common
 

char variables can be byte aligned and appear at any byte boundary
 

short (2 byte) variables must be 2 byte aligned, they can appear at any
even byte boundary. This means that 0x10004567 is not a valid location
for a short variable but 0x10004566 is.
 

long (4 byte) variables must be 4 byte aligned, they can only appear at
byte boundarys that are a multiple of 4 bytes. This means that
0x10004566 is not a valid location for a long variable but 0x10004568
is.
 

Structure padding occurs because the members of the structure must
appear at the correect byte boundary, to achieve this the compiler puts
in padding bytes (or bits if bit fields are in use) so that the
structure members appear in the correct location. Additionally the size
of the structure must be such that in an array of the structures all
the structures are correctly aligned in memory so there may be padding
bytes at the end of the structure too
 

struct example {

 char c1;

 short s1;

 char c2;

 long l1;

 char c3;

}
 

In this structure, assuming the alignment scheme I have previously stated then
 

c1 can appear at any byte boundary, however s1 must appear at a 2 byte boundary so there is a padding byte between c1 and s1.  
 

c2 can then appear in the available memory location, however l1 must be
at a 4 byte boundary so there are 3 padding bytes between c2 and l1
 

c3 then appear in the available memory location, however because the
structure contains a long member the structure must be 4 byte aligned
and must be a multiple of 4 bytes in size. Therefore there are 3
padding bytes at the end of the structure. it would appear in memory in
this order
 

c1

padding byte

s1 byte 1

s1 byte 2

c2

padding byte

padding byte

padding byte

l1 byte 1

l1 byte 2

l1 byte 3

l1 byte 4

c3

padding byte

padding byte

padding byte
 

The structure would be 16 bytes long.
 

re-written like this
 

struct example {

 long l1;

 short s1;

 char c1;

 char c2;

 char c3;

}
 

Then l1 appears at the correct byte alignment, s1 will be correctly
aligned so no need for padding between l1 and s1. c1, c2, c3 can appear
at any location. The structure must be a multiple of 4 bytes in size
since it contains a long so 3 padding bytes appear after c3
 

It appears in memory in the order
 

l1 byte 1

l1 byte 2

l1 byte 3

l1 byte 4

s1 byte 1

s1 byte 2

c1

c2

c3

padding byte

padding byte

padding byte
 

and is only 12 bytes long.
 
 

I should point out that structure packing is platform and compiler (and in some cases compiler switch) dependent.
 
 
 
 

Memory Pools are just a section of memory reserved for allocating temporarily to other parts of the application
 
 

A memory leak occurs when you allocate some memory from the heap(or a
pool) and then delete all references to that memory without returning
it to the pool it was allocated from.
         

tyreld Familiar Sight Oct 3 '06

re: what is structure padding 1.) The simple answer is compilers pad structures to optimize data transfers. This is an hardware architecture issue. Most modern CPUs perform best when fundemental types, like 'int' or 'float', are algined on memory boundarys of a particular size (eg. often a 4byte word on 32bit archs). Many architectures don't allow misaligned access or if they do inccur a performance penalty. When a compiler processes a structure declaration it will add extra bytes between fields to meet alignment needs. Expand|Select|Wrap|Line Numbers struct MyStructA { char a; char b; int c; }; struct MyStructB { char a; int c; char b; }; int main(void) { int sizeA = sizeof(struct MyStructA); int sizeB = sizeof(struct MyStructB); printf("A = %d\n", sizeA); printf("B = %d\n", sizeB); return 0; } Results compiling with gcc on a Linux x86 system, it will vary for other CPU/OS/compiler combination. In this example the gcc compiler is aligning the structure fields on 4byte boundaries. In MyStructA we have (1 byte + 1 byte + 2 bytes of padding + 4 bytes = 8bytes). In MyStructB we have (1 byte + 3 bytes of padding + 4 bytes + 1 byte + 3 bytes of padding = 12 bytes). Expand|Select|Wrap|Line Numbers tyreld@susie:~/Desktop> ./a.out A = 8 B = 12 This example illustrates a good rule of thumb. Generally, it is good to group structure fields of the same type together to minimize the extra padding. 2.) The following link gives a basic overview of memory pools . 3.) My laziness as a programmer is clearly showing as I'm going to refer you now to the wikipedia page discussing memory leaks.

svlsr2000 Expert Join Date: Feb 2007 Location: Bangalore Posts: 182 #4: May 11 '07

re: what is structure padding Those are 3 different things. Structure Padding char variables can be byte aligned and appear at any byte boundary short (2 byte) variables must be 2 byte aligned, they can appear at any even byte boundary. This means that 0x10004567 is not a valid location for a short variable but 0x10004566 is. long (4 byte) variables must be 4 byte aligned, they can only appear at byte boundarys that are a multiple of 4 bytes. This means that 0x10004566 is not a valid location for a long variable but 0x10004568 is. Structure padding occurs because the members of the structure must appear at the correect byte boundary, to achieve this the compiler puts in padding bytes (or bits if bit fields are in use) so that the structure members appear in the correct location. Additionally the size of the structure must be such that in an array of the structures all the structures are correctly aligned in memory so there may be padding bytes at the end of the structure too I was just brushing up my c skills and especially structure padding. i have the following doubt Expand|Select|Wrap|Line Numbers #include #pragma pack(push) #pragma pack(1) struct test{ char a;//1 byte //Genrally padded so that int can start from 4 byte alignment int b;// char c;//1 byte //generally padded so that d can start in 2 byte allignment short d; }; #pragma pack(pop) typedef struct test testStructure; int main() { testStructure testData; testStructure testDataArray[4]; int iterator; printf("\n Address of test Data is 0x %x \n", &testData); printf(" Address of char a in testData is 0x %x \n", &(testData.a)); printf(" Address of int b in testData is 0x %x \n", &(testData.b)); printf(" Address of char c in testData is 0x %x \n", &(testData.c)); printf(" Address of short d in testData is 0x %x \n", &(testData.d)); printf(" size of struct test is %d\n", sizeof(struct test)); printf("\n Printing the address in Array\n"); for(iterator = 0; iterator <> { printf("Iterator value is %d \n", iterator); printf("\n Address of testDataArray is 0x %x \n", &testDataArray[iterator]); printf(" Address of char a in testDataArray is 0x %x \n", &(testDataArray[iterator].a)); printf(" Address of int b in testDataArray is 0x %x \n", &(testDataArray[iterator].b)); printf(" Address of char c in testDataArray is 0x %x \n", &(testDataArray[iterator].c)); printf(" Address of short d in testDataArray is 0x %x \n", &(testDataArray[iterator].d)); } return 0; } The output of this program compiled in windows xp, visual studio 2005 is as follows Address of test Data is 0x 12ff50 Address of char a in testData is 0x 12ff50 Address of int b in testData is 0x 12ff51 Address of char c in testData is 0x 12ff55 Address of short d in testData is 0x 12ff56 size of struct test is 8 Printing the address in Array Iterator value is 0 Address of testDataArray is 0x 12ff58 Address of char a in testDataArray is 0x 12ff58 Address of int b in testDataArray is 0x 12ff59 Address of char c in testDataArray is 0x 12ff5d Address of short d in testDataArray is 0x 12ff5e Iterator value is 1 Address of testDataArray is 0x 12ff60 Address of char a in testDataArray is 0x 12ff60 Address of int b in testDataArray is 0x 12ff61 Address of char c in testDataArray is 0x 12ff65 Address of short d in testDataArray is 0x 12ff66 Iterator value is 2 Address of testDataArray is 0x 12ff68 Address of char a in testDataArray is 0x 12ff68 Address of int b in testDataArray is 0x 12ff69 Address of char c in testDataArray is 0x 12ff6d Address of short d in testDataArray is 0x 12ff6e Iterator value is 3 Address of testDataArray is 0x 12ff70 Address of char a in testDataArray is 0x 12ff70 Address of int b in testDataArray is 0x 12ff71 Address of char c in testDataArray is 0x 12ff75 Address of short d in testDataArray is 0x 12ff76 My doubt: When we use #pragma pack the compilers usually stops padding the structure, then how are these variables accessed. And this is contradictory with " Additionally the size of the structure must be such that in an array of the structures all the structures are correctly aligned in memory so there may be padding bytes at the end of the structure too". Though we save much space here why the compilers dont have packing as default? sorry for poor english.

Banfa Site Moderator

re: what is structure padding Though we save much space here why the compilers dont have packing as default? The reason that compilers put in padding is to align members on boundaries that make the data easy to access. Taking your example Expand|Select|Wrap|Line Numbers #pragma pack(1) struct test{ char a;//1 byte //Genrally padded so that int can start from 4 byte alignment int b;// char c;//1 byte //generally padded so that d can start in 2 byte allignment short d; }; the int would be aligned on a 4 byte boundary because this allows the compiler to produce machine code using the processors 32bit access instructions (which often have to act on a 32bit boundary). By packing the code into memory the machine code produced can no longer use the 32bit access routines and has to read and load each byte of the int individually and reconstitute the 32 bit value in it's registers from the individual bytes. This takes many more processor instructions. So the answer to your question is that while not padding the structure saves space it also makes the code much more efficient and if memory is not at a premium then the wastage caused by padding is considered worth it for the increased processor performance.