soagen: Structure-of-Arrays for C++

TL;DR

The leading section of this page is an overview of what Structures-of-Arrays (SoA) are, what problems they solve, and the annoyances of working with them in C++. Following that is an overview of soagen - a new Structure-Of-Arrays library and generator for C++17 and later.

Skip to Introducing soagen if you already know all about SoA and want to go straight to learning about soagen instead.

Motivation

struct employee
{
    unsigned id;
    std::string name;
    std::tuple<unsigned short, unsigned char, unsigned char> dob;
    int salary;
    // ... plus a bunch more
};

std::vector<employee> all_employees;

struct entity
{
    unsigned id;
    std::string name;
    vec3 pos;
    quaternion orient;
    // ... and so on
};

std::vector<entity> all_entities;

struct entities
{
    std::vector<unsigned> id;
    std::vector<std::string> name;
    std::vector<vec3> pos;
    std::vector<quaternion> orient;
    // ... and so on
};

Introducing soagen

I'd to present my solution to the problems of working with Structure-of-Arrays in C++: soagen. Soagen is fundamentally two things:

1. soagen, a command-line code utility for generating bespoke std::vector-like SoA containers, and
2. soagen.hpp, a single-header backing library upon which the generated code depends.

If you have no interest in using a command-line tool to generate SoA classes and instead want to build your own using soagen.hpp directly, skip to Creating your own SoA types without the generator.

Typically you only need to use the command-line tool soagen, and don't need to know anything about soagen.hpp beyond "this needs to be on my include path somewhere" (since it's largely an implementation detail). You may need to learn more about the backing library if you're doing more advanced stuff, but we'll cover that later.

I'll go over how to use soagen, and the code it generates, by demonstrating how to we'd use it to create a nice SoA version of the entity class described above.

I stylize the name as 'soagen' (all lowercase), only capitalizing the S when it's the first word in a sentence, but I don't feel strongly about it. Render it however you like, I'm not fussed. SoAgen, Soagen, SOAgen, whatever.

Getting started

> pip install soagen

> soagen --help

usage: soagen [-h] [-v] [--version] [--install <dir>] [--werror | --no-werror]
              [--color | --no-color] [--clang-format | --no-clang-format]
              [--doxygen | --no-doxygen] [--natvis | --no-natvis] [--bug-report]
              [configs ...]

  ___  ___   __ _  __ _  ___ _ __
 / __|/ _ \ / _` |/ _` |/ _ \ '_ \
 \__ \ (_) | (_| | (_| |  __/ | | |
 |___/\___/ \__,_|\__, |\___|_| |_|
                   __/ |
                  |___/   v0.7.0 - marzer.github.io/soagen

Struct-of-Arrays generator for C++ projects.

