42 ms·
Struct of Arrays vs Array of Structs have different performance, depending on how they are accessed, mainly due to how memory will be cached. If you are iterat
by Dwedit 1y ago
Struct of Arrays vs Array of Structs have different performance, depending on how they are accessed, mainly due to how memory will be cached.
If you are iterating over objects sequentially, and looking at every field, they will perform about the same. If you are iterating over objects sequentially, and only looking at a few fields, Struct of Arrays performs better. If you are accessing objects at random, and reading every field, Array of Structs performs better.
Array of Structs has a multiplication step when you calculate the address of an element. Struct of Arrays basically guarantees that the multiplication will be by a power of 2, so it's a bitshift rather than a multiplication. (Unless your struct contains a type whose size is not a power of 2). Multiplication is still very fast though on most architectures, so that's not all that much of a difference.
- bombela 1y agoHow could it not be a power of 2? The compiler makes sure to align fields and pad structs to power of 2 anyways.
- tomsmeding 1y agoIf your struct contains a field that is itself a struct, e.g. one containing three int32_t's, then that field has size 12, which is not a power of two.
- compiler-guy 1y agoDoesn't even need to be a struct within a struct: struct Foo { int8_t a; int8_t b; int8_t c; }; will have a size of 3 and an alignment of 1. Alignment is always power of 2, and size modulus alignment will always be zero. But alignment can be less than size, and size need not be a power of two, just have one power-of-two factor.
- bombela 1y agoBrain was not fully loaded yet, thank you. I don't think the struct in struct is relevant in your example by the way. i32 requires 4-bytes alignment. An array of a struct{3×i32} will be aligned to 12 bytes. Which maintains the 4 bytes alignment of the fields. If this structure is embedded into another one, it will be padded accordingly to the alignment requirement of the outer field. { { 3×i32 } i32 } will be 16 bytes. { { 3×i32 } i64 } will be 12, padding 4, 8. Totalling 24. I am assuming x86_64.
- compiler-guy 1y agoStruct of arrays have the potential to be much more memory efficient if the original struct had padding. struct Foo { int64_t i; int8_t c; // 7 bytes of padding for alignment. }; A Foo array will have seven bytes of wasted space per element. That can add up, and can even blow away what would be nice caching effects if looking at both elements. Access patterns do matter a lot to this, but it isn't as easy as describing one. Always profile. [Edit, I wish hn supported markdown.]
- WalterGR 1y agoLines that start with 2 spaces are monospaced. https://news.ycombinator.com/formatdoc https://news.ycombinator.com/formatdoc
- silisili 1y agoI haven't benched them, but it feels like in some languages bounds checking would hamper SoA performance, no?