Structure padding and packing

Consi开发者_运维问答der:

struct mystruct_A
{
   char a;
   int b;
   char c;
} x;

struct mystruct_B
{
   int b;
   char a;
} y;

The sizes of the structures are 12 and 8 respectively.

Are these structures padded or packed?

When does padding or packing take place?

---

Padding aligns structure members to "natural" address boundaries - say, int members would have offsets, which are mod(4) == 0 on 32-bit platform. Padding is on by default. It inserts the following "gaps" into your first structure:

struct mystruct_A {
    char a;
    char gap_0[3]; /* inserted by compiler: for alignment of b */
    int b;
    char c;
    char gap_1[3]; /* -"-: for alignment of the whole struct in an array */
} x;

Packing, on the other hand prevents compiler from doing padding - this has to be explicitly requested - under GCC it's __attribute__((__packed__)), so the following:

struct __attribute__((__packed__)) mystruct_A {
    char a;
    int b;
    char c;
};

would produce structure of size 6 on a 32-bit architecture.

A note though - unaligned memory access is slower on architectures that allow it (like x86 and amd64), and is explicitly prohibited on strict alignment architectures like SPARC.

---

(The above answers explained the reason quite clearly, but seems not totally clear about the size of padding, so, I will add an answer according to what I learned from The Lost Art of Structure Packing, it has evolved to not limit to C, but also applicable to Go, Rust.)

---

Memory align (for struct)

Rules:

• Before each individual member, there will be padding so that to make it start at an address that is divisible by its alignment requirement.
  E.g., on many systems, an int should start at an address divisible by 4 and a short by 2.
• char and char[] are special, could be any memory address, so they don't need padding before them.
• For struct, other than the alignment need for each individual member, the size of whole struct itself will be aligned to a size divisible by strictest alignment requirement of any of its members, by padding at end.
  E.g., on many systems, if struct's largest member is int then by divisible by 4, if short then by 2.

Order of member:

• The order of member might affect actual size of struct, so take that in mind. E.g., the stu_c and stu_d from example below have the same members, but in different order, and result in different size for the 2 structs.

---

Address in memory (for struct)

Empty space:

• Empty space between 2 structs could be used by non-struct variables that could fit in.
  e.g in test_struct_address() below, the variable x resides between adjacent struct g and h.
  No matter whether x is declared, h's address won't change, x just reused the empty space that g wasted.
  Similar case for y.

---

Example

(for 64 bit system)

memory_align.c:

/**
 * Memory align & padding - for struct.
 * compile: gcc memory_align.c
 * execute: ./a.out
 */ 
#include <stdio.h>

// size is 8, 4 + 1, then round to multiple of 4 (int's size),
struct stu_a {
    int i;
    char c;
};

// size is 16, 8 + 1, then round to multiple of 8 (long's size),
struct stu_b {
    long l;
    char c;
};

// size is 24, l need padding by 4 before it, then round to multiple of 8 (long's size),
struct stu_c {
    int i;
    long l;
    char c;
};

// size is 16, 8 + 4 + 1, then round to multiple of 8 (long's size),
struct stu_d {
    long l;
    int i;
    char c;
};

// size is 16, 8 + 4 + 1, then round to multiple of 8 (double's size),
struct stu_e {
    double d;
    int i;
    char c;
};

// size is 24, d need align to 8, then round to multiple of 8 (double's size),
struct stu_f {
    int i;
    double d;
    char c;
};

// size is 4,
struct stu_g {
    int i;
};

// size is 8,
struct stu_h {
    long l;
};

// test - padding within a single struct,
int test_struct_padding() {
    printf("%s: %ld\n", "stu_a", sizeof(struct stu_a));
    printf("%s: %ld\n", "stu_b", sizeof(struct stu_b));
    printf("%s: %ld\n", "stu_c", sizeof(struct stu_c));
    printf("%s: %ld\n", "stu_d", sizeof(struct stu_d));
    printf("%s: %ld\n", "stu_e", sizeof(struct stu_e));
    printf("%s: %ld\n", "stu_f", sizeof(struct stu_f));

    printf("%s: %ld\n", "stu_g", sizeof(struct stu_g));
    printf("%s: %ld\n", "stu_h", sizeof(struct stu_h));

    return 0;
}

