Why can't C compilers rearrange struct members to eliminate alignment padding? [duplicate]

Question

Possible Duplicate:
Why doesn't GCC optimize structs?
Why doesn't C++ make the structure tighter?

Consider the following example on a 32 bit x86 machine:

Due to alignment constraints, the following struct

struct s1 {
    char a;
    int b;
    char c;
    char d;
    char e;
}

could be represented more memory-efficiently (12 vs. 8 bytes) if the members were reordered as in

struct s2 {
    int b;
    char a;
    char c;
    char d;
    char e;
}

I know that C/C++ compilers are not allowed to do this. My question is why the language was designed this way. After all, we may end up wasting vast amounts of memory, and references such as struct_ref->b would not care about the difference.

EDIT: Thank you all for your extremely useful answers. You explain very well why rearranging doesn't work because of the way the language was designed. However, it makes me think: Would these arguments would still hold if rearrangement was part of the language? Let's say that there was some specified rearrangement rule, from which we required at least that

1. we should only reorganize the struct if actually necessary (don't do anything if the struct is already "tight")
2. the rule only looks at the definition of the struct, not inside inner structs. This ensures that a struct type has the same layout whether or not it is internal in another structure
3. the compiled memory layout of a given struct is predictable given its definition (that is, the rule is fixed)

Adressing your arguments one by one I reason:

• Low-level data mapping, "element of least surprise": Just write your structs in a tight style yourself (like in @Perry's answer) and nothing has changed (requirement 1). If, for some weird reason, you want internal padding to be there, you could insert it manually using dummy variables, and/or there could be keywords/directives.

• Compiler differences: Requirement 3 eliminates this concern. Actually, from @David Heffernan's comments, it seems that we have this problem today because different compilers pad differently?

• Optimization: The whole point of reordering is (memory) optimization. I see lots of potential here. We may not be able to remove padding all together, but I don't see how reordering could limit optimization in any way.

• Type casting: It seems to me that this is the biggest problem. Still, there should be ways around this. Since the rules are fixed in the language, the compiler is able to figure out how the members were reordered, and react accordingly. As mentioned above, it will always be possible to prevent reordering in the cases where you want complete control. Also, requirement 2 ensures that type-safe code will never break.

The reason I think such a rule could make sense is because I find it more natural to group struct members by their contents than by their types. Also it is easier for the compiler to choose the best ordering than it is for me when I have a lot of inner structs. The optimal layout may even be one that I cannot express in a type-safe way. On the other hand, it would appear to make the language more complicated, which is of course a drawback.

Note that I am not talking about changing the language - only if it could(/should) have been designed differently.

I know my question is hypothetical, but I think the discussion provides deeper insight in the lower levels of the machine and language design.

I'm quite new here, so I don't know if I should spawn a new question for this. Please tell me if this is the case.

Babbitt

@Joe That's a different question. This question is about why the C and C++ standards specify that members appear in the order in which they are declared. – Felizio

If I had to guess (and since I don't know, I will have to guess), I'd say that the first C compilers layed out members in order of declaration because that was the simplest thing to do. In due course, compilers will have been written that aligned members. And then when it came time to standardise, the standardisation body realised that there was lots of extant code that assumed that members appeared in declaration order. And so that had better be written into the standard. Remember that the language existed long before the standard. – Felizio

I am not so sure about your assertion that C++ doesn't allow reordering in general. (The case here is more specific, it shouldn't be allowed in any case.) – Keefer

@jens C++ does allow reordering for non PODs – Felizio

@David, thanks, that's what I thought. And also even C allows the reordering of bit fields if they are part of the same storage component (don't remember the exact term). – Keefer

The C standard specifies that when two structs are included in a union and the initial 'n' elements in source-code order match, those elements must be aliased cleanly. There might be some way by which a compiler could reorder elements while still complying with that rule, but it would seem rather complicated at best. – Sepulcher

This probably isn't enough for a full answer, but the simplest explanation is: They wanted to give the programmer the freedom to lay structs out in both efficient and inefficient manners, depending on which is better for the task at hand, without having to mess around with compiler settings or directives to do so. If automatic reordering was ever added to the standard, it would have to be opt-in instead of opt-out, likely with a standardised preprocessor directive (perhaps #realign x or #realign(x), where x is an integer value indicating the desired bit alignment). – Catapult

Additionally, it would have to be on a per-struct basis, with the directive specified for each struct that needs automatic realignment. [Additionally, either the compiler would be explicitly required to parse the entire struct before it begins working on it, or the preprocessor directive would have to be placed at the start of the struct definition, before any members are listed.] – Catapult

One point I would like to make along the lines of 'trust the programmer' concerns (i) large reads, and (ii) cache hotness. If you let the programmer control the order of fields, then most-frequently-accessed 'hot' fields can be put in a suitable place, and kept together to maximise hotness and relatively cold fields can be parked out of the way so they don't spoil hotness by separating hot small objects – Dexter

Sorting by hand can keep related hot fields next to one another so that a read of one field makes a subsequent read of a second field be a cache hit. As for small fields, a read on one may bring in a cache line so that temporally close accesses of related fields are already fetched. For the very smallest fields, fetching a field that is only a very few bytes wide will presumably mean that the whole containing machine word (at least) actually gets fetched, so you are in fact getting other fields pre-fetched for you for free into very close ultra-high-speed internal small buffers. – Dexter

Answer 1

There are multiple reasons why the C compiler cannot automatically reorder the fields:

• The C compiler doesn't know whether the struct represents the memory structure of objects beyond the current compilation unit (for example: a foreign library, a file on disc, network data, CPU page tables, ...). In such a case the binary structure of data is also defined in a place inaccessible to the compiler, so reordering the struct fields would create a data type that is inconsistent with the other definitions. For example, the header of a file in a ZIP file contains multiple misaligned 32-bit fields. Reordering the fields would make it impossible for C code to directly read or write the header (assuming the ZIP implementation would like to access the data directly):

  struct __attribute__((__packed__)) LocalFileHeader {
      uint32_t signature;
      uint16_t minVersion, flag, method, modTime, modDate;
      uint32_t crc32, compressedSize, uncompressedSize;
      uint16_t nameLength, extraLength;
  };
  

  The packed attribute prevents the compiler from aligning the fields according to their natural alignment, and it has no relation to the problem of field ordering. It would be possible to reorder the fields of LocalFileHeader so that the structure has both minimal size and has all fields aligned to their natural alignment. However, the compiler cannot choose to reorder the fields because it does not know that the struct is actually defined by the ZIP file specification.

• C is an unsafe language. The C compiler doesn't know whether the data will be accessed via a different type than the one seen by the compiler, for example:

  struct S {
      char a;
      int b;
      char c;
  };
  
  struct S_head {
      char a;
  };
  
  struct S_ext {
      char a;
      int b;
      char c;
      int d;
      char e;
  };
  
  struct S s;
  struct S_head *head = (struct S_head*)&s;
  fn1(head);
  
  struct S_ext ext;
  struct S *sp = (struct S*)&ext;
  fn2(sp);
  

  This is a widely used low-level programming pattern, especially if the header contains the type ID of data located just beyond the header.

• If a struct type is embedded in another struct type, it is impossible to inline the inner struct:

  struct S {
      char a;
      int b;
      char c, d, e;
  };
  
  struct T {
      char a;
      struct S s; // Cannot inline S into T, 's' has to be compact in memory
      char b;
  };
  

  This also means that moving some fields from S to a separate struct disables some optimizations:

  // Cannot fully optimize S
  struct BC { int b; char c; };
  struct S {
      char a;
      struct BC bc;
      char d, e;
  };
  

• Because most C compilers are optimizing compilers, reordering struct fields would require new optimizations to be implemented. It is questionable whether those optimizations would be able to do better than what programmers are able to write. Designing data structures by hand is much less time consuming than other compiler tasks such as register allocation, function inlining, constant folding, transformation of a switch statement into binary search, etc. Thus the benefits to be gained by allowing the compiler to optimize data structures appear to be less tangible than traditional compiler optimizations.

Andalusia

I accept type casting argument. However I'm not sure I see the problems with optimization. I was just thinking that the compiler could treat the struct exactly as if I had written it in ordered form myself. Sure there are cases where we cannot compact completely, but this is the case anyway. Also, regarding your first argument: If the standard required a specific reordering, would this argument still hold? One could say that when you write a struct to represent some external data, you should be aware of reordering and choose your types accordingly. – Babbitt

+1 for the first point: @HalleKnast - One example is reading a blob of data and casting it to a struct type. The order of the elements in the struct will matter in that case. – Golgi

@HalleKnast Another live example would be Perry's answer – Golgi

@Atom can you please expand on your first bullet point? Possibly an example? Thanks! – Crum

Of these four reasons, only the second one makes any sense, but the reason is not "C is an unsafe language" but that the standard specifically supports that behavior as a means of poor man's subtyping. The fourth reason implies this would be a difficult optimization, which it wouldn't. The first and third reasons say that you can't reorder in certain cases, which is true, but doesn't mean you can't reorder in other cases. – Adabelle

Answer 2

C is designed and intended to make it possible to write non-portable hardware and format dependent code in a high level language. Rearrangement of structure contents behind the back of the programmer would destroy that ability.

Observe this actual code from NetBSD's ip.h:

/*
 * Structure of an internet header, naked of options.
 */
struct ip {
#if BYTE_ORDER == LITTLE_ENDIAN
    unsigned int ip_hl:4,       /* header length */
             ip_v:4;        /* version */
#endif
#if BYTE_ORDER == BIG_ENDIAN
    unsigned int ip_v:4,        /* version */
             ip_hl:4;       /* header length */
#endif
    u_int8_t  ip_tos;       /* type of service */
    u_int16_t ip_len;       /* total length */
    u_int16_t ip_id;        /* identification */
    u_int16_t ip_off;       /* fragment offset field */
    u_int8_t  ip_ttl;       /* time to live */
    u_int8_t  ip_p;         /* protocol */
    u_int16_t ip_sum;       /* checksum */
    struct    in_addr ip_src, ip_dst; /* source and dest address */
} __packed;

That structure is identical in layout to the header of an IP datagram. It is used to directly interpret blobs of memory blatted in by an ethernet controller as IP datagram headers. Imagine if the compiler arbitrarily re-arranged the contents out from under the author -- it would be a disaster.

And yes, it isn't precisely portable (and there's even a non-portable gcc directive given there via the __packed macro) but that's not the point. C is specifically designed to make it possible to write non-portable high level code for driving hardware. That's its function in life.

