Why is summing over members of this struct of arrays much faster than summing over an array of structs?

Question

I have been using https://github.com/google/benchmark and g++ 9.4.0 to check the performance of data access in different scenarios (compilation with "-O3"). The result has been surprising to me.

My baseline is accessing longs in an std::array ("reduced data"). I want to add an additional byte datum. One time I create an additional container ("split data") and one time I store a struct in the arrays ("combined data").

This is the code:

#include <benchmark/benchmark.h>

#include <array>
#include <random>

constexpr int width  = 640;
constexpr int height = 480;

std::array<std::uint64_t, width * height> containerWithReducedData;

std::array<std::uint64_t, width * height> container1WithSplitData;
std::array<std::uint8_t, width * height>  container2WithSplitData;

struct CombinedData
{
    std::uint64_t first;
    std::uint8_t  second;
};

std::array<CombinedData, width * height> containerWithCombinedData;

void fillReducedData(const benchmark::State& state)
{
    // Variable is intentionally unused
    static_cast<void>(state);

    // Generate pseudo-random numbers (no seed, therefore always the same numbers)
    // NOLINTNEXTLINE
    auto engine = std::mt19937{};

    auto longsDistribution = std::uniform_int_distribution<std::uint64_t>{};

    for (int row = 0; row < height; ++row)
    {
        for (int column = 0; column < width; ++column)
        {
            const std::uint64_t number = longsDistribution(engine);

            containerWithReducedData.at(static_cast<unsigned int>(row * width + column)) = number;
        }
    }
}

std::uint64_t accessReducedData()
{
    std::uint64_t value = 0;

    for (int row = 0; row < height; ++row)
    {
        for (int column = 0; column < width; ++column)
        {
            value += containerWithReducedData.at(static_cast<unsigned int>(row * width + column));
        }
    }

    return value;
}

static void BM_AccessReducedData(benchmark::State& state)
{
    // Perform setup here
    for (auto _ : state)
    {
        // Variable is intentionally unused
        static_cast<void>(_);

        // This code gets timed
        benchmark::DoNotOptimize(accessReducedData());
    }
}

BENCHMARK(BM_AccessReducedData)->Setup(fillReducedData);

void fillSplitData(const benchmark::State& state)
{
    // Variable is intentionally unused
    static_cast<void>(state);

    // Generate pseudo-random numbers (no seed, therefore always the same numbers)
    // NOLINTNEXTLINE
    auto engine = std::mt19937{};

    auto longsDistribution = std::uniform_int_distribution<std::uint64_t>{};
    auto bytesDistribution = std::uniform_int_distribution<std::uint8_t>{};

    for (int row = 0; row < height; ++row)
    {
        for (int column = 0; column < width; ++column)
        {
            const std::uint64_t number                                                  = longsDistribution(engine);
            container1WithSplitData.at(static_cast<unsigned int>(row * width + column)) = number;

            const std::uint8_t additionalNumber                                         = bytesDistribution(engine);
            container2WithSplitData.at(static_cast<unsigned int>(row * width + column)) = additionalNumber;
        }
    }
}

std::uint64_t accessSplitData()
{
    std::uint64_t value = 0;

    for (int row = 0; row < height; ++row)
    {
        for (int column = 0; column < width; ++column)
        {
            value += container1WithSplitData.at(static_cast<unsigned int>(row * width + column));
            value += container2WithSplitData.at(static_cast<unsigned int>(row * width + column));
        }
    }

    return value;
}

static void BM_AccessSplitData(benchmark::State& state)
{
    // Perform setup here
    for (auto _ : state)
    {
        // Variable is intentionally unused
        static_cast<void>(_);

        // This code gets timed
        benchmark::DoNotOptimize(accessSplitData());
    }
}

BENCHMARK(BM_AccessSplitData)->Setup(fillSplitData);

