What are the implications of a 'packed' keyword/feature?

Question

I am bothered by the fact that, in C, struct types can be arbitrarily large. We have no control over their memory layout except for the fact that the first member is always at the beginning of the memory and the elements are arranged in the order we defined them in. A 'conforming' but never to be seen in practice C implementation may handle a struct as follows:

struct S {
    char x; // 1 byte
    // 999999999 bytes padding
    char y; // 1 byte
    // 999999999 bytes padding
    short z; // 2 bytes
    // 999999998 bytes padding
}; // Total size: 3 GB

To solve such problems, I am considering implementing a packed keyword to my programming language. packed struct would require using the least amount of space with no padding, and that all elements immediately follow each other. packed enum would use the smallest type that can hold all enumerators instead of some default type such as int.

What are the implications to implementing such a feature? Are there reasons, performance, compatibility, or otherwise, to refrain?

Answer 1

Padding and Packing

The layout of structures is defined by the ABI (Application Binary Interface). The typical mindset of an ABI designer is mechanical sympathy, with an eye towards performance (speed).

To talk about padding, we need to talk about alignment, size, and stride.

First is alignment. Native types tend to have an alignment, that is the architecture expects that a double is either 4 or 8 bytes aligned (depending). This alignment then bleeds into compound types: the only way to ensure that a double field is 8 bytes aligned is for the compound type containing the field to itself by 8 bytes aligned, hence a compound type's alignment is the greater alignment of any of its components.

Second is size. Native types have a size, too. For example a double is typically 8 bytes. The size of the compound type will depend on the size and alignment of its components, as per the ABI rules.

Finally is stride. The stride of a type is the spacing between consecutive array elements. Swift is one of the few languages differentiating size and stride, in C the stride is always the size.

With that in mind, here is a typical product type ABI, as can generally be found in C:

• The alignment of the product type is the maximum alignment of any of its fields.
• The first field starts at the first byte of its product type.
• Any subsequent field starts at the next offset which guarantees its alignment, which may lead to "in-between" padding bytes.
• The size of the struct is rounded-up to a multiple of its alignment, which may lead to "tail" padding bytes.

And since a picture is clearer than words:

struct ProductType {
    int i;
    char __padding_0[P0];
    double d;
    char __padding_1[P1];
    char c;
    char __padding_2[P2];
};

On x64, we have:

• int: 4 bytes, 4-bytes aligned.
• double: 8 bytes, 8-bytes aligned.
• char: 1 byte, 1-byte aligned.

Therefore:

• P0 = 4. This is because d must start at an offset that is a multiple of 8, and after i the offset is only 4.
• P1 = 0. This is because c must start at an offset that is a multiple of 1, and any offset is.
• P2 = 7. This is because the alignment of ProductType is 8, hence its size must be a multiple of 8.

Note that Swift would have P2 = 0.

The effect of packing is, very simply, to remove all padding.¹

¹ I am aware that some compilers take the opportunity to also allow specifying the struct alignment when packing. That's a potentially useful extra feature, but it's not packing.

Implications of Packing

The first and foremost implication is that you should implement it properly, or users will curse you.

For example, it seems reasonable to allow taking a reference (or pointer) to a field of a packed struct. However, this reference (or pointer) may now be under-aligned: that is, its alignment may be strictly less than the expected alignment of a pointer of this type.

Different languages & toolchains handle the situation differently:

• In Zig, pointer alignment is a part of the pointer type, so a compilation error will follow if one attempts to use an under-aligned pointer where a regular pointer is expected.
• In GCC (C or C++), the compiler handles under-aligned pointers properly within the function in which the pointer was created, but allows passing the under-aligned pointers to functions expecting a regular pointer... which leads to Undefined Behavior.
• In Rust, manipulating packed fields is unsafe, and the user is on the hook to tread carefully, or they will trigger Undefined Behavior.

I would argue that the situation of being able to create an under-aligned pointer, but then have to walk on eggshells forever, is not desirable from a user point of view, and thus that language designers going the packed way should either disallow forming such pointers, or follow through and ensure they provide users the tooling they need to manipulate under-aligned pointers.

