c++ 为什么对这个数组结构体的成员求和比对一个结构体数组求和要快得多？

pod7payv  于 2023-03-10  发布在  其他
关注(0)|答案(1)|浏览(153)

我一直在使用https://github.com/google/benchmark和g++ 9.4.0来检查不同场景下的数据访问性能（使用“-O3“编译），结果令我感到惊讶。
我的基线是访问std::array中的long（“reduced data”）。我想添加一个额外的字节数据。一次我创建了一个额外的容器（“split data”），一次我在数组中存储了一个struct（“combined data”）。
这是密码：

#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
这就是结果

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

我对BM_AccessCombinedData的长运行时间并不感到惊讶。添加字节需要额外的工作（与“减少的数据”相比）。我的解释是，添加的字节不再适合该高速缓存行，这使得访问成本高得多。（可能还有其他影响吗？）
但是为什么访问不同的容器（“分割数据”）会这么快呢？数据位于内存中的不同位置，并且交替访问。这不是应该更慢吗？但是它几乎比访问合并数据快三倍！这难道不令人惊讶吗？

c++

1条答案

按热度按时间
jqjz2hbq

jqjz2hbq1#

前言：此答案 * 仅 * 针对您在基准测试链接中提供的示例/场景编写：对不同大小的整数的交错集合与非交错集合的求和归约。求和是一种无序操作。你可以访问集合的元素，并以任何顺序将它们添加到累加结果中。无论你是“合并”（通过结构体）还是“拆分”（通过单独的数组），累加的顺序都无关紧要。
注：如果您提供一些关于优化技术的已知信息以及处理器/内存的通常能力，将会有所帮助。您的评论表明您了解缓存，但我不知道您还了解什么，或者您对缓存的确切了解是什么。

术语

“合并”与“拆分”的选择还有其他众所周知的名称：

这个问题符合人们在谈论data-oriented design时所关心的领域。
在本答案的其余部分，我将与您的术语保持一致。

对齐、填充和结构

引用CppReference，
C++ 有以下要求：
每个完整的对象类型都有一个称为对齐要求的属性，它是size_t类型的整数值，表示可以分配此类型对象的连续地址之间的字节数。有效的对齐值是2的非负整数幂。
“每个完整对象”都包含内存中的结构体示例。
为了满足结构的所有成员的对齐要求，可以在其某些成员之后插入填充。
其中一个例子表明：

// 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

这就是Peter Cordes在评论中提到的，因为 C++ 的这个要求/属性/特性，所以为您的“组合”集合插入了填充。
我不确定这里的填充是否会对缓存性能造成很大的损害，因为和只访问数组的每个元素一次，在元素经常被访问的场景中，这可能更重要：当与分离表示相比时，组合表示的填充导致该高速缓存的“浪费”字节，并且该浪费更可能对高速缓存性能具有显著影响，但是其重要程度取决于重新访问数据的模式。

单指令多数据集

wikipedia article
SIMD指令是专门的CPU机器指令，用于对内存中的多段数据执行操作，例如对内存中一个接一个排列的一组大小相同的整数求和（这正是您的场景的“拆分”表示版本中可以完成的操作）。
与不使用SIMD的机器码相比，使用SIMD可以提供常数因子的改进（常数因子的值基于SIMD指令）。例如，将8个字节加在一起的SIMD指令应该比做同样事情的循环或做同样事情的展开循环快8倍。
其他关键词：矢量化、并行化代码。
Peter Cordes提到了相关的例子（psadbw，paddq），这里有一个英特尔SSE算术指令列表。
正如Peter所提到的，在“组合”表示中，SIMD的使用程度仍然是可能的，但不如“分割”表示那样多。这取决于目标机器架构的指令集提供了什么。我不认为您的示例的“组合”表示有专用的SIMD指令。

密码

对于“拆分”表示，我将执行如下操作：

// ...
#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{});
}

// ...

这是一种更直接的方式来（向代码的读者和编译器）传递整数集合的无序和。

但是不同的立场又如何呢？

在那里，数据位于内存中的不同位置，并且可以交替访问，这不是应该更慢吗？
正如我在上面的代码中所展示的，对于您的特定场景，不需要交替访问，但是如果将特定场景更改为需要交替访问，一般来说，我认为不会对缓存产生太大影响。
如果拆分数组的对应条目Map到相同的缓存集，则可能存在conflict misses问题。我不知道这种情况发生的可能性有多大，或者C++中是否有技术可以防止这种情况。如果有人知道，请编辑此答案。如果缓存具有N路集关联性，而对“split”表示数据的访问模式只访问热循环中的N或更少的数组（即不访问任何其他内存），我相信应该不可能遇到这种情况。

其他注解

我建议您保持问题中的基准链接不变，如果您想更新它，请添加一个新链接，以便查看讨论的人能够看到引用的旧版本。
出于好奇，你为什么不使用像gcc 11这样的新版本编译器来进行基准测试呢？
我强烈推荐我展示的std::reduce的用法。广泛推荐的做法是使用专用的C标准算法，而不是适合任务的原始循环。请参阅CppCoreGuidlines链接中引用的原因。代码可能很长（从这个意义上说，很难看），但它清楚地传达了在归约运算符（plus）未排序的情况下执行求和的意图。
您的问题是关于 * 速度 * 的，但值得注意的是，在C中，在 * 空间 * 成本很重要的地方，选择数组结构还是数组结构可能很重要，这正是因为对齐和填充。
在选择数组的结构体和结构体的数组时，还有更多我没有列出的注意事项：存储器访问模式是性能的主要考虑因素，可读性和简单性也是重要的考虑因素;您可以通过构建良好的抽象来缓解问题，但这仍然是有限制的，而且构建抽象本身的维护、可读性和简单性成本也是有限的。
您可能还会发现this video by Matt Godbolt on "Memory and Caches"非常有用。

赞(0）分享  回复(0）举报  2023-03-10
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com