AoAoAoTT

AoAoAoTT provides AoS and SoA containers interchangeable between each other in terms of interfaces.

More details are discussed in this talk (in Russian): Interchangeable AoS and SoA containers, C++ Russia 2021.

Motivation

Array of Structures and Structure of Arrays are two ways to arrange a sequence of records in computer memory. Whereas SoA is more friendly with SIMD instructions and data prefetching, AoS usually utilizes spatial and temporal locality of CPU caches. Therefore, choose of the most performing data representation can hardly be theoretically proven, and the meainingful results may be obtained only by a quantative measurement.

However, arrangement of the experiment is laborious, as most of the programming languages natively support only AoS structures, and SoA versions of algorithms has to be made from scratch.

AoAoAoTT simplifies the process for C++. The basic idea is to keep the data structures as they were defined by programmer, and touch only containers and access to them.

Example

Consider the following simple example of AoS:

struct SomeDataStructure {
    std::array<char, 256> key;
    int value;
    int previous_value;
};

std::array<SomeDataStructure, 10000> storage;

int find_value(int value_to_find) {
    for (const auto& e : storage)
        if (e.value == value_to_find)
            return i;
    return -1;
}

Now you want to check whether SoA performs better. With AoAoAoTT, you have to do two simple steps: replace std::array by aoaoaott::Array and access members with the magical ->* operator instead of common ..

+#include <aoaoaott.hpp>
+using namespace aoaoaott;

-std::array<SomeDataStructure, 10000> storage;
+SoAArray<SomeDataStructure, 10000> storage;

 int find_value(int value_to_find) {
     for (const auto& e : storage)
-        if (e.value == value_to_find)
+        if (e->*(&SomeDataStructure::value) == value_to_find)
            return i;
    return -1;
}

Imagine that for some reason SoA did not perform well and you want to rollback to AoS to make more accurate measurements. That would be very simple: just substitute SoA container by fully interface-compatible AoS.

-SoAArray<SomeDataStructure, 10000> storage;
+AoSArray<SomeDataStructure, 10000> storage;

With some macro or SFINAE helpers you would be able to change the arrangement easily, e.g. from the command line.

Summary

To sum up, let's enumerate the basic principles of AoAoAoTT design:

1. Input structures should not be specially prepared.
2. Interfaces for AoS and SoA containers are perfectly matched.
3. AoS and SoA containers provide STL-like interfaces (iterators, begin/end, ranges etc.)
4. Minimal dependencies: header-only Boost and C++17 STL.

---

Supported interfaces

Four containers are provided along with element facade objects and iterators: SoAVector, AoSVector, SoAArray, SoAVector; Both AoS and SoA container mimic well-known behavior of std::vector and std::array:

• Construction and fill: AoS<Structure> storage(20), storage_init(20, Structure(42));
• Assignment LHS: storage[index] = construct_some_structure()
• Assignment RHS: some_structure = storage[index]
• Full support of random access iterators

Vector specific operations:

• Resize: storage.resize(30, Structure(42))
• Push back: storage.push_back
• Capacity, reserve, and shrink-to-fit.

However, access to elements is performed with magic operators:

• Constexpr element access: storage[index].get<&Structure::field>()
• Elegant element access: storage[index]->*(&Structure::field)
• Aggregate and call a method: storage[index].method<&Structure::update>(param1, param2)
• Elegant lambda call: (storage[index]->*(&Structure::update))(param1, param2)

The best and the most actual reference is provided by unit tests.

---

Known limitations

Consider using Rule of Zero structures

That has a reason: how would you adjust copy methods, move methods, or destructors if the fields are distributed all around the memory? For example:

   struct Point1 {
       int x, y;
       int *z;
       ~Point1() { delete z; }
   };

One you move the object to SoA, C++ will consider it dead and call the destructor. Data is lost!

However, we cannot forbid anything which is not is_trivially_.... Consider an example of Rule of Zero structure:

   struct Point2 {
       int x, y;
       std::unique_ptr<int> z;
   };

While this class has a non-trivial destructor, it has no issues with SoA, because unique_ptr will be moved correctly.

Aggregation is costly

Similarly to the one above, you cannot run storage[i].some_method. Instead, AoAoAoTT provides an interface to aggregate a structure to stack, call a method, and dissipate it back. Obviously, these operations have overheads.

• Q: Can dissipation be explicitly bypassed if a method is const-qualified?
• A: No. Structure may contain mutable fields, and we must update them as well.

C-style arrays are not supported

You cannot assign a structure with C-style array to SoA container:

   struct Example {
       char array[128];
   };
   SoA<Example> storage(1, Example()); // Does not work;

However, you can use std::array without any problems:

-       char array[128];
+       std::array<char, 128> array;

Inherited structures are not supported

To decompose data structure, we use PFR mechanism which does not support inherited structures at the moment. The issue is described in PFR docs.

Padding bytes are not supported

Since C++ reflection capabilities are very low, support of padding bytes cannot be provided at the moment. However, if people care about SoA data representation, one might consider they have already handled padding bytes wisely.

One more obvious case is empty structures: they have a single padding byte, and that's why they could not be stored to AoAoAoTT storages.

Packed structures are not supported

It is a undocumented restriction of PFR.

Booleans are not supported in SoAVector

As you may guess, it is a result of STL-incompliance of std::vector<bool>.

---

Impact

• C++Russia 2021 talk.
• LLVM bug reported: llvm-project/llvm#52617.
• Few ideas for C++ standard: cpp-ru/ideas#482, cpp-ru/ideas#484, cpp-ru/ideas#529

Further reading

• Nomad Game Engine: Part 4.3 — AoS vs SoA by Niko Savas — nice demonstration of SoA advantages.
• Example of AoS outperforming SoA by Paul R
• The C++ Type Loophole (C++14) by Alexandr Poltavsky — explanation of Loophole compile-time reflection, the core code of AoAoAoTT.

Thanks

• Paolo Crosetto for his inspiring SoAvsAoS implementation
• Alexandr Poltavsky for public domain implementation of Loophole and Type List
• Antony Polukhin and contributors for Boost.PRF
• Timur Safin and Alexey Klimkin for reviewing C++ Russia 2021 talk.
• @Fuyutsubaki for elegant pointer-to-member to index converter
• Alexandr Titov for assistance with benchmarking