void fillCombinedData(const benchmark::State& state)
{
    // Variable is intentionally unused
    static_cast<void>(state);

    // Generate pseudo-random numbers (no seed, therefore always the same numbers)
    // NOLINTNEXTLINE
    auto engine = std::mt19937{};

    auto longsDistribution = std::uniform_int_distribution<std::uint64_t>{};
    auto bytesDistribution = std::uniform_int_distribution<std::uint8_t>{};

    for (int row = 0; row < height; ++row)
    {
        for (int column = 0; column < width; ++column)
        {
            const std::uint64_t number = longsDistribution(engine);
            containerWithCombinedData.at(static_cast<unsigned int>(row * width + column)).first = number;

            const std::uint8_t additionalNumber = bytesDistribution(engine);
            containerWithCombinedData.at(static_cast<unsigned int>(row * width + column)).second = additionalNumber;
        }
    }
}

std::uint64_t accessCombinedData()
{
    std::uint64_t value = 0;

    for (int row = 0; row < height; ++row)
    {
        for (int column = 0; column < width; ++column)
        {
            value += containerWithCombinedData.at(static_cast<unsigned int>(row * width + column)).first;
            value += containerWithCombinedData.at(static_cast<unsigned int>(row * width + column)).second;
        }
    }

    return value;
}

static void BM_AccessCombinedData(benchmark::State& state)
{
    // Perform setup here
    for (auto _ : state)
    {
        // Variable is intentionally unused
        static_cast<void>(_);

        // This code gets timed
        benchmark::DoNotOptimize(accessCombinedData());
    }
}

BENCHMARK(BM_AccessCombinedData)->Setup(fillCombinedData);

Live demo

And this is the result:

Run on (12 X 4104.01 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x6)
  L1 Instruction 32 KiB (x6)
  L2 Unified 256 KiB (x6)
  L3 Unified 12288 KiB (x1)
Load Average: 0.33, 1.82, 1.06
----------------------------------------------------------------
Benchmark                      Time             CPU   Iterations
----------------------------------------------------------------
BM_AccessReducedData       55133 ns        55133 ns        12309
BM_AccessSplitData         64089 ns        64089 ns        10439
BM_AccessCombinedData     170470 ns       170470 ns         3827

I am not surprised by the long running times of BM_AccessCombinedData. There is additional effort (compared to "reduced data") to add the bytes. My interpretation is that the added byte does not fit into the cache line anymore, which makes the access much more expensive. (Might there be even another effect?)

But why is it so fast to access different containers ("split data")? There the data is located at different positions in memory and there is alternating access to it. Shouldn't this be even slower? But it is almost three times faster than the access of the combined data! Isn't this surprising?

Answer 1

Preface: This answer was written only for the example/scenario you provided in your benchmark link: a summing reduction over interleaved vs non-interleaved collections of differently sized integers. Summing is an unsequenced operation. You can visit elements of the collections and add them to the accumulating result in any order. And whether you "combine" (via struct) or "split" (via separate arrays), the order of accumulation doesn't matter.

Note: It would help if you provided some information about what you already know about optimization techniques and what processors/memory are usually capable of. Your comments show you know about caching, but I have no idea what else you know, or what exactly you know about caching.

Terminology

This choice of "combined" vs "split" has other well known names:

• parallel array (wikipedia article)
• structure of arrays vs array of structures (wikipedia article)

This question fits into the area of concerns people have when talking about data-oriented design.

For the rest of this answer, I will stay consistent with your terminology.

Alignment, Padding, and Structs

quoting from CppReference,

The C++ language has this requirement:

Every complete object type has a property called alignment requirement, which is an integer value of type size_t representing the number of bytes between successive addresses at which objects of this type can be allocated. The valid alignment values are non-negative integral powers of two.

"Every complete object" includes instances of structs in memory. Reading on...

In order to satisfy alignment requirements of all members of a struct, padding may be inserted after some of its members.

One of its examples demonstrate:

// objects of struct X must be allocated at 4-byte boundaries
// because X.n must be allocated at 4-byte boundaries
// because int's alignment requirement is (usually) 4
struct X {
    int n;  // size: 4, alignment: 4
    char c; // size: 1, alignment: 1
    // three bytes padding
}; // size: 8, alignment: 4

This is what Peter Cordes mentioned in the comments. Because of this requirement/property/feature of the C++ language, there is inserted padding for your "combined" collection.

