Struct Reordering by compiler [duplicate]

Question

Suppose I have a struct like this:

struct MyStruct
{
  uint8_t var0;
  uint32_t var1;
  uint8_t var2;
  uint8_t var3;
  uint8_t var4;
};

This is possibly going to waste a bunch (well not a ton) of space. This is because of necessary alignment of the uint32_t variable.

In actuality (after aligning the structure so that it can actually use the uint32_t variable) it might look something like this:

struct MyStruct
{
  uint8_t var0;
  uint8_t unused[3];  //3 bytes of wasted space
  uint32_t var1;
  uint8_t var2;
  uint8_t var3;
  uint8_t var4;
};

A more efficient struct would be:

struct MyStruct
{
  uint8_t var0;
  uint8_t var2;
  uint8_t var3;
  uint8_t var4;
  uint32_t var1;
};

Now, the question is:

Why is the compiler forbidden (by the standard) from reordering the struct?

I don't see any way you could shoot your self in the foot if the struct was reordered.

Scoff

For a start, the reordering would need to be "deterministic" and published as part of the toolchain's ABI. – Vanburen

Serialization? You streamed out a struct to a file, then recompiled, and tried to stream it back in. If a compiler were allowed to re-order the members, what would the result be? – Aronarondel

@Aronarondel - that's dangerous anyway, in general (without using platform-specific packing pragmas, etc.) – Vanburen

@Aronarondel As far as I understood that already could change (unless it was packed, which is not supported by the standard) – Scoff

I don't know why the standard explicitly forbids reordering. But even if it didn't compilers still couldn't do it as it would require the compiler to be omniscient. (Remember, it is legal to access a structure through a pointer to a structure of a compatible, but not identical, type.) – Bhopal

I am doomed if that structure was my protocol header struct. – Turnout

@OliverCharlesworth: Alignment is part of the language specification (see e.g. alignas). Of course, the binary representation isn't specified, so you have to make sure that all competing parties agree. That, too, is a solvable challenge. – Aronarondel

@Aronarondel - Didn't notice this was also tagged as C++! But that's conceptually the same as pragmas and other magic - the point being that in situations where you care about bitwise layout, you'd already be explicitly controlling it (which presumably doesn't apply to the OP's question, which seems to be about scenarios where you (the programmer) don't care about the layout). – Vanburen

Side note: generally, ordering members from largest to smallest (in size) is better than from smallest to largest. – Pickings

Looks like gcc tried this but failed: #14671753 – Cryptoanalysis

@MarcinJędrzejewski: Good find. Probably worth an answer based around that. – Liturgical

Note that gcc and clang support the -Wpadded warning, which will tell you if your struct has extra padding in the middle. – Shortly

Eric Raymond says, in The Lost Art of C Structure Packing that "C is a language originally designed for writing operating systems and other code close to the hardware. Automatic reordering would interfere with a systems programmer’s ability to lay out structures that exactly match the byte and bit-level layout of memory-mapped device control blocks." – Goodman

Worth noting that in C++, the compiler can reorder members, to a certain degree. – Spoilt

Answer 1

Why is the compiler forbidden (by the standard) from reordering the struct?

The basic reason is: for compatibility with C.

Remember that C is, originally, a high-level assembly language. It is quite common in C to view memory (network packets, ...) by reinterpreting the bytes as a specific struct.

This has led to multiple features relying on this property:

• C guaranteed that the address of a struct and the address of its first data member are one and the same, so C++ does too (in the absence of virtual inheritance/methods).

• C guaranteed that if you have two struct A and B and both start with a data member char followed by a data member int (and whatever after), then when you put them in a union you can write the B member and read the char and int through its A member, so C++ does too: Standard Layout.

The latter is extremely broad, and completely prevents any re-ordering of data members for most struct (or class).

---

Note that the Standard does allow some re-ordering: since C did not have the concept of access control, C++ specifies that the relative order of two data members with a different access control specifier is unspecified.

As far as I know, no compiler attempts to take advantage of it; but they could in theory.

