What is there to be gained by deterministic field ordering in the memory layout?

Question

Members of a structure are allocated within the structure in the order of their appearance in the declaration and have ascending addresses.

I am faced with the following dilemma: when I need to declare a structure, do I

(1) group the fields logically, or

(2) in decreasing size order, to save RAM and ROM size?

Here is an example, where the largest data member should be at the top, but also should be grouped with the logically-connected colour:

struct pixel{
    int posX;
    int posY;

    tLargeType ColourSpaceSecretFormula;
    char colourRGB[3];
}

The padding of a structure is non-deterministic (that is, is implementation-dependent), so we cannot reliably do pointer arithmetic on structure elements (and we shouldn't: imagine someone reordering the fields to his liking: BOOM, the whole code stops working).

-fpack-structs solves this in gcc, but bears other limitations, so let's leave compiler options out of the question.

On the other hand, code should be, above all, readable. Micro optimizations are to be avoided at all cost.

So, I wonder, why are structures' members ordered by the standard, making me worry about the micro-optimization of ordering struct member in a specific way?

You don't have a dilemma until you have a problem. Looks like you're trying to optimize something without having a clear goal (in a form of requirement, perhaps) and without knowing how far you are from it and without knowing what direction to move to reach it. — Alexey Frunze, Apr 25 '13 at 12:33

score 3 · Accepted Answer · answered Apr 25 '13 at 12:55

3

The compiler is limited by several traditional and practical limitations.

The pointer to the struct after a cast (the standard calls it "suitably converted") will be equal to the pointer to the first element of the struct. This has often been used to implement overloading of messages in message passing. In that case a struct has the first element that describes what type and size the rest of the struct is.

The last element can be a dynamically resized array. Even before official language support this has been often used in practice. You allocate sizeof(struct) + length of extra data and can access the last element as a normal array with as many elements that you allocated.

Those two things force the compiler to have the first and last elements in the struct in the same order as they are declared.

Another practical requirement is that every compilation must order the struct members the same way. A smart compiler could make a decision that since it sees that some struct members are always accessed close to each other they could be reordered in a way that makes them end up in a cache line. This optimization is of course impossible in C because structs often define an API between different compilation units and we can't just reorder things differently on different compilations.

The best we could do given the limitations is to define some kind of packing order in the ABI to minimize alignment waste that doesn't touch the first or last element in the struct, but it would be complex, error prone and probably wouldn't buy much.

answered Apr 25 '13 at 12:55

Art

19,807
1
34
60

The restriction on the last element probably only really applies in cases where it's an array. Behavior with `union` could be odd if struct fields could get reordered, but I'm not sure of any situations where standards-defined behavior not involving pointer comparison operators would change. Note that if a union contains a struct which contains a coarsely-aligned element but ends with a small one, and another struct which starts with the same elements but includes a second small element at the end, the second small element of the latter struct... – supercat Apr 25 '13 at 15:29
...could (likely would) end up being placed within the padding area of the first struct. My initial thought was that the sequencing rule was designed to prevent the confusion that could result if a structure element got placed in the padding area of an aliased structure, but I don't think the rule does prevent that. It's obvious that for structs to be useful any reordering of fields would have to be specified in the ABI, but an ABI which specified that non-array items will get placed in the first suitably-sized "gap", if any exists would seem straightforward. – supercat Apr 25 '13 at 15:35
1

I just thought of another reason why the compiler shouldn't touch the order of the fields. Around 13-14 years ago I did some heavy optimization of a network driver that was used for packet forwarding. One large gain (20% more pps) was from reordering the fields in a control struct for better cache behavior. The compiler couldn't know the hot paths in the code and if it was reordering things for packing it would probably mess this up. Sometimes you don't want to optimize for packing and the philosophy of C is that the programmers know what they're doing. – Art Apr 26 '13 at 07:19
Even under today's rules, many compilers have some `#pragma` or other directives which allow non-default arrangements of structures. Certainly any compiler which could rearrange structures should provide some means of specifying a particular layout. Actually, I'd really like to see a standard means of specifying explicit layouts of structures, including bit-fields. Overlaying structures on byte arrays to serialize and deserialize data is icky and non-portable, but if the language included directives to explicitly specify the memory layout, a compiler might be able to generate good code... – supercat Apr 26 '13 at 14:35
...that could exploit particular processor features. For example, if the compiler generating code for a little-endian processor that included an instruction to flip bytes within a word needed to produce code to access a 32-bit int that would be 32-bit aligned but kept in network byte order, it might be able to generate efficient code using the byte-swap instruction. – supercat Apr 26 '13 at 14:38

score 2 · Answer 2 · answered Apr 25 '13 at 12:13

2

If you couldn't rely on the ordering, then it would be much harder to write low-level code which maps structures onto things like hardware registers, network packets, external file formats, pixel buffers, etc.

Also, some code use a trick where it assumes that the last member of the structure is the highest-addressed in memory to signify the start of a much larger data block (of unknown size at compile time).

answered Apr 25 '13 at 12:13

Graham Borland

60,055
21
138
179

1

Any reasonable implementation must provide a means of declaring a struct that will obey known rules for ordering. That does not in and of itself imply that those rules could not entail structs being laid out in something other than source-code order; indeed, an implementation might legitimately and usefully allow `#pragma` directives to specify some other arrangement. – supercat Apr 25 '13 at 15:26

score 1 · Answer 3 · answered Apr 25 '13 at 12:56

Reordering fields of structures can sometime yield good gains in data size and often also in code size, especially in 64 bit memory model. Here an example to illustrate (assuming common alignment rules):

struct list {
   int  len;
   char *string;
   bool isUtf;
};

will take 12 bytes in 32 bit but 24 in 64 bit mode.

struct list {
   char *string;
   int  len;
   bool isUtf;
};

will take 12 bytes in 32 bit but only 16 in 64 bit mode.

If you have an array of these structures you gain 50% in the data but also in code size, as indexing on a power of 2 is simpler than on other sizes. If your structure is a singleton or not frequent, there's not much point in reordering the fields. If it is used a lot, it's a point to look at.

As for the other point of your question. Why doesn't the compiler do this reordering of fields, it is because in that case, it would be difficult to implement unions of structures that use a common pattern. Like for example.

struct header {
    enum type;
    int  len;
};

struct a {
    enum type;
    int  len;
    bool whatever1;
};

struct b {
    enum type;
    int  len;
    long whatever2;
    long whatever4;
};

struct c {
    enum type;
    int  len;
    float fl;
};


 union u {
    struct h header;
    struct a a;
    struct b b;
    struct c c;
 };

If the compiler rearranged the fields, this construct would be much more inconvenient, as there would be no guarantee that the type and len fields were identical when accessing them via the different structs included in the union. If I remember correctly the standard even mandates this behaviour.

What is there to be gained by deterministic field ordering in the memory layout?

3 Answers3