c++ - 如何加速非顺序数组填充？

Question

上下文

我有这样的代码:

..
vector<int> values = ..., vector<vector<int>> buckets;
//reserve space for values and each buckets sub-vector
for (int i = 0; i < values.size(); i++) {
  buckets[values[i]].push_back(i);
}
...

所以我得到一个“桶”，其中包含具有相同值的条目的索引。这些桶随后用于进一步处理。

实际上，我使用的是原生动态数组 (int ** buckets;)，但为了简单起见，我在上面使用了 vector 。

在填充之前我知道每个桶的大小。

vector 的大小约为 2,000,000,000。

问题

如您所见，上面的代码以随机方式访问“buckets”数组。因此它有持续的高速缓存未命中，这会大大减慢执行时间。是的，我在配置文件报告中看到了这样的遗漏。

问题

有没有办法提高此类代码的速度？

我尝试创建一个辅助 vector 并将第一次出现的值放在那里，这样我就可以在找到第二个索引时将两个索引放在相应的存储桶中。这种方法没有提供任何加速。

谢谢!

Answer 1

为什么您认为是缓存未命中导致您的代码变慢？您是否进行了概要分析，或者这就是您想到的？

从性能的角度来看，您的代码存在很多问题。第一个也是最明显的一点是您从不保留 vector 大小。发生的情况是您的 vector 开始时​​非常小(例如，2 个元素)，然后每次您添加超过该大小时，它都会再次调整大小并将内容复制到新的内存位置。如果您说有 2 十亿 个条目，那么您可能正在调整大小 30 次!

您需要调用函数 vector.reserve()(或 vector.resize()，具体取决于哪种行为最适合你)在你看其他改进之前。

编辑

是认真的吗？你提到你甚至没有在你的 PS 中使用 vector ？我们应该如何猜测您的实际代码是什么样子以及它将如何执行？