Alternatives

There are alternatives to packing, for the memory conscious.

As mentioned, packing is about avoiding padding, and there are two sources of padding:

• In-between fields padding.
• Tail padding.

Tail padding is eliminated in a language such as Swift which differentiates size & stride.

In-between fields padding is eliminated in a language such as Rust which reserves the right to re-order fields arbitrarily -- and typically will reorder them by descending alignment, which removes all in-between fields padding.

Those two alternatives, combined, remove nearly² any and all padding in a struct³ without introducing under-aligned references and pointers into the fray.

I would typically advise considering them first:

• Provide the same memory gains as packed, without taxing the user.
• Without performance penalty incurred from under-aligned pointers.
• Without headaches induced by under-aligned pointers.

You may still want to later introduce under-aligned pointers in the language, separately.

² Unless reordering can interleave the fields from different field structs, there may still be some padding in between structs. For example, a struct A (int, char) followed by itself would still have 3 bytes of padding between the two instances, no matter the order.

³ Padding may still occur between array elements, the exact amount of padding inserted being equal to stride - size.

Answer 2

According to “The Lost Art of Structure Packing” by Eric S. Raymond, structure packing can slow down your program or worse:

The first thing to understand is that, on modern processors, the way your compiler lays out basic datatypes in memory is constrained in order to make memory accesses faster. Our examples are in C, but any compiled language generates code under the same constraints.

…

Self-alignment [that is, aligning to an address divisible by the size of the datatype] makes access faster because it facilitates generating single-instruction fetches and puts of the typed data. Without alignment constraints, on the other hand, the code might end up having to do two or more accesses spanning machine-word boundaries.

…

I said “on modern processors” because on some older ones forcing your C program to violate alignment rules (say, by casting an odd address into an int pointer and trying to use it) didn’t just slow your code down, it caused an illegal instruction fault.

On the other hand, structure packing is useful “if you intend to write code for memory-constrained embedded systems, or operating-system kernels. It is useful if you are working with application data sets so large that your programs routinely hit memory limits. It is good to know in any application where you really, really care about optimizing your use of memory bandwidth and minimizing cache-line misses.” Raymond goes on to describe a program of his that kept getting OOM errors, for which he managed “to cut the working-set size by around 40%” by carefully arranging his structures.

Answer 3

Generally, compilers optimise for program speed rather than memory use. This is because in typical desktop and laptop PCs, memory is abundant, and a suboptimal struct layout won't waste that much memory; even a naive compiler should not make a struct take up more than twice as much space as necessary. On the other hand, optimising the execution speed of the program can easily yield improvements by much greater factors than two.

---

Another issue is that modern compilers are often better able to know whether an optimisation is worth applying, than the human writing the code. When languages allow the programmer to provide optimisation hints, like an inline keyword for functions, these are typically just treated as hints and the compiler will gladly inline other functions regardless, and may choose not to inline some functions even when the programmer declared them as inline.

If a packed keyword is treated as a hint then it would not add that much value to the language, since the compiler won't follow it strictly; on the other hand, if a packed keyword forces the compiler to use a packed layout, then it prevents the compiler from choosing an optimal layout and there is a real risk that most programmers will use the keyword incorrectly. (Some will even think that packed means "optimise the struct better" and blindly apply it to every struct, resulting in worse performance more often than not.)

---

Optimisation is not the only reason users may want control over the memory layout of their structs; binary compatibility is also an important issue when data needs to be passed over a network, stored in particular file formats, transferred to the GPU, or so on. But a simple yes/no packed keyword doesn't provide much control over this; for example, it doesn't help programmers who need to insert padding in particular places for correctness reasons.

For these other use-cases, it would be more valuable to offer a mechanism for the programmer to choose the exact layout of their structs, rather than just ask for sequential packing. Using GLSL as an example, the layout qualifier can be used to specify the exact offsets of struct fields. (This qualifier is necessarily attached to individual fields, rather than the struct as a whole.)

Answer 4