Outside of C++, languages such as Rust allow compilers to re-order fields and the main Rust compiler (rustc) does so by default. Only historical decisions and a strong desire for backward compatibility prevent C++ from doing so.

Nevski

Some good points here. Reminds me that ordering can differ between compilation runs if you change the value of the -std flag ;) – Liturgical

Answer 2

I don't see any way you could shoot your self in the foot, if the struct was reordered.

Really? If this were permitted, communication between libraries/modules even in the same process would be ludicrously dangerous by default.

"In universe" argument

We must be able to know that our structs are defined the way that we've asked them to be. It's bad enough that padding is unspecified! Fortunately, you can control this when you need to.

Okay, theoretically, a new language could be made such that, similarly, members were re-orderable unless some attribute were given. After all, we're not supposed to do memory-level magic on objects so if one were to use only C++ idioms, you'd be safe by default.

But that's not the practical reality in which we live.

---

"Out of universe" argument

You could make things safe if, in your words, "the same reorder was used every time". The language would have to state unambiguously how members would be ordered. That's complicated to write in the standard, complicated to understand, and complicated to implement.

It's much easier to just guarantee that the order will be as it is in code, and leave these decisions to the programmer. Remember, these rules have origin in old C, and old C gives power to the programmer.

You've already shown in your question how easy it is to make the struct padding-efficient with a trivial code change. There's no need for any added complexity at the language level to do this for you.

Liturgical

Not if the same reorder was used every time..... – Scoff

@DarthRubik: And how do you enforce every run of every compiler using the same order every time? Oh, that's right, by leaving it as the programmer wrote it lol – Liturgical

Communication between libraries/modules within the same process would be ludicrously dangerous. – Vanburen

@OliverCharlesworth: Yep, good point - stolen :) – Liturgical

@LightnessRacesinOrbit Well, in his example it was easy to make. One can easily imagine examples in which it is not so easy to make, especially in code meant to be portable to platforms with different object sizes and alignment requirements. It could also make the code harder to understand and document, as you couldn't group members by function. – Bhopal

@DavidSchwartz: Granted. I guess I'd support the addition of an attribute to permit re-ordering, but it could not be on by default. – Liturgical

@Scoff You will have to describe an algorithm whch will, given sizes and aligment element of sequence, deterministacally transform their order, so size of final object will be minimal. This smells like packing problem and it might or not be NP-hard. – Ice

@Ice A platform could, as part of its ABI, specify a simple, deterministic reordering scheme that got a significant fraction of packing benefit for minimal cost. For example, just stably sorting objects by size (largest first) would do. – Bhopal

@DavidSchwartz It would just defer question further: "why compiler does not reorder elements in this case where better order is obvious". Idea of specific attribute which will allow compler to reorder members is good though. – Ice

The Language does not have to specify padding or order for compatibility across modules; this handled by the ABI, much like function calls are. – Nevski

Seems more fit for a warning like "misaligned struct" than something automatic. – Roll

@Revolver_Ocelot: How would that defer the question further? He's talking about doing the packing, not omitting it. And when you do the packing, the question of "Why doesn't it do the packing?" no longer exists. It is not deferred, it is gone. Protocol-related issues could be resolved via a keyword (e.g. unpacked struct { ... } or similar). For modern C++, the opposite keyword would of course be needed, because of backwards compatibility. – Cowherb

@TimČas there is no packing mentioned anywhere. We are talking about automatic reordering of struct elements to minimise amount of padding due to size/aligment requirements of adjanced members. Perfect reordering might not be possible/feasimle to calculate (it looks too similar to packing problem), imperfect reordering would just change title of question from "why compiler don't optimise" to "why compiler don't optimise better" – Ice

@Revolver_Ocelot: I know what you're talking about. And how is this similar to the packing problem? Just do a stable sort, and done. This can be done in linear time with a counting sort. – Cowherb

@TimČas Sort on what criteria? How would it take into account that both 1-byte members with 16-byte alignment and 16-byte members without any alignment restriction can exist? (and any other combination of size/alignment) – Ice

