An Introduction to Data Oriented Design with Rust

Re:An Introduction to Data Oriented Design with Rust by dragontamer on Thursday September 17, 2020 @11:26PM (#24512670)

> 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

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.

[ Parent | on HN ]

Re:An Introduction to Data Oriented Design with Rust by kmeisthax on Friday September 18, 2020 @07:21PM (#24522831)

Right, 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.

[ Parent | on HN ]

Re:An Introduction to Data Oriented Design with Rust by dragontamer on Friday September 18, 2020 @11:39PM (#24524775)

It'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.

[ Parent | on HN ]

Re:An Introduction to Data Oriented Design with Rust by dragontamer on Monday September 21, 2020 @12:23PM (#24545256)

> 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.

[ Parent | on HN ]