在 c 中使用文件支持的 mmap 进行预取

Question

我正在编写一些性能关键代码（即在非常紧密循环中并通过分析表明）其逻辑基本上是（the_key 是一个参数并且 mmap_base是内存映射文件的基地址):

while (current_item && (struct my_struct *)(mmap_base + current_item) -> key < the_key){
    /* Do something less performance critical */
    current_item = (struct my_struct *)(mmap_base + current_item) -> next;
}

分析表明这段代码在取消引用时受磁盘限制(mmap_base + current_item)，这是有道理的，因为随机磁盘 IO 相当慢。

mmap 中的相关部分无法加载到内存中，因为文件很大，大约有 100 GB。我正在考虑使用 __builtin_prefetch():

while (current_item && (struct my_struct *)(mmap_base + current_item) -> key < the_key){
    __builtin_prefetch(mmap_base + ((struct my_struct *)(mmap_base + current_item) -> next), 0, 0);
    /* Do something less performance critical */
    current_item = (struct my_struct *)(mmap_base + current_item) -> next;
}

但是，这是行不通的。看起来 __builtin_prefetch() 对 mmap 内存毫无用处。
然后我尝试了 madvise():

while (current_item && (struct my_struct *)(mmap_base + current_item) -> key < the_key){
    madvise(mmap_base + ((struct my_struct *)(mmap_base + current_item) -> next), sizeof(struct my_struct), MADV_WILLNEED);
    /* Do something less performance critical */
    current_item = (struct my_struct *)(mmap_base + current_item) -> next;
}

然而，这甚至降低了性能，分析显示 madvise() 调用现在成为主要开销。

是否有一些内置编译器（x86_64、GCC）或其他方法告诉内核（linux）将数据从磁盘预取到 memory/CPU 缓存中？

编辑 1：
一些人认为，如果不改进数据局部性，这是根本不可能的。然而，在这种情况下，我确实想知道为什么在转到“性能不那么关键”的部分时不可能对磁盘进行异步读取，这应该允许更快的访问；是更多关于内核没有实现这个还是只是 theoretical/physical 限制？

编辑 2：
一些建议使用单独的线程来预访问内存，以便让内核预取它们。但是，我认为线程可能很昂贵。每次预取都启动一个线程真的有用吗？代码处于紧密循环中，因此这可能意味着需要 started/joined 很多线程。另一方面，如果我只使用一个线程，我应该如何与它沟通预取的内容？

Answer 1

这种类型的访问模式总是很慢，因为它可能会跳来跳去，没有任何明智的方式来预测模式。

我会尝试的方法是生成一个单独的 memory-mapped 键索引文件，其中仅包含键值和相应记录的偏移量；键按升序排序。这样，使用非常简单的二进制搜索，找到一个特定的键大约需要 O(log N) 的时间复杂度（取决于你如何处理重复的键）。

如果在运行过程中修改了100GB文件中的key，单个平面文件不适合描述数据。

如果你能处理代码的复杂性，数组形式的分区二叉搜索树有更好的性能。在这种情况下，您将索引文件分成 fixed-size 部分，比如 64 kB（4096 key-offset 对），以数组形式包含完美平衡二叉搜索树的矩形部分。例如，第一个分区包含中间键、1/4 和 3/4 键、1/8、3/8、5/8 和 7/8 键，等等。此外，您只在主索引文件中包含键，并使用辅助索引文件作为记录偏移量。（如果你有重复的键，让二级索引文件引用第一个，每个重复的第二个索引文件条目引用下一个，所以你可以直接跟踪链，但没有额外的时间损失 space费用。）

这比对已排序数组的二进制搜索具有更好的局部性，但代码和逻辑复杂性有点令人生畏。

在 c 中使用文件支持的 mmap 进行预取

Prefetch with file backed mmap in c

c

linux

gcc

mmap