比较 BFS 算法的两种不同实现时了解性能细节
Understanding perf detail when comparing two different implementations of a BFS algorithm
以下结果是在具有 32 个内核的计算服务器上使用 perf 测得的。我知道我的实现是未优化的，但我是故意的，因为我想进行比较。我知道图形算法往往具有研究人员试图解决的低局域性。
不过我不清楚结果。流逝的时间具有误导性。我的实现在大约 10 秒内运行了一个具有大约 4mm 节点的图形，其余时间进行预处理。优化版本使用相同的输入并遍历大约 10 次，每次不到一秒，因此它实际上只是预处理时间。我不想达到同样的目的。只是理解为什么这可能基于性能。
我发现我的页面错误要高得多。我不是 100 确定为什么会这样，因为注释（据我所知）没有指向我的代码的任何特定部分...
__gnu_cxx::new_allocator<std::_List_node<int> >::construct<int, int const&>
这似乎是我处理图形本身的时候，因为我为邻接列表创建了链表。我认为这实际上可能会导致问题，并且无论如何都想进行调查。我应该能够通过切换到锯齿状数组来改善页面错误（并希望提高性能）？
优化后的算法有更高的最后一级缓存未命中率，我认为这可以解释局部性较低的 BFS/图算法的主要问题，但性能似乎不受此影响，我的未优化算法明显较低。
然后是前端/后端周期，在比较两者时，就性能问题而言似乎是相反的 - 我在前端更差，而优化在后端更差。
我是否遗漏或不理解一些明显的东西？我认为在查看 perf 时会出现一些明显的低局部性问题，但我对优化版本感到困惑。
这是我未优化的并行 BFS 的实现（运行 一次）...
这是使用来自基准套件的优化并行 BFS（运行 10 次）...
在进行并行搜索之前，两者都需要大约 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 亿，而您的算法的 LLC 未命中数约为 380，但在此基准测试中，您是 运行 优化算法的 10 倍而你只有一次。因此，优化后的算法可能有 6200 万次未命中，而您的算法有 六倍 LLC 未命中的次数。是的，您的算法具有较低的 LLC 未命中率 - 但 LLC 未命中的绝对数量对性能至关重要。较低的未命中率仅意味着您进行的总访问次数多于 6 倍的数字：基本上您进行的内存访问次数比优化版本多很多，这会导致更高的命中率但总的未命中次数更多。
所有这些都指向在未优化的算法中访问更多的总内存，或者可能以缓存不友好的方式访问它。这也可以解释更高数量的页面错误。总的来说，这两种算法的 IPC 都很低，而你的特别低（0.49 IPC）并且考虑到没有分支预测问题，并且你已经将这些算法识别为具有 locality/memory 访问问题的图算法，停顿而等待内存的可能性很大。
幸运的是，有一种更好的方法可以尝试根据 perf stat 输出对可能的瓶颈进行逆向工程。英特尔开发了 whole methodology which tries to this type of top-down analysis in a way that determines the true bottlenecks. It's not perfect, but it's far and away better than looking at the plain perf stat counters. VTune isn't free, but you can get a similar analysis based on the same methodology effect using Andi Kleen's toplev。我强烈建议您从这里开始。
以下结果是在具有 32 个内核的计算服务器上使用 perf 测得的。我知道我的实现是未优化的，但我是故意的，因为我想进行比较。我知道图形算法往往具有研究人员试图解决的低局域性。
不过我不清楚结果。流逝的时间具有误导性。我的实现在大约 10 秒内运行了一个具有大约 4mm 节点的图形，其余时间进行预处理。优化版本使用相同的输入并遍历大约 10 次，每次不到一秒，因此它实际上只是预处理时间。我不想达到同样的目的。只是理解为什么这可能基于性能。
我发现我的页面错误要高得多。我不是 100 确定为什么会这样，因为注释（据我所知）没有指向我的代码的任何特定部分...
__gnu_cxx::new_allocator<std::_List_node<int> >::construct<int, int const&>
这似乎是我处理图形本身的时候，因为我为邻接列表创建了链表。我认为这实际上可能会导致问题，并且无论如何都想进行调查。我应该能够通过切换到锯齿状数组来改善页面错误（并希望提高性能）？
优化后的算法有更高的最后一级缓存未命中率，我认为这可以解释局部性较低的 BFS/图算法的主要问题，但性能似乎不受此影响，我的未优化算法明显较低。
然后是前端/后端周期，在比较两者时，就性能问题而言似乎是相反的 - 我在前端更差，而优化在后端更差。
我是否遗漏或不理解一些明显的东西？我认为在查看 perf 时会出现一些明显的低局部性问题，但我对优化版本感到困惑。
这是我未优化的并行 BFS 的实现（运行 一次）...
这是使用来自基准套件的优化并行 BFS（运行 10 次）...
在进行并行搜索之前，两者都需要大约 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 亿，而您的算法的 LLC 未命中数约为 380，但在此基准测试中，您是 运行 优化算法的 10 倍而你只有一次。因此，优化后的算法可能有 6200 万次未命中，而您的算法有 六倍 LLC 未命中的次数。是的，您的算法具有较低的 LLC 未命中率 - 但 LLC 未命中的绝对数量对性能至关重要。较低的未命中率仅意味着您进行的总访问次数多于 6 倍的数字：基本上您进行的内存访问次数比优化版本多很多，这会导致更高的命中率但总的未命中次数更多。
所有这些都指向在未优化的算法中访问更多的总内存，或者可能以缓存不友好的方式访问它。这也可以解释更高数量的页面错误。总的来说，这两种算法的 IPC 都很低，而你的特别低（0.49 IPC）并且考虑到没有分支预测问题，并且你已经将这些算法识别为具有 locality/memory 访问问题的图算法，停顿而等待内存的可能性很大。
幸运的是，有一种更好的方法可以尝试根据 perf stat 输出对可能的瓶颈进行逆向工程。英特尔开发了 whole methodology which tries to this type of top-down analysis in a way that determines the true bottlenecks. It's not perfect, but it's far and away better than looking at the plain perf stat counters. VTune isn't free, but you can get a similar analysis based on the same methodology effect using Andi Kleen's toplev。我强烈建议您从这里开始。