可预测地分析单个函数
Profiling a Single Function Predictably
我需要一种更好的分析数字代码的方法。假设我在 64 位 x86 上的 Cygwin 中使用 GCC，并且我不打算购买商业工具。
情况是这样的。我在一个线程中只有一个函数 运行ning。没有代码依赖性或 I/O 除了内存访问之外，可能链接的一些数学库除外。但在大多数情况下，它都是 table 查找、索引计算和数值处理。我已经缓存对齐堆和堆栈上的所有数组。由于算法、循环展开和长宏的复杂性，汇编列表可能会变得非常冗长——数千条指令。
我一直在求助于使用 Matlab 中的 tic/toc 计时器，bash shell 中的时间实用程序，或者直接使用时间戳计数器 (rdtsc)功能。问题是这样的：时序的方差（可能高达 运行时间的 20%）大于我所做的改进 ，所以我无法知道更改后代码是好是坏。你可能会认为是时候放弃了。但我不同意。如果您坚持不懈，许多渐进式改进可以使性能提高两到三倍。
有一个问题我遇到过很多次，特别让人抓狂的是，我做了一个改变，性能似乎持续提高了 20%。第二天，收益就失去了。现在有可能我做了我认为对代码无害的更改，然后完全忘记了它。但我想知道是否有可能发生其他事情。就像 GCC 可能不会像我相信的那样产生 100% 的确定性输出。或者它可能更简单，例如 OS 将我的流程移至更繁忙的核心。
我考虑了以下几点，但我不知道这些想法是否可行或有意义。如果是，我想要关于如何实施解决方案的明确说明。 目标是最大限度地减少 运行 时间的方差，以便我可以有意义地比较不同版本的优化代码。
- 将我处理器的一个核心专用于 运行 我的日常工作。
- 直接控制缓存（加载或清除缓存）。
- 确保我的 dll 或 executable 始终加载到内存中的相同位置。我的想法是，缓存的集合关联性可能与 RAM 中的 code/data 位置相互作用，以改变每个 运行.
的性能
- 某种周期精确的仿真器工具（非商业）。
- 是否可以对上下文切换进行一定程度的控制？或者它甚至重要吗？我的想法是上下文切换的时间导致了可变性，可能是由于管道在不合时宜的时间被刷新。
过去，我通过计算汇编列表中的指令在 RISC 体系结构上取得了成功。当然，这只适用于指令数量很少的情况。一些编译器（例如 TI 的 C67x 代码编写器）将为您详细分析它如何让 ALU 保持忙碌。
我还没有发现 GCC/GAS 生成的汇编列表特别有用。通过全面优化，代码到处移动。对于散布在汇编列表中的单个代码块，可以有多个位置指令。此外，即使我能理解程序集如何映射回我的原始代码，我也不确定现代 x86 机器上的指令数和性能之间是否存在很大的相关性。
我尝试使用 gcov 进行逐行分析，但由于我构建的 GCC 版本与 MinGW 编译器不兼容，它无法正常工作。
您可以做的最后一件事是对很多很多试验 运行 进行平均，但这需要很长时间。
编辑（回复：调用堆栈采样）
我的第一个问题是，实际上，我该怎么做？在您的一张幻灯片中，您展示了使用 Visual Studio 来暂停程序。我拥有的是由 GCC 编译的 DLL，在 Cygwin 中进行了全面优化。然后由 Matlab 使用 VS2013 编译器编译的 mex DLL 调用它。
我使用 Matlab 的原因是因为我可以轻松地尝试不同的参数并可视化结果，而无需编写或编译任何低级代码。此外，我可以将我的优化 DLL 与高级 Matlab 代码进行比较，以确保我的优化没有破坏任何东西。
我使用 GCC 的原因是我对它的体验比对 Microsoft 编译器的体验要丰富得多。我熟悉许多标志和扩展。此外，微软一直不愿意维护和更新原生 C 编译器 (C99)，至少在过去是这样。最后，我看到 GCC 让商业编译器脱颖而出，我查看了汇编列表以了解它实际上是如何完成的。所以我对编译器实际上如何 思考 .
有一些直觉
现在，关于猜测要修复的内容。这不是真正的问题；这更像是猜测如何 修复它。在这个例子中，就像数值算法中经常出现的情况一样，实际上没有 I/O（不包括内存）。没有函数调用。几乎没有任何抽象。这就像我坐在一块保鲜膜上。我可以看到下面的计算机体系结构，中间真的没有任何东西。如果我重新卷起所有循环，我可能可以将代码放在大约一页上，而且我几乎可以数出生成的汇编指令。然后我可以粗略比较单个内核能够执行的理论操作数，看看我离最佳状态有多近。问题是我失去了从展开中获得的自动矢量化和指令级并行化。 unrolled，汇编列表太长，无法这样分析。
关键是这段代码确实没有太多内容。然而，由于编译器和现代计算机体系结构的复杂性令人难以置信，因此即使在这个级别也有相当多的优化。但我不知道微小的变化会对编译代码的输出产生多大影响。让我举几个例子。
第一个有点含糊，但我肯定我已经见过几次了。你做了一个小的改变，得到了 10% 的改进。你做了另一个小的改变，又得到了 10% 的改进。您撤消第一个更改并获得另外 10% 的改进。嗯？编译器优化既不是线性的，也不是单调的。有可能，第二个更改需要一个额外的寄存器，它通过强制编译器更改其寄存器分配算法来破坏第一个更改。也许，第二个优化以某种方式阻碍了编译器进行优化的能力，这是通过撤消第一个优化来修复的。谁知道。除非编译器足够内省以转储其在每个抽象级别的完整分析，否则您永远不会真正知道最终的汇编是如何结束的。
这是最近发生在我身上的一个更具体的例子。我正在手工编码 AVX 内在函数以加速过滤器操作。我想我可以展开外循环来增加指令级并行性。所以我这样做了，结果是代码慢了一倍。发生的事情是没有足够的 256 位寄存器可供使用。所以编译器暂时将结果保存在堆栈上，这会降低性能。
正如我在 this post 中暗示的那样，您对此发表了评论，最好告诉编译器您想要什么，但不幸的是，您通常别无选择，被迫手动调整优化，通常通过猜测并检查。
所以我想我的问题是，在这些情况下（代码在展开之前实际上很小，每个增量性能变化很小，并且您在非常低的抽象级别上工作），会更好吗有 "precision of timing" 还是调用堆栈采样更好地告诉我 哪个代码更好 ?
我前段时间遇到过类似的问题，但那是在 Linux 上，这使得它更容易调整。基本上由 OS（称为 "OS jitter"）引入的噪音在 SPEC2000 测试中高达 5-10%（我可以想象它在 Windows 上要高得多，因为英国媒体报道软件的数量要多得多） .
我能够通过以下组合将偏差降低到 1% 以下：
- 禁用动态频率缩放（最好在 BIOS 和 Linux 内核中都这样做，因为并非所有内核版本都能可靠地做到这一点）
- 禁用内存预取和其他花哨的设置，如 "Turbo boost" 等（BIOS，再次）
- 禁用超线程
- 在内核中启用高性能进程调度程序
- 将进程绑定到核心以防止线程迁移（使用核心 0 - 由于某种原因它在我的内核上更可靠，请看图）
- 启动到单用户模式（其中没有服务 运行）——这在基于 systemd 的现代发行版中并不容易
- 禁用 ASLR
- 禁用网络
- 删除OS页面缓存
可能还有更多，但 1% 的噪音对我来说已经足够了。
如果您需要，我可能会在今天晚些时候将详细说明发送至 github。
-- 编辑--
我已经发布了我的基准测试脚本和说明 here。
我说的对吗，您正在做的是有根据地猜测要修复的内容，修复它，然后尝试测量它是否有任何不同？
我用不同的方式来做，当代码变大时效果特别好。
我没有猜测（我当然可以），而是让程序通过使用 this method 告诉我时间是如何花费的。
如果该方法告诉我 大约 30% 花在做某某事上，我就可以集中精力寻找更好的方法来做到这一点。
然后我可以 运行 它并只是计时。
我不需要太精确。
如果它更好，那就太好了。
如果情况更糟，我可以撤消更改。
如果差不多的话，我可以说"Oh well, maybe it didn't save much, but let's do it all again to find another problem,"
我不用担心。
如果有加速程序的方法，这将精确定位它。
通常问题不仅仅是像 "line or routine X spends Y% of the time" 这样的简单语句，而是 "the reason it's doing that is Z in certain cases" 并且实际的修复可能在其他地方。
修复它之后，可以再次执行该过程，因为以前很小的另一个问题现在更大了（以百分比表示，因为通过修复第一个问题已经减少了总数）。
重复是关键，因为每个加速因子都会乘以所有之前的因子，就像复利一样。
当程序不再指出我可以解决的问题时，我可以确定它接近最优，或者至少没有其他人可能打败它。
在这个过程中，我从来不需要非常精确地测量时间。
之后，如果我想在 powerpoint 中吹嘘它，也许我会做多次计时以获得更小的标准误差，但即便如此，人们真正关心的是整体加速因子，而不是精度。
我需要一种更好的分析数字代码的方法。假设我在 64 位 x86 上的 Cygwin 中使用 GCC，并且我不打算购买商业工具。
情况是这样的。我在一个线程中只有一个函数 运行ning。没有代码依赖性或 I/O 除了内存访问之外，可能链接的一些数学库除外。但在大多数情况下，它都是 table 查找、索引计算和数值处理。我已经缓存对齐堆和堆栈上的所有数组。由于算法、循环展开和长宏的复杂性，汇编列表可能会变得非常冗长——数千条指令。
我一直在求助于使用 Matlab 中的 tic/toc 计时器，bash shell 中的时间实用程序，或者直接使用时间戳计数器 (rdtsc)功能。问题是这样的：时序的方差（可能高达 运行时间的 20%）大于我所做的改进 ，所以我无法知道更改后代码是好是坏。你可能会认为是时候放弃了。但我不同意。如果您坚持不懈，许多渐进式改进可以使性能提高两到三倍。
有一个问题我遇到过很多次，特别让人抓狂的是，我做了一个改变，性能似乎持续提高了 20%。第二天，收益就失去了。现在有可能我做了我认为对代码无害的更改，然后完全忘记了它。但我想知道是否有可能发生其他事情。就像 GCC 可能不会像我相信的那样产生 100% 的确定性输出。或者它可能更简单，例如 OS 将我的流程移至更繁忙的核心。
我考虑了以下几点，但我不知道这些想法是否可行或有意义。如果是，我想要关于如何实施解决方案的明确说明。 目标是最大限度地减少 运行 时间的方差，以便我可以有意义地比较不同版本的优化代码。
- 将我处理器的一个核心专用于 运行 我的日常工作。
- 直接控制缓存（加载或清除缓存）。
- 确保我的 dll 或 executable 始终加载到内存中的相同位置。我的想法是，缓存的集合关联性可能与 RAM 中的 code/data 位置相互作用，以改变每个 运行. 的性能
- 某种周期精确的仿真器工具（非商业）。
- 是否可以对上下文切换进行一定程度的控制？或者它甚至重要吗？我的想法是上下文切换的时间导致了可变性，可能是由于管道在不合时宜的时间被刷新。
过去，我通过计算汇编列表中的指令在 RISC 体系结构上取得了成功。当然，这只适用于指令数量很少的情况。一些编译器（例如 TI 的 C67x 代码编写器）将为您详细分析它如何让 ALU 保持忙碌。
我还没有发现 GCC/GAS 生成的汇编列表特别有用。通过全面优化，代码到处移动。对于散布在汇编列表中的单个代码块，可以有多个位置指令。此外，即使我能理解程序集如何映射回我的原始代码，我也不确定现代 x86 机器上的指令数和性能之间是否存在很大的相关性。
我尝试使用 gcov 进行逐行分析，但由于我构建的 GCC 版本与 MinGW 编译器不兼容，它无法正常工作。
您可以做的最后一件事是对很多很多试验 运行 进行平均，但这需要很长时间。
编辑（回复：调用堆栈采样）
我的第一个问题是，实际上，我该怎么做？在您的一张幻灯片中，您展示了使用 Visual Studio 来暂停程序。我拥有的是由 GCC 编译的 DLL，在 Cygwin 中进行了全面优化。然后由 Matlab 使用 VS2013 编译器编译的 mex DLL 调用它。
我使用 Matlab 的原因是因为我可以轻松地尝试不同的参数并可视化结果，而无需编写或编译任何低级代码。此外，我可以将我的优化 DLL 与高级 Matlab 代码进行比较，以确保我的优化没有破坏任何东西。
我使用 GCC 的原因是我对它的体验比对 Microsoft 编译器的体验要丰富得多。我熟悉许多标志和扩展。此外，微软一直不愿意维护和更新原生 C 编译器 (C99)，至少在过去是这样。最后，我看到 GCC 让商业编译器脱颖而出，我查看了汇编列表以了解它实际上是如何完成的。所以我对编译器实际上如何 思考 .
有一些直觉现在，关于猜测要修复的内容。这不是真正的问题；这更像是猜测如何 修复它。在这个例子中，就像数值算法中经常出现的情况一样，实际上没有 I/O（不包括内存）。没有函数调用。几乎没有任何抽象。这就像我坐在一块保鲜膜上。我可以看到下面的计算机体系结构，中间真的没有任何东西。如果我重新卷起所有循环，我可能可以将代码放在大约一页上，而且我几乎可以数出生成的汇编指令。然后我可以粗略比较单个内核能够执行的理论操作数，看看我离最佳状态有多近。问题是我失去了从展开中获得的自动矢量化和指令级并行化。 unrolled，汇编列表太长，无法这样分析。
关键是这段代码确实没有太多内容。然而，由于编译器和现代计算机体系结构的复杂性令人难以置信，因此即使在这个级别也有相当多的优化。但我不知道微小的变化会对编译代码的输出产生多大影响。让我举几个例子。
第一个有点含糊，但我肯定我已经见过几次了。你做了一个小的改变，得到了 10% 的改进。你做了另一个小的改变，又得到了 10% 的改进。您撤消第一个更改并获得另外 10% 的改进。嗯？编译器优化既不是线性的，也不是单调的。有可能，第二个更改需要一个额外的寄存器，它通过强制编译器更改其寄存器分配算法来破坏第一个更改。也许，第二个优化以某种方式阻碍了编译器进行优化的能力，这是通过撤消第一个优化来修复的。谁知道。除非编译器足够内省以转储其在每个抽象级别的完整分析，否则您永远不会真正知道最终的汇编是如何结束的。
这是最近发生在我身上的一个更具体的例子。我正在手工编码 AVX 内在函数以加速过滤器操作。我想我可以展开外循环来增加指令级并行性。所以我这样做了，结果是代码慢了一倍。发生的事情是没有足够的 256 位寄存器可供使用。所以编译器暂时将结果保存在堆栈上，这会降低性能。
正如我在 this post 中暗示的那样，您对此发表了评论，最好告诉编译器您想要什么，但不幸的是，您通常别无选择，被迫手动调整优化，通常通过猜测并检查。
所以我想我的问题是，在这些情况下（代码在展开之前实际上很小，每个增量性能变化很小，并且您在非常低的抽象级别上工作），会更好吗有 "precision of timing" 还是调用堆栈采样更好地告诉我 哪个代码更好 ?
我前段时间遇到过类似的问题，但那是在 Linux 上，这使得它更容易调整。基本上由 OS（称为 "OS jitter"）引入的噪音在 SPEC2000 测试中高达 5-10%（我可以想象它在 Windows 上要高得多，因为英国媒体报道软件的数量要多得多） .
我能够通过以下组合将偏差降低到 1% 以下：
- 禁用动态频率缩放（最好在 BIOS 和 Linux 内核中都这样做，因为并非所有内核版本都能可靠地做到这一点）
- 禁用内存预取和其他花哨的设置，如 "Turbo boost" 等（BIOS，再次）
- 禁用超线程
- 在内核中启用高性能进程调度程序
- 将进程绑定到核心以防止线程迁移（使用核心 0 - 由于某种原因它在我的内核上更可靠，请看图）
- 启动到单用户模式（其中没有服务 运行）——这在基于 systemd 的现代发行版中并不容易
- 禁用 ASLR
- 禁用网络
- 删除OS页面缓存
可能还有更多，但 1% 的噪音对我来说已经足够了。
如果您需要，我可能会在今天晚些时候将详细说明发送至 github。
-- 编辑--
我已经发布了我的基准测试脚本和说明 here。
我说的对吗，您正在做的是有根据地猜测要修复的内容，修复它，然后尝试测量它是否有任何不同？
我用不同的方式来做，当代码变大时效果特别好。 我没有猜测（我当然可以），而是让程序通过使用 this method 告诉我时间是如何花费的。 如果该方法告诉我 大约 30% 花在做某某事上，我就可以集中精力寻找更好的方法来做到这一点。 然后我可以 运行 它并只是计时。 我不需要太精确。 如果它更好，那就太好了。 如果情况更糟，我可以撤消更改。 如果差不多的话，我可以说"Oh well, maybe it didn't save much, but let's do it all again to find another problem,"
我不用担心。 如果有加速程序的方法，这将精确定位它。 通常问题不仅仅是像 "line or routine X spends Y% of the time" 这样的简单语句，而是 "the reason it's doing that is Z in certain cases" 并且实际的修复可能在其他地方。 修复它之后，可以再次执行该过程，因为以前很小的另一个问题现在更大了（以百分比表示，因为通过修复第一个问题已经减少了总数）。 重复是关键，因为每个加速因子都会乘以所有之前的因子，就像复利一样。
当程序不再指出我可以解决的问题时，我可以确定它接近最优，或者至少没有其他人可能打败它。
在这个过程中，我从来不需要非常精确地测量时间。 之后，如果我想在 powerpoint 中吹嘘它，也许我会做多次计时以获得更小的标准误差，但即便如此，人们真正关心的是整体加速因子，而不是精度。