基准测试

大多数好的软件工程实践都以这样或那样的方式解决了加快开发周期的问题：你希望更快地编译软件（构建系统），尽快发现错误（静态分析、持续集成），在新版本准备好后立即发布（持续部署），并毫不拖延地对用户反馈做出反应（敏捷开发）。

性能工程也不例外。如果你做得正确，它也应该类似于一个周期：

运行程序并收集指标。
找出瓶颈在哪里。
移除瓶颈，然后转到步骤1。

在本节中，我们将讨论基准测试，并讨论一些实用的技术，这些技术可以缩短此周期并帮助你更快地迭代。大多数建议都来自于本书的编写，因此你可以在本书的代码库中找到许多真实示例。

C++内部的基准测试

编写基准测试代码有很多方法。最流行的方法也许是在一个文件中包含几个要比较的相同语言实现，从主函数中分别调用它们，并在同一源文件中计算所有需要的指标。

这种方法的缺点是，你需要编写大量的样板代码（boilerplate code），并为每个实现重复它，但这可以用元编程（metaprogramming）解决一部分。例如，当你要对多个gcd实现进行基准测试时，可以使用此高阶函数来显著减少基准测试代码：

const int N = 1e6, T = 1e9 / N;
int a[N], b[N];

void timeit(int (*f)(int, int)) {
    clock_t start = clock();

    int checksum = 0;

    for (int t = 0; t < T; t++)
        for (int i = 0; i < n; i++)
            checksum ^= f(a[i], b[i]);
    
    float seconds = float(clock() - start) / CLOCKS_PER_SEC;

    printf("checksum: %d\n", checksum);
    printf("%.2f ns per call\n", 1e9 * seconds / N / T);
}

int main() {
    for (int i = 0; i < N; i++)
        a[i] = rand(), b[i] = rand();
    
    timeit(std::gcd);
    timeit(my_gcd);
    timeit(my_another_gcd);
    // ...

    return 0;
}

这是一种开销非常低的方法，可以让你运行更多次的实验，并从中获得更准确的结果。你仍然需要执行一些重复的操作，但它们在很大程度上可以通过框架实现自动化，谷歌基准库是C++最流行的选择。一些编程语言也有方便的内置工具用于基准测试：这里特别提一下Python的timeit函数和Julia的@benchmark宏。

尽管在执行速度方面效率很高，但C和C++并不是最具生产效率的语言，尤其是在分析方面。当你的算法依赖于一些参数（如输入大小），并且你需要从每个实现中收集不止一个数据点时，你确实希望将基准测试代码与外部环境集成，并使用其他方法分析结果。

拆分实现

提高模块性和可重用性的一种方法是将所有测试和分析代码与算法的实际实现分离，并在不同的文件中实现不同的版本，但具有相同的接口。

在C/C++中，你可以通过创建单个头文件（例如gcd.hh）来实现，头文件中包含函数接口，所有基准测试代码都在main函数中：

int gcd(int a, int b); // to be implemented

// for data structures, you also need to create a setup function
// (unless the same preprocessing step for all versions would suffice)

int main() {
    const int N = 1e6, T = 1e9 / N;
    int a[N], b[N];
    // careful: local arrays are allocated on the stack and may cause stack overflow
    // for large arrays, allocate with "new" or create a global array

    for (int i = 0; i < N; i++)
        a[i] = rand(), b[i] = rand();

    int checksum = 0;

    clock_t start = clock();

    for (int t = 0; t < T; t++)
        for (int i = 0; i < n; i++)
            checksum += gcd(a[i], b[i]);
    
    float seconds = float(clock() - start) / CLOCKS_PER_SEC;

    printf("%d\n", checksum);
    printf("%.2f ns per call\n", 1e9 * seconds / N / T);
    
    return 0;
}

然后，为每个算法版本创建实现文件（例如v1.cc、v2.cc等，或者一些有意义的名称（如果适用）），这些文件都包括上述头文件：

#include "gcd.hh"

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

这样做的最终目的是能够在不接触任何源代码文件的情况下，通过命令行对特定的算法版本进行基准测试。为此，你可能还想暴露基准测试可能具有的任何参数——例如，可以通过从命令行参数解析它们：

int main(int argc, char* argv[]) {
    int N = (argc > 1 ? atoi(argv[1]) : 1e6);
    const int T = 1e9 / N;

    // ...
}

另一种方法是使用C风格的全局宏定义，然后用-D N=...标志在编译期间传入它们：

#ifndef N
#define N 1000000
#endif

const int T = 1e9 / N;

通过这种方式，你可以利用编译期常数，这可能对某些算法的性能非常有益，但每次更改参数时都必须重新构建程序，这大大增加了收集一系列性能度量指标所需的时间。

Makefiles

通过拆分源文件，可以使用带缓存的构建系统（如Make）加快编译速度。

我通常会在我的项目中携带这样一个版本的Makefile：

compile = g++ -std=c++17 -O3 -march=native -Wall

%: %.cc gcd.hh
	$(compile) $< -o $@ 

%.s: %.cc gcd.hh
	$(compile) -S -fverbose-asm $< -o $@

%.run: %
	@./$<

.PHONY: %.run

现在，你可以使用make example编译example.cc，并使用make example.run来自动运行它。

你还可以在Makefile中添加用于计算统计信息的脚本，或者将其与perf stat调用结合起来，以使分析自动化。

Jupyter Notebooks

为了加快high-level分析，你可以创建一个Jupyter notebook，用于放置所有的脚本和绘制所有的绘图。

添加一个用于基准测试的包装器很方便，它只返回一个标量结果：

def bench(source, n=2**20):
    !make -s {source}
    if _exit_code != 0:
        raise Exception("Compilation failed")
    res = !./{source} {n} {q}
    duration = float(res[0].split()[0])
    return duration

然后你可以使用它来编写干净的分析代码：

ns = list(int(1.17**k) for k in range(30, 60))
baseline = [bench('std_lower_bound', n=n) for n in ns]
results = [bench('my_binary_search', n=n) for n in ns]

# plotting relative speedup for different array sizes
import matplotlib.pyplot as plt

plt.plot(ns, [x / y for x, y in zip(baseline, results)])
plt.show()