Adjunct

If this were the problem, they'd just add a __no_reorder compiler extension, or just have __packed imply it. The C standard doesn't support this, as you note; why would the standard support the no-reordering part while leaving the no-padding part up to each implementation? There is a reason the standard doesn't allow reordering, but it isn't this. It's the common-initial-sequence rule. – Adabelle

Answer 3

Not being a member of WG14, I can't say anything definitive, but I have my own ideas:

1. It would violate the principle of least surprise - there may be a damned good reason why I want to lay my elements out in a specific order, regardless of whether or not it's the most space-efficient, and I would not want the compiler to rearrange those elements;

2. It has the potential to break a non-trivial amount of existing code - there's a lot of legacy code out there that relies on things like the address of the struct being the same as the address of the first member (saw a lot of classic MacOS code that made that assumption);

The C99 Rationale directly addresses the second point ("Existing code is important, existing implementations are not") and indirectly addresses the first ("Trust the programmer").

Multure

I think your point #2 (the address of a struct being the same as the one of its first member) is the only reason among all the ones given in all the answers to this question and the linked-to related questions that sounds to me like a real reason. (As many people have pointed out, padding in order to satisfy alignment constraints is definitely not portable.) – Sebi

Answer 4

C [and C++] are regarded as systems programming languages so they provide low level access to the hardware, e.g., memory by means of pointers. Programmer can access a data chunk and cast it to a structure and access various members [easily].

