c++ - 向后读取文件的适当 madvise 设置是什么？

Question

我在 64 位 Linux 机器上使用 gcc 4.7.2。

我有 20 个大型排序的二进制 POD 文件，我需要将其作为外部合并排序中最终合并的一部分进行读取。

通常，我会 mmap所有用于阅读和使用的文件 multiset<T,LessThan>在执行 mmap 之前管理从小到大的归并排序写到磁盘。

但是，我意识到如果我保留 std::mutex在这些文件中的每一个上，我可以创建第二个线程向后读取文件，并同时从大到小排序。如果我事先决定第一个线程将恰好获取 n/2 个元素，而第二个线程将获取其余元素，那么我将不需要在输出端使用互斥锁。

在这种特殊情况下，读取锁争用预计会发生，平均而言，可能是二十分之一，所以这是可以接受的。

现在，这是我的问题。在第一种情况下，很明显我应该调用 madvise与 MADV_SEQUENTIAL , 但我不知道我应该为第二种情况做些什么，我正在向后读取文件。

我没看到 MADV_REVERSE在手册页中。我应该使用 MADV_NORMAL 吗？或者也许不打电话 madvise有没有？

回想一下，当数据量大到无法放入内存时，需要进行外部排序。所以我们剩下一个更复杂的算法来使用磁盘作为临时存储。分而治之算法通常涉及分解数据、进行部分排序，然后合并部分排序。

我的外部合并排序步骤

1. 取 n=10 亿个随机数并将它们分成 20 个大小相等的碎片。
2. 将每个分片从小到大单独排序，并将每个分片写入自己的文件。
3. 打开 40 个 mmap，每个文件 2 个，一个用于前进，一个用于后退，为每个文件关联一个互斥量。
4. 实例化一个std::multiset<T,LessThan> buff_fwd;对于正向线程和 std::multiset<T,GreaterThan> buff_rev对于反向线程。有些人更喜欢在这里使用优先级队列，但本质上，sort-on-insert 容器可以在这里工作。
5. 我喜欢将这两个缓冲区称为 surface 和 rockbottom，分别代表尚未添加到最终排序中的最小和最大数字。
6. 从碎片中添加项目，直到用完 n/2，然后在另一个线程中使用 mmap 从开始到中间，从末端到中间，将碎片刷新到一个输出文件。您基本上可以随意刷新，但至少应该在任一缓冲区用完太多内存之前执行此操作。

Answer 1

我建议:

MADV_RANDOM

防止无用的预读(方向错误)。