benchmark

大多数好的软件工程实践以某种方式都在解决加快开发周期的问题：你想更快地编译软件（构建系统），尽早发现错误（静态分析、持续集成），一旦新版本准备就绪就发布（持续部署），并且在不需要太多延迟的情况下对用户反馈做出反应（敏捷开发）。

性能工程也不例外。如果正确执行，它也应该类似于一个循环：

运行程序并收集指标。 找出瓶颈所在。 移除瓶颈并回到步骤1。 在本节中，我们将讨论基准测试，并讨论一些使这个循环更短，帮助你更快迭代的实用技术。大多数建议来自于这本书的工作，因此你可以在这本书的代码仓库中找到许多描述的设置的真实例子。

在C++内部进行基准测试

编写基准测试代码有几种方法。也许最受欢迎的一种是在一个文件中包含几个想要比较的同一语言实现，分别从main函数调用它们，并在同一个源文件中计算你想要的所有指标。

这种方法的缺点是你需要编写大量的样板代码并为每个实现重复它，但可以通过元编程部分中和。例如，当你在对多个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++来说，Google基准测试库是最受欢迎的选择。一些编程语言还有方便的内置工具进行基准测试：这里特别提到Python的timeit函数和Julia的@benchmark宏。

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

分割实现

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

在C/C++中，你可以通过创建一个单独的头文件（例如，gcd.hh）来做到这一点，其中包含函数接口和其所有基准测试代码在main中：

int gcd

(int a, int b); // 待实现

// 对于数据结构，你还需要创建一个设置函数
// （除非所有版本的相同预处理步骤就足够）

int main() {
    const int N = 1e6, T = 1e9 / N;
    int a[N], b[N];
    // 注意：局部数组分配在栈上，可能导致大数组栈溢出
    // 对于大数组，用"new"分配或创建全局数组

    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;

这样你可以利用编译时常量，这对某些算法的性能可能非常有利，但代价是每次想改变参数时都必须重新构建程序，这大大增加了你需要在一系列参数值中收集指标的时间。

Makefile

分割源文件允许你使用诸如Make这样的缓存构建系统加速编译。

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

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

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

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

%.run: %
	@./lt;

.PHONY: %.run

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

你也可以在Makefile中添加脚本来计算统计数据，或者将其与perf stat调用结合起来使性能分析自动化。

Jupyter笔记本

为了加速高级分析，你可以创建一个Jupyter笔记本，在其中放置所有脚本并做所有绘图。

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

def bench(source, n=2**20):
    !make -s {source}
    if _exit_code != 0:
        raise Exception("Compilation failed")
    res = !./{source} {n}
    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]

# 绘制不同数组大小的相对加速图
import matplotlib.pyplot as plt

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

一旦建立，这种工作流使你能够更快地迭代，并专注于优化算法本身。