c++ - 找到最昂贵的方法并评估/分析它们

Question

我想知道是否有可用的技术或工具可以告诉您执行特定方法需要多少时间。

类似于数学/计算机科学中的大 O 符号可以让您了解算法的复杂性，我想知道代码分析是否有类似的东西。

Answer 1

分析是一种分析程序以确定在特定功能或方法中花费的相对时间量的方法。它对于凭经验发现程序中的性能问题很有用。例如，使用 GCC，您可以：

• -pg使用启用分析的选项编译程序。

• 运行可执行文件以生成一个名为 的文件gmon.out，其中包含有关程序实际运行时的运行时特性的信息。

• 运行gprof以显示由检测的可执行文件生成的信息。

一般来说，人类分析是发现特定算法的渐近（即大O）复杂性的唯一方法——据我所知，没有机械的方法可以做到这一点。

Answer 2

如果您想知道一个函数花费了多少时间，请使用所谓的“分析器”。

但是，复杂性分析超出了分析器的范围，因为分析器会告诉您运行一次程序时会发生什么，而复杂性会告诉您在运行具有越来越大的输入的无限程序序列时会发生什么的极限行为。

所以：你想知道你的程序中哪些函数是最昂贵的（在这种情况下为你的 C++ 实现找到一个分析器并遵循它的文档），或者你想知道时间复杂度（在这种情况下你几乎需要一个人工分析您的代码）？

Answer 3

您应该尝试在 callgrind 启动的情况下运行您的代码，它会记录调用了哪些函数、调用了多少次，但代码运行速度会慢 20 倍左右。获得 callgrind 输出后，您应该使用 kcachegrind 打开它以查看调用的树结构。在那里你可以四处浏览，看看你在哪里有瓶颈

有用的链接：
kcachegrind http://kcachegrind.sourceforge.net/html/Home.html
callgrind 文档http://valgrind.org/docs/manual/cl-manual.html
（valgrind 是框架，callgrind 是组件）
如何如果程序产生进程并且您也想分析这些进程，则启动 callgrind（用您的程序替换 sage bench.py​​）https://github.com/titusnicolae/pynac-callgrind/blob/master/run.sh
编辑： “- -instr-atstart=no" 如果您不打算稍后启用检测，则应从参数列表中删除

Answer 4

这与停机问题有何不同？

请注意，我可以使用您的自动复杂性分析器轻松解决停机问题——您的问题更难。停机问题已经无法确定。