MultiFieldArray container library

C++17 library which implements the well known "parallel array" or "structure of arrays" (SoA), called a "multi-field array" here. The container is essentially a data-oriented alternative to a std::vector<S>, where S is a structure with multiple fields, and is, thus, an "array of structures" (AoS).

Dependencies

General Use

• C++17 Standard Library

Unit Tests

• C++17 Standard Library
• google-test

Benchmarking

• C++17 Standard Library
• google-benchmark

Motivation

Take the following use case:

#include <iostream>
#include <string>
#include <vector>

struct MyStruct
{
  float a;
  double b;
  std::string c;
};

std::vector<MyStruct> vec;

vec.resize(5);

for (const auto& v : vec)
{
  std::cout << v.a << std::endl;
}

When we iterate over std::vector<MyStruct>, all fields (a.k.a. comonent, member variable) of each element of type MyStruct is loaded into CPU cache, even if we don't need it. Instead, we can take a data-oriented approach where each field is stored in its own buffer. A container which models this approach might look as follows:

template<typename A, typename B, typename C>
struct MultiFieldArray
{
  // std::vector<X> for exposition only...
  std::vector<A> a_data;
  std::vector<B> b_data;
  std::vector<C> c_data;
};

The MultiFieldArray follows this approach, and provides accessors for iterating over subsets of the types that it manages. For instance, one can achieve the following:

mf::multi_field_array<int, float, char> mfa;

for (auto [a, b] : mfa.view<int, float>())
{
  // Iterating over just the int and float fields
}

for (auto [a, b, c] : mfa.view())
{
  // Iterating over all fields
}

One can also access a subset of components positionally, like so:

mf::multi_field_array<int, float, char> mfa;

mfa.resize(10);

auto view = mfa.view<int, float>();

auto [int_ref, float_ref] = view[3];

int_ref = 1;

float_ref = 3.f;

auto [int_ref_b, float_ref_b] = view.at(3);  // with bounds checking

Accessing all components positionally is also possible:

mf::multi_field_array<int, float, char> mfa;

mfa.resize(10);

auto [int_ref, float_ref, char_ref] = mfa[3];

int_ref = 1;

float_ref = 3.f;

char_ref = 'a';

auto [int_ref_b, float_ref_b, char_ref_b] = mfa.at(3);  // with bounds checking

Performance

Running micro-benchmarking tests

bazel test //test/benchmark/... --test_output=all --cache_test_results=no

Example micro-benchmarking output

Run on (8 X 4500 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x4)
  L1 Instruction 32 KiB (x4)
  L2 Unified 256 KiB (x4)
  L3 Unified 8192 KiB (x1)
Load Average: 0.66, 0.48, 0.49

--------------------------------------------------------------------------------------
Benchmark                                            Time             CPU   Iterations
--------------------------------------------------------------------------------------
Iteration_One_Of_Two_Fields_MFA                 911860 ns       911152 ns          765   <-- Accessing one field of MultiFieldArray of two field types
Iteration_One_Of_Two_Fields_Vec                1924595 ns      1921561 ns          387   <-- Accessing one field of std::vector<Struct> with two members
Iteration_Two_Of_Two_Fields_MFA                2335226 ns      2331385 ns          301
Iteration_Two_Of_Two_Fields_Vec                2542674 ns      2538851 ns          288
Iteration_Two_Of_Many_Fields_MFA_View          2454603 ns      2450854 ns          265
Iteration_Two_Of_Many_Fields_MFA_All_Fields    2286510 ns      2283481 ns          292
Iteration_Two_Of_Many_Fields_Vec               2908417 ns      2907053 ns          240
Iteration_One_Of_Many_Fields_MFA_View           909963 ns       909970 ns          766
Iteration_One_Of_Many_Fields_MFA_All_Fields     908849 ns       908857 ns          760
Iteration_One_Of_Many_Fields_Vec               2556763 ns      2556768 ns          263
Allocation_Two_Fields_MFA                        20553 ns        20554 ns        34162
Allocation_Two_Fields_Vec                        25640 ns        25641 ns        27229
Allocation_Many_Fields_MFA                       20441 ns        20441 ns        33742
Allocation_Many_Fields_Vec                       35104 ns        35104 ns        19913
================================================================================

TODOs

• Add "single allocation" strategy option, which will allocate all field memory at once, rather than with separate allocation calls
• Add CMake build configuration
• Add CMake CI step
• Add Doxygen documentation page releases
• Add benchmark tests