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 .

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

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