1

我正在研究一种排序算法，它遍历一堆整数并将它们放入桶中。

桶的确切类型是类似于 的自定义数据结构std::vector。正如您可以想象的那样，有一个类似于这个的片段，对于存储桶中已经分配了足够的内存来写入我要添加的元素的情况：

*_end = _new_value; // LINE 1
++_end; // Line 2

我在 vtune 优化器中发现 LINE 1 约占我算法运行时间的 1/3。我很好奇我是否可以做得更好，所以我开始尝试一些东西。

我的工作站是 Linux，我通常用 gcc 编译。我们的软件也必须支持其他编译器和系统，但仅 Linux 的优化被认为是可以的，因为我们“建议”用户使用 Linux。

首先，我只是在调用上述代码段的循环中添加了一个前瞻。展望未来buffer_size的迭代，它得到了以下结果：

int * Bucket::get_end() {
    __builtin_prefetch(_end, 1); // Line 3
    return _end++; // Line 4
}

并将这些结果存储在类似于以下内容的缓冲区中buffer：

using delayed_write = std::pair<int, int*>; // Line 5
std::array<delayed_write, buffer_size> buffer; // Line 6

我会运行相当于：

*(buffer[i + buffer_size].second) = buffer[i + buffer_size].first;

这消除了我在 vtune 第 2 行看到的瓶颈，但算法总体上较慢。（我尝试了 4 和 8 作为buffer_size）。

我尝试了其他一些东西。特别是，我做了一些非常复杂的事情，我一次完全批处理 4 或 8 个整数，并且一次对所有整数执行每一步。我编写了代码来尝试查看是否需要重新分配；如果没有，我巧妙地编写了一些循环，避免了循环步骤之间的任何数据依赖性。当然，所有这些复杂性都可以预见地使算法变得更慢。:)

有可能它根本无法变得更快，但我直觉上应该有一些方法可以利用在循环结束之前第 2 行的写入没有数据依赖性，因此无需等待可能的缓存未命中有待解决。

我的理解是缓存未命中的延迟非常高，但我有点想知道为什么 CPU 不能继续运行并将写入留在缓冲区中以异步处理。

如果有一种方法可以保证在调用一些同步函数来提交到目前为止的所有写入之前我不会读取该内存，那将是非常酷的。

你认为事实上我正在填满写缓冲区吗？（在这种情况下没有解决方案？）

如果没有，有没有人知道有什么方法可以利用在热循环之后才会读取写入的事实？

4

0 回答 0