Another example is a struct like the one below, which stores variable sized data.

struct {
  uint32_t data_size;
  uint8_t  data[1]; // this has to be the last member
} _vv_a;

Upstanding

forget files, structs can be mapped to actual hardware registers/addresses. Its not quite possible for the compiler to move silicon around to suit. – Latham

I think the pointers to HW is the best argument against, but it would be nice to turn off – Supplement

Is that actually defined by the standard, or is it technically "undefined behaviour" that seems to work conveniently with most compilers? – Impressure

For this to work, there has to be no reordering and no padding and the compiler has to allow out-of-range accesses of the data array. The standard only mandates the first of the three. If the no-reordering rule was meant to support this use, why didn't they add the rest of the support? There is a reason the standard doesn't allow reordering, but it isn't this. It's the common-initial-sequence rule. – Adabelle

Answer 5

It would change the semantics of pointer operations to reorder the structure members. If you care about compact memory representation, it's your responsibility as a programmer to know your target architecture, and organize your structures accordingly.

Gaussmeter

"It would change the semantics of pointer operations to reorder the structure members." I don't know what you mean. Could you elaborate. Remember that the question is why the language was designed the way it is and so a good answer has to give language design motivations. – Felizio

@DavidHeffernan I think he means the reorder would change the pointer offsets, but it seems to me that the compiler could easily handle that since it's doing the reordering. – Supplement

@DavidHeffernan You're allowed to, for example, cast and then dereference a pointer to get access to the first member of the struct. If the compiler were to reorder them, this would give bad results. – Beatabeaten

@aaron the language designers could have banned that. The question is about the design of the language and not its current state. – Felizio

Upvoted for "organize your structures accordingly" as one can manually do this in cases where it matters. I've done it. – Cantabrigian

@DavidHeffernan: and the language designers consider it a good idea to let you do that -- probably because one of the most common things to put into any struct is a pointer to another struct, giving you simple syntax for checking to see if the pointer was null. – Christeenchristel

@AaronDufour: More notably, one can use memcpy to copy all portions of a struct that precede a given element without disturbing any elements that follow. – Sepulcher

Answer 6

If you were reading/writing binary data to/from C structures, reordering of the struct members would be a disaster. There would be no practical way to actually populate the structure from a buffer, for example.

