I've been thinking about this for the last few years. What would an APL-like language look like with structured data? Is that possible? Could you make a language where you specify if a value is SoA or AoS? Is it possible to automatically convert an AoS-based algorithm to SoA?
It really changes how you do basic things like sorting. In the standard AoS approach in C-like languages you swap entire structures around the array. In an SoA approach in APL-like languages you generate a list of indices that would put the data in sorted order then apply it to each column. A number of times I written code to do this in C++ for high-performance systems, and it works great, but is definitely a different way of thinking about things.
IIRC there was a proof of concept for a Rust compiler plugin where you could switch between SoA/AoS via a single annotation on the struct. I can't remember the extent to which that impacted algorithms though.
That's the sort of thing where you want to feed profiling data back into the compiler. Intel used to be big on that, mostly for branch prediction. Itanium needed the most likely path chosen at compile time.
You could do a fairly straightforward conversion but it would be terribly slow for many things.
Take the sorting example i gave. In a column-oriented program you would generate a list of indices and apply them to each column. That has very good cache locality as you work on each independently. Also you tend to manipulate that index list instead of the data and after all is done, filtered, and whatever then apply it to the data.
If you did things the AoS way you would be bouncing around in memory going from column to column.
Dealing with SoA and column orientated data is more than just a storage decision.
You could do a fairly straightforward conversion but it would be terribly slow for many things.
Is there a non-straightforward conversion that isn't? It seems to me like any SoA->AoS transformation is going to have pretty much the same effect on locality.
> It seems to me like any SoA-AoS transformation is going to have pretty much the same effect on locality
Not at all. In a SoA system you want to operate on each attribute individually but on an AoS system you operates across structs. Besides improved cache locality it keeps loops small so they operate out of the iop loop/stream cache among other things like better packing off data etc.
If you haven't worked on a system little this sometimes it can be difficult to see how different things can be. It's literally APL vs C.
It really changes how you do basic things like sorting. In the standard AoS approach in C-like languages you swap entire structures around the array. In an SoA approach in APL-like languages you generate a list of indices that would put the data in sorted order then apply it to each column. A number of times I written code to do this in C++ for high-performance systems, and it works great, but is definitely a different way of thinking about things.