HN Explorer

11 comments

[ 2.9 ms ] story [ 40.2 ms ] thread
happythought
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
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
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
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
Is there any reason go can’t do this automatically at compile time?
efferifick
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
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.
The_rationalist
Does anybody know if any mainstream compiler/JIT is experimenting with struct of arrays to array of structs & vice versa conversions?
efferifick
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.