Again my pet ignored language/compiler technology issue goes unmentioned: data layout optimizations.
Control flow and computation optimizations have enabled use of higher level abstractions with little or no performance penalty, but at the same time it's almost unheard of to automatically perform (or even facilitate) the data structure transformations that are daily bread and butter for programmers doing performance work. Things like AoS->SoA conversion, compressed object references, shrinking fields based on range analysis, flattening/dernormalizing data that is used together, converting cold struct members to indirect lookups, compiling different versions of the code for different call sites based on input data, etc.
It's baffling considering that everyone agrees memory access and cache footprint are the current primary perf bottlenecks, to the point that experts recommend considering on-die computation is free and counting only memory accesses in first-order performance approximations.
Jonathan Blow's language "jai" allows for seamlessly switching between AoS and SoA and generally seems to value efficient data layout and "gradual" optimization over safety (in contrast to e.g. Rust).
Unfortunately, no public compiler seems to be available at this time.
I think that's cool, but I would almost say that's like the `const` problem of c++ and the Open System problem. It's a single special keyword. Not a point to extend with arbitrary layouts. It is progress, but a very small step.
AoS is useful for things where you want to effectively have fast (e.g. no cache misses) random access to many fields; the common OO approach. SoA is useful when you want fast iteration across only a couple fields of many objects; the common simulation loop approach. Effectively what Jai allows is deciding which to use when you declare a chunk of memory.
A lot of concerns I have can all theoretically be fixed in user space, on the other hand the same can be said for any language, and hence sort of defeats the purpose of a keyword. The point of the keyword is that it can inspect the fields of a type and decide how many arrays of what size to allocate. Here are some issues which would be annoying to implement in user space with AoS/SoA being merely an orthogonal keyword (e.g. limited operator overloading and without Turing Complete templates or macros):
* Alignment and padding so certain fields can be loaded into specific registers. This effects the layout of memory differently in each mode.
* Multiple buffers for some fields. A heavily used field (say position) could have a number of buffers which are rotated in SoA mode (e.g. render-posistions, last-frame-step, next-frame-step; allowing for reader/writer systems), and are simply an array of fields in AoS mode. Where as other fields retain their singular arity.
* Concurrency concerns. Partitioning arrays in SoA so cores don't fight over the lower caches. Aligning AoS on cache lines so whole objects can be locked at once without causing cache problems with neighboring objects.
* Sparse fields. If a field is generally empty, space is still allocated for it (e.g. in SoA using a dictionary rather than an array), or a cache miss due to usage of a pointer.
* But to answer the actual question it comes down to data structures: If I wanted to iterate across objects in an arbitrary quad-tree node and it's children, there are efficient ways to layout memory so that that and similar useful operations are fast (e.g. minimal cache misses). Yes I could put the data-structure in a different array but then I am looking up values in the data array randomly (e.g. cache misses). Many useful data structures have efficient systems for laying out their values and their structure in the same memory.
To elaborate on the last one more, maybe I have a structure that has 4 fields, two are keys that can be structured (e.g. string name, and x,y pos), and two are are actual data members. Regardless of `AoS` or `SoA`, I would have to write custom data structures to maintain string (trie) and pos2 (quad tree) indices, that would also be doing slow lookups. Alternatively, if I could set the layout of an array to `Trie.name` (Trie using name field) I would be saying, layout this container to be as fast as possible (e.g minimal cache misses) for string based lookups by making it the primary layout, without having to change any code that uses it (you could even go the next step with something like: `SoA | Trie.name | QuadTree.pos` to allow reordering a single line of code to effect the performance of all code referencing it, but for the semantics of the line to act like normal bit flags).
tl;dr: Think database indices on columns, but improving runtime performance by rearranging the data itself into the index so as to better fit the algorithm and CPU requirements (e.g. rather than more abstract decisions in databases, where the model of a piece of hardware isn't usually a concern).
I mean I'm not worrying about it at that level, just that it's something relevant to the idea of layout. C++'s templates are a powerful language feature for doing layout optimization however, and it's sort of the thing to beat in power.
Yes, there's a little research about it out there, but the industry side seems to be in deeper apathy about it.
It would be very interesting to hear what happened to these LLVM research directions. I guess the default answer is "nobody wanted to fund it after the publications got written"...
It might just be timing. 2004 was when everyone was switching from Java and C++ to Perl, PHP, Python, and Ruby. Hard to make a case for a compiler optimization that might save 10x on a couple percent of workloads when everybody a.) is focused on the workloads that it's not useful for and b.) is using languages that give up 30x performance from the beginning.
Things may be different now that Moore's Law no longer holds and many programs are cache-bound, but any current research also needs to take into account GPUs, distributed computing, and deep learning. There might be room for new research, but the research would likely be as much about auto-vectorization and minimizing trips between memory spaces as about local optimizations like AoS -> SoA conversion.
Isn't C the worst language to do this in? Because a lot of C programs contain their own implicit data layout, which can't be violated without breaking the program.
Contrast with Scala where the programmer doesn't have the ability to reason about memory AFAIK:
http://halide-lang.org/ should be much better known than it is. It has programmer-specified optimizations and data layout separated from algorithm definitions.
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.
Memory layout should be library/protocol. Look at the gigawatt hours that have been spent on serialization, and the resulting work one has to put into having a serialization-free format like Capnproto. The heap should be like a well formed database and those accessors should be portable across languages and systems.
One should be able to specify a compile time macro that controls memory layout.
These are mainly implementation level optimizations, not language-level improvements. i.e. You could easily build two compiler respecting a language spec, with and without these optimizations.
If only it were so. Sadly there are many semantics in many/most current languages that make these optimizations difficult to implement while guaranteeing compliance.
More generally, the history of computing is littered with remains of plans involving "this can work, assuming we build a sufficiently smart compiler..." - you really need a language that is proactively friendly to these concepts to make the implementation straightforward and robust so language users can lean on it.
I think you may be talking past each other? I think the sort of thing the falafel is referring to is the problem of data-locality.
Let's say I have a Vec<User>. Perhaps it would be more efficient to have a tuple of: Vec<User::Name>, Vec<User::Address>, Vec<User::Siblings>...
That is, can we design a language where the fields of a type can be analyzed by a container, and deconstructed to be able to implicitly reconstitute an object from its fields?
This is what entity component systems try to do, but some of it can be clumsy, and you have to build these entities and components with the system at the beginning. Could we achieve more if we baked some of this into the language and allowed more "introspective" generic types?
Edit: Here's a trivial example of an optimization that could be possible. In systems like C#'s LINQ, or JavaScript's lodash, we might sometimes like to take a set of objects and group them by a key. So we do listOfThings.GroupBy(x => x.key). Why do we need to store the full "x" and the key separately? Or if we, in a subsequent step, return a sum over a field, could we intelligently remove the data shuffling of all the other fields, and construct an intersection-type consisting of only the fields we care about?
That's what a relational database does. Most of those things can be done in SQL. You can add indices after creating a table. You can join tables and create derived data.
Unless you are talking about a column-store, most SQL databases fall to the same criticism; they are row-oriented with poor data locality.
Using column-oriented data is more that just a storage decision. It affects other parts of the language and especially your thought process and how you use the language.
Anybody who has used systems that are column (SoA) oriented understands this. And those that haven't all see to not understand how much it changes things.
It is not what a relational database does (see another's reply on row-oriented vs column-oriented storage), but you miss the fact that this is fundamental for data locality in an application.
It depends a bit on how much sugar you'd like, but it isn't too hard to get Rust to spin things around for you. Here are two implementations, depending on what you need (resp, for serialization, vs traversal). YMMV.
Control flow and computation optimizations have enabled use of higher level abstractions with little or no performance penalty, but at the same time it's almost unheard of to automatically perform (or even facilitate) the data structure transformations that are daily bread and butter for programmers doing performance work. Things like AoS->SoA conversion, compressed object references, shrinking fields based on range analysis, flattening/dernormalizing data that is used together, converting cold struct members to indirect lookups, compiling different versions of the code for different call sites based on input data, etc.
It's baffling considering that everyone agrees memory access and cache footprint are the current primary perf bottlenecks, to the point that experts recommend considering on-die computation is free and counting only memory accesses in first-order performance approximations.