4 ms·

I assume that we want to access these arrays as "array of structs" for most functions but as "structure of arrays" for some calculation intensive functions. The

I assume that we want to access these arrays as "array of structs" for most functions but as "structure of arrays" for some calculation intensive functions. The article suggests storing it as array of structs and to make copies for those calculations but this seems inefficient to me. Modern C++ should provide a way to efficiently decouple the access model from the memory layout. Can we hide the actual memory layout without big overhead using C++ inline/template functions/classes? Would that be the visitor pattern?

mamcx 7y ago
> Modern C++ should provide a way to efficiently decouple the access model from the memory layout. I try a lot to make a "array of structs" and also"structure of arrays" for my own little relational language in rust. Is just not possible (that I know). At best, you could store as packed arrays or arrays of arrays then at runtime static dispatch them. P.D: Or generate code for both. Anyway is not easy to build... the OPTIMAL algorithms for both cases diverge enough.
- BubRoss 7y ago
  ISPC, Halide and the unreleased Jai all have ways of doing this.
  - mamcx 7y ago
    Is explained how them do it?
a_t48 7y ago
IIRC this was something JAI was trying to do.
- DiseasedBadger 7y ago
  I think that was just refactoring tools.
  - dkersten 7y ago
    I’m pretty sure Jai has (or at least did when I last looked) a type modifier keyword that changes the layout (the code working with it doesn’t change)
    - dymk 7y ago
      It should based on livestreams, but details on Jai are so far and few between, it's hard to say
      - dkersten 7y ago
        Yeah, my comment was based on some old fan-made documentation and the latest live streams I've seen where he talked about it (which was a good many months ago now, but it certainly seemed like its supported)
- lasagnaphil 7y ago
  I've heard in one of his videos that Jonathan Blow ditched the AOS -> SOA conversion feature, but he may come back to the idea sometime later. (One problem with Jai is that unless you are viewing his Youtube videos regularly, you cannot catch up on what is going on with the language...)
  - a_t48 7y ago
    That's unfortunate.
pavlov 7y ago
I don't think the article is suggesting ever making temporary copies of data into a structure-of-arrays (SOA) format. Rather the choice should be made at design time and you write your code accordingly for those parts that deal with SOA data. The author's advice is that you should go with the standard array-of-structures (AOS) format by default, but if you know you'll be doing number crunching, use an "unrolled by eight" grouped SOA format that's both SIMD- and cache-friendly.
- std_throwaway 7y ago
  FTA: "Another thing I might consider is to keep the data stored at AoS, but generate temporary SoA data for processing by some algorithm."
  - pavlov 7y ago
    Missed that, thanks!
plopz 7y ago
Doesn't the memory layout actually matter for cache locality? So you would still need to be able to have both memory layouts for performance.
- std_throwaway 7y ago
  Cache locality is kind of the whole point of it. Some algorithms benefit hugely if you choose a specific layout. Other algorithms do some kind of random access to a few fields only and they don't benefit at all. Those algorithms can make up 90% of your code but only account for 10% of the computation. Therefore it would be easier to have your data look like a AoS in 90% of your code but actually be stored as a SoA to gain the speed in 90% of the computation.
- hermitdev 7y ago
  Most definitely. If, for example you've got a vector of structs (which is a basic tabular store, that is row major). Depending on the operations you're performing, you may see huge performance benefits from instead using a column oriented data structure. Especially with very large datasets. A large part of this because of cache locality and prefetch. I see this in finance often. For querying large, slowly changing datasets, column store RDBMS destroy traditional row oriented stores. Column stores can be colloquially an order of magnitude faster for some operations, such as computing aggregates grouped by a date (but theyre significantly much slower for inserts and even more so for updates). As usual, when it comes down to optimizations, depends on the use case, and experiment and measure, measure, measure. Also, another big caveate is that it can change arbitrarily with different hardware or even OS revisions. Edit: spelling
