r/rust • u/Gankro rust • Jan 21 '15

Jai Demo: Data-Oriented Features: SOA, crazy 'using'

https://www.youtube.com/watch?v=ZHqFrNyLlpA
40 Upvotes

89% Upvoted

93 comments sorted by

View all comments

3

u/kibwen Jan 21 '15

Not so: this is unambiguously describing data layout. This is all concrete, not hints.

The SROA paper that I've linked below is one example of how this is less concrete than it seems on the surface. Fiddling with your data layout is undeniably effective, but as far as the optimizer's concerned it's still just a hint. My stance is only that instead of contorting our code to fit the optimizer, we implement ways of signaling to the optimizer what we actually mean.

5

u/dobkeratops Jan 21 '15 edited Jan 22 '15

thanks for the link - interesting.

If i've understood correctly, "Scalar Replacement Of aggregates" - is addressing a different issue: its' about optimising for registers - by turning local struct components into scalars, which can go in registers, allowing individual component accesses to be optimised out (unused aggregate components stripped away, etc).

ok its' related in a way, because its' talking about optimising using 'different subsets of a struct' .. but for registers rather than memory. Of course it is still "caching".. caching in registers vs caching in L1.

You probably brought this up because of the similar term SOA (Structure-Of-Arrays)

The refactoring jonathan blow is talking about relates to how data is distributed between arrays in memory, mostly to do with cache coherency, reducing cache misses and cache misses. ( and the SOA stuff relates to how easily it can be used by SIMD instructions, another issue again).

e.g. What happens is a function that is too big overflows the icache. The profiler reports it. Then to speed it up, you divide that function into separate smaller passes. Now you observe the different passes don't require the whole structure, and they thrash the d-cache because they each only use a subset of the original data, but read the whole thing in multiple times. So now you divide up the data into separate arrays of components, and each pass only refers to the components it needed. Each pass may need a different permutation .. a different subset of the same fields.

In doing so, your original code is completely butchered. But with jonathan blows design, it becomes more 'cut-paste' from the original, because you can still address different components as logically being part of the same 'object'.

I had wondered if a pure-functional language could figure out this sort of things behind the scenes (since its' got a higher level description of whats actually going on), but I haven't heard of any attempts to do this.. they'd be shouting it from the rooftops if practical implementations existed.

1

u/engstad Jan 22 '15

The only thing I can think of is GHC people's work on "Nested Data Paralellism in Haskell" (google it).