// test - address of struct,
int test_struct_address() {
    printf("%s: %ld\n", "stu_g", sizeof(struct stu_g));
    printf("%s: %ld\n", "stu_h", sizeof(struct stu_h));
    printf("%s: %ld\n", "stu_f", sizeof(struct stu_f));

    struct stu_g g;
    struct stu_h h;
    struct stu_f f1;
    struct stu_f f2;
    int x = 1;
    long y = 1;

    printf("address of %s: %p\n", "g", &g);
    printf("address of %s: %p\n", "h", &h);
    printf("address of %s: %p\n", "f1", &f1);
    printf("address of %s: %p\n", "f2", &f2);
    printf("address of %s: %p\n", "x", &x);
    printf("address of %s: %p\n", "y", &y);

    // g is only 4 bytes itself, but distance to next struct is 16 bytes(on 64 bit system) or 8 bytes(on 32 bit system),
    printf("space between %s and %s: %ld\n", "g", "h", (long)(&h) - (long)(&g));

    // h is only 8 bytes itself, but distance to next struct is 16 bytes(on 64 bit system) or 8 bytes(on 32 bit system),
    printf("space between %s and %s: %ld\n", "h", "f1", (long)(&f1) - (long)(&h));

    // f1 is only 24 bytes itself, but distance to next struct is 32 bytes(on 64 bit system) or 24 bytes(on 32 bit system),
    printf("space between %s and %s: %ld\n", "f1", "f2", (long)(&f2) - (long)(&f1));

    // x is not a struct, and it reuse those empty space between struts, which exists due to padding, e.g between g & h,
    printf("space between %s and %s: %ld\n", "x", "f2", (long)(&x) - (long)(&f2));
    printf("space between %s and %s: %ld\n", "g", "x", (long)(&x) - (long)(&g));

    // y is not a struct, and it reuse those empty space between struts, which exists due to padding, e.g between h & f1,
    printf("space between %s and %s: %ld\n", "x", "y", (long)(&y) - (long)(&x));
    printf("space between %s and %s: %ld\n", "h", "y", (long)(&y) - (long)(&h));

    return 0;
}

int main(int argc, char * argv[]) {
    test_struct_padding();
    // test_struct_address();

    return 0;
}

Execution result - test_struct_padding():

stu_a: 8
stu_b: 16
stu_c: 24
stu_d: 16
stu_e: 16
stu_f: 24
stu_g: 4
stu_h: 8

Execution result - test_struct_address():

stu_g: 4
stu_h: 8
stu_f: 24
address of g: 0x7fffd63a95d0  // struct variable - address dividable by 16,
address of h: 0x7fffd63a95e0  // struct variable - address dividable by 16,
address of f1: 0x7fffd63a95f0 // struct variable - address dividable by 16,
address of f2: 0x7fffd63a9610 // struct variable - address dividable by 16,
address of x: 0x7fffd63a95dc  // non-struct variable - resides within the empty space between struct variable g & h.
address of y: 0x7fffd63a95e8  // non-struct variable - resides within the empty space between struct variable h & f1.
space between g and h: 16
space between h and f1: 16
space between f1 and f2: 32
space between x and f2: -52
space between g and x: 12
space between x and y: 12
space between h and y: 8

Thus address start for each variable is g:d0 x:dc h:e0 y:e8

---

I know this question is old and most answers here explains padding really well, but while trying to understand it myself I figured having a "visual" image of what is happening helped.

The processor reads the memory in "chunks" of a definite size (word). Say the processor word is 8 bytes long. It will look at the memory as a big row of 8 bytes building blocks. Every time it needs to get some information from the memory, it will reach one of those blocks and get it.

