3 ms·
> This is just as cumbersome in the array-of-structs case: some structs are larger than others in the same array, you need some signalling mechanism to know whi
by dragontamer 6y ago
> This is just as cumbersome in the array-of-structs case: some structs are larger than others in the same array, you need some signalling mechanism to know which structs are and aren't Point3Ds
Strong disagree. The traditional OOP approach is passing indirect pointers to everything and incurring an inefficient level of indirection.
Ex:
vector<Point*> blah;
blah.push_back(&somePoint2D);
blah.push_back(&somePoint3D.xy);
foo(blah); // "Function foo" works on Point2D and Point3Ds, none the wiser
// Note that foo may change *blah[10].x += 5
// and it updates the original Point2D or Point3D. This
// wouldn't work for a copied array.
I think OOP's inefficiency is well known and often criticized. Critics are correct: OOP methodologies are inefficient (compared to other techniques). But OOP seems to have a win on various software-engineering metrics: Extendability, Open-Closed, DRY, etc. etc.
> In Rust the AOS case would be an Enum of Point and Point3D, and the SOA case would be two Vecs of ints and one Vec of Option<int>s.
Rust is a general purpose language. I'm not too good at Rust, but the AOS case would simply be a Box(Point2D).
> More generally, this sounds like a language support problem <snip>
ISPC got SOA types by the way. Check em out if you're interested:
https://ispc.github.io/ispc.html#structure-of-array-types https://ispc.github.io/ispc.html#structure-of-array-types
You don't need a very large SOA-type to take advantage of SIMD or auto-vectorization. You can "gather" into an SOA, then "scatter" back to your main representation.
- kmeisthax 6y agoRight, but your example isn't an array of structs anymore. It's an array of pointers. You are correct that it's easier to take an array of structs and turn it into an array of pointers, or to take a single struct and get a pointer to one of it's members, whereas a struct of arrays would have to be scattered in order to get anything referenceable. ISPC sounds pretty cool. How much of a performance penalty is scatter/gather into and out of an SOA? I assumed you'd want to store all of your data-parallel fields in SOA format, rather than gathering into one every time you wanna do some maths-heavy operation.
- dragontamer 6y agoIt's O(n) to gather and to scatter. So it's definitely expensive if you are doing only a single pass. But if you are doing any big o bigger than O(n) (ex: matrix multiplication, which is O(n^2.4) or so), then it's relatively cheap. Indeed, optimized matrix multiplications transpose the data to speed it up!! There is something to be said about gather and scatter patterns as a methodology, especially as a first step into optimizing your algorithms. It's not the ultimate speed form, but relatively straightforward and simple to implement.
- dragontamer 6y ago> ISPC sounds pretty cool. It should also be noted that in ISPC, CUDA, ROCm, OpenCL (etc. etc.), your thread-local variables are compiled into SOA form for maximum performance. SIMD architectures benefit more from SOA, and as such... making maximum use of SOA is built into those languages implicitly. If you're finding yourself reaching for SIMD-techniques, maybe its time to use a dedicated SIMD-language.