原文：https://zeuxcg.org/2019/01/17/is-c-fast
和面向过程的 C 语言相比，其继承者 C++ 不仅可以进行 C 语言的过程化程序设计，还可以进行以继承和多态为特点的面向对象的程序设计。要论两者上手的难易度，对此，有网友评价道，学好 C 只要 1 年，而学好 C++ 需要的可能不止 10 年。然而这么多年过去了，C++ 却一直未能取代 C，且在本文中，作者发现自己常用的库，可以使用到的 C++ 特性越来越少，进而准备向 C 语言过渡。我最近经常使用 meshoptimizer 这个库，随着时间的推移，能用到的 C++ 库的特性越来越少。截至目前，尽管其中仍包含一些 C ++ 特性，但整体上来看，其代码已与 C 极为相似。（https://github.com/zeux/meshoptimizer）这些变化背后有很多原因，例如删除 C++ 11 的要求可以确保任何人都能在任何平台上编译库；删除 std::vector 大大改进了未优化构建的性能；删除 algorithm 可以提升编译速度等等。但是，我目前更改的这个代码库并没有完全变成 C 语言的代码。今天我们来探索这个特定算法，网格简化器，后面简称为 simplifier.cpp，看看这个算法的全部 C ++ 实现的范围，是否值得一直改进到 C 语言的版本。这个网格简化器，是通过多次调整以改善代码的性能和质量的一种基于边缘压缩的二次曲面简化算法的实现结果。该算法仍处于开发阶段，但已投入相当大的努力。细节真的不那么重要，但它有助于理解结构和大小：- 整个算法在一个独立的 .cpp 文件中实现，该文件几乎有一千行代码（撰写本文时为 1004 行），包括注释，空行，带括号的行等。
- 该算法基本上只使用堆分配的数组作为数据结构，并使用原始指针。
我们将看一下实现的几个变化过程，首先是从使用 C ++ 容器和算法的变化开始，这将有助于该算法，然后一次删除一个 C ++ 特性并测试编译速度和运行时的性能。我们使用了三种编译器，分别是 gcc7.3、clang 6 和 msvc 2017，并将它们运行在 Core i7-8700K 上的 Windows 10 / Ubuntu 16.10 系统中。我们将通过编译一个 .cpp 文件（debug 使用默认选项，release 使用 -O2）来测量编译性能，并通过将 buddha.obj （1M 左右的三角形网格）简化为其大小的 25％，用来测试运行时性能。在我们达到这一状态之后，我们再来探究将代码更改为纯 C99。请注意，我完成这些实现的方式是通过获取现在可以在存储中看到的代码，并将其更改为更惯用的 Modern C ++ [1]。但是，这些通常与之前版本的simplifier.cpp非常接近，不同之处在于现在可以直接比较变化。
我们开始的版本是来自 current meshoptimizer master 的原始 simplifier.cpp，具有以下修改：- 我们使用 std::unordered_set 取代原自定义的哈希表
- 我们使用 std::sort 取代原自定义的排序例程
我们基准测试的先前版本的秘密就在于 unordered_set 从来没有在那个版本中存在过。虽然 meshoptimizer 最初使用的是 STL 容器和算法，但它从未使用过 std::unordered_set。因为根据以前的经验，我预计性能不足以满足我想要编写的算法类型，但是有一个自定义替代方式就是使用二次探测在一个大的二维数组中实现，这类似于谷歌的 dense_hash_set 设计。它是我通常在不同的代码库中为不同的应用程序经常实现和使用的一种哈希表，所以我对它非常熟悉。在 simplifier.cpp 中的实现只有35行代码 [2]，可见这个方式很容易插入并适应手头的用例。让我们看看当我们使用它时会发生什么。测试结果突显了 std::unordered_set 不适用于起决定性能的重要工作，特别是那些插入量很大的工作负载。不幸的是，这不是一个实现缺陷，因此无法纠正，这个问题是无序容器的标准要求妨碍了更有效的实现。希望最后我们能够在标准中得到一个更好的哈希表。在开发 simplifier 的过程中，对各种网格的重复分析表明，大量时间都花在了 std::sort 上。现在，std::sort 不是最快的排序算法，但它通常与自定义实现相比极具竞争力，并且在不改变问题的情况下很难被击败。在我的例子中，排序用于边压缩的数组，排序键是一个浮点错误值，所以很自然的是使用3遍基数排序，依次使用键的11位，11位和10位（浮点值为32位每次使用一部分用于排序）。但是，我们这里有一个有趣的替代方案，我们可以使用11位的排序键仅需进行1次基数排序 [3]。我们有一个 32 位的非负浮点值会发生什么;如果我们取前 12 位并忽略最前面的1位（因为第一位是一个符号位且始终为0），我们得到11位代表8位指数和3位尾数，这本质上给了我们一个近似的数值但却存在一个严重的舍入错误。如果我们使用此值作为键进行排序，那么排序顺序就不会完全按照完整的32位键进行排序。然而，在我们的例子中，我们需要排序以便能够首先更好的基于启发式算法处理边压缩，并且启发式算法是一个粗略的近似过程，因此我们的排序带来的额外错误并不明显。这种技术在其他您不一定需要确切顺序的领域中非常有用。一次基数排序的好处是它更快（你只需要对数据进行1次排序而不是 3 次！）并且比完整的基数排序更容易实现，只需 36 行代码 [4]。有一个数字是我们尚未大幅度调整的，那就是使用 MSVC 在调试代码所需的时间。虽然很自然的会想到未经优化的构建过程会比优化后的慢，但是优化后的代码它们必须足够快才行。有时你希望在有意义的输入数据集上调试问题。有时你希望运行调试能够进行全面检查以通过你的测试，确保在发布版本中它们不会触发任何可能在隐匿的 bug。有时你试图调试程序的不同部分，但仍需要运行其余部分。程序员创造性地提出了许多变通方法，使问题不那么严重，例如你可以制作特殊的构建来实现一些优化而不是全部，你也可以对不同的项目使用混合优化设置，你可以使用 #pragma optimize 这样的指令来暂时禁用有问题的部分的代码的优化，但所有的这些看起来像是临时使用的补丁。让我们尝试用一个非常简单的动态数组替换我们仍然使用的唯一 STL 组件 std::vector。我们的代码中不需要 resize 或 push_back，所有数组都使用正确的大小进行初始化。我们的要求足够低，我们这种 std::vector 的替代方式仅仅需要 40行代码 [5]，并且主要由 operator[] 定义组成。发布的性能整体来看也略有提高，这是因为对于我们代码中的许多数组而言，std::vector 的构造函数执行的默认初始化是多余的，因为我们无论如何都要填充数组。当然，使用 std::vector，你也可以 resize 那些大数组的大小，然后计算条目（这需要对每个条目进行冗余的默认初始化），或者 reserve 和 push_back（这需要更多的代码来每个条目进行添加，而这个花销是累加起来的）。与之相反的是，使用自定义容器，可以轻松地选择跳过初始化。实际上，在我们的替换代码中这是唯一的选项，因为如果需要，可以很轻松的手动添加 memset 设置数组大小。带有边界检查的 operator[] 的自定义容器大部分都是成功的，但它并不能让我满意。在某些算法中，容器的额外成本仍然非常庞大。在一些算法中，内部函数将使用原始指针来最佳化发布的运行性能，这意味着无论如何都不会执行边界检查。此外，算法输入使用原始指针，需要仔细处理。由于在许多关键位置使用了原始指针，我会使用 Address Sanitizer 作为 CI 管道的一部分运行构建，偶尔也会在本地运行尝试，因此我对缺少越界访问感到安全。在没有自定义可视化工具的情况下，调试器将无法显示数组，更关键的是，在评估成员访问权限时会遇到问题（这在 std::vector 中也是如此，因为这取决于调试器），这使得查看表达式更加复杂，调试也不那么愉快。现状是既没有提供完美的安全性，也没有提供完美的性能，因此我决定尝试使用原始指针。当然，容器的另一个好处是对内存泄漏的额外保护，由于我不是特别热衷于记住释放每个分配的指针，所以我创建了一个 meshopt_Allocator 类[7]。这个类可以分配大块的类型数据并且会记住分配的每一个指针，在运行末尾阶段，它将会删除所有已分配的块。这导致融合的分配器+数组的类被拆分为两部分，一个是特殊的分配器类用于完成了内存管理任务，而对于数组而言一个原始指针就足够了。Address Sanitizer，以及严格的测试和手动填写的断言声明，这些将保持代码正确。虽然我对这种权衡并不是百分之百满意，但到目前为止它仍然运行良好。删除与确定每个函数中是否应该使用原始指针、迭代器或容器相关的检测的开销是很有必要的。值得注意的是，使用 Address Sanitizer 构建的开销是非常合理的，并且使用它会让我感觉更安全，因为它会捕获容器中的问题边界检查的超集。一旦我们切换到原始指针，我们的代码中 C ++ 就剩不下多少了。偶尔还有一两个模板（template），但实例化的数量足够小，这样我们可以仅为我们需要的每种类型复制代码。meshoptimizer 使用了 C ++ 中的指针类型强制转换和函数调用方式的强制转换（例如int(v)），但 C 语言没有这两种强制转化的方式，所以必须对代码进行相应的调整。同样，我们还遇到了一些其他的语法问题，但实际上在这一方面将代码更改为 C 语言的版本并不难。这样做的确需要更多的牺牲，还有就是 MSVC 的问题，要么我们必须使用 C89，要么将我们的 C99 代码编译为 C ++，除非我们愿意只支持最新的 MSVC 版本，但这样做确实是可行的。在我们停止使用每个 C ++ 标准头之后，这些真的重要吗？对 gcc / clang 编译时间有显着影响，我们通过将代码切换到 C 语言之后可以节省大约 40 ms。此时的真正区别在于标准头文件上。例如simplifier.cpp 使用的 math.h 这个头文件在 C ++模式下与 C 模式下相比实际上大了不少，一旦默认编译模式设置为 C ++ 17 时，这种差异将会增加得更多：问题是 math.h 在 gcc / clang 编译时会包含 cmath，cmath 会带来很多 C ++ 机制进而增加运行成本，而在 libstdc ++ 中的 C ++ 17 中则会添加一连串新的特殊函数，这些函数却很少有用，但无论如何都会使编译速度变慢。在这种情况下，删除对 math.h 的依赖很容易[8]：#ifdef __GNUC__
#define fabsf(x) __builtin_fabsf(x)
#define sqrtf(x) __builtin_sqrtf(x)
#else
#include <math.h>
#endif
就是上述这样的方式一直到改成 C 语言版本的编译时间。这绝对是 libstdc++ 和 libc++ 未来可以改进的领域。我认为对使用 C 的头文件的而言，承担 C++ 的包带来的成本是不合理的。除了 math.h 问题之外，假设在编译时间中 C 语言的代码有意识的用到了 C++ 的子集，这样的结果看起来 C 语言版本的代码的编译时间并不比 C++ 版本的快，所以这种情况的时候切换到 C 语言也不能保证 meshoptimizer 会更快。希望通过 simplifier.cpp 中的过去、现在和未来可能的变化进行探索是有用的。在制作 C / C ++ 库时，重要的是要注意不仅仅只有代码的正确性，而可移植性、编译的简易性、编译时间、在调试和发布时的运行时间、可调试性等等，所有的这些都很重要，这些有助于减少库和代码贡献者之间的冲突。C ++ 是一种无情的语言，但是，如果有足够的时间和精力，就可以获得良好的表现。前提是你愿意质疑一切，甚至包括有时被认为是极其常见的方法，例如 STL 或 CRT 的有效性或效率。我们在调试模式下在 gcc 中用了半秒的编译时间，在 MSVC 中用了 36s 的运行时间，并以 gcc 的 100ms 编译时间和 MSVC 上大约一秒的运行时间结束，这种方式使用起来更加愉快。当然，在 1K 行编译 100ms 的前提下，并假设是线性关系，每 10K 行我们大约需要一整秒，这样的结果仍然比其他一些语言慢得多，但这对于在单核上运行的完整构建来说并非完全不合理。为开发多年的大型代码库提供服务是一个更难的问题，这些将留给读者作为练习了;）[1]：去年，在工作中讨论了 C ++，有人说“这是一个很好的 C++ 子集，一个拥有类的 C 语言”，我回答说“有一个更好的子集，拥有结构的 C 语言”。这就是大多数 meshoptimizer 源代码的样子，除了几个模板。[2]：哈希表接口只有两个函数，hashBuckets和hashLookup：simplifier.cpp:124 。[3]：使用 11 位是一个合理的选择，因为它需要一个 2048 条目的直方图，它需要 8 KB 并且可以轻松地适应 16 KB 的 L1 缓存。给定 32 KB L1 高速缓存，你可以将直方图扩展到 12 位，但超出此范围通常效率较低。你可以在 Pierre Terdiman 的 Radix Sort Revisited 文章中阅读有关基数排序的更多信息（http://www.codercorner.com/RadixSortRevisited.htm）。 [4]：sortEdgeCollapses 函数的完整实现可在此处获得：simplifier.cpp:712（https://github.com/zeux/meshoptimizer/blob/c93ba0987baa84bd73b61edf1c0ba7ba2e48df4b/src/simplifier.cpp#L712）。[5]：这个类不再是 meshoptimizer 的一部分了，但你可以在这里查看较旧的稍长版本：meshoptimizer.h:605（https://github.com/zeux/meshoptimizer/blob/5b0d10bb3c0c174965b716dda3270bce4f3278b6/src/meshoptimizer.h#L605）。[6]：我在调查了调试中的奇怪性能差异后发现了这一点；我不愿重复所有先前测试用例的调试基准，所以我假设开销是 std::vector 导致的额外的大约 30％。希望这不会改变一般情况。我不确定为什么默认情况下这些断言没有首先启用，这似乎不是用户友好的，但这应该反映了使用这些库的默认体验。[7]：所有 meshoptimizer 中的算法都使用了此类，可在此处获得：meshoptimizer.h:662（https://github.com/zeux/meshoptimizer/blob/c93ba0987baa84bd73b61edf1c0ba7ba2e48df4b/src/meshoptimizer.h#L662）。[8]：这感觉就像补丁，而且我必须独立地应用于多个源文件，所以现在我选择不这样做。但是，如果在修复此问题之前 C ++ 17 模式成为默认模式，我将不得不重新考虑，因为 2x 编译时间损失有点太大了。
相关素材