There's not really any need for this feature, and using it could cause performance issues (e.g. requiring extra memory fetches and realignment for each item, or even a memory fault).

In situations where minimizing the size is important, the programmer would simply define the struct in an appropriate way based on the alignment requirements of the target architecture.

Generally: define the fields in the order of the size of their basic type. The first field will naturally have proper alignment, and all following fields will also get proper alignment if their natural size is not larger than their preceding field.

This structure should contain no padding, except possibly at the end:

typedef struct {
    long double f1;
    double f2;
    long long i1;
    float f3;
    long i2;
    int i3;
    short i4;
    char s1[3];
} MyStruct;
#define MYTEST() (assert(sizeof(MyStruct) == 48)

And then invoke MYTEST() at the beginning of the test program, since the 48 and the appropriate order might change from one architecture to another.

Or even simpler:

#include <static.h>
…
} Mystruct;
static_assert(sizeof(MyStruct) == 48);

and the test will be done at compile time.

Answer 5

I see no harm in including this as an optional feature, but be aware of performance issues that could be caused using this.

Many processors do not support many operations on non-aligned data. For example, adding 1 to a misaligned int a may involve something like this:

• Load the aligned section containing the first half of the number into one register
• Load the aligned series of bytes containing the second half into another register
• Bit shift each register so it contains only the parts corresponding to the number you want to edit
• Use bitwise OR to combine them into one number
• Add 1
• Use AND with a mask to separate it into 2 halves again
• Shift them back into their original position
• Mask the part of each section you do not want to modify and OR it
• Write each half back to its aligned memory slot

While on the other hand if the data is aligned you can just add 1 in one step, overall easily 10x faster. Even on processor architectures that do support unaligned load and store, it will be slower, though not by quite as much.

Of course there are good reasons a developer might want to use it, like a large list of data that is rarely accessed. This should not be default, though, and you should warn developers about its use.

There is also a precedent; Rust has #[repr(packed)] which isn't quite what you are suggesting but serves much the same purpose.

Answer 6

More useful than a packed keyword would be a more general means of specifying that a blob of memory should be treated as a structure with a precisely-specified layout which might be relied upon by outside code. Code which repeatedly assesses data items within such a structure would generally be slower than code which converts a structure's contents to an implementation's "native" numeric formats, manipulates them, and converts them back, but if it's only necessary to manipulate a small portion of the data structure, the overhead of performing such manipulation "in place" may be less than the cost of performing a round-trip conversion on the entire structure. Note that even if a field uses a format inconsistent with a platform's normal numeric formatting (e.g. a big-endian field on a little-endian platform), it would be easier for an implementation given e.g. thingie.woozle++;, where woozle is a 32-bit big-endian value at offset 38 of a word-aligned structure, to generate efficient machine code to handle that task than to generate equally-good machine code for all of the ways programmers might try to accomplish that task without such a language feature.

Although situations in which the space savings of using a packed data structure would be relevant are rare, situations where it would be useful to treat a blob of data which is formatted to fit the needs of some outside code using the same syntax as native-format data are much more common, and a language which is intended to facilitate the writing of portable programs should include features to work with octet-based data in precisely-specified formats. Note that such features would be especially useful on implementations that don't use octet-based storage, since it would allow non-octet-based platforms to exchange information with octet-based systems using information-interchange code written for octet-based platforms.

Answer 7

For precedent, Microsoft's compiler has a pragma for that: #pragma pack():

To pack a class is to place its members directly after each other in memory. It can mean that some or all members can be aligned on a boundary smaller than the default alignment of the target architecture. [...] If you change the alignment of a structure, it may not use as much space in memory. However, you may see a loss of performance or even get a hardware-generated exception for unaligned access.

Also, R. Chen wrote a page about #pragma pack, packed with good insight and examples of generated code (pun forced). For example:

Changing the default structure packing has another consequence: It changes the alignment of the structure itself. In this case, the #pragma pack(1) declares that the structure P can itself be placed at any byte boundary, instead of requiring it to be placed on a 4-byte boundary.

Some other compilers also have or had similar pragmas. GCC also has __attribute__ ((__packed__)).