Why doesn't GCC optimize structs?

Question

Systems demand that certain primitives be aligned to certain points within the memory (ints to bytes that are multiples of 4, shorts to bytes that are multiples of 2, etc.). Of course, these can be optimized to waste the least space in padding.

My question is why doesn't GCC do this automatically? Is the more obvious heuristic (order variables from biggest size requirement to smallest) lacking in some way? Is some code dependent on the physical ordering of its structs (is that a good idea)?

I'm only asking because GCC is super optimized in a lot of ways but not in this one, and I'm thinking there must be some relatively cool explanation (to which I am oblivious).

Hauck

You can try the -fipa-struct-reorg option in the struct-reorg-branch. Is there a GCC keyword to allow structure-reordering? – Aperture

Answer 1

gcc does not reorder the elements of a struct, because that would violate the C standard. Section 6.7.2.1 of the C99 standard states:

Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared.

Kolnos

Yes, but why was it defined this way? – Susian

@Susian The programmer may be making assumptions as to the order of the data in the struct and may be using masking to get each portion. If the struct is reordered than the masking my be incorrect. – Bondsman

@Evo510: I’m confused. To use masking, you have to know padding, too, which is not guaranteed by the language. So, you can’t use masks. Am I missing something? – Susian

@Susian I've seen numerical integration code which makes the assumption that all of its inputs are floats in sequential order. You pass it the pointer to the first value to integrate, and the last, and it scans between them. However, you keep the information in a struct because, for everything except integration, it is a more convenient format. – Doucette

While it will violate the Standard, there is useful reordering method to protect Linux kernel from rootkits/exploits: part of Linux KSPP (kernsec.org/wiki/index.php/Kernel_Self_Protection_Project) is some struct fields randomization/reordering: openwall.com/lists/kernel-hardening/2017/05/26/8 (Introduce struct layout randomization plugin), related paper: sec.taylor.edu/doc/… ("Improved kernel security through memory layout randomization" - DM Stanley - ‎2013) – Rollandrollaway

@Susian There are cases where assumptions are made, for example working with the network: the connect() call specifies a sockaddr as its argument, which in OOP terms is something like a 'base class' and in reality you will be sending in a 'subclass member', that is a different structure (sockaddr_in for example) and the kernel relies on the field identifying what type you passed in being in the same place as in sockaddr. – Swingeing

Answer 2

Structs are frequently used as representations of the packing order of binary file formats and network protocols. This would break if that were done. In addition, different compilers would optimize things differently and linking code together from both would be impossible. This simply isn't feasible.

Galvan

this has nothing to do with networking or file structures. Indeed the header of a BMP structure IS tightly packed with elements falling on non-natural boundaries that are alien to the compiler. – Illusion

Err, yes? You've misinterpreted the question. Reread the second paragraph, where he talks about struct ordering. This is entirely different from padding. – Galvan

your first point is very valid. but i think your second isn't. compiled code from different compilers is not compatible anyway. – Wispy

@JohannesSchaub-litb that depends; if both compilers adhere to the same ABI there is no reason for them to produce incompatible code. Examples are GCC and Clang, and 32-bit GCC and MSVC for C on Windows. – Feltie

Answer 3

tl;dr GCC does not reorder struct members.

GCC is smarter than most of us in producing machine code from our source code; however, I shiver if it was smarter than us in re-arranging our structs, since it's data that e.g. can be written to a file. A struct that starts with 4 chars and then has a 4 byte integer would be useless if read on another system where GCC decided that it should re-arrange the struct members.

Eurhythmics

Reading/Writing structs directly to a file is not compiler/platform portable anyway because of alignment (which is allowed), see this SO answer. – Bellboy

Answer 4

gcc SVN does have a structure reorganization optimization (-fipa-struct-reorg), but it requires whole-program analysis and isn't very powerful at the moment.

Bandaid

Stock gcc 10 years later (version 7.2, packaged by Ubuntu 17.10) does not document this option in manual page. Strangely the option string is recognized by the gcc executable, though. – Vicinage

Answer 5

Not saying it's a good idea, but you can certainly write code that relies on the order of the members of a struct. For example, as a hack, often people cast a pointer to a struct as the type of a certain field inside that they want access to, then use pointer arithmetic to get there. To me this is a pretty dangerous idea, but I've seen it used, especially in C++ to force a variable that's been declared private to be publicly accessible when it's in a class from a 3rd party library and isn't publicly encapsulated. Reordering the members would totally break that.

Seduce

I believe the linux kernel does this for linked lists. – Diatessaron

Answer 6

C compilers don't automatically pack structs precisely because of alignment issues like you mention. Accesses not on word boundaries (32-bit on most CPUs) carry heavy penalty on x86 and cause fatal traps on RISC architectures.

Inquiring

I wasn't talking about getting rid of the buffering, I'm talking about putting all the longs/pointers end-to-end, then all the shorts end-to-end, then all the characters end-to-end, etc. so that you're only losing space at the end. – Hauck

Well, that's half true. The C compiler will default to packing them, they just do it aligned to the natural word boundaries of the architecture. That's why you need to #pragma pack(0) structs that are using chars/shorts in packed protocols, to stop it from adding padding. – Galvan

@Alex, err. You're going to waste the same amount of space, since your character would have to be padded the same amount. You wouldn't benefit at all, space or performance-wise. – Galvan

Oh. Yeah, that causes trouble with binary formats, as Cody attested. Plus, ANSI guarantees that structure element offsets must be in increasing order. – Inquiring

@Cody, all the space will be wasted at the very end and is either less than or equal to the regular "allocate as you go approach" case and point: struct blah { char a; short b; char c; }; struct blah2 { short b; char a, c; }; blah wastes 2 more bytes than blah2 – Hauck

because one character can go between the other character and the short rather than wasting a pad character for each. – Hauck

That's not the case, though. If you disable padding you get the same size, but you lose the reason you need padding -- most architectures can't access it at all, and those that can will do so more slowly. So you're losing padding and reordering to get... the same thing. – Galvan

you don't lose any of the benefits of padding by arranging the struct properly. With a short, char, char, you can have 0 padding, but all elements fall on the correct offset. In general, yo will not lose any speed at all for this, as they fall on their natural bounds – Hauck

No, this is not correct on the majority of architectures. Even if it's allowed, accessing memory that is not word-aligned (meaning 32-bit typically) is penalized, even if it's allowed. – Galvan

You can maintain word-aligned memory. Characters can be placed on any byte (obviously). Shorts can be started on any byte that is a multiple of 2. Ints on any byte that is a multiple of 4. given char a, b; short c; |a|b|c|c is valid, but rearranged to a,c,b it must be |a|x|c|c|b|x| – Hauck

Answer 7

You might want to try the latest gcc trunk or, struct-reorg-branch which is under active development.

https://gcc.gnu.org/wiki/cauldron2015?action=AttachFile&do=view&target=Olga+Golovanevsky_+Memory+Layout+Optimizations+of+Structures+and+Objects.pdf

Honorarium