如何从路径列表中优化目录列表？

写保险丝文件系统时，我有一个unordered_map<std::string, struct stat>作为缓存，它在启动时为所有文件和目录启动以减少硬盘驱动器上的读取。如何从路径列表中优化目录列表？

为了满足readdir()回调我写了下面的循环：

const int sp = path == "/" ? 0 : path.size(); 
for (auto it = stat_cache.cbegin(); it != stat_cache.cend(); it++) 
{ 
    if (it->first.size() > sp) 
    { 
     int ls = it->first.find_last_of('/'); 
     if (it->first.find(path, 0) == 0 && ls == sp) 
      filler(buf, it->first.substr(ls + 1).c_str(), const_cast<struct stat*>(&it->second), 0, FUSE_FILL_DIR_PLUS); 
    } 
}

的想法是一个对象，它的路径与目录路径开始且其最后的斜杠的目录路径的终点将是一个它的成员。我已经彻底地测试了它，它的工作原理。
插图：

Reading directory: /foo/bar 
Candidate file: /bazboo/oof - not in dir (wrong prefix) 
Candidate file: /foo/bar/baz/boo - not in dir (wrong lastslash location) 
Candidate file: /foo/bar/baz - in dir!

然而现在，这是惊人的慢（尤其是在文件系统有50多万的物体在高速缓存）。 Valgrind/Callgrind特别指责std::string:find_last_of()和std::string::find()电话。

我已经添加了if (it->first.size() > sp)以尝试加速循环，但性能增益最多是最小的。

我也尝试了通过在四个区块中并行化循环来加速这个例程，但是在unordered_map::cbegin()期间以段错误结束。
我没有实际的代码了，但我相信它看起来是这样的：

const int sp = path == "/" ? 0 : path.size(); 
ThreadPool<4> tpool; 
ulong cq = stat_cache.size()/4; 
for (int i = 0; i < 4; i++) 
{ 
    tpool.addTask([&]() { 
     auto it = stat_cache.cbegin(); 
     std::next(it, i * cq); 
     for (int j = 0; j < cq && it != stat_cache.cend(); j++, it++) 
     { 
      if (it->first.size() > sp) 
      { 
       int ls = it->first.find_last_of('/'); 
       if (it->first.find(path, 0) == 0 && ls == sp) 
        filler(buf, it->first.substr(ls + 1).c_str(), const_cast<struct stat*>(&it->second), 0, FUSE_FILL_DIR_PLUS); 
      } 
     } 
    }); 
} 
tpool.joinAll();

我也试图与通过地图桶，这unordered_map::cbegin(int)提供了一个方便的过载拆分它，但它仍然隔断了。

同样，我目前正在使用第一个（非并行）代码，并且希望对那个代码有所帮助，因为并行化代码没有工作。我只是认为我会把我的并行尝试包括在内，以便完整性，小白点和努力证明。

是否有任何其他优化此循环的选项？

来源

2017-10-04 Cobra_Fast

如果代码在其他方面工作，并且您只是要求优化速度/效率，那么您应该在[CodeReview]（http://codereview.stackexchange.com）上发布此代码。 –

使用不是'unordered_map'而是'map'，调用'upper_bound'传入目录名以查找O（lg N）中的第一个条目，然后所有其他条目都相邻。 'readdir'的最终成本：O（k + lg N） –

的一件小事在这里做的是改变从这个if：

if (it->first.find(path, 0) == 0 && ls == sp)

简单：

if (ls == sp && it->first.find(path, 0) == 0)

显然，比较两个整数比找一个子快得多。
我不能保证它会改变性能，但这是一件微不足道的事情，可以帮助跳过很多不必要的std::string::find调用。也许编译器已经做到了，我会研究反汇编。另外，由于filepathes无论如何都是唯一的，所以我会使用std::vector<std::pair<...>>来代替 - 更好的缓存局部性，更少的内存分配等等，只要记住先保留大小即可。

来源

2017-10-04 16:10:55

另一个微不足道的修改是'it-> first.find_last_of（'/'，sp）;' –

我不确定std :: vector >'会是一个不错的选择，因为缓存会根据字符串键获得大量随机访问，例如'getattr（）'调用。有了vector，我必须扫描整个事物，直到找到它不再是O（1）的unordered_map承诺的地方。对？ –

@Cobra_Fast您可以添加所有路径并对它们进行排序，然后使用二进制搜索查找特定键。一如既往，只有基准这两个建议，才能保证性能的提高，这些都是理论。 –

真正的问题是

for (auto it = stat_cache.cbegin(); it != stat_cache.cend(); it++)

有效去除unordered_maps最大的优势和暴露出的弱点之一。你不仅没有O（1）查找，而且你可能需要搜索地图来查找条目，这使得O（N）的O（N）有非常大的K（如果不是额外的N即O（N^2））。

最快的解决方案是O（1）用于查找（在幸运的无序映射中），O（strlen（目标））在桶中或O（lgN）在二进制中。然后沿struct stat有孩子的名单，为O（#children）。

来源

2017-10-04 20:44:07 Surt

如何从路径列表中优化目录列表？

回答

相关问题