4 ms·

Isn't reordering struct members something that compilers should do automatically? Are there scenarios where reordering produces undefined behaviour?

deleted 5y ago
[deleted]
onphonenow 5y ago
per https://jonasdevlieghere.com/order-your-members/ https://jonasdevlieghere.com/order-your-members/ Smaller size is good for cache, but other factors matter From the above Single-Threaded Environment When a single thread on a single core is accessing the data in a struct, we can improve caching performance by using as little cache lines as possible. By optimizing for memory footprint, as discussed in the previous section, the struct uses less memory and hence occupies less space in the cache. By placing heavily used members close together, we hope (based on the locality of reference principle) that they will end up closer together in the cache, preferably even on the same cache line, and hence use less cache space. By separating hot fields form cold ones, we reduce the amount of cache lines filled with unused data.
berkut 5y ago
Not undefined behaviour, but you can get "false sharing" where data from structs/member variables ends up in particular cache lines depending on their address (and the -way of the caches of the processors). Depending on the algorithm and the access patterns it's relatively common (at leasts in HPC space in my experience) to get overhead / inefficiencies due to false sharing or other aliasing issues (4k aliasing on Intel CPUs, although that's arguably a slightly different issue), due to cache line 'collisions' of different member variables being written to in the caches in sub-optimal ways due to the algorthm. So for HPC code, you very much do want the ability to re-order them manually.
olliej 5y ago
Automatic reordering makes maintaining ABI compatibility either very hard (how do you add a field to a struct if you don’t know where the compiler will put it?), or slow (objc supports field reordering, etc but it results in a lot of indirection when you access a field from outside the class’s implementation section) C, C++, Pascal all define the order explicitly, the platform ABI generally defines the padding rules.
- rsecora 5y ago
  Underrated comment
- fulafel 5y ago
  Most languages don't have stable native ABIs.
  - olliej 5y ago
    What? Define “most” here, because every actual system language has a stable ABI, otherwise they can’t be used for system libraries. If you include toy languages, you might get there. Even languages like Go and Rust recognize that at API boundaries you need a stable and defined ABI.
    - fulafel 5y ago
      Most of today's apps languages, for example. But also Go documents that there's only a internal ABI that's not stable across versions, so it doesn't serve for most ABIy things, like system libraries. Rust seems to be similar. I wonder what the situation is like in GPU language land... These languages still allow you to consume and provide C compatible ABIs explicitly but this does not interfere with data optimizations for native data.
      - olliej 5y ago
        Again, provide an actual example. Many “modern” languages don’t ship in compiled form so the important part is mostly just API. Go and rust can’t be used for system libraries: you have to create C interface. This means that if you have two libraries, both written in rust then they have to communicate through a C layer. The alternative (what rust does) is to have every application contain a complete copy of every library it uses, which is horrific for performance.
        deleted 5y ago
        [deleted]
fulafel 5y ago
Yes, they should. Also many other kinds of data representation optimizations whwre there are lots of fruit to pick. Unfortunately this rarely happens. Language specs rarely support it well, so much of the blame is on language designers. But it's a somewhat chicken and egg situation. Language users don't demand it either because they never had it in other languages.
- pjmlp 5y ago
  Doing it automatically messes up ABI and binary libraries infrastructure. There is more to it than lazy language designers.
  - fulafel 5y ago
    Yes, JIT runtimes have an easier time here (and can more easily do feedback based optimizations on access patterns). For AOT you can do LTO / whole program opt and punt on calls to outside libs, plus provide generics style specializable library code that is not AOT compiled. I submit it's mostly solvable in language design. They're not all lazy of course, but claiming to be very performance-oriented is a half truth as long as you don't have a strong story here.
    - pjmlp 5y ago
      That doesn't work in environments based on shared libraries or OS IPC component models.
  - masklinn 5y ago
    > Doing it automatically messes up ABI and binary libraries infrastructure. Neither is an issue in Go, since everything’s statically compiled and it doesn’t make any ABI guarantee. Making this opt-out (or making precise layout opt-in) actually improves the situation there, because then you have clear, explicit guarantees.
    - pjmlp 5y ago
      Apparently people keep missing the news that Go nowadays also does dynamic linking.