tom_mellior 7y ago
> Can we hide the actual memory layout without big overhead using C++ inline/template functions/classes? This seems to claim to do it: https://github.com/crosetto/SoAvsAoS https://github.com/crosetto/SoAvsAoS Found that while looking for this, which I vaguely knew about and which also seems to do that: https://m-sp.org/downloads/cgo2018-src-poster.pdf https://m-sp.org/downloads/cgo2018-src-poster.pdf
jonv98 7y ago
> make copies for those calculations but this seems inefficient to me I haven't read the whole article, but this "make copies of elements from an array into another array for the current frame only" is common in game development. Remember that on modern CPUs, an L3 miss is about 200x slower than an L1 hit. RAM isn't random access: randomly jumping around is slow, but iterating over an array is fast, both because of the cache and because of pre-fetching. Say you have a big array of A's, and another big array of B's. For the current frame, some of the A's need to interact with some of the B's. If you go through the entire list of B's, and copy the ones that will definitely need to interact into a new list, call it B2, then maybe (or not) do the same with the A's into A2, then it can often be approximately 30 times faster. Multiply that by 4 (or 8) if you can "zip" through your A2's and B2's with SIMD. Not only that, but your A2 and B2 lists can be put on a stack allocator (nothing to do with allocating on the stack - it's a special type of O(1) heap allocator whose contents are discarded at the end of each video frame).
- std_throwaway 7y ago
  Copying is fast if the access pattern is a good fit for the CPU architecture. If you need to copy only every N-th byte from a AoS it might be as inefficient as random access. So, copying could be expensive. The article suggests striping your data in blocks but then you end up with the worst of both worlds in terms of program code complexity.
kllrnohj 7y ago
> Can we hide the actual memory layout without big overhead using C++ inline/template functions/classes? Not super easily because the array type needs to know the fields of the class it's containing to do the re-write. This is where you need more substantial codegen to enter the picture. Something like the metaclasses proposal should handle it just fine. Or macros in the meantime.
- gpderetta 7y ago
  I posted this elsethread: https://godbolt.org/z/rBeWOA https://godbolt.org/z/rBeWOA But yes, better reflection is needed to make it truly generic.
mhh__ 7y ago
Do you mean switching the memory layout depending on runtime conditions or just changing the software interface to a constant (shape) block of memory?
daemin 7y ago
This sounds like you want to use ranges, which were introduced in C++20 and quite a few game developers found them too complicated. The way I see it to store your data in whatever is the most efficient form for your computations to use, and use a simple view for those functions. Then for functions which need to look at the data in another form you use more complicated views which can abstract some of the data layout for you and make it simpler to manipulate. Unfortunately I can see some people decrying this sort of code as too complex and complicated, but I think it can be made to work rather well.

mamcx 7y ago

> Modern C++ should provide a way to efficiently decouple the access model from the memory layout. I try a lot to make a "array of structs" and also"structure of arrays" for my own little relational language in rust. Is just not possible (that I know). At best, you could store as packed arrays or arrays of arrays then at runtime static dispatch them. P.D: Or generate code for both. Anyway is not easy to build... the OPTIMAL algorithms for both cases diverge enough.

BubRoss 7y ago
ISPC, Halide and the unreleased Jai all have ways of doing this.
- mamcx 7y ago
  Is explained how them do it?

a_t48 7y ago

IIRC this was something JAI was trying to do.

DiseasedBadger 7y ago
I think that was just refactoring tools.
- dkersten 7y ago
  I’m pretty sure Jai has (or at least did when I last looked) a type modifier keyword that changes the layout (the code working with it doesn’t change)
  - dymk 7y ago
    It should based on livestreams, but details on Jai are so far and few between, it's hard to say
    - dkersten 7y ago
      Yeah, my comment was based on some old fan-made documentation and the latest live streams I've seen where he talked about it (which was a good many months ago now, but it certainly seemed like its supported)
lasagnaphil 7y ago
I've heard in one of his videos that Jonathan Blow ditched the AOS -> SOA conversion feature, but he may come back to the idea sometime later. (One problem with Jai is that unless you are viewing his Youtube videos regularly, you cannot catch up on what is going on with the language...)
- a_t48 7y ago
  That's unfortunate.

pavlov 7y ago

I don't think the article is suggesting ever making temporary copies of data into a structure-of-arrays (SOA) format. Rather the choice should be made at design time and you write your code accordingly for those parts that deal with SOA data. The author's advice is that you should go with the standard array-of-structures (AOS) format by default, but if you know you'll be doing number crunching, use an "unrolled by eight" grouped SOA format that's both SIMD- and cache-friendly.

std_throwaway 7y ago
FTA: "Another thing I might consider is to keep the data stored at AoS, but generate temporary SoA data for processing by some algorithm."
- pavlov 7y ago
  Missed that, thanks!

plopz 7y ago

Doesn't the memory layout actually matter for cache locality? So you would still need to be able to have both memory layouts for performance.

std_throwaway 7y ago
Cache locality is kind of the whole point of it. Some algorithms benefit hugely if you choose a specific layout. Other algorithms do some kind of random access to a few fields only and they don't benefit at all. Those algorithms can make up 90% of your code but only account for 10% of the computation. Therefore it would be easier to have your data look like a AoS in 90% of your code but actually be stored as a SoA to gain the speed in 90% of the computation.
hermitdev 7y ago
Most definitely. If, for example you've got a vector of structs (which is a basic tabular store, that is row major). Depending on the operations you're performing, you may see huge performance benefits from instead using a column oriented data structure. Especially with very large datasets. A large part of this because of cache locality and prefetch. I see this in finance often. For querying large, slowly changing datasets, column store RDBMS destroy traditional row oriented stores. Column stores can be colloquially an order of magnitude faster for some operations, such as computing aggregates grouped by a date (but theyre significantly much slower for inserts and even more so for updates). As usual, when it comes down to optimizations, depends on the use case, and experiment and measure, measure, measure. Also, another big caveate is that it can change arbitrarily with different hardware or even OS revisions. Edit: spelling

tom_mellior 7y ago

> Can we hide the actual memory layout without big overhead using C++ inline/template functions/classes? This seems to claim to do it: https://github.com/crosetto/SoAvsAoS https://github.com/crosetto/SoAvsAoS Found that while looking for this, which I vaguely knew about and which also seems to do that: https://m-sp.org/downloads/cgo2018-src-poster.pdf https://m-sp.org/downloads/cgo2018-src-poster.pdf

jonv98 7y ago

> make copies for those calculations but this seems inefficient to me I haven't read the whole article, but this "make copies of elements from an array into another array for the current frame only" is common in game development. Remember that on modern CPUs, an L3 miss is about 200x slower than an L1 hit. RAM isn't random access: randomly jumping around is slow, but iterating over an array is fast, both because of the cache and because of pre-fetching. Say you have a big array of A's, and another big array of B's. For the current frame, some of the A's need to interact with some of the B's. If you go through the entire list of B's, and copy the ones that will definitely need to interact into a new list, call it B2, then maybe (or not) do the same with the A's into A2, then it can often be approximately 30 times faster. Multiply that by 4 (or 8) if you can "zip" through your A2's and B2's with SIMD. Not only that, but your A2 and B2 lists can be put on a stack allocator (nothing to do with allocating on the stack - it's a special type of O(1) heap allocator whose contents are discarded at the end of each video frame).

std_throwaway 7y ago
Copying is fast if the access pattern is a good fit for the CPU architecture. If you need to copy only every N-th byte from a AoS it might be as inefficient as random access. So, copying could be expensive. The article suggests striping your data in blocks but then you end up with the worst of both worlds in terms of program code complexity.

kllrnohj 7y ago

> Can we hide the actual memory layout without big overhead using C++ inline/template functions/classes? Not super easily because the array type needs to know the fields of the class it's containing to do the re-write. This is where you need more substantial codegen to enter the picture. Something like the metaclasses proposal should handle it just fine. Or macros in the meantime.

gpderetta 7y ago
I posted this elsethread: https://godbolt.org/z/rBeWOA https://godbolt.org/z/rBeWOA But yes, better reflection is needed to make it truly generic.

mhh__ 7y ago

Do you mean switching the memory layout depending on runtime conditions or just changing the software interface to a constant (shape) block of memory?

daemin 7y ago

This sounds like you want to use ranges, which were introduced in C++20 and quite a few game developers found them too complicated. The way I see it to store your data in whatever is the most efficient form for your computations to use, and use a simple view for those functions. Then for functions which need to look at the data in another form you use more complicated views which can abstract some of the data layout for you and make it simpler to manipulate. Unfortunately I can see some people decrying this sort of code as too complex and complicated, but I think it can be made to work rather well.