An Introduction to Data Oriented Design with Rust

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 ]