As seem in the image above, doesn't matter where a Char (1 byte long) is, since it will be inside one of those blocks, requiring the CPU to process only 1 word.

When we deal with data larger than one byte, like a 4 byte int or a 8 byte double, the way they are aligned in the memory makes a difference on how many words will have to be processed by the CPU. If 4-byte chunks are aligned in a way they always fit the inside of a block (memory address being a multiple of 4) only one word will have to be processed. Otherwise a chunk of 4-bytes could have part of itself on one block and part on another, requiring the processor to process 2 words to read this data.

The same applies to a 8-byte double, except now it must be in a memory address multiple of 8 to guarantee it will always be inside a block.

This considers a 8-byte word processor, but the concept applies to other sizes of words.

The padding works by filling the gaps between those data to make sure they are aligned with those blocks, thus improving the performance while reading the memory.

However, as stated on others answers, sometimes the space matters more then performance itself. Maybe you are processing lots of data on a computer that doesn't have much RAM (swap space could be used but it is MUCH slower). You could arrange the variables in the program until the least padding is done (as it was greatly exemplified in some other answers) but if that's not enough you could explicitly disable padding, which is what packing is.

---

Structure packing suppresses structure padding, padding used when alignment matters most, packing used when space matters most.

Some compilers provide #pragma to suppress padding or to make it packed to n number of bytes. Some provide keywords to do this. Generally pragma which is used for modifying structure padding will be in the below format (depends on compiler):

#pragma pack(n)

For example ARM provides the __packed keyword to suppress structure padding. Go through your compiler manual to learn more about this.

So a packed structure is a structure without padding.

Generally packed structures will be used

• to save space

• to format a data structure to transmit over network using some protocol (this is not a good practice of course because you need to
  deal with endianness)

---

Padding and packing are just two aspects of the same thing:

• packing or alignment is the size to which each member is rounded off
• padding is the extra space added to match the alignment

In mystruct_A, assuming a default alignment of 4, each member is aligned on a multiple of 4 bytes. Since the size of char is 1, the padding for a and c is 4 - 1 = 3 bytes while no padding is required for int b which is already 4 bytes. It works the same way for mystruct_B.

---

Rules for padding:

1. Every member of the struct should be at an address divisible by its size. Padding is inserted between elements or at the end of the struct to make sure this rule is met. This is done for easier and more efficient Bus access by the hardware.
2. Padding at the end of the struct is decided based on the size of the largest member of the struct.

Why Rule 2: Consider the following struct,

If we were to create an array(of 2 structs) of this struct, No padding will be required at the end:

Therefore, size of struct = 8 bytes

Assume we were to create another struct as below:

If we were to create an array of this struct, there are 2 possibilities, of the number of bytes of padding required at the end.

A. If we add 3 bytes at the end and align it for int and not Long:

B. If we add 7 bytes at the end and align it for Long:

The start address of the second array is a multiple of 8(i.e 24). The size of the struct = 24 bytes

Therefore, by aligning the start address of the next array of the struct to a multiple of the largest member(i.e if we were to create an array of this struct, the first address of the second array must start at an address which is a multiple of the largest member of the struct. Here it is, 24(3 * 8)), we can calculate the number of padding bytes required at the end.

---

The variables are stored at any addresses divisible by its alignment(by its size generally). So, padding/packing is not just for struct only. Actually, all data has its own alignment requirement:

int main(void) {
    // We assume the `c` is stored as first byte of machine word
    // as a convenience! If the `c` was stored as a last byte of previous
    // word, there is no need to pad bytes before variable `i`
    // because `i` is automatically aligned in a new word.

    char      c;  // starts from any addresses divisible by 1(any addresses).
    char pad[3];  // not-used memory for `i` to start from its address.
    int32_t   i;  // starts from any addresses divisible by 4.

This is similar to struct, but there are some differences. First, we can say there are two kinds of padding— a) To start each member from its address properly, some bytes are inserted between members. b) To start next struct instance from its address properly, some bytes are appended to each struct:

