现代硬件算法[5.1]: 性能检测

性能检测（Instrumentation）是一个非常复杂的术语，意思是将计时器和其他跟踪代码插入程序中。最简单的例子是在类Unix系统中使用time来测量整个程序的执行持续时间。

更一般的情况，我们想知道程序的哪些部分需要优化。编译器和IDE附带的一些工具可以自动对指定函数进行计时，但使用本语言提供的任何与时间交互的方法，手动执行计时更为鲁棒：

clock_t start = clock();
do_something();
float seconds = float(clock() - start) / CLOCKS_PER_SEC;
printf("do_something() took %.4f", seconds);

这里的一个细节是，你不能用这种方式测量特别快速的函数的执行时间，因为clock函数以微秒( $10^{-6}$ )为单位返回当前时间戳，并且其本身也需要高达几百纳秒才能完成。类似地，所有其他与时间相关的实用程序都具有至少微秒的粒度，这在低级别优化的世界中是约定俗成的。

为了获得更高的精度，可以在循环中重复调用待测函数，对整个过程计时一次，然后将总时间除以迭代次数：

#include <stdio.h>
#include <time.h>

const int N = 1e6;

int main() {
    clock_t start = clock();

    for (int i = 0; i < N; i++)
        clock(); // benchmarking the clock function itself

    float duration = float(clock() - start) / CLOCKS_PER_SEC;
    printf("%.2fns per iteration\n", 1e9 * duration / N);

    return 0;
}

你还需要确保没有任何内容被缓存、被编译器优化或受到类似副作用的影响。这是一个单独的、更加复杂的主题，我们将在本章末尾更详细地讨论。

事件抽样

性能检测还可以用于收集其他类型的信息，这些信息可以提供关于特定算法性能的有用建议。例如：

对于哈希函数，我们感兴趣的是其输入的平均长度；
对于二叉树，我们关心它的大小和高度；
对于排序算法，我们想知道它会做多少次比较。

以类似的方式，我们可以在代码中插入计数器，以统计这些特定算法的信息。

添加计数器的缺点是引入了开销，尽管你可以通过只对一小部分调用随机执行来减轻大部分开销：

void query() {
    if (rand() % 100 == 0) {
        // update statistics
    }
    // main logic
}

如果采样率足够小，那么每次调用的开销就只有随机数生成和条件检查。有趣的是，我们可以用一些统计魔法来优化它。

从数学上讲，我们在这里所做的是从伯努利分布中反复采样（ $P$ 等于采样率），直到我们采样成功为止。还有另一个分布（几何分布）告诉我们需要进行多少次伯努利采样的迭代才能获取一个正样本。我们可以用几何分布的值作为减少的计数器：

void query() {
    static next_sample = geometric_distribution(sample_rate);
    // if (next_sample--) {		// 原文档代码
    if (next_sample-- == 0) {	// 译者注
    	next_sample = geometric_distribution(sample_rate);
        // ...
    }
    // ...
}