以下结果是在具有 32 个内核的计算服务器上使用 perf 测量的。我知道我的实现是未优化的，但我是故意的，因为我想进行比较。我知道图算法往往具有研究人员试图解决的低局域性。
不过，我不清楚结果。流逝的时间具有误导性。我的实现在大约 10 秒内运行了一个具有大约 4mm 节点的图形，其余时间进行预处理。优化版本使用相同的输入并遍历大约 10 次，每次不到一秒，因此它实际上只是预处理时间。我不想达到同样的目的。只需了解为什么这可能基于性能。
我发现我的页面错误要高得多。我不是 100 确定为什么会这样，因为注释(据我所知)没有指向我的代码的任何特定部分......
__gnu_cxx::new_allocator<std::_List_node<int> >::construct<int, int const&>
这似乎是我处理图形本身的时候，因为我为邻接列表创建了链表。我认为这实际上可能会导致问题，并且无论如何都想进行调查。我应该能够通过切换到锯齿状数组来改善页面错误(并希望提高性能)？
优化后的算法有更高的最后一级缓存未命中率，我认为这可以解释具有低局部性的 BFS/图算法的主要问题，但性能似乎不受此影响，我的未优化算法明显较低。
然后是前端/后端循环，在比较两者时，它们在性能问题上似乎是相反的——我在前端更差，而优化的在后端更差。
我是否遗漏或不理解一些明显的东西？我认为在查看 perf 时会出现明显的低局部性问题，但我对优化版本感到困惑。
这是我未优化的并行 BFS 的实现(运行一次)...
这是使用来自基准套件(运行 10 次)的优化并行 BFS...
在进行并行搜索之前，两者都需要大约 40 秒来预处理一次数据。
最佳答案
不幸的是，perf stat 通常没有提供足够的信息来真正确定应用程序中的瓶颈所在。可能有两个应用程序具有截然不同的底层瓶颈，但具有非常相似的 perf stat 配置文件。例如，两个应用程序可能有相同数量或比例的 L2 缓存未命中，但一个应用程序可能受此影响为主，而另一个应用程序可能几乎完全不受影响，具体取决于重叠工作的数量和性质。
因此，如果您尝试从这些高级计数器进行深入分析，您通常只是在暗中摸索。我们仍然可以做一些观察。你提到:
The optimized algorithm has a much higher last level cache miss which I thought would explain the primary issue with BFS / graph algorithms with low locality but performance seems to be unaffected by this and my unoptimized is significantly lower.
首先，优化算法的 LLC 未命中数约为 6.2 亿，您的算法的未命中数约为 380，但您在此基准测试中运行优化算法 10 次，而您的只运行一次。因此，优化后的算法可能有 6200 万次未命中，而您的算法的 LLC 未命中次数是六倍。是的，您的算法具有较低的 LLC 未命中率 - 但 LLC 未命中的绝对数量才是衡量性能的关键。较低的未命中率仅意味着您进行的总访问次数多于 6 倍的数字:基本上您进行的内存访问比优化版本多很多，这导致更高的命中率但总未命中次数更多。
所有这些都指向在未优化的算法中访问更多的总内存，或者可能以缓存不友好的方式访问它。这也可以解释更高数量的页面错误。总的来说，这两种算法的 IPC 都很低，而你的特别低(0.49 IPC)并且考虑到没有分支预测问题，并且你已经将这些算法识别为具有局部性/内存访问问题的图形算法，在等待时停顿内存很有可能。
幸运的是，有一种更好的方法可以尝试根据 perf stat 输出对可能的瓶颈进行逆向工程。英特尔开发了一个 whole methodology它试图以一种确定真正瓶颈的方式进行这种自上而下的分析。它并不完美，但比查看普通的 perf stat 计数器要好得多。 VTune 不是免费的，但您可以使用 Andi Kleen 的 toplev 获得基于相同方法效果的类似分析。 .我强烈建议您从这里开始。
关于algorithm - 比较 BFS 算法的两种不同实现时了解性能细节，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49907288/