【C\u002FC++】对象向量vs指针向量和内存访问模式

内存访问模式是编写在大型数据集上运行的高效代码的关键因素之一。在此博客文章中，您将了解为什么在使用指针向量与值类型向量时，在两个方向上可能会有近2.5倍的性能差异（双向！）。

用例

让我们比较以下情况：

std::vector<Object>std::vector<std::shared_ptr<Object>>std::vector<std::unique_ptr<Object>>

对于此博客文章，我们假设它Object只是一个常规类，没有任何虚拟方法。

使用指向基类的指针以及虚拟方法，您可以实现运行时多态，但这是其他一些实验的故事。例如，我们可以尝试std::variant避免常规的运行时多态性……

好的，那么每个集合之间有什么区别？让我们进行比较：

std::vector<Object>

内存是在堆上分配的，但是向量保证mem块是连续的。

在上图中，您可以看到向量的所有元素在内存块中彼此相邻。

std::vector<std::unique_ptr<Object>>

这次，每个元素都是一个指向在RAM中可能不同位置分配的存储块的指针。我们unique_ptr这样使用，以便我们对资源拥有明确的所有权，同时原始指针的开销几乎为零。

如果我们使用默认删除器或无状态删除器，则没有额外的内存使用。您可以在单独的博客文章中阅读更多内容：C ++智能指针的自定义删除器

std::vector<std::shared_ptr<Object>>

有了shared_ptr我们，指针的集合可以被多个指针拥有。例如，这可以模拟C＃中的引用。

但是，这次与的情况相比，我们有更多的开销unique_ptr。为了支持引用计数，共享指针需要有一个单独的控制块。在该块内部，有一个地方可以存储引用计数器，“弱”计数器以及删除对象。

如果通过创建共享指针make_shared，则控制块将放置在对象的存储块旁边。但是在一般情况下，控制块可能位于不同的位置，这就是共享指针包含两个指针的原因：一个指向对象，另一个指向控制块。

测试代码

完整的存储库可以在这里找到：github / fenbf / PointerAccessTest，但是代码也已经通过Quick Bench进行了测试：

该update()方法的基准：@QuickBench基准std::sort： @QuickBench

在https://github.com/fenbf/benchmarkLibsTest上也有实验代码，在这里我用不同的库编写了相同的基准：Celero，Google Benchmark，Nonius或Hayai（并参见相应的博客文章：Revisiting a Old Benchmark-Vector of对象或指针）

基准测试的核心部分：

创建一个对象容器运行generate方法-这样我们可以分配一些随机数update()N次运行方法运行std::sort()N次对象类-粒子

为了为对象类提供一个有用的示例，我选择了Particle类，该类可以模拟某些物理交互并实现基本的Euler方法：

class Particle {
public:
    float pos[4];
    float acc[4];
    float vel[4];
    float col[4];
    float rot;
    float time;
    //uint8_t extra[EXTRA_BYTES];
public:

    void generate() noexcept {
        acc[0] = randF();
        acc[1] = randF();
        acc[2] = randF();
        acc[3] = randF();
        pos[0] = pos[1] = pos[2] = pos[3] = 0.0f;
        vel[0] = randF();
        vel[1] = randF();
        vel[2] = randF();
        vel[3] = vel[1] + vel[2];
        rot = 0.0f;
        time = 2.0f+randF();
    }

    void update(float dt) noexcept {
        vel[0] += acc[0] * dt;
        vel[1] += acc[1] * dt;
        vel[2] += acc[2] * dt;
        vel[3] += acc[3] * dt;
        pos[0] += vel[0] * dt;
        pos[1] += vel[1] * dt;
        pos[2] += vel[2] * dt;
        pos[3] += vel[3] * dt;
        col[0] = pos[0] * 0.001f;
        col[1] = pos[1] * 0.001f;
        col[2] = pos[2] * 0.001f;
        col[3] = pos[3] * 0.001f;
        rot += vel[3] * dt;
        time -= dt;

        if (time < 0.0f)
            generate();
    }
};

粒子类包含72个字节，并且还有一些额外的数组供我们进一步测试（目前已注释）。该update()方法很简单，只有几个算术运算和一个分支。此方法将受内存限制，因为内部的所有操作都太简单了。

指针向量：

这是向量的代码，向量unique_ptr的代码几乎相同shared_ptr。

static void UniquePtrUpdate(benchmark::State& state) {
  std::vector<std::unique_ptr<Particle>> particles(count);
    for (auto& p : particles)
        p = std::make_unique<Particle>();

  for (auto& p : particles)
            p->generate();

  ShuffleVector(particles);

  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    for (auto& p : particles)
            p->update(DELTA_TIME);
  }
}
BENCHMARK(UniquePtrUpdate);

这也是基准测试的代码std::sort：

