6 ms·

Alright this might be a stupid question, but if packing is about the order in which the fields are arranged... shouldn't the compiler optimize that? I mean, it

by dysoco 10y ago

Alright this might be a stupid question, but if packing is about the order in which the fields are arranged... shouldn't the compiler optimize that? I mean, it does much more complex optimizations already doesn't it?

Arnavion 10y ago
The language spec prevents it from doing so for ABI reasons. The optimization is present in other languages that did not start with this restriction, but it's too late for C now.
- valarauca1 10y ago
  >The optimization is present in other languages that did not start with this restriction, but it's too late for C now. Which? .NET is the only one I could find that appears to do some from of smart packing [1] The new hotness languages behave like: Go doesn't sort by size. It packs to the byte, but guarantees structures within structures will start on the 32/64bit boundary (depending on 32/64bit system) so it'll pad for them. Rust ignores field size and just aligns to the 32bit boundary, unless you trigger `#[repr(C)]` which will pack like C. Rust doesn't give any guarantees about a structure is laid out to be perfectly honest. C++, NIM, D. I can find no reference on Crystal except that you can opt into C behavior. So I don't know what default is. [1] https://msdn.microsoft.com/en-us/library/ms253935(v=vs.80).aspx https://msdn.microsoft.com/en-us/library/ms253935(v=vs.80).a...
  - ygra 10y ago
    The linked site explains structure packing for C/C++ and the related compiler options. It has nothing to do with the CLR.
  - dbaupp 10y ago
    Rust doesn't ignore field size nor does it align to any particular boundary. E.g. struct Foo { x: u8 } is one byte and has alignment 1, and similarly struct Bar { x: u8, y: i16 } is 4 bytes and has alignment 2. The compiler doesn't give guarantees about structure layout so that it is able to reduce the size by reordering fields.
    - valarauca1 10y ago
      So the nomicon is out of date? It says Struct fields are aligned to to the 32/64bit boundary based on system architecture. Then you have #[repr(u8/u16/u32/u64)] which will align to 8/16/32/64 boundary.
      - Gankro 10y ago
        No you're just making stuff up. https://doc.rust-lang.org/nomicon/repr-rust.html https://doc.rust-lang.org/nomicon/repr-rust.html The bulk of this section is describing how Rust has reserved the right to reorder and pack stuff. The first example happens to be 32-bit aligned because it contains a value that is.
cdavid 10y ago
The compiler can't optimize this in general as this affects the ABI when the struct itself is exposed (that's one of the reason why it is useful to avoid exposing struct themselves but just pointer when you can).
dalailambda 10y ago
A lot of systems code involves directly messing with the memory of a specific struct, and if a compiler moved the struct fields around with the programmer knowing, there would be a lot of memory problems.
gaius 10y ago
What if your struct is actually a memory-mapped I/O device? Far from optimizing you need to give a hard guarantee that it will NEVER be optimized by the compiler.
- kazinator 10y ago
  Suppose C didn't require order of struct members. How could we support I/O devices? Simply by wrapping them behind functions or macros which take a base address and access a specific register relative to that address using pointer arithmetic and dereferencing. You see this being done anyway! if ((SERIAL_STATUS_PORT(port_addr) & SERIAL_DTR) != 0) { /* DTR line is asserted */ }
  - gaius 10y ago
    More likely you'd have to drop down into ASM for those bits... You see in a lot of high performance networking code too, you just get a block of bytes off the wire, cast it to a struct and use it straight away. High risk, high reward :-)