Stowaway

But the C standard does not say anything about packing and alignment which it would need to if you wanted to do what you describe. In other words, I can't believe that mapping of structs onto binary files in a portable way can have been a motivating factor in the language design. – Felizio

Actually, given that C was designed as a systems language -- and this sort of work is typical of network and or file based i/o -- I'm pretty sure this is exactly the sort of thing that motivated the language design. – Stowaway

Well I thought that, but if C compilers are free to add whatever padding they see fit, that would completely scupper such programming techniques. – Felizio

You're making a mistake here. Sure, you can't map structs onto binary data in a portable manner, but C is designed to be useful for producing nonportable code like embedded systems software, device drivers, etc., where the nonportability is not an issue and using a high level language is precisely the point. – Adjunct

Answer 7

Keep in mind that a variable declaration, such as a struct, is designed to be a "public" representation of the variable. It's used not only by your compiler, but is also available to other compilers as representing that data type. It will probably end up in a .h file. Therefore, if a compiler is going to take liberties with the way the members within a struct are organized, then ALL compilers have to be able to follow the same rules. Otherwise, as has been mentioned, the pointer arithmetic will get confused between different compilers.

Harelip

But different compilers lay out the same struct in different ways due to alignment differences. And then there can be differences in the size of data types, e.g. int can differ in size on different compilers. – Felizio

Which is exactly my point. If two pieces of code need to share access to a struct (either in memory or in a binary file format), then both compilers need to agree on the internal representation of the struct. Different compilers will do this differently, especially based on the host operating system, but they then allow you to override this using #pragma pack. – Harelip

Answer 8

Structs are used to represent physical hardware at the very lowest levels. As such the compiler cannot move things a round to suit at that level.

However it would not be unreasonable to have a #pragma that let the compiler re-arrange purely memory based structs that are only used internally to the program. However I don't know of such a beast (but that doesn't meant squat - I'm out of touch with C/C++)

Latham

Answer 9

Your case is very specific as it would require the first element of a struct to be put re-ordered. This is not possible, since the element that is defined first in a struct must always be at offset 0. A lot of (bogus) code would break if this would be allowed.

More generally pointers of subobjects that live inside the same bigger object must always allow for pointer comparison. I can imagine that some code that uses this feature would break if you'd invert the order. And for that comparison the knowledge of the compiler at the point of definition wouldn't help: a pointer to a subobject doesn't have a "mark" do which larger object it belongs. When passed to another function just as such, all information of a possible context is lost.

Keefer

Answer 10

Here's a reason I didn't see so far - without standard rearrangement rules, it would break compatibility between source files.

Suppose a struct is defined in a header file, and used in two files.
Both files are compiled separately, and later linked. Compilation may be at different times (maybe you touched just one, so it had to be recompiled), possibly on different computers (if the files are on a network drive) or even different compiler versions.
If at one time, the compiler would decide to reorder, and at another it won't, the two files won't agree on where the fields are.

As an example, think of the stat system call and struct stat.
When you install Linux (for example), you get libC, which includes stat, which was compiled by someone sometime.
You then compile an application with your compiler, with your optimization flags, and expect both to agree on the struct's layout.

Bourn

Different padding can give the same effect. However, it is easier to specify padding rules than putative reordering rules. – Felizio

Answer 11

suppose you have a header a.h with

struct s1 {
    char a;
    int b;
    char c;
    char d;
    char e;
}

and this is part of a separate library (of which you only have the compiled binaries compiled by a unknown compiler) and you wish to use this struct to communicate with this library,

if the compiler is allowed to reorder the members in whichever way it pleases this will be impossible as the client compiler doesn't know whether to use the struct as-is or optimized (and then does b go in front or in the back) or even fully padded with every member aligned on 4 byte intervals

to solve this you can define a deterministic algorithm for compacting but that requires all compilers to implement it and that the algorithm is a good one (in terms of efficiency). it is easier to just agree on padding rules than it is on reordering

it is easy to add a #pragma that prohibits the optimization for when you need the layout of to a specific struct be exactly what you need so that is no issue

Flirt

I don't think that would be a problem, if the rule were that putting particular set of elements in a structure in a particular order must always yield the same arrangement but the implementation could use whatever arrangement it favors (e.g. all bytes first, then all halfwords, etc.). On the other hand, I don't know how anything other than an in-order requirement could satisfy the "union" rule which says that if a union contains two structs, and the first n fields, in source code order, are identical, they will be aliased cleanly. – Sepulcher

The "union" rule would work if the compiler assigns an offset to each member as they are defined, without looking at later members, but moves later members into gaps. For example, if your struct members are 1, 4, 2, 1 bytes in that order, the compiler could assign them to offsets 0, 4, 2, 1. – Emmalynn