5 ms·

Show HN: 33% Memory Reduction by Reordering Struct Fields

19 points by lanecwagner 6y ago

happythought 6y ago
Nice post, thanks. Did you happen to raise an issue with the Go team? Maybe it would be low hanging fruit for a compiler optimization.
- efferifick 6y ago
  I might be biased because I'm currently working on this same optimization but for GCC. I think that it is more complicated than it seems. Defining the layout of a structure is normally done during parse time (at least in GCC). And one cannot know if it is safe to reorder fields all the way up until link time. This means that a lot of optimizations and assumptions that were made might not longer be valid. For example, in GCC the results of the sizeof operator are evaluated at parse time. One might need to change these values link time. Otherwise statements like: memset(&astruct, 0, sizeof(astruct)); will overwrite memory that is no longer part of the struct. Furthermore, constant propagation might have propagated the value of a sizeof operator and it might have been folded into different arithmetic operations. This can be solved in different ways, but if the compiler was not built this way, it might take some time to implement. Also, all pointer arithmetic will need to be changed...
anitil 6y ago
In my time in the embedded world we would reorder fields to deal with issues like alignment in MIPS. If you wanted to avoid this you would have to use a directive like __attribute__((packed)). Does go allow you do do the same? So I used to do things like this (hopefully the formatting is correct): ~/Desktop$ cat test1.c #include <stdio.h> #include <stdint.h> // Original Ordering struct stats { uint8_t NumPosts; uint16_t Reach; uint8_t NumLikes; }; // Packed struct struct stats_packed { uint8_t NumPosts; uint16_t Reach; uint8_t NumLikes; } __attribute__((packed)); // Reordered struct stats_reordered { uint8_t NumPosts; uint8_t NumLikes; uint16_t Reach; }; int main(){ printf("sizeof(struct stats) = %ld\n", sizeof(struct stats)); printf("sizeof(struct stats_packed) = %ld\n", sizeof(struct stats_packed)); printf("sizeof(struct stats_reordered) = %ld\n", sizeof(struct stats_reordered)); return 0; } ~/Desktop$ gcc test1.c && ./a.out sizeof(struct stats) = 6 sizeof(struct stats_packed) = 4 sizeof(struct stats_reordered) = 4
- hinkley 6y ago
  I first ran into this the other way around: misaligned 64 bit values on 64 bit MIPS (and PPC) hardware. But it's the sort of thread that once you pull on it, you just keep pulling. Getting the alignment made the data bigger, then we had to shrink it back, and while you're in there you might as well keep looking around...
jtsiskin 6y ago
Is there any reason go can’t do this automatically at compile time?
- efferifick 6y ago
  Mmm... I might be able to provide some insight... For the C language it is not possible to reorder fields generally at compile time. This is because if a user defines a struct and the struct is passed to a library that was pre-compiled, then the library and your application hold a different representation for the struct. You can at link-time be able to change some structure definitions if you know the structure definition is not escaping your application (i.e. it is not passed to a library). There are possibly other things that might hinder the reordering of the fields, for example casting or placing a structure in a union. If you are casting a structure to another, you might be expecting that the underlying memory to be represented in a specific way in order for the cast to make sense. The same thing happens when you place a struct in a union.
Gibbon1 6y ago
That go enforces alignment by padding structs is full of sad and fail. Since what's important with modern processors is cache line alignment not word alignment. All they get for that optimization is more memory usage and cache pressure.
- Gibbon1 6y ago
  Stay classy HN
srean 6y ago
Not the same language but this is still an important read http://www.catb.org/esr/structure-packing/ http://www.catb.org/esr/structure-packing/ although its not quite a lost art as it is made out to be. A developer is expected to know this.
The_rationalist 6y ago
Does anybody know if any mainstream compiler/JIT is experimenting with struct of arrays to array of structs & vice versa conversions?
- efferifick 6y ago
  I know the person who is working on an implementation of this in GCC. However, it is still early days and the implementation is not ready for public consumption. Other than that, I've only seen this transformation on academic papers.

