c++ - 帮助缓存局部化的载体吗？ (C++)

Question

上周，我读了一些很棒的概念，例如cpu中的缓存局部性和流水线。尽管这些概念很容易理解，但我有两个问题。假设可以在对象 vector 或对象指针 vector 之间进行选择(如this question所示)。

那么使用指针的一个论点是，整理较大的对象可能很昂贵。但是，我找不到何时应该将一个大对象调用。几个字节的对象是否已经很大？

反对指针的一个论点是缓存局部性的丧失。如果一个人使用两个 vector ，其中第一个 vector 包含对象并且不会被重新排序，而第二个 vector 包含指向这些对象的指针，是否有帮助？假设我们有一个包含200个对象的 vector ，并创建一个带有指向这些对象的指针的 vector ，然后随机地随机播放最后一个 vector 。如果我们使用指针遍历 vector ，缓存位置是否会丢失？

在我的程序中，我有城市对象，然后有大约200个指向这些城市的指针 vector ，这在我的程序中经常发生。为了避免每个城市有200个实例，我使用指针 vector 而不是城市 vector 。

Answer 1

这个问题没有简单的答案。您需要了解系统如何与内存交互，在容器上执行哪些操作以及其中哪些操作“重要”。但是通过了解概念以及什么会影响事物，您可以更好地了解事物的工作方式。因此，这里有一些关于该主题的“讨论”。

“缓存位置”主要是关于“将内容保存在缓存中”。换句话说，如果您查看A，那么B和A都位于B附近，那么它们很可能会一起加载到缓存中。

如果对象足够大以至于它们可以填充一个或多个高速缓存行(现代CPU的高速缓存行为64-128字节，移动高速缓存的行有时更小)，则“行中的下一个对象”将始终不在高速缓存中[1 ]，因此“ vector 中的下一个元素”的缓存局部性不太重要。对象越小，获得的效果越好-假设您以对象的存储顺序访问它们。如果选择一个随机数，则其他因素开始变得很重要[2]，而缓存位置的重要性则要低得多。

另一方面，随着对象变大，将它们在 vector 中移动(包括增长，删除，插入以及“随机混洗”)将更加耗时，因为复制更多数据会变得更加广泛。

当然，与直接从 vector 中读取元素相比，始终需要从指针读取进一步的步骤，因为在获取pointee对象中的实际数据之前，必须先“读取”指针本身。同样，这在随机访问事物时变得更加重要。

我总是从“最简单的事情”开始(这取决于代码的整体结构，例如，有时创建指针 vector 会更容易，因为首先必须动态创建对象)。系统中的大多数代码无论如何对性能都不是至关重要的，所以为什么要担心它的性能-如果性能测试中没有发现问题，就让它正常工作并保持现状。

当然，同样，如果您要在容器中进行大量对象的移动，也许 vector 不是最佳容器。这就是为什么存在多个容器变量-vector，list，map，tree，deque的原因-它们在访问和插入/删除以及线性遍历数据方面具有不同的特征。

哦，在您的示例中，您提到了200个城市对象-嗯，无论如何，它们可能都适合所有现代CPU的缓存。因此，将它们粘贴在 vector 中。除非城市包含该城市中每个人的 list ...否则，它本身可能应该是vector(或其他容器对象)。

作为实验，请制作一个对std::vector<int>和std::vector<int*>执行相同操作的程序(例如用随机数填充，然后对元素进行排序)，然后制作一个较大的对象(在其中粘贴一些整数数组，或类似的方法) ]，使用一个整数，以便您可以对此执行完全相同的操作。改变所存储对象的大小，并查看其行为。在您的系统上，拥有指针比拥有普通对象的好处在哪里？当然，也可以改变元素的数量，以了解其效果。

[1]好吧，现代处理器使用高速缓存预取，它可以推测性地将“下一个数据”加载到高速缓存中，但是我们当然不能依靠它。

[2]这种情况的极端情况是与大量用户(数百万)的电话交换机。发出 call 时，将在表中查找 call 者和被 call 者。但是 call 者或被 call 者进入缓存的机会几乎为零，这是因为(假设我们正在与伦敦等大城市打交道)每秒发出和接收的 call 数量非常大。因此，缓存变得无用，而且情况变得更糟，因为处理器还缓存了页表条目，而且很有可能也已过时。对于这类应用程序，CPU设计人员拥有“巨大的页面”，这意味着内存被分为1GB的页面，而不是已经存在了一段时间的通常的4K或2MB的页面。这减少了“我们到达正确的位置”之前所需的内存读取量。当然，其他各种“大型数据库，不可预测的模式”也一样-航空公司，facebook，stackoverflow都存在此类问题。