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);
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?
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.
This choice of "combined" vs "split" has other well known names:
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.
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 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.
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.
std::reducestd::execution::<...>
std::plusThere 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.
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.