19 points by lanecwagner 6y ago

Nice post, thanks. Did you happen to raise an issue with the Go team? Maybe it would be low hanging fruit for a compiler optimization.

efferifick 6y ago
I might be biased because I'm currently working on this same optimization but for GCC. I think that it is more complicated than it seems. Defining the layout of a structure is normally done during parse time (at least in GCC). And one cannot know if it is safe to reorder fields all the way up until link time. This means that a lot of optimizations and assumptions that were made might not longer be valid. For example, in GCC the results of the sizeof operator are evaluated at parse time. One might need to change these values link time. Otherwise statements like: memset(&astruct, 0, sizeof(astruct)); will overwrite memory that is no longer part of the struct. Furthermore, constant propagation might have propagated the value of a sizeof operator and it might have been folded into different arithmetic operations. This can be solved in different ways, but if the compiler was not built this way, it might take some time to implement. Also, all pointer arithmetic will need to be changed...

anitil 6y ago

In my time in the embedded world we would reorder fields to deal with issues like alignment in MIPS. If you wanted to avoid this you would have to use a directive like __attribute__((packed)). Does go allow you do do the same? So I used to do things like this (hopefully the formatting is correct): ~/Desktop$ cat test1.c #include <stdio.h> #include <stdint.h> // Original Ordering struct stats { uint8_t NumPosts; uint16_t Reach; uint8_t NumLikes; }; // Packed struct struct stats_packed { uint8_t NumPosts; uint16_t Reach; uint8_t NumLikes; } __attribute__((packed)); // Reordered struct stats_reordered { uint8_t NumPosts; uint8_t NumLikes; uint16_t Reach; }; int main(){ printf("sizeof(struct stats) = %ld\n", sizeof(struct stats)); printf("sizeof(struct stats_packed) = %ld\n", sizeof(struct stats_packed)); printf("sizeof(struct stats_reordered) = %ld\n", sizeof(struct stats_reordered)); return 0; } ~/Desktop$ gcc test1.c && ./a.out sizeof(struct stats) = 6 sizeof(struct stats_packed) = 4 sizeof(struct stats_reordered) = 4

hinkley 6y ago
I first ran into this the other way around: misaligned 64 bit values on 64 bit MIPS (and PPC) hardware. But it's the sort of thread that once you pull on it, you just keep pulling. Getting the alignment made the data bigger, then we had to shrink it back, and while you're in there you might as well keep looking around...

jtsiskin 6y ago

Is there any reason go can’t do this automatically at compile time?

efferifick 6y ago
Mmm... I might be able to provide some insight... For the C language it is not possible to reorder fields generally at compile time. This is because if a user defines a struct and the struct is passed to a library that was pre-compiled, then the library and your application hold a different representation for the struct. You can at link-time be able to change some structure definitions if you know the structure definition is not escaping your application (i.e. it is not passed to a library). There are possibly other things that might hinder the reordering of the fields, for example casting or placing a structure in a union. If you are casting a structure to another, you might be expecting that the underlying memory to be represented in a specific way in order for the cast to make sense. The same thing happens when you place a struct in a union.

Gibbon1 6y ago

That go enforces alignment by padding structs is full of sad and fail. Since what's important with modern processors is cache line alignment not word alignment. All they get for that optimization is more memory usage and cache pressure.

Gibbon1 6y ago
Stay classy HN

srean 6y ago

Not the same language but this is still an important read http://www.catb.org/esr/structure-packing/ http://www.catb.org/esr/structure-packing/ although its not quite a lost art as it is made out to be. A developer is expected to know this.

The_rationalist 6y ago

Does anybody know if any mainstream compiler/JIT is experimenting with struct of arrays to array of structs & vice versa conversions?

efferifick 6y ago
I know the person who is working on an implementation of this in GCC. However, it is still early days and the implementation is not ready for public consumption. Other than that, I've only seen this transformation on academic papers.