c - 测试算法速度。如何？

Question

我目前正在测试不同的算法，这些算法确定整数是否是真正的平方。在我的研究过程中，我在 SOF 发现了这个问题: Fastest way to determine if an integer's square root is an integer

我对编程领域比较陌生。当测试问题中提出的不同算法时，我发现这个

bool istQuadratSimple(int64 x)
{
    int32 tst = (int32)sqrt(x);
    return tst*tst == x;
}

实际上比我发布的问题中 A. Rex 提供的更快。我使用 NS-Timer 对象进行此测试，并使用 NSLog 打印结果。

我现在的问题是:如何以专业的方式进行速度测试？如何获得与我在上面发布的问题中提供的结果相同的结果？

Answer 1

在循环中仅调用此函数的问题是所有内容都将位于缓存中(数据和指令)。你不会测量任何有意义的东西；我不会那样做。

考虑到这个函数有多小，我会尝试查看该函数和另一个函数生成的汇编代码，然后尝试根据汇编代码进行推理(例如指令数和 cost of the individual instructions ) )。

不幸的是，它只适用于微不足道/接近微不足道的情况。例如，如果汇编代码相同，那么您就知道没有差异，无需测量任何内容。或者，如果一个代码与另一个代码相似，再加上附加说明；在这种情况下，您知道时间越长的执行时间就越长。还有一些不太清楚的情况......:(
(请参阅下面的更新。)

您可以使用 clang 中的 -S -emit-llvm 标志和 gcc 中的 -S 标志获取程序集。

希望这有帮助。

---

---

更新:回复 Prateek's question in the comment “有什么方法可以确定一种特定算法的速度吗？”

是的，这是可能的，但它很快就会变得非常复杂。长话短说，忽略现代处理器的复杂性并简单地累积一些与指令相关的预定义成本可能会导致非常非常不准确的结果(由于缓存和管道等原因，估计值相差 100 倍)。如果您尝试考虑现代处理器、分层缓存、管道等的复杂性，事情就会变得非常困难。例如，参见Worst Case Execution Time Prediction .

除非您处于明确的情况(琐碎/近乎琐碎的情况)，例如生成的汇编代码是相同的或者一个与另一个相似加上一些指令，否则也很难根据生成的汇编来比较算法。

但是，这里显示了两行的简单函数，为此，查看程序集可能会有所帮助。这就是我的答案。