- Grishnakh 10y ago
  Well if we were making an all-new C-like language, we could just add a compiler directive which prevents optimization for cases like this. For all I know, other languages may do just this (there's a comment farther down about Rust which appears to say this).
kazinator 10y ago
ISO C has codified the C tradition that structure members are laid out in the order in which they are declared. The first member has the same address as the struct itself. The remaining members are then at increasing offsets from that address. Languages which allow compilers to reorganize structures for better packing (like, I think, Ada) have to have some provision to disable that in cases when the programmer requires the structure to conform to some externally imposed layout. I wish we could say that C does this to adhere to some principle of being predictable and obeying the programmer literally. However, that cannot be claimed with a straight face by anyone who knows anything about this language, in which you can cause undefined behavior just by giving the code a dirty look in the text editor window. What C gives you with predictable structure layout, it immediately takes away with scrambled evaluation order of function arguments and constituent subexpressions of most operators. Anyway, one consequence of a predictable layout is that C programs can do punning among structures which share a common initial sequence of members. One form of such punning is even required by ISO C to work: when a union is made of such struct types. Related hacks not involving binding through a union, however, also broadly work in de facto practice.
superuser2 10y ago
Structs get written directly to disk and network. Copies of the same program would produce different output depending on the optimization strategy they were compiled with. That's vigorously not allowed.
- kazinator 10y ago
  Also, the translation unit compilation model of C would be troublesome here, if optimization settings could influence struct layout. You can't have different translation units interpreting the same struct type declaration differently.
  - maccard 10y ago
    > You can't have different translation units interpreting the same struct type declaration differently. Sure you can! // MyHeader.h struct MyStruct { int A; char b; int* c; }; // A.cpp #include "MyHeader.h" <...> // B.cpp #pragma pack(push, 16) #include "MyHeader.h" #pragma pack(pop) <...>
jlarocco 10y ago
No. A huge and important use of structs is to communicate with other things, like hardware, libraries, and other languages, and in in those cases it's very important that the struct matches what the other side expects. You don't want the compiler to rearrange your TCP packet, for example. It might make sense to have a compiler extension to optimize packing for internal-only data structures, but I doubt any compilers bother. It's just another entry on the long list of things that C assumes the programmer will do themselves if it's important to them.
easytiger 10y ago
Then the memory layout of the struct will be different. So when you serialise it read it back it would be different, if you perhaps used a different non optimising compiler.
MaulingMonkey 10y ago
Aside from the ABI, file I/O, and memory mapping concerns voiced by others, it's also not always a performance optimization: Occasionally you really want two members of a struct to e.g. reside in different cachelines to avoid "false sharing" murdering your performance in multithreaded code (where multiple cores repeatedly fight over who owns / can update the cacheline in question.) Modern compilers all have warnings you can opt into, to alert you when the compiler inserts implicit padding, if you want to ensure things get packed nicely.
- marmaduke 10y ago
  > false sharing I wasn't aware of that sort of thing. any resources on learning these sorts of details of performance tuning, aside from hard-earned experience?
  - MaulingMonkey 10y ago
    I mostly just vacuum up a huge amount of material from as many sources as I can. My focus on game development might help here. A lot of it flows from understanding CPUs from a low level hardware perspective - you might be able to reverse engineer this kind of knowledge from the wikipedia articles, although I haven't tried doing so myself. E.g. the page for "CPU cache" references: - CPUs read/write by cacheline - Caches need to coordinate to avoid stale data through "cache coherence protocols" (which have a cost as mentioned on their own wiki page) "False sharing" is just the interplay of those two mechanisms in worst case scenarios and such corner cases. About the only time I've used this knowledge of false sharing has been when implementing a work-stealing task queue system. And I suppose the few times I've written a parallel for loop of some description. Trying to think of similar performance issues to guide you towards, a few come to mind: 1) CPU caches are basically implemented as fixed sized hashmaps with a really poor hash - the address modulo some power of two, with a fixed limit of collisions supported. http://www.lshift.net/blog/2013/10/08/cpu-cache-collisions-in-the-context-of-performance/ http://www.lshift.net/blog/2013/10/08/cpu-cache-collisions-i... I've never actually used this knowledge, although I could see it coming up if I were working on the design of a database's in-memory storage or something. 2) Reading "write combined" memory is really bad, including implicitly reading by failing to write entire cachelines (comes up with GPU resources such as textures) https://fgiesen.wordpress.com/2013/01/29/write-combining-is-not-your-friend/ https://fgiesen.wordpress.com/2013/01/29/write-combining-is-... This one I'm mindful of whenever I'm porting programs to use new graphics APIs, or writing the low level systems that deal with them in the first place. I feel there's at least one more situation where write combined memory has come up for me in practice (since typical memory access is not write combined), but it escapes me at the moment. Fortunately most graphics API docs at least warn you not to read the memory they're pointing you towards, although they're not always as explicit as "memcpy entire cachelines from orbit, just to be sure." 3) Performance of atomics touching multiple cachelines is terrible, when it's even supported: https://fgiesen.wordpress.com/2014/08/18/atomics-and-contention/ https://fgiesen.wordpress.com/2014/08/18/atomics-and-content... Normally I find out that this has been happening when I port a program to ARM and suddenly it crashes doing some kind of atomic operation or lock, because someone reinterpreted a char buffer instead of allocating properly, because cross-cacheline atomics are too crazy for ARM to bother implementing. Things like SSE and AVX also tend to perform... not so great, unless stuff is properly aligned for them. EDIT: I guess fgiesen is one resource, at least, as it cropped up twice trying to google for sources for the things I'm talking about ;)