I am not sure if there is a significant detriment to cache performance resulting from the padding here, since the sum only visits each element of the arrays once. In a scenario where elements are frequently revisited, this is more likely to matter: the padding of the combined representation results in "wasted" bytes of the cache when compared with the split representation, and that wastage is more likely to have a significant impact on cache performance. But the degree to which this matters depends on the patterns of revisiting the data.

SIMD

wikipedia article

SIMD instructions are specialized CPU machine instructions for performing an operation on multiple pieces of data in memory, such as summing a group of same-sized integers which are laid out next to each other in memory (which is exactly what can be done in the "split"-representation version of your scenario).

Compared to machine code that doesn't use SIMD, SIMD usage can provide a constant-factor improvement (the value of the constant factor is based on the SIMD instruction). Ex. a SIMD instruction that adds 8 bytes together should be 8 times faster than a loop which does the same thing, or an unrolled loop which does the same thing.

Other keywords: vectorization, parallelized code.

Peter Cordes mentioned relevant examples (psadbw, paddq). Here's a list of intel SSE instructions for arithmetic.

As Peter mentioned, a degree of SIMD usage is still possible in the "combined" representation, but not as much as is possible with the "split" representation. It comes down to what the target machine architecture's instruction set provides. I don't think there's a dedicated SIMD instruction for your example's "combined" representation.

The Code

For the "split" representation, I would do something like:

// ...
#include <numeric>    // for `std::reduce`
#include <execution>  // for `std::execution`
#include <functional> // for `std::plus`

std::uint64_t accessSplitData()
{
    return std::reduce(std::execution::unseq, container1WithSplitData.cbegin(), container1WithSplitData.cend(), std::uint64_t{0}, std::plus{});
         + std::reduce(std::execution::unseq, container2WithSplitData.cbegin(), container2WithSplitData.cend(), std::uint64_t{0}, std::plus{});
}

// ...

It's a much more direct way to communicate (to readers of the code and to a compiler) an unsequenced sum of collections of integers.

• CppReference for std::reduce
• CppReference for std::execution::<...>
  • Execution policies allow you to convey how an algorithm can and is desired to be performed (whether it is safe/still-correct and desirable to use SIMD or multiple threads). Many of the algorithms in the C++ standard library have a similar overload to accept an execution policy argument.
• CppReference for std::plus

But What about the Different Positions?

There the data is located at different positions in memory and there is alternating access to it. Shouldn't this be even slower?

As I showed in the code above, for your specific scenario, there doesn't need to be alternating access. But if the specific scenario is changed to require alternating access, on average, usually I don't think there would be much cache impact.

There is the possible problem of conflict misses if the corresponding entries of the split arrays map to the same cache sets. I don't know how likely this is to be encountered, or if there are techniques in C++ to prevent that. If anyone knows, please edit this answer. If a cache has N-way set associativity, and the access pattern to the "split" representation data only accesses N or fewer arrays in the hot loop (ie. doesn't access any other memory), I believe it should be impossible to run into this.

---

Misc Notes

I would recommend that you keep your benchmark link in your question unchanged, and if you want to update it, add a new link, so people viewing the discussion will be able to see older versions being referred to.

Out of curiosity, is there a reason why you're not using newer compiler versions for the benchmark like gcc 11?

I highly recommend the usage I showed of std::reduce. It's a widely recommended practice to use a dedicated C++ standard algorithm instead of a raw loop where the algorithm is suited for the task. See the reasons cited in the CppCoreGuidlines link. The code may be long (and in that sense, ugly), but it clearly conveys the intent to perform a sum where the reduction operator (plus) is unsequenced.

Your question is specifically about speed, but it's noteworthy that in C++, the choice of struct-of-array vs array-of-struct can be important where space costs matter, precisely because of alignment and padding.

There are more considerations in choosing struct-of-array vs array-of-struct that I haven't listed: memory-access-patterns are the main consideration for performance. readability and simplicity are also important considerations; you can alleviate problems by building good abstractions, but there's still a limit to that, and maintenance, readability, and simplicity costs of building the abstraction itself.

You may also find this video by Matt Godbolt on "Memory and Caches" useful.