// Example for rule 1 below.
struct st {
    char      c;  // starts from any addresses divisible by 4, not 1.
    char pad[3];  // not-used memory for `i` to start from its address.
    int32_t   i;  // starts from any addresses divisible by 4.
};

// Example for rule 2 below.
struct st {
    int32_t   i;  // starts from any addresses divisible by 4.
    char      c;  // starts from any addresses.
    char pad[3];  // not-used memory for next `st`(or anything that has same
                  // alignment requirement) to start from its own address.
};

1. The struct's first member always starts from any addresses divisible by struct's own alignment requirement which is determined by largest member's alignment requirement(here 4, alignment of int32_t). This is different with normal variables. The normal variables can start any addresses divisible by its alignment, but it is not the case for struct's first member. As you know, the address of a struct is the same as the address of its first member.
2. There can be additional padded trailing bytes inside a struct, making next struct(or next element in an array of structs) starting from its own address. Think of struct st arr[2];. To make arr[1](arr[1]'s first member) starting from an address divisible by 4, we should append 3 bytes at the end of each struct.

This is what i learned from The Lost Art of Structure Packing.

NOTE : You can investigate what the data type's alignment requirement is through _Alignof operator. Also, you can get member's offset inside a struct through offsetof macro.

---

Are these structures padded or packed?

They're padded.

The only possibility that initially springs to mind, where they could be packed, is if char and int were the same size, so that the minimum size of the char/int/char structure would allow for no padding, ditto for the int/char structure.

However, that would require both sizeof(int) and sizeof(char) to be four (to get the twelve and eight sizes). The whole theory falls apart since it's guaranteed by the standard that sizeof(char) is always one.

Were char and int the same width, the sizes would be one and one, not four and four. So, in order to then get a size of twelve, there would have to be padding after the final field.

---

When does padding or packing take place?

Whenever the compiler implementation wants it to. Compilers are free to insert padding between fields, and following the final field (but not before the first field).

This is usually done for performance as some types perform better when they're aligned on specific boundaries. There are even some architectures that will refuse to function (i.e, crash) is you try to access unaligned data (yes, I'm looking at you, ARM).

You can generally control packing/padding (which is really opposite ends of the same spectrum) with implementation-specific features such as #pragma pack. Even if you cannot do that in your specific implementation, you can check your code at compile time to ensure it meets your requirement (using standard C features, not implementation-specific stuff).

For example:

// C11 or better ...
#include <assert.h>
struct strA { char a; int  b; char c; } x;
struct strB { int  b; char a;         } y;
static_assert(sizeof(struct strA) == sizeof(char)*2 + sizeof(int), "No padding allowed");
static_assert(sizeof(struct strB) == sizeof(char)   + sizeof(int), "No padding allowed");

Something like this will refuse to compile if there is any padding in those structures.

---

Structure packing is only done when you tell your compiler explicitly to pack the structure. Padding is what you're seeing. Your 32-bit system is padding each field to word alignment. If you had told your compiler to pack the structures, they'd be 6 and 5 bytes, respectively. Don't do that though. It's not portable and makes compilers generate much slower (and sometimes even buggy) code.

---

There are no buts about it! Who want to grasp the subject must do the following ones,

• Peruse The Lost Art of Structure Packing written by Eric S. Raymond
• Glance at Eric's code example
• Last but not least, don't forget the following rule about padding that a struct is aligned to the largest type’s alignment requirements.

---

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) or larger. Data alignment means putting the data at a memory address 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.

1. In order to align the data in memory, one or more empty bytes (addresses) are inserted (or left empty) between memory addresses which are allocated for other structure members while memory allocation. This concept is called structure padding.
2. Architecture of a computer processor is such a way that it can read 1 word (4 byte in 32 bit processor) from memory at a time.
3. To make use of this advantage of processor, data are always aligned as 4 bytes package which leads to insert empty addresses between other member’s address.
4. Because of this structure padding concept in C, size of the structure is always not same as what we think.