by dysoco 10y ago

Arnavion 10y ago

The language spec prevents it from doing so for ABI reasons. The optimization is present in other languages that did not start with this restriction, but it's too late for C now.

valarauca1 10y ago
>The optimization is present in other languages that did not start with this restriction, but it's too late for C now. Which? .NET is the only one I could find that appears to do some from of smart packing [1] The new hotness languages behave like: Go doesn't sort by size. It packs to the byte, but guarantees structures within structures will start on the 32/64bit boundary (depending on 32/64bit system) so it'll pad for them. Rust ignores field size and just aligns to the 32bit boundary, unless you trigger `#[repr(C)]` which will pack like C. Rust doesn't give any guarantees about a structure is laid out to be perfectly honest. C++, NIM, D. I can find no reference on Crystal except that you can opt into C behavior. So I don't know what default is. [1] https://msdn.microsoft.com/en-us/library/ms253935(v=vs.80).aspx https://msdn.microsoft.com/en-us/library/ms253935(v=vs.80).a...
- ygra 10y ago
  The linked site explains structure packing for C/C++ and the related compiler options. It has nothing to do with the CLR.
- dbaupp 10y ago
  Rust doesn't ignore field size nor does it align to any particular boundary. E.g. struct Foo { x: u8 } is one byte and has alignment 1, and similarly struct Bar { x: u8, y: i16 } is 4 bytes and has alignment 2. The compiler doesn't give guarantees about structure layout so that it is able to reduce the size by reordering fields.
  - valarauca1 10y ago
    So the nomicon is out of date? It says Struct fields are aligned to to the 32/64bit boundary based on system architecture. Then you have #[repr(u8/u16/u32/u64)] which will align to 8/16/32/64 boundary.
    - Gankro 10y ago
      No you're just making stuff up. https://doc.rust-lang.org/nomicon/repr-rust.html https://doc.rust-lang.org/nomicon/repr-rust.html The bulk of this section is describing how Rust has reserved the right to reorder and pack stuff. The first example happens to be 32-bit aligned because it contains a value that is.

cdavid 10y ago

The compiler can't optimize this in general as this affects the ABI when the struct itself is exposed (that's one of the reason why it is useful to avoid exposing struct themselves but just pointer when you can).

dalailambda 10y ago

A lot of systems code involves directly messing with the memory of a specific struct, and if a compiler moved the struct fields around with the programmer knowing, there would be a lot of memory problems.

gaius 10y ago

What if your struct is actually a memory-mapped I/O device? Far from optimizing you need to give a hard guarantee that it will NEVER be optimized by the compiler.

kazinator 10y ago
Suppose C didn't require order of struct members. How could we support I/O devices? Simply by wrapping them behind functions or macros which take a base address and access a specific register relative to that address using pointer arithmetic and dereferencing. You see this being done anyway! if ((SERIAL_STATUS_PORT(port_addr) & SERIAL_DTR) != 0) { /* DTR line is asserted */ }
- gaius 10y ago
  More likely you'd have to drop down into ASM for those bits... You see in a lot of high performance networking code too, you just get a block of bytes off the wire, cast it to a struct and use it straight away. High risk, high reward :-)
