Data-oriented design or why you might shoot yourself in the foot with OOP (2009)

Re:Data-oriented design or why you might shoot yourself in t... by megameter on Monday June 28, 2021 @05:34AM (#27659704)

If we are speaking of C code, it's not quite so bad as it looks to have somewhat fat structs across multiple arrays, since you can fit 64 bytes in a cache line on contemporary desktop CPUs, and that sets your real max-unit-size; the CPU is actively trying to keep the line hot and it does so (in the average case) by speculating that you're going to fetch the next index of the array. Since you have multiple cache lines, you can keep multiple arrays hot at the same time, it's just a matter of keeping it easy to predict fetching behavior by using simple loops that don't jump around...which leads to the pattern parent suggests, of cascading messages or buffers in groups of same type so that you get a few big iterations out of the way, and then a much smaller number of indirected accesses.

[ Parent | on HN ]

Re:Data-oriented design or why you might shoot yourself in t... by volta83 on Monday June 28, 2021 @05:41AM (#27659737)

If you loose vectorization, you might be loosing a 4x, 8x, 16, ... 32x perf difference by organizing your data in such a way that memory operations and data manipulation can't be vectorized.

[ Parent | on HN ]

Re:Data-oriented design or why you might shoot yourself in t... by lasagnaphil on Monday June 28, 2021 @11:15AM (#27662999)

But you usually can't achieve vectorization by just simply changing your data layout, the compiler's auto-vectorization features usually doesn't work that well. SOA or AOSOA layout for vectorization only becomes important when you begin to explicitly write SIMD code in intrinsics or pure assembly.

And explicitly writing in SIMD is quite a hard feat in itself: it's okay when you're accelerating small, simple, and isolated algorithms in hot-code paths, but when you're doing much more complex calculations the time you need to invest in it to make it work goes out of hand pretty quickly.

[ Parent | on HN ]

Re:Data-oriented design or why you might shoot yourself in t... by volta83 on Tuesday June 29, 2021 @04:33AM (#27673331)

> But you usually can't achieve vectorization by just simply changing your data layout, the compiler's auto-vectorization features usually doesn't work that well.

Please don't build a straw man.

You (or the compiler) can't achieve vectorization if you have the wrong data layout. Period.

How easy / hard is for you or the compiler to vectorize something depends on the application.

It can "just work", it might require a one line `pragma simd`, it might require you to use portable `std::simd` types by hands, or use SIMD intrinsics, or write assembly manually.

But none of these are options if you have the wrong data layout.

[ Parent | on HN ]

Re:Data-oriented design or why you might shoot yourself in t... by moldavi on Monday June 28, 2021 @10:24AM (#27662373)

When you say vectorize, are you referring to loop unrolling? Or SIMD or something?

[ Parent | on HN ]

Re:Data-oriented design or why you might shoot yourself in t... by simiones on Monday June 28, 2021 @10:37AM (#27662563)

I have never heard vectorization to refer to anything other than SIMD. Loop unrolling is usually only a useful technique to enable SIMD, as far as I know (at least on modern processors, where branch prediction has greatly decreased the cost of jump instructions).

[ Parent | on HN ]

Re:Data-oriented design or why you might shoot yourself in t... by jhgb on Monday June 28, 2021 @12:14PM (#27663753)

> as far as I know (at least on modern processors, where branch prediction has greatly decreased the cost of jump instructions).

What about ILP? Can't that benefit from an unrolled loop in some cases? For example if there's a fairly long dependency chain but you might still be able to go through two loop bodies at once instead.

[ Parent | on HN ]

Re:Data-oriented design or why you might shoot yourself in t... by tsimionescu on Monday June 28, 2021 @01:04PM (#27664445)

I don't know for sure at all, but I don't think it's impossible that speculative execution could also achieve the same at the processor level.

[ Parent | on HN ]

Re:Data-oriented design or why you might shoot yourself in t... by jhgb on Monday June 28, 2021 @01:07PM (#27664472)

I don't see how this has anything to do with speculation? In most cases where you care about this you don't have to speculate if all the loop iterations are needed. For example in matrix multiplication all of those iterations will be needed.

[ Parent | on HN ]

Re:Data-oriented design or why you might shoot yourself in t... by tsimionescu on Monday June 28, 2021 @01:20PM (#27664651)

What I'm thinking is that the processor has an instruction stream that looks like this:

  loop: 
    instr_1
    instr_2
    ...
    instr_n 
    jcond loop

Now, assuming the loop is not unrolled, it would need to speculate that `jcond loop` will jump to be able to execute 2 copies of instr_1 in parallel - I'm saying that it may be able to do that, though I am by no means sure.

[ Parent | on HN ]

Re:Data-oriented design or why you might shoot yourself in t... by jhgb on Monday June 28, 2021 @01:25PM (#27664713)

Oh, I see what you mean -- I was talking (and thinking) about the unrolled version so it didn't make sense how speculation could help there. But I imagine that typically the kind of long chains that you might want to do in parallel in a single basic block are perhaps something that wouldn't get executed that far after a branch, if the only purpose is to not waste time after a branch misprediction. Plus from what I understand you'd still be wasting execution units here, just not by idling them but rather by speculating the "I'm done" branch repeatedly.

EDIT: I just found that the idea that I had in my head actually exists and is called "modulo scheduling".

[ Parent | on HN ]