positional arguments:
  configs               zero or more .toml files describing your structures-of-arrays
                        (wildcards are accepted, e.g. soa/*.toml)

options:
  -h, --help            show this help message and exit
  -v, --verbose         enable very noisy diagnostic output
  --version             print the version and exit
  --install <dir>       install soagen.hpp into a directory
  --werror, --no-werror
                        treat warnings as errors (default: False)
  --color, --no-color   use colors in terminal output (default: True)
                        (the British spelling "colour" is also accepted)
  --clang-format, --no-clang-format
                        attempt to run clang-format on generated code (default: True)
  --doxygen, --no-doxygen
                        include doxygen markup in the generated code (default: False)
  --natvis, --no-natvis
                        generate .natvis files for Visual Studio (default: True)
  --bug-report          capture all inputs and outputs in a bug-report zip file

Creating an SoA container class

soagen creates the output XXXX.hpp next to each XXXX.toml input you pass in. Given a game engine project with a fairly standard file structure:

docs/
include/
    quaternion.hpp
    vector.hpp
    ...
src/
README.md
... etc

...if we want entities.hpp to end up in src/ because it's an implementation detail, then that's where the soagen configuration file entities.toml should go, too. Let's create src/entities.toml and populate it thus:

namespace = 'game'

[structs.entities]
variables = [
    {name = 'id',     type = 'unsigned' },
    {name = 'name',   type = 'std::string', default = '""' },
    {name = 'pos',    type = 'vec3',        default = '{}' },
    {name = 'orient', type = 'quaternion',  default = '{1, 0, 0, 0}' },
]

There are many more options in the Config Schema but for now we'll just stick with the basics.

Now run soagen:

> soagen src/*.toml

soagen v0.7.0
Reading src/entities.toml
Running clang-format for src/entities.hpp
Writing src/entities.hpp
Writing src/entities.natvis
All done!

We now have src/entities.hpp containing the definition of game::entities, a std::vector-like SoA container class (here's the documentation if you'd like to see the API).

Our project now looks like this:

docs/
include/
    quaternion.hpp
    vector.hpp
src/
    entities.hpp     <
    entities.natvis  <----- new
    entities.toml    <
README.md

Installing soagen.hpp

Inspecting the contents of entities.hpp, we see that right near the top it expects to be able to #include <soagen.hpp>. This means we need to 'install' it somewhere. The command-line utility is responsible for that, too:

> soagen --install src

soagen v0.7.0
Copying soagen.hpp to src
All done!

Our project now looks like this:

docs/
include/
    quaternion.hpp
    vector.hpp
src/
    entities.hpp
    entities.natvis
    entities.toml
    soagen.hpp    <----- new
README.md

You can also combine the source generation and install steps in the same command invocation:

> soagen src/*.toml --install src

This is the same as doing them both separately.

Configuring #includes

Taking another look at the contents of entities.hpp, we see that soagen has detected the use of std::string in the class interface and automatically added #include <string> for us. This will work for most standard library types (please file a bug report if not!), but not for types specific to our codebase. This means that we'd need to add an #include to make the vec3 and quaternion types visible. Fortunately soagen knows how to do that.

Assuming that these math types live in include/vector.hpp and include/quaternion.hpp, and include/ is configured as one our include paths in our project build system, then we need to add the following to our entities.toml:

[hpp]
includes.internal = [
    'vector.hpp',
    'quaternion.hpp'
]

After regenerating entities.hpp we'll see this:

#include "vector.hpp"
#include "quaternion.hpp"

Now the compiler will be happy and we can start writing some code :)

A brief aside: terminology

From here down there will be a slight change in terminology:

Adding rows

Now then, lets do what we came here to do: stick entities in our new container! Tables have all the same insertion operations as std::vector, only with multiple parameters:

// assuming you have #included "entities.hpp" somewhere:

game::entities e;

// push_back works as you'd expect
e.push_back(0, "foo", {0,0,0}, {1,0,0,0});

// it will also take advantage of the defaults
// we specified in the config, allowing us to elide
// some initializers:
e.push_back(1, "bar");

// insert has the same semantics too
e.insert(e.end(), 2, "qux", {1,2,3});

// ... but can also take a size_type as the position
// argument, not just iterators
e.insert(e.size(), 3, "kek");

for (auto&& row : e)
    std::cout << row.id << ": " << row.name << "\n";

0: foo
1: bar
2: qux
3: kek

We also have emplace() and emplace_back() just like std::vector, but there's a catch: the std::vector versions are variadic to allow for constructing a single value with any number of constructor arguments. Since we have multiple values per row, there's no way we can have a variadic emplace()/emplace_back() that somehow deduces which arguments go to which values. We need to add an extra level of indirection for that:

using soagen::emplacer;

// emplacer is fast + lightweight - doesn't make any copies
e.emplace_back(4, emplacer{ 10, 'A' }, vec3{0,0,0}, quaternion{1,0,0,0});

// other tuple-like types are fine;
// defaults work here too
e.emplace_back(5, std::tuple{ 10, 'B' });

for (auto&& row : e)
    std::cout << row.id << ": " << row.name << "\n";

0: foo
1: bar
2: qux
3: kek
4: AAAAAAAAAA
5: BBBBBBBBBB

You're not limited to manually enumerating all the arguments when you call emplace_back() and emplace() - you can also unpack any type that implements the tuple protocol to describe the whole row at once:

e.emplace_back(6, std::tuple{ "CCCCCCCCCC", vec3{0,0,0}, quaternion{1,0,0,0} });

// nesting tuples works too!
e.emplace_back(7, std::tuple{ "DDDDDDDDDD", std::tuple{0,0,0}, quaternion{1,0,0,0} });

for (auto&& row : e)
    std::cout << row.id << ": " << row.name << "\n";

0: foo
1: bar
2: qux
3: kek
4: AAAAAAAAAA
5: BBBBBBBBBB
6: CCCCCCCCCC
7: DDDDDDDDDD

Removing rows

Soagen tables support pop_back(), erase() and resize() just like std::vector, and also unordered_erase() for fast erasure when order doesn't matter:

// erase CCCCCCCCCC and DDDDDDDDDD - pop_back takes a 'num' param
e.pop_back(2);

// erase BBBBBBBBBB
e.pop_back();

// erase AAAAAAAAAA
e.erase(e.end() - 1);

// erase kek (erase() also supports size_type)
e.erase(e.size() - 1);

// erase foo quickly using swap-and-pop:
e.unordered_erase(e.begin());

for (auto&& row : e)
    std::cout << row.id << ": " << row.name << "\n";

2: qux <---- this was moved here by unordered_erase()
1: bar

Capacity

Soagen tables have capacity(), max_capacity(), reserve(), and shrink_to_fit() as you'd expect:

std::cout << "size: " << e.size() << "\n";
std::cout << "capacity: " << e.capacity() << "\n\n";

e.reserve(100);
std::cout << "size: " << e.size() << "\n";
std::cout << "capacity: " << e.capacity() << "\n\n";

e.shrink_to_fit();
std::cout << "size: " << e.size() << "\n";
std::cout << "capacity: " << e.capacity() << "\n\n";

size: 2
capacity: 6

size: 2
capacity: 100

size: 2
capacity: 2

Working with columns

Recall that our table has four columns:

• id: unsigned
• name: std::string
• pos: vec3
• orient: quaternion

Since we don't have just one element type like a std::vector, we don't access these via data() - you use their names! Each returns a pointer to their respective column's data:

for (std::size_t i = 0; i < e.size(); i++)
    std::cout << "id " << i << ": " << e.id()[i] << "\n";

for (std::size_t i = 0; i < e.size(); i++)
    std::cout << "name " << i << ": " << e.name()[i] << "\n";

// ...and so on

id 0: 2
id 1: 1
name 0: qux
name 1: bar

Working with rows and iterators

Soagen tables support treating rows as if they were regular AoS structs in their own right via soagen::row. This is what you get from operator[], at(), and by dereferencing soagen::iterators.

Rows have reference semantics; if we retrieve a row from a non-const lvalue reference to our entities table, we'll get a row filled with named lvalue references to the members. For example:

// entities&, operator[]
auto row = e[0];

// fetches an instance of this:
struct row
{
    unsigned& id;
    std::string& name;
    vec3& pos;
    quaternion& orient;
};

Similarly, if we took a row from a const-qualified lvalue reference to our entities, we'd get lvalue references to const members:

// const entities&, at():
auto row = std::as_const(e).at(0);

// fetches an instance of this:
struct row
{
    const unsigned& id;
    const std::string& name;
    const vec3& pos;
    const quaternion& orient;
};

Same applies for rvalues:

// entities&&, dereferencing an iterator:
auto row = *(std::move(e).begin());

// fetches an instance of this:
struct row
{
    unsigned&& id;
    std::string&& name;
    vec3&& pos;
    quaternion&& orient;
};

Note that rows don't have to be all-or-nothing; if you want a row view of just two of your members, you can call row() to specify the columns you want:

// columns 0 and 1 of row 0
auto row = e.row<0, 1>(0);

// fetches an instance of this:
struct row
{
    unsigned& id;
    std::string& name;
};

This is true of iterators as well:

auto row = e.begin<0, 1>(0);

Any rows generated by dereferencing the iterator above will only have id and name members.

You can even rearrange the order of the columns if you need to do some swizzling:

auto row = e.row<3,2,1>(0);

// fetches an instance of this:
struct row
{
    quaternion& orient; // column 3
    vec3& pos;          // column 2
    std::string& name;  // column 1
};

Of course, using the raw column indices is quite susceptible to human error (particularly if you change the table members later), so tables all have a columns member enum with named constants for each column:

auto row = e.begin<entities::columns::id, entities::columns::name>(0);

No matter the column configuration, a soagen::row will implement the tuple protocol so you can use it with structured bindings and other fun template stuff:

auto r = e.row<3, 0>();

auto&& [orient, id] = r;

auto&& member_0 = r.get<0>(); // orient
auto&& member_1 = r.get<1>(); // id

auto&& column_0 = r.column<0>();    // id
// auto&& column_1 = r.column<1>(); // ERROR - r doesn't view column 1
// auto&& column_2 = r.column<2>(); // ERROR - r doesn't view column 2
auto&& column_3 = r.column<3>();    // orient

Finally, since rows implement the tuple protocol, you can use them with emplace_back() and emplace():

e.emplace_back(e[0]); // push a copy of row[0] onto the end of the table

Equality

If all the column types implement the named requirement EqualityComparable (i.e. they have operator==), then so too do your tables:

game::entities e1;
game::entities e2;

e1.push_back(0, "cat");

std::cout << (e1 == e2) << "\n";

e2.push_back(0, "cat");

std::cout << (e1 == e2) << "\n";

e1.push_back(1, "dog");

std::cout << (e1 == e2) << "\n";

false
true
false

The same is true of rows; if all of the viewed members are EqualityComparable, then so too are the rows:

std::cout << (e1[0] == e2[0]) << "\n";
std::cout << (e1[0] == e1[1]) << "\n";

true
false

Comparison

Tables are comparable with operators <, <=, > and >= if all their column types implement the named requirement LessThanComparable (i.e. they have operator<). Comparison is done row-wise, with row members compared lexicographically:

game::entities e1;
game::entities e2;

e1.push_back(0, "cat");
e2.push_back(0, "cat");

e1.push_back(1, "dog");
e2.push_back(1, "dog");

std::cout << (e1 <  e2) << "\n";
std::cout << (e1 <= e2) << "\n";
std::cout << (e1 >  e2) << "\n";
std::cout << (e1 >= e2) << "\n\n";

e2[1].name = "bird";

std::cout << (e1 <  e2) << "\n";
std::cout << (e1 <= e2) << "\n";
std::cout << (e1 >  e2) << "\n";
std::cout << (e1 >= e2) << "\n";

false
true
false
true

true
true
false
false

Over-aligning columns

Owing to its very nature, SoA-structured data is often used in contexts where memory alignment is important. One common example is SIMD; you may have a column of floats that need to be aligned on a 16, 32 or 64-byte boundary, according to whatever the minimum instruction set is you're targeting.

Soagen has support for this without you needing to come up with custom allocators or jump through any template hoops. Let's re-visit our entities.toml file from earlier, only this time, we're going to over-align the pos column by adding an alignment:

namespace = 'game'

[structs.entities]                                                 #    |
variables = [                                                      #    |
    {name = 'id',     type = 'unsigned' },                         #   \|/
    {name = 'name',   type = 'std::string', default = '""' },      #    V
    {name = 'pos',    type = 'vec3',        default = '{}', alignment = 32 },
    {name = 'orient', type = 'quaternion',  default = '{1, 0, 0, 0}' },
]

Re-generating the table now would see that the entities::pos() data pointer always returned a value that was aligned on an (at least) 32-byte boundary.

It can also be the case that you need to advance through the table in 'aligned batches', where the start of each batch for each column has the same alignment as the value you specified in the config. Soagen has you covered here, too: tables have aligned_stride as a public constant:

constexpr auto stride = entities::aligned_stride;
for (auto ptr = e.pos(), end = ptr + e.size(); ptr < end; ptr += stride)
{
    // ...
}

Note that <your table>::aligned_stride is across every column; if you have multiple over-aligned columns, this value will be the lowest-common-multiple of all of their aligned_strides, such that stepping through by that amount would have them all correctly aligned. This value may be larger than you like; if you're really just interested in one column, you can fetch the aligned_stride for it specifically using column_traits:

constexpr auto stride = entities::column_traits<2>::aligned_stride;
for (auto ptr = e.pos(), end = ptr + e.size(); ptr < end; ptr += stride)
{
    // ...
}

Using custom allocators

Soagen tables will use their own allocator by default: the soagen::allocator. This is one of the mechanisms that allow soagen to propagate the nice alignment hints all the way through to your user code.

It is the default, but you're not stuck with it. You can change the allocator for any struct in your config like this:

allocator = 'foo::allocator' # at root level to change it for all classes, or

[structs.entity]
allocator = 'foo::fancy_allocator' # ...can also be overridden set per-struct

The only requirements of your allocator are:

• It must properly implement the named requirement Allocator, and
• Have a value_type of char, unsigned char or std::byte.

struct my_allocator
{
    inline constexpr std::size_t min_alignment = 64;
}

struct my_allocator
{
    value_type* allocate(std::size_t size, std::align_val_t alignment)
    {
        return my_aligned_alloc_function(size, static_cast<std::size_t>(alignment));
    }
}

Accessing the underlying buffer

Soagen allocates one contiguous buffer for the entire table. If all the column types in your table are TriviallyCopyable you'll be able to access the underlying buffer directly with data(), and determine it's size with allocation_size(), allowing you to serialize/deserialize it directly, stream it, hash it, et cetera.

Integrating with reflection systems

For lack of an in-language solution, C++ reflection systems are typically heavily based on stringification tricks, magic macros and source-code scanners (e.g. Unreal Engine's UnrealHeaderTool). Soagen has functionality specifically aimed at integration with these systems.

Firstly, each table class has a constexpr variable template for fetching the name of a column:

std::cout << "column 0 name: " << entities::column_name<0> << "\n";

column 0 name: id

Additionally, the generator supports adding custom annotations and attributes to the generated table class so you can use things like UE's UCLASS():

[structs.entities]
annotations = [ 'UCLASS()' ]
header = '''
GENERATED_BODY();
'''
default_constructible = 'auto' # let GENERATED_BODY create the default ctor

Creating your own SoA types without the generator

What if you don't want to use a command-line tool to generate code, and instead want to build your own SoA types? That's totally fine! soagen.hpp was written with that use-case in mind. The generated classes buy you named members and default arguments to push_back() and friends, and are simply thin wrappers around the soagen::table.

To use a soagen::table directly, you need to express it terms of soagen::table_traits, which is itself expressed in terms of the individual columns. For example, to create a 'raw' verson of the entity table we've generated above:

using entities = soagen::table<
    soagen::table_traits<
        unsigned,
        std::string,
        soagen::column_traits<vec3, 32>, // over-aligned
        quaternion
    >,
    soagen::allocator
>;

entities e;

e.emplace_back(/* ... */); // etc

The interface of soagen::table is a little bit less 'furnished' than it's soagen-generated brethren. Making more features available without using the generator is on the roadmap, so support for this use-case will improve in future.

Next steps

If all of this sounds like it would solve a problem for you, please consider giving soagen a try! I'm eager to see how people get on with it.

• A loose development roadmap can be found here
• Bug reports and feature requests can be made here here
• A contribution guide can be found here

Thanks!

About the author

I'm Mark. You might know me as the toml++ guy. I write code. Some of it is alright. Almost all of it is C++.