Grishnakh 10y ago
Well if we were making an all-new C-like language, we could just add a compiler directive which prevents optimization for cases like this. For all I know, other languages may do just this (there's a comment farther down about Rust which appears to say this).

kazinator 10y ago

ISO C has codified the C tradition that structure members are laid out in the order in which they are declared. The first member has the same address as the struct itself. The remaining members are then at increasing offsets from that address. Languages which allow compilers to reorganize structures for better packing (like, I think, Ada) have to have some provision to disable that in cases when the programmer requires the structure to conform to some externally imposed layout. I wish we could say that C does this to adhere to some principle of being predictable and obeying the programmer literally. However, that cannot be claimed with a straight face by anyone who knows anything about this language, in which you can cause undefined behavior just by giving the code a dirty look in the text editor window. What C gives you with predictable structure layout, it immediately takes away with scrambled evaluation order of function arguments and constituent subexpressions of most operators. Anyway, one consequence of a predictable layout is that C programs can do punning among structures which share a common initial sequence of members. One form of such punning is even required by ISO C to work: when a union is made of such struct types. Related hacks not involving binding through a union, however, also broadly work in de facto practice.

superuser2 10y ago

Structs get written directly to disk and network. Copies of the same program would produce different output depending on the optimization strategy they were compiled with. That's vigorously not allowed.

kazinator 10y ago
Also, the translation unit compilation model of C would be troublesome here, if optimization settings could influence struct layout. You can't have different translation units interpreting the same struct type declaration differently.
- maccard 10y ago
  > You can't have different translation units interpreting the same struct type declaration differently. Sure you can! // MyHeader.h struct MyStruct { int A; char b; int* c; }; // A.cpp #include "MyHeader.h" <...> // B.cpp #pragma pack(push, 16) #include "MyHeader.h" #pragma pack(pop) <...>

jlarocco 10y ago

No. A huge and important use of structs is to communicate with other things, like hardware, libraries, and other languages, and in in those cases it's very important that the struct matches what the other side expects. You don't want the compiler to rearrange your TCP packet, for example. It might make sense to have a compiler extension to optimize packing for internal-only data structures, but I doubt any compilers bother. It's just another entry on the long list of things that C assumes the programmer will do themselves if it's important to them.

easytiger 10y ago

Then the memory layout of the struct will be different. So when you serialise it read it back it would be different, if you perhaps used a different non optimising compiler.

MaulingMonkey 10y ago

Aside from the ABI, file I/O, and memory mapping concerns voiced by others, it's also not always a performance optimization: Occasionally you really want two members of a struct to e.g. reside in different cachelines to avoid "false sharing" murdering your performance in multithreaded code (where multiple cores repeatedly fight over who owns / can update the cacheline in question.) Modern compilers all have warnings you can opt into, to alert you when the compiler inserts implicit padding, if you want to ensure things get packed nicely.

marmaduke 10y ago
> false sharing I wasn't aware of that sort of thing. any resources on learning these sorts of details of performance tuning, aside from hard-earned experience?
- MaulingMonkey 10y ago
  I mostly just vacuum up a huge amount of material from as many sources as I can. My focus on game development might help here. A lot of it flows from understanding CPUs from a low level hardware perspective - you might be able to reverse engineer this kind of knowledge from the wikipedia articles, although I haven't tried doing so myself. E.g. the page for "CPU cache" references: - CPUs read/write by cacheline - Caches need to coordinate to avoid stale data through "cache coherence protocols" (which have a cost as mentioned on their own wiki page) "False sharing" is just the interplay of those two mechanisms in worst case scenarios and such corner cases. About the only time I've used this knowledge of false sharing has been when implementing a work-stealing task queue system. And I suppose the few times I've written a parallel for loop of some description. Trying to think of similar performance issues to guide you towards, a few come to mind: 1) CPU caches are basically implemented as fixed sized hashmaps with a really poor hash - the address modulo some power of two, with a fixed limit of collisions supported. http://www.lshift.net/blog/2013/10/08/cpu-cache-collisions-in-the-context-of-performance/ http://www.lshift.net/blog/2013/10/08/cpu-cache-collisions-i... I've never actually used this knowledge, although I could see it coming up if I were working on the design of a database's in-memory storage or something. 2) Reading "write combined" memory is really bad, including implicitly reading by failing to write entire cachelines (comes up with GPU resources such as textures) https://fgiesen.wordpress.com/2013/01/29/write-combining-is-not-your-friend/ https://fgiesen.wordpress.com/2013/01/29/write-combining-is-... This one I'm mindful of whenever I'm porting programs to use new graphics APIs, or writing the low level systems that deal with them in the first place. I feel there's at least one more situation where write combined memory has come up for me in practice (since typical memory access is not write combined), but it escapes me at the moment. Fortunately most graphics API docs at least warn you not to read the memory they're pointing you towards, although they're not always as explicit as "memcpy entire cachelines from orbit, just to be sure." 3) Performance of atomics touching multiple cachelines is terrible, when it's even supported: https://fgiesen.wordpress.com/2014/08/18/atomics-and-contention/ https://fgiesen.wordpress.com/2014/08/18/atomics-and-content... Normally I find out that this has been happening when I port a program to ARM and suddenly it crashes doing some kind of atomic operation or lock, because someone reinterpreted a char buffer instead of allocating properly, because cross-cacheline atomics are too crazy for ARM to bother implementing. Things like SSE and AVX also tend to perform... not so great, unless stuff is properly aligned for them. EDIT: I guess fgiesen is one resource, at least, as it cropped up twice trying to google for sources for the things I'm talking about ;)