@Revolver_Ocelot: You sort by alignment. The former cannot exist, because 16-byte alignment immediately means at least a 16-byte size, (because of arrays). Even assuming they existed (e.g. for some sort of advanced optimization, though then you'd run into some OOP-related issues), you could use a hole-filling algorithm. I've implemented it before, it's not rocket science. As for the latter case, that's easy: you put it exactly where you'd put a 1-byte member without alignment restriction (the only difference is that you allocate 15 bytes more space for it). – Cowherb

Answer 3

The standard guarantees an allocation order simply because structs may represent a certain memory layout, such as a data protocol or a collection of hardware registers. For example, neither the programmer nor the compiler is free to re-arrange the order of the bytes in the TPC/IP protocol, or the hardware registers of a microcontroller.

If the order was not guaranteed, structs would be mere, abstract data containers (similar to C++ vector), of which we can't assume much, except that they somehow contain the data we put inside them. It would make them substantially more useless when doing any form of low-level programming.

Natatorial

But doesn't this violate the basic "don't pay for what you don't use" maxim? Surely such cases are in the minority and the benefits of less memory consumption and less memory bandwidth usage are not tiny. This is a good argument for a keyword to avoid reordering but not for never reordering. – Bhopal

@DavidSchwartz Well... structs are a half-hearted attempt to suit everyone, hardware programmers as well as CPUs with alignment. They would be far more useful and portable if struct padding was not handled automatically by the compiler. I suppose two different data types: "strict struct" and "i dont care struct" would have been very handy. Kind of like uint8_t versus uint_fast8_t. – Natatorial

So maybe it was because you sometimes need structs whose order is preserved and there never seemed to be a good enough reason to specifying two different types of structs in the standard? – Bhopal

@DavidSchwartz These days, if you really need tighter memory usage then you're almost certainly working on an embedded platform, because memory usage at this kind of level hasn't really been a serious consideration on PCs for a couple of decades. If you're working on embedded stuff, it's pretty much inevitable that you know about these kind of issues and are able to sort it out yourself - and if you don't then it's high time you did. So the only people this would help would be less-competent novice embedded coders, and on the scale of challenges they face, I think this is pretty small beer. – Spurge

@Spurge The issue with struct member ordering and padding is not memory use, but that it can cause a struct not to replicate the intended data protocol/hardware registers it should represent. A struct with both fixed order and no padding would help everyone. Today we have to resort to non-standard C like #pragma pack etc to make this work. – Natatorial

@DavidSchwartz I wouldn't say it's the minority case at all. Most C programmers I've dealt with assume the structures have a fixed in-memory layout, and exploit it to full benefit - most importantly, for replacing serialization with a simple cast. For example, the original Warcraft made a save game by copying the entire game state from memory to file in a single write (and vice versa for loading). We're talking about C here - it's a glorified assembly language with improved portability. But even in C# (a managed language), this rule holds by default - to simplify interop. – Nies

@Natatorial Memory use is the angle the OP was coming from. I agree that silently padding structures could be an issue for protocols too, although it's unlikely to be an issue for hardware registers because those are typically the size of the processor word length and so are word-boundary-aligned. But again, that's down in embedded code (or at least driver code) and that's not a mission for a novice programmer. I can see the benefit of it being available, but equally anyone likely to need it will also know how to sort it themselves. – Spurge

Answer 4

The compiler should keep the order of its members in the case the structures are read by any other low-level code produced by another compiler or another language. Say you were creating an operating system, and you decide to write part of it in C, and part of it in assembly. You could define the following structure:

struct keyboard_input
{
    uint8_t modifiers;
    uint32_t scancode;
}

You pass this to an assembly routine, where you need to manually specify the memory layout of the structure. You would expect to be able to write the following code on a system with 4-byte alignment.

; The memory location of the structure is located in ebx in this example
mov al, [ebx]
mov edx, [ebx+4]

Now say the compiler would change the order of the members in the structure in an implementation defined way, this would mean that depending on the compiler you use and the flags you pass to it, you could either end up with the first byte of the scancode member in al, or with the modifiers member.

Of course the problem is not just reduced to low-level interfaces with assembly routines, but would also appear if libraries built with different compilers would call each other (e.g. building a program with mingw using the windows API).

Because of this, the language just forces you to think about the structure layout.

Calotte

This doesn't make sense. The standards doesn't require enough to guarantee this. For example, it permits the padding to change based on what compiler you use and what flags you pass to it. So this doesn't explain why reordering specifically is prohibited. – Bhopal

Hence the system with 4-byte alignment. It would be a system where all members of data structures are padded to start on a 4-byte boundary, which is rather common on 32-bit systems. – Calotte

@DavidSchwartz Yes, but that doesn't matter - padding is a thing of the system, and when you're writing assembly, you're coding to the system already. And don't think there aren't plenty of people who are annoyed by the automatic packing either ;) – Nies

Answer 5

Remember that not only automatic re-ordering of the elements to improve packing can work in detriment of specific memory layouts or binary serialization, but the order of the properties may have been carefully chosen by the programmer to benefit cache-locality of frequently used members against the more rarely accessed.

Stiff

Answer 6

The language designed by Dennis Ritchie defined the semantics of structures not in terms of behavior, but in terms of memory layout. If a structure S had a member M of type T at offset X, then the behavior of M.S was defined as taking the address of S, adding X bytes to it, interpreting it as a pointer to T, and interpreting the storage identified thereby as an lvalue. Writing a structure member would change the contents of its associated storage, and changing the contents of a member's storage would change the value of a member. Code was free to use a wide variety of ways of manipulating the storage associated with structure members, and the semantics would be defined in terms of operations on that storage.

Among the useful ways that code could manipulate the storage associated with a structure was the use of memcpy() to copy an arbitrary portion of one structure to a corresponding portion of another, or memset() to clear an arbitrary portion of a structure. Since structure members were laid out sequentially, a range of members could be copied or cleared using a single memcpy() or memset() call.

The language defined by the Standard Committee eliminates in many cases the requirement that changes to structure members must affect the underlying storage, or that changes to the storage affect the member values, making guarantees about structure layout less useful than they had been in Ritchie's language. Nonetheless, the ability to use memcpy() and memset() was retained, and retaining that ability required keeping structure elements sequential.

Knudsen

Answer 7

You also quote C++, so I'll give you a practical reasons why that can't happen.

Given there's no difference between class and struct, consider:

class MyClass
{
    string s;
    anotherObject b;

    MyClass() : s{"hello"}, b{s} 
    {}

};

Now C++ requires non-static data members to be initialized in the order they were declared:

— Then, non-static data members are initialized in the order they were declared in the class definition

as per [base.class.init/13]. So the compiler cannot reorder fields within the class definition, because otherwise (as an example) members depending on the initialization of others couldn't work.

The compiler isn't strictly required not reorder them in memory (for what I can say) — but, especially considering the example above, it would be terribly painful to keep track of that. And I doubt of any performance improvements, unlike padding.

Merrimerriam

[C++11: 9.2/14]: Nonstatic data members of a (non-union) class with the same access control (Clause 11) are allocated so that later members have higher addresses within a class object. (my emphasis) – Circuity

Surely initialisation order is independent of physical layout. – Tillietillinger

@Jeremy: It's not "sure". It actually is an immediate consequence, as I explain in my answer (if it's a bit unclear, I'll try to clarify it). – Merrimerriam

Please do clarify. – Tillietillinger

What do you mean by "The compiler isn't strictly required not reorder them in memory (for what I can say)"? Can you clarify that? – Oust

Answer 8

Imagine this struct layout is actually a memory sequence received 'over the wire', say an Ethernet packet. if the compiler re-aligned things to be more efficient, then you would have to do loads of work pulling out bytes in the required order, rather than just using a struct which has all the correct bytes in the correct order and place.

Enthusiasm

That's dangerous anyway, in general (without using platform-specific packing pragmas, etc. at both ends of the wire). – Vanburen

@OliverCharlesworth yup, but if you're on an embedded processor with limited ram/rom, it's potentially the only way to go ! – Enthusiasm

Agreed. But the point is that in that scenario, you should already be explicitly controlling the struct layout. – Vanburen