deleted 5y ago

[deleted]

onphonenow 5y ago

per https://jonasdevlieghere.com/order-your-members/ https://jonasdevlieghere.com/order-your-members/ Smaller size is good for cache, but other factors matter From the above Single-Threaded Environment When a single thread on a single core is accessing the data in a struct, we can improve caching performance by using as little cache lines as possible. By optimizing for memory footprint, as discussed in the previous section, the struct uses less memory and hence occupies less space in the cache. By placing heavily used members close together, we hope (based on the locality of reference principle) that they will end up closer together in the cache, preferably even on the same cache line, and hence use less cache space. By separating hot fields form cold ones, we reduce the amount of cache lines filled with unused data.

berkut 5y ago

Not undefined behaviour, but you can get "false sharing" where data from structs/member variables ends up in particular cache lines depending on their address (and the -way of the caches of the processors). Depending on the algorithm and the access patterns it's relatively common (at leasts in HPC space in my experience) to get overhead / inefficiencies due to false sharing or other aliasing issues (4k aliasing on Intel CPUs, although that's arguably a slightly different issue), due to cache line 'collisions' of different member variables being written to in the caches in sub-optimal ways due to the algorthm. So for HPC code, you very much do want the ability to re-order them manually.

olliej 5y ago

Automatic reordering makes maintaining ABI compatibility either very hard (how do you add a field to a struct if you don’t know where the compiler will put it?), or slow (objc supports field reordering, etc but it results in a lot of indirection when you access a field from outside the class’s implementation section) C, C++, Pascal all define the order explicitly, the platform ABI generally defines the padding rules.

rsecora 5y ago
Underrated comment
fulafel 5y ago
Most languages don't have stable native ABIs.
- olliej 5y ago
  What? Define “most” here, because every actual system language has a stable ABI, otherwise they can’t be used for system libraries. If you include toy languages, you might get there. Even languages like Go and Rust recognize that at API boundaries you need a stable and defined ABI.
  - fulafel 5y ago
    Most of today's apps languages, for example. But also Go documents that there's only a internal ABI that's not stable across versions, so it doesn't serve for most ABIy things, like system libraries. Rust seems to be similar. I wonder what the situation is like in GPU language land... These languages still allow you to consume and provide C compatible ABIs explicitly but this does not interfere with data optimizations for native data.
    - olliej 5y ago
      Again, provide an actual example. Many “modern” languages don’t ship in compiled form so the important part is mostly just API. Go and rust can’t be used for system libraries: you have to create C interface. This means that if you have two libraries, both written in rust then they have to communicate through a C layer. The alternative (what rust does) is to have every application contain a complete copy of every library it uses, which is horrific for performance.
      - deleted 5y ago
        [deleted]

fulafel 5y ago

Yes, they should. Also many other kinds of data representation optimizations whwre there are lots of fruit to pick. Unfortunately this rarely happens. Language specs rarely support it well, so much of the blame is on language designers. But it's a somewhat chicken and egg situation. Language users don't demand it either because they never had it in other languages.

pjmlp 5y ago
Doing it automatically messes up ABI and binary libraries infrastructure. There is more to it than lazy language designers.
- fulafel 5y ago
  Yes, JIT runtimes have an easier time here (and can more easily do feedback based optimizations on access patterns). For AOT you can do LTO / whole program opt and punt on calls to outside libs, plus provide generics style specializable library code that is not AOT compiled. I submit it's mostly solvable in language design. They're not all lazy of course, but claiming to be very performance-oriented is a half truth as long as you don't have a strong story here.
  - pjmlp 5y ago
    That doesn't work in environments based on shared libraries or OS IPC component models.
- masklinn 5y ago
  > Doing it automatically messes up ABI and binary libraries infrastructure. Neither is an issue in Go, since everything’s statically compiled and it doesn’t make any ABI guarantee. Making this opt-out (or making precise layout opt-in) actually improves the situation there, because then you have clear, explicit guarantees.
  - pjmlp 5y ago
    Apparently people keep missing the news that Go nowadays also does dynamic linking.