static void SharedPtrSort(benchmark::State& state) {
  std::vector<std::shared_ptr<Particle>> particles(count);
    for (auto& p : particles)
        p = std::make_shared<Particle>();

  for (auto& p : particles)
            p->generate();

  ShuffleVector(particles);

  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    std::sort(std::begin(particles), std::end(particles),
            [](const std::shared_ptr<Particle>& a, const std::shared_ptr<Particle>& b) {
                return a->pos[0] < b->pos[0];
            }
        );
  }
}
BENCHMARK(SharedPtrSort);

有关后续内存分配的额外说明

当您一个接一个地分配数百个（智能）指针时，它们可能最终位于彼此相邻的内存块中。当对象在随机时间以随机顺序分配然后添加到容器中时，这可能会影响性能，并且与常规用例完全不同。为了缓解此问题，基准代码添加了一个随机化步骤：ShuffleVector()。

在随机化之前，我们可以获得以下指针的地址：

地址与前一个元素的差异（字节）16738564016712876-2568816712972961676806055088167681569616768252961676834896167684449616768540961676863696167687329616768828961676892496167704041480

随机后：

地址与前一个元素的差异（字节）14772484014832644601601484695614312148769723001614802076-7489614802172961480991677441485857248656148756281705614816612-5901614819756314414822996324014802844-20152148046121768

第二张表显示相邻对象之间的距离较大。它们非常随机，CPU硬件预取器无法应对这种模式。

对象向量：

对象向量只是一个带有调用update方法的常规向量。

static void ValueUpdate(benchmark::State& state) {
  std::vector<Particle> particles(count);

  for (auto& p : particles)
    p.generate();

  ShuffleVector(particles);

  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    for (auto& p : particles)
        p.update(DELTA_TIME);
  }
}
BENCHMARK(ValueUpdate);

update()方法的结果内存访问模式

要完全理解为什么会有如此性能差异，我们需要谈谈内存延迟。

这是一个很好的摘要，可以解释问题：

图片来自《系统性能：企业与云》一书

在图片中，您可以看到变量离CPU越近，内存访问就越快。如果您的对象位于CPU缓存中，则其速度可能比需要从主内存中提取对象的速度快两个数量级。

那么，为什么关心迭代连续的内存块如此重要？

让我们看一下主循环：

for each particle p:
    p->update(DELTA_TIME);

连续案在我们可以更新第一个粒子的任何字段之前，必须将其从主内存中提取到缓存/寄存器中。我们的粒子大小为72字节，因此我们需要两次缓存行加载（缓存行通常为64字节）：首先将加载64字节，然后再加载64字节。请注意，只有第二次加载的前8个字节才用于第一个粒子。其余的-56b-是第二个粒子的字节。在第二步中，我们已经有56个字节的第二个粒子，因此我们需要另一个负载-64个字节-以获取其余部分。这次我们也得到了第三粒子的一些数据。然后图案重复出现……

对于1000个粒子，我们需要1000 * 72bytes = 72000个字节，这意味着72000/64 = 1125个缓存行负载。换句话说，对于每个粒子，我们将需要1.125缓存行读取。

但是CPU很聪明，将另外使用称为Hardware Prefetcher的东西。CPU会检测到我们在一个巨大的内存块上运行，并会在我们询问之前预取一些缓存行。因此，它不必等待内存，而已在缓存中！

带有指针向量的情况如何？

指针盒加载第一个粒子的数据。两次缓存行读取。加载第二个粒子的数据。Uups…这一次，我们不能使用第二个高速缓存行中加载的数据（从第一步开始），因为第二个粒子数据位于内存中的其他位置！因此，对于第二个粒子，我们还需要两个载荷！重复的模式...

对于1000个粒子，我们平均需要读取2000条缓存行！这比第一种情况多了78％的高速缓存行读取！此外，硬件Prefetcher无法确定模式-它是随机的-因此将有很多缓存未命中和停顿。

在我们的一项实验中，用于80k粒子的指针代码比连续情况要慢266％。

sort()基准测试结果

我们还可以问另一个问题：容器中的指针是否总是一件坏事？

看一下std::sort()情况：

..好的...那里发生了什么？

正如您在这次看到的那样，我们可以看到相反的效果。具有对象向量比指针向量要慢得多。

当粒子对象的大小增加到128个字节（以前是72个字节）时，这是另一个结果：

参见基准@QuickBench

结果是因为诸如排序之类的算法需要在容器内移动元素。因此，他们不仅读取数据，而且执行复制（当算法决定根据顺序交换项目或移至正确的位置时）。

复制指针比复制大对象要快得多。

如果您知道复制是容器中元素的阻止程序，那么甚至可以将排序算法替换为选择排序-这比快速排序的复杂性要差，但是“写入”的次数最少，这可能会很好。因此，像往常一样，最好进行测量和测量。

原文地址：https://www.bfilipek.com/2014/05/vector-of-objects-vs-vector-of-pointers.html

关注我：带你遨游代码的世界~获取更多：私信 “资料” 获取