CPU指令与持续时间之间的关系

Question

我有两个不同的用于解决数学问题的C++程序（程序A和B）

相比之下，A的表现比B好大约10倍（以持续时间为衡量）。现在，我通过valgrind工具callgrind计算了执行的CPU指令数量，并意识到程序A只需要程序B执行指令数量的1/3。我本来期望这个因素大约是1/10。

我知道有些CPU指令需要更多的CPU周期（例如内存访问），但是按设计，A应该包含比B更多的此类昂贵的指令。
另外，我不知道callgrind如何计算这些指令（在文档中找不到任何相关信息）。
有人能给出这种行为的合理解释吗？谢谢！

编辑：（由于评论）
不幸的是，代码太复杂了，无法在此处发布...两个程序都在同一台机器上运行。两者都是完全并行化的（每个线程运行程序的独立副本，只需告诉其他线程何时找到了解决方案）。但是指令计数是在一个线程上完成的，因为callgrind无论如何都会对程序进行排序。如上所述，A需要比B更多的内存。
我不希望得到完全正确的答案，只是给我一些提示，可以解释这个问题的原因。

- Memphisd

---

有许多因素会影响程序的持续时间。代码局部性、CPU缓存大小和并行化可能性都会起作用。如果不看你的代码和汇编输出，几乎不可能确定。 - RedX

有很多可能性。例如，程序B可以将一些日志数据输出到硬盘上。或者它可能没有被适当地优化。或者使用了较慢的算法。如果没有看到实际代码，就无法确定。 - Ari0nhh

考虑到L1缓存未命中的速度大约比缓存命中慢10倍，我怀疑内存访问模式比指令计数更可能成为主导因素。 - Martin Bonner supports Monica

一条导致停顿的指令可能比大量立即执行的指令昂贵数百倍。 - Kerrek SB

不需要提供完整的代码。您应该创建一个MCVE（最小化可重现代码示例）或SSCCE（简短、自包含、可运行的示例）。 - phuclv

Answer 1

你没有说明运行的平台，每个CPU都有自己的一套做和不做的规则。

例如，在x86上，指令数量与总执行时间之间几乎没有相关性，因为：

1. x86首先将指令翻译成内部微操作码（uops），然后运行它们，因此它实际上执行的是与可执行文件中对人类可见的机器码完全不同的代码。它还会重新排序uops，因此即使你模拟翻译，也无法确定这些操作的执行顺序（除非你模拟CPU、缓存和内存的整个体系结构）。
2. 多个uop可以在单个时钟周期内执行，或者反过来，单个uop可能会阻塞CPU数个时钟周期，因此任何两个x86指令的执行时间可能相差100倍以上（即使在两次运行中相同的指令如果在缓存未命中时会有截然不同（约100倍）的执行时间）。
3. 内存访问。内存比CPU慢得多，因此按可预测的顺序顺序读取内存，并尽可能紧凑地存储数据（以充分重用缓存）比指令数量（算法）更关键。在一些极端情况下，一个设计良好的数据结构可以击败甚至更好的算法，例如对于大约100k个项目，使用随机插入/删除的std::vector<int>比链表快得多，尽管向量的插入/删除是O(n^2)，而链表仅约为O(n)。CPU手头唯一可以接触到的内存是L0缓存，L1就像在街上，L2就像去其他城市旅行，L3则是不同的国家。内存本身几乎就像在月球上。
4. 其他I/O访问...如果内存很慢，那么访问磁盘就像去太阳（SSD）或超出太阳系（HDD）。

因此，正如您所看到的，在极端情况下，x86 CPU甚至可以执行具有约200条指令+处理30倍内存的代码，其速度与具有约10条指令的不同例程相同。在边缘情况下，差异可能非常极端，通过阅读源代码难以想象。这就是为什么在x86上证明代码优化的唯一有效方法是使用接近真实数据的数据对代码进行分析。仅凭理论、大O符号和“直觉”进行“优化”可能很容易出现问题，即使是10-20年前也是如此，即使那时我们也使用工具对结果进行了分析验证。

当然，更多的指令本身更容易掉出缓存，使指令读取停顿，但如果您可以创建更好的数据结构，即使是30kiB与1kiB的代码也可以被证明是合理的（尽管在被OS中断时可能会冒很多缓存未命中的风险）。

callgrind网站表示：“可选地，缓存模拟和/或分支预测（类似于Cachegrind）可以产生有关应用程序运行时行为的进一步信息。”，因此，您可以获得比指令计数更精细的数据，并查看是否存在一些瓶颈，其中代码/数据的重新组织将使其停顿更少。

- Ped7g

---

谢谢解释。我正在使用AMD64平台。顺便说一句，我从未说过我通过指令计数或“理论、大O符号和直觉”来优化我的代码。只是想以多种方式进行比较。这些算法源于理论，因此复杂性分析存在，并且与我的实现无关。 - Memphisd

@Memphisd 是的，理论复杂度是预期性能的一个很好的普遍指标，但实现仍然可以产生巨大的（在大O符号中的顺序）差异。而且没有其他可靠的方法来衡量实现影响，除了以尽可能接近实际使用的方式进行分析。因此，1:10的时间差异基本上只取决于实现/运行时细节（理论最小输入），超过1:1000的差异几乎只能通过理论解决，忽略平台/实现细节。在硬件细节之间开始有所不同。 - Ped7g

@Memphisd：嗯...思考一下，对你来说重要的信息应该是关于数据结构和内存访问模式的影响。在你解决数据结构之前（如果你的数据非常庞大，比如1e6+计数），比较指令计数是完全无用的。一旦你优化了内存访问，那么计算指令数量就开始变得重要了，但它比内存少一个数量级的重要性。 - Ped7g

感谢您花费时间编写这篇文章...但是为了澄清，1:10的时间差异并不需要引起怀疑。实际上，算法B使用的唯一数据结构算法是一个约500x500的位矩阵，而算法A需要存储更多的数据结构（哈希表、列表、许多矩阵等），并且性能更好。从理论上讲，算法A的复杂度也更好。我想知道的是，几乎没有内存访问和1:10的时间差异，B算法只有A算法的3倍指令数。 - Memphisd