本文并不是在讨论哪种编程语言更好,而是讨论用于开发最快的服务器端系统软件(例如数据库引擎和 HTTPS 服务器)的最强大的工具集。这类软件有着以下几个特定的属性:

  • 相对较大的代码库,超过 100,000 行 C 或 C++ 代码。尽管可以用汇编语言编写特定的最“热门”的函数,但用汇编语言编写整个程序是不切实际的。
  • 数据库和 Web 服务器是关键性支撑软件。多年以来我们已经习惯了使用有 MySQL 和 Nginx 进程的 Linux 系统。有一些简单的高可用最佳实践可以缓解由于可能的奔溃而导致的停机时间,但这是另一篇文章的主题。同时,值得一提的是,如果你真的在乎可用性,那么你应该在假设系统的任何组件随时可能奔溃的前提下构建基础架构,就像 Facebook 是这样做的一样,该公司在最新的 Linux 推出之后,就立刻部署使用了。

多年来,我们一直在开发使用 C,C++ 和汇编语言最快的软件。 既然 Rust 一直“专注于性能”,我们当然对此非常感兴趣。虽然有些怀疑,想想当年 Java 编程语言的兴起:有许多报道表明 JIT 编译产生的代码比 C++ 更快。现在很难出现这种 C++ 比 Java 慢的情况,请参见基准测试的例子。还值得一题的是,Java 中的内存垃圾回收(GC)会导致较高的尾部等待时间,并且很难甚至根本无法解决该问题。由于 GC,不能将 Go 语言用于高性能编程。

C 还是 C++ ? 或者都是?

C 语言在系统编程中占着主导地位。操作系统内核是最复杂的系统软件之一,不仅因为它直接与硬件打交道,而且还由于严格的性能要求。Linux 和 FreeBSD 内核以及其他 UNIX 和 Windows 内核都是用 C 编写的。让我们从这个高性能系统软件的出色示例开始进行讨论。

C++ 开发操作系统内核

FreeBSD 已经支持 C++ 模块 有一段时间了。虽然 Linux 内核从不支持 C++,但是有一个用 C++ 编写并用作 Linux 内核模块的 Click 模块化路由器。如果您对操作系统内核开发的 C++ 适用性感兴趣,那么可以在 C++Bare bones 文章中找到相当不错的讨论。但是,有一些本质的原因反对使用 C++ 进行操作系统内核开发:

  • 不需要 libstdc++RTTI ,以及内核空间异常处理。事实上,dynamic_cast 并不经常使用,并且有很多 C++ 项目并没有 RTTI 编译。如果需要异常处理,则必须将它们一直到内核中。libstdc++ 使用基本的 C 分配,因此必须对内核进行大量修改。
  • 不能使用 STL 和 Boost 库。实际上,所有内核都已经拥有自己的库。C++ 引入了文件系统,线程和网络库,这在操作系统内核中是毫无意义的。另一方面,现代的操作系统提供了高级同步原语,而这些原语在标准 C++ 中仍然不可用(例如,在 C++ 中仍然没有读写自旋锁)。
  • Linux 内核提供的内存分配的数量(SLAB,页面 vmalloc(), kmalloc() 等),因此你必须使用 placement new 和/或 只使用 C 函数的内存分配和释放。对齐内存对于提高性能至关重要,但是你需要编写特殊的包装程序才能对齐使用 new.
  • 当原始内存指针经常被强制转换为某些数据结构时,强类型安全性对于系统编程而言并不那么舒适。尽管还是有争议的:虽然有些人不习惯用冗长的 reinterpret_cast<Foo *>(ptr) 替代不是简短的 (Foo *)ptr. 但其他人却拥有更多的类型和更多的类型安全性。
  • 命名空间和函数重载,必须要 C++ 的名称处理。而这使函数很难从汇编调用,因此需要使用 extern "C".
  • 你必须为静态对象的构造函数和析构函数 .ctor 以及 .dtor 相应的对象创建特殊的代码段。
  • C++ 异常不能跨越上下文边界,即:你不能在一个线程中抛出异常而在另一个线程中捕获它。操作系统内核需要处理更复杂的上下文模型:内核线程,进入内核的用户空间线程,延迟和硬件中断。上下文可以以自愿或合作的方式相互抢占,因此当前上下文的异常处理可以被另一个上下文抢占。还有内存管理和上下文切换代码,它们可能与异常处理代码冲突。就像 RTTI 一样,可以在内核中实现该机制,但是不能使用当前的标准库。
  • 虽然 Clang 和 G++ 支持 __restrict__ 扩展,但是官方的 C++ 标准 不支持.
  • 不鼓励 在 Linux 内核中使用可变长数组(VLA),在某些情况下它们仍然很方便,但是 在 C++ 中完全不可用

因此,在内核空间中使用 C++,基本上只有模版,类继承和一些语法糖(如 lambda 函数)。由于系统代码很少需要复杂的抽象和继承,那么在内核空间中使用 C++ 仍然有意义吗?

C++ 异常

这是最值得争辩 的 C++ 功能之一,值得写上一章。例如:MySQL 的项目,以下为 Google 编码风格不使用异常。Google 编码风格提供了优秀的使用异常的优缺点列表。在这里,我们仅关注性能方面。

当我们不得不在可能的地方处理错误代码时,异常可以提高性能,例如(让函数内联并且很小)

if (func_1())
    return -EINVAL;
if (func_2())
    return -EINVAL;
....
if (func_100())
    return -EINVAL;

该代码的问题是存在额外的条件跳转。现代 CPU 可以很好地进行分支预测,但是仍然会影响性能。在 C++ 中,我们可以编写

try {
    func_1();
    func_2();
    ...
    func_100();
} catch (...) {
    return -EINVAL;
}   

,因此路径中没有多余的条件。但是,这不是自由的:你的 C++ 代码中的大多数函数都必须带有额外的结尾,这些异常表带有这些函数可以捕获的异常表和适当的清除表。函数结尾没有在正常的工作流中执行,但是它们增加了代码的大小,从而导致 CPU 指令缓存中的额外污染。你可以在 Nico Brailovsky 的博客中找到有关 C++ 异常处理内部的详细信息。

C++ 仍然不错?

是的。首先,实际上并不是整个代码都必须尽可能快,并且在大多数情况下,我们不需要自定义内存分配,也不在乎异常开销。大多数项目(尤其是新项目)都是在用户空间中开发的,并且受益于相对丰富的 C++ 标准和 Boost 库(虽然不如 Java 丰富)。

其次,C++ 最大的特点就是:它是 C。如果你不想使用异常或 RTTI,则只需要关闭功能即可。大多数 C 程序都可以使用 C++ 编译器进行编译,只需进行很小的更改或完全不进行任何更改。举个例子,我们只需要这个微不足道的更改

$ diff -up nbody.c nbody-new.cc
    @@ -112,9 +112,9 @@ static void advance(body bodies[]){
         // ROUNDED_INTERACTIONS_COUNT elements to simplify one of the following
         // loops and to also keep the second and third arrays in position_Deltas
         // aligned properly.
    -    static alignas(__m128d) double
    -      position_Deltas[3][ROUNDED_INTERACTIONS_COUNT],
    -      magnitudes[ROUNDED_INTERACTIONS_COUNT];
    +    static double
    +      position_Deltas[3][ROUNDED_INTERACTIONS_COUNT] __attribute__((aligned(16))),
    +      magnitudes[ROUNDED_INTERACTIONS_COUNT] __attribute__((aligned(16)));

         // Calculate the position_Deltas between the bodies for each interaction.
         for(intnative_t i=0, k=0; i < BODIES_COUNT-1; ++i)    

用 G++ 编译器编译 C 程序 。现代的 C++ 编译器提供了 C 兼容性扩展,例如 _restrict 关键字。我们总是可以用 C 风格编写 C++ 程序中性能最关键的代码。如果你不喜欢 带有额外开销的 STL 容器,则可以使用 Boost.intrusive ,或者甚至从 Linux 内核或其他高速 C 项目移植类似的容器。在大多数情况下,这不会感到痛苦。例如,请参阅如何在 C++ benchmark 中使用 PostgreSQL 的哈希表,Tempesta DB 的 HTrie 以及 Linux 内核读/写自旋锁(全部都是用 C 编写的。)

关于使用 C++ 编写高性能程序的最后一件事必须提到的是模板元编程。对于现代 C++ 标准而言,令人兴奋的是,使用模板可以编写非常复杂的逻辑,这些逻辑在编译时就可以完全计算出来,而在运行时则不增加任何负担。

GOTO - C 的力量所在

专业的工具必须允许你以最有效的方式使用它。 高级和高性能的编程语言的目标是生成最高效的机器代码。每种硬件体系结构都支持 jumps 指令,这意味着你可以在任何条件下跳转到任何地址。C 和 C++ 编程语言中最接近跳转的抽象就是goto 操作符。它不像汇编那样灵活 jmp ,但是 C 编译器提供了扩展,使操作符几乎可以完全等同于汇编的 jmp. 不幸的是,Rust 并不支持 goto,这使它在整个性能关键性任务中都显得笨拙。

我们谈论解析器。这里并不是说通过一堆 switchif 语言完美完成的配置文件解析器,而是关于大型且非常快速的解析器(如 HTTP 解析器)。你可能会认为这是 “太狭窄” 或 “太具体” 的任务,但是回想一下解析器生成器,例如 RagelGNU Bison. 如果开发这样的解析器生成器,那么你将永远不知道将出现多大的解析器。(顺便说一下,Ragel 广泛使用 goto 生成非常快的解析器。)还要注意每个 RDMS 中的 SQL 解析器。实际上,我们可以将任务的类别概括为大型和快速的有限状态机,例如:正则表达式。

Tempesta FW 中的 HTTP 解析器 比其他 Web 服务器中的 HTTP 解析器要大得多,因为,除了基本的 HTTP 解析,也做了很多的安全检查,严格验证对 RFC 的输入。此外,我们的解析器还可以处理零拷贝数据,因此也非常关心数据块。在 SCALE 17x 会议上的演讲中描述了解析器的技术细节,您可以观看演讲视频或者幻灯片

通常,HTTP 解析器被实现为输入字符和嵌套 switch 语句的循环,以获取允许的字符和可用状态。例如 ngx_http_parse_request_line() ,请参见 Nginx 解析器源代码。为了简洁其间,让我们考虑一个简化的代码版本:

while (++str_ptr) {
    switch (current_state) {
    case 0:
        ...
    case 1:
        ...
    ...
    case 100:
        switch (*str_ptr) {
        case 'a':
            ...
            current_state = 200;
            break;
        case 'b':
            ...
            current_state = 101;
            break;
        }
        break;
    case 101:
        ...
    ...
    }
}

假设解析器已经完成了对处于状态 100 的先前数据块的解析,而当前数据库从字符 b 开始。不管 switch语句优化(可以由编译器使用查找表或二进制搜索进行优化),代码都存在以下三个问题:

  1. 查找状态 100 仍然比直接跳转更耗时。
  2. 当状态码放置在状态 100 后的状态 101 时,我们必须重新进入 whileswitch 语句,即再次查找下一个状态,而不是仅一步移动一个字符并直接跳到下一个状态。
  3. 即使我们总是在状态 100 后的状态 101,编译器也可以通过以下方式重新组织代码:将状态 101 放在 switch 语句的开头,而将状态 100 放在语句的末尾。

Tempesta FW 使用 goto 语句和标签的 GCC 编译器扩展(标签变量标签属性)通过以下代码解决了所有问题:

// Use labels as values to remember the current state when we
// exit the state machine at the end of current data chunk.
parser->state = &&state_100;
goto *parser->state;

while (true) {
state_0:
    ...
state_1:
    ...
// The state is placed by a compiler closer to the beginning
// of the code.
state_100: __attribute__((hot))
    // We still use small switches for small character sets. 
    switch (*str_ptr) {
    case 'a':
        ...
        ++str_ptr;
        goto state_200;
    case 'b':
        ...
        ++str_ptr;
        // Just fall through to the state 101.
    }
// This state is placed by the compiler after state_100.
state_101: __attribute__((cold))
    ...
}   

由于 Rust 不支持 goto 语句,因此我们需要使用汇编语言通过直接跳转和最佳代码布局来实现状态机。

当汇编比 C 容易时

现在我们先看一个示例,该示例中的汇编语言不仅可以生成更快的代码,还可以以更有效率的方式编写程序。此示例是关于多精度整数运算。

公钥密码学和椭圆曲线密码算法尤其依赖大整数运算。Tom St Denis所著的《BigNum Math:实现加密多精度算术》一书提供了有关该主题以及许多算法的 C 实现的详细细节,但现在让我们考虑一下 64 位上 128 位长的两个大整数的基本加法机。大整数包括几个块,两个64位 long。为了求和整数,我们必须关心块之间的进位,因此生成的C代码看起来像(参见书中的4.2.1):

// a := a + b
// x[0] is the less significant limb,
// x[1] is the most significant limb.
void s_mp_add(unsigned long *a, unsigned long *b)
{
    unsigned long carry;

    a[0] += b[0];
    carry = (a[0] < b[0]);

    a[1] += b[1] + carry;
}    

代码虽小又简单,但是你可能不得不考虑使用进行操作的正确性的 carry。幸运的事,x86-64 是 CISC 体系结构,它为我们提供了许多计算功能,其中就有带进位的计算,因此上面的代码只用两条指令就可以完成,而无需进行比较:

// Pointer to a is in %RDI, pointer to b is in %RSI
movq    (%rdi), %r8
movq    8(%rdi), %r9

addq    (%rsi), %r8     // add with carry
addc    8(%rsi), %r9    // use the carry in the next addition

movq    (%r8), (%rdi)
movq    (%r9), 8(%rdi)

如果您查看任何经过优化的加密库,例如 OpenSSLTempesta TLS,那么您会发现很多汇编代码(OpenSSL实际上使用Perl脚本生成了汇编源代码)。

Rust 一览

乍一看,Rust具备开发非常高效的代码的精良装备:SIMD内在函数内存对齐内存屏障内联汇编。Rust 与 C 或 C++ 有很多比较,例如 Rust与CC++ 的速度比 Rust 更快,更安全:Yandex 基准测试。但是,如果你考虑使用 Rust 开发基准测试领先产品,那么您可能会面临一些障碍以及缺少 goto 操作符的麻烦:

  • 从技术上讲,Rust支持自定义内存分配器,但是存在严重的局限性。值得一提的是,任何高性能软件都使用许多临时内存分配器
  • 就像 C++ 一样,Rust 不提供 VLA 。但是,如果 C++ 仍然可以使用 alloca(3),Rust 根本不会提供堆栈分配。太可惜了,因为栈分配是消耗最小的,而由于先前的考虑,自定义内存分配器不是一个选择。
  • 这似乎可能/不可能支持是比现代的C或C ++编译器强大得多。
  • 在 Rust 中可以从原始内存读写数据结构,但是比 C 甚至 C++ 需要更多的代码。不过没什么大不了的。
  • Rust的泛型功能远不及 C++ 模板和 C 宏所提供的功能强大。虽然,这也不是那么关键。

关于Rust系统编程的最关键的失望是它处理原始内存的能力有限,这是内存安全的另一方面。

C++ 和 Rust 中的可靠性和安全性

如果不解决 Rust 和 C++ 编程语言提供的可靠性和安全性,本文将是不完整的。幸运的是,Microsoft 的 Sunny Chatterjee 最近在 CppCon 2020上发表了这个话题。Rust的主要好处是内存和并发安全性,但是现代的C ++也解决了这些主题。在本演示中,Sunny 解决了 Rust 与 C++ 之间的以下6个差距:转换,switch 语句,更智能的循环,更智能的复制,生存期和可变性。让我们回顾一下差距。

  • 带有编译器选项的现代 C 和 C++ 编译器可以很好地处理类型转换 -Wall
  • switch语句也使用进行处理 -Wall。此外,GCC 还引入了 -Wimplicit-fallthrough编译器选项,该选项使“通过”明确。
  • 自 C++ 11起,更聪明的循环由基于C ++范围的for循环解决
  • const auto &参考和细粒度的复制和移动语义会注意智能复制
  • RAII提供了强大的生命周期,但不幸的是并非涵盖所有情况
  • const带有或不带有mutable成员,const引用和变量的C ++类提供了细粒度的可变性,但是bust也不能涵盖所有情况

演示最后以“ C++ 核心准则规定许多重大项目”进行了总结,且现代 C 和 C++ 编译器趋向于实现忽略检查。还值得一提的是,C / C++世界有效地使用了地址清理器(例如,ASAN内置于LLVM和GCC编译器的现代版本中)来捕获越界内存访问。毕竟,unsafe就像在C ++中使用原始指针一样,您仍然可以使用Rust中的代码来产生错误。

计算机语言的基准测试

由于我们在谈论性能,因此我们必须看一下“计算机语言基准测试”。要比较不同语言的性能,您需要以相同的方式在所有语言中实现相同的任务。这不是人们通常要做的事情,因此很难找到不同语言的真实代码示例,这些示例使您可以将桔子与桔子进行比较,而不是将桔子与苹果进行比较。虽然Benchmarks游戏是一款游戏,它会比较一些小的特定任务的实现,但这是我们拥有的最好的游戏之一。所述VS锈比较C ++ 11是C ++和Rust中相等实现的又一比较。Benchmarks游戏中没有汇编语言,但是相应地有Rust(用于G ++编译器的C ++)和两个用于Clang和GCC编译器的C。在撰写本文时,实现的性能为(以秒为单位,越少越好):

Problem G++ GCC Clang Rust
fannkuch-redux 8.07 7.53 9.45 6.88
spectral-norm 0.72 0.72 0.72 0.71
n-body 4.09 4.30 3.31 3.31
binary-trees 1.12 1.78 1.88 1.20
fasta 1.04 0.82 0.88 0.91
pidigits 0.71 0.73 0.81 0.74
mandelbrot 0.84 1.27 2.09 0.92
regex-redux 1.08 0.80 0.81 1.28
reverse-complement 0.63 0.87 0.98 0.75
k-nucleotide 1.93 3.71 6.19 3.29

只有一个测试,第一个测试,其中 Rust 或多或少明显优于 C 和 C++ 实现。

性能分析

您可能很好奇,为什么 Rust中fannkuch-redux 实现C 实现更快?我们也是。这两个程序的副本已附在下文:

C 程序

// The Computer Language Benchmarks Game
// https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
//
// Contributed by Jeremy Zerfas
// Based on the Ada program by Jonathan Parker and Georg Bauhaus which in turn
// was based on code by Dave Fladebo, Eckehard Berns, Heiner Marxen, Hongwei Xi,
// and The Anh Tran and also the Java program by Oleg Mazurov.

// This value controls how many blocks the workload is broken up into (as long
// as the value is less than or equal to the factorial of the argument to this
// program) in order to allow the blocks to be processed in parallel if
// possible. PREFERRED_NUMBER_OF_BLOCKS_TO_USE should be some number which
// divides evenly into all factorials larger than it. It should also be around
// 2-8 times the amount of threads you want to use in order to create enough
// blocks to more evenly distribute the workload amongst the threads.
#define PREFERRED_NUMBER_OF_BLOCKS_TO_USE 12

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

// intptr_t should be the native integer type on most sane systems.
typedef intptr_t intnative_t;


int main(int argc, char ** argv){
   const intnative_t n=atoi(argv[1]);

   // Create and initialize factorial_Lookup_Table.
   intnative_t factorial_Lookup_Table[n+1];
   factorial_Lookup_Table[0]=1;
   for(intnative_t i=0; ++i<=n;)
      factorial_Lookup_Table[i]=i*factorial_Lookup_Table[i-1];

   // Determine the block_Size to use. If n! is less than
   // PREFERRED_NUMBER_OF_BLOCKS_TO_USE then just use a single block to prevent
   // block_Size from being set to 0. This also causes smaller values of n to
   // be computed serially which is faster and uses less resources for small
   // values of n.
   const intnative_t block_Size=factorial_Lookup_Table[n]/
     (factorial_Lookup_Table[n]<PREFERRED_NUMBER_OF_BLOCKS_TO_USE ?
     1 : PREFERRED_NUMBER_OF_BLOCKS_TO_USE);

   intnative_t maximum_Flip_Count=0, checksum=0;

   // Iterate over each block.
   #pragma omp parallel for \
     reduction(max:maximum_Flip_Count) reduction(+:checksum)
   for(intnative_t initial_Permutation_Index_For_Block=0;
     initial_Permutation_Index_For_Block<factorial_Lookup_Table[n];
     initial_Permutation_Index_For_Block+=block_Size){

      intnative_t count[n];
      int8_t temp_Permutation[n], current_Permutation[n];


      // Initialize count and current_Permutation.
      count[0]=0;
      for(intnative_t i=0; i<n; ++i)
         current_Permutation[i]=i;
      for(intnative_t i=n-1,
        permutation_Index=initial_Permutation_Index_For_Block; i>0; --i){
         const intnative_t d=permutation_Index/factorial_Lookup_Table[i];
         permutation_Index=permutation_Index%factorial_Lookup_Table[i];
         count[i]=d;

         for(intnative_t j=0; j<n; ++j)
            temp_Permutation[j]=current_Permutation[j];
         for(intnative_t j=0; j<=i; ++j)
            current_Permutation[j]= j+d<=i ?
              temp_Permutation[j+d] : temp_Permutation[j+d-i-1];
      }


      // Iterate over each permutation in the block.
      const intnative_t last_Permutation_Index_In_Block=
        initial_Permutation_Index_For_Block+block_Size-1;
      for(intnative_t permutation_Index=initial_Permutation_Index_For_Block; ;
        ++permutation_Index){

         // If the first value in the current_Permutation is not 1 (0) then
         // we will need to do at least one flip for the current_Permutation.
         if(current_Permutation[0]>0){

            // Make a copy of current_Permutation[] to work on. Note that we
            // don't need to copy the first value since that will be stored
            // in a separate variable since it gets used a lot.
            for(intnative_t i=0; ++i<n;)
               temp_Permutation[i]=current_Permutation[i];

            intnative_t flip_Count=1;

            // Flip temp_Permutation until the element at the first_Value
            // index is 1 (0).
            for(intnative_t first_Value=current_Permutation[0];
              temp_Permutation[first_Value]>0; ++flip_Count){

               // Record the new_First_Value and restore the old
               // first_Value at its new flipped position.
               const int8_t new_First_Value=temp_Permutation[first_Value];
               temp_Permutation[first_Value]=first_Value;

               // If first_Value is greater than 3 (2) then we are flipping
               // a series of four or more values so we will also need to
               // flip additional elements in the middle of the
               // temp_Permutation.
               if(first_Value>2){
                  intnative_t low_Index=1, high_Index=first_Value-1;
                  // Note that this loop is written so that it will run at
                  // most 16 times so that compilers will be more willing
                  // to unroll it. Consequently this won't work right when
                  // n is greater than 35. This would probably be the
                  // least of your concerns since 21! won't fit into 64
                  // bit integers and even if it did you probably wouldn't
                  // want to run this program with a value that large
                  // since it would take thousands of years to do on a
                  // modern desktop computer. ;-)
                  do{
                     const int8_t temp=temp_Permutation[high_Index];
                     temp_Permutation[high_Index]=
                       temp_Permutation[low_Index];
                     temp_Permutation[low_Index]=temp;
                  }while(low_Index+++3<=high_Index-- && low_Index<16);
               }

               // Update first_Value to new_First_Value that we recorded
               // earlier.
               first_Value=new_First_Value;
            }


            // Update the checksum.
            if(permutation_Index%2==0)
               checksum+=flip_Count;
            else
               checksum-=flip_Count;

            // Update maximum_Flip_Count if necessary.
            if(flip_Count>maximum_Flip_Count)
               maximum_Flip_Count=flip_Count;
         }


         // Break out of the loop when we get to the
         // last_Permutation_Index_In_Block.
         if(permutation_Index>=last_Permutation_Index_In_Block)
            break;

         // Generate the next permutation.
         int8_t first_Value=current_Permutation[1];
         current_Permutation[1]=current_Permutation[0];
         current_Permutation[0]=first_Value;
         for(intnative_t i=1; ++count[i]>i;){
            count[i++]=0;
            const int8_t new_First_Value=current_Permutation[0]=
              current_Permutation[1];

            for(intnative_t j=0; ++j<i;)
               current_Permutation[j]=current_Permutation[j+1];

            current_Permutation[i]=first_Value;
            first_Value=new_First_Value;
         }
      }
   }


   // Output the results to stdout.
   printf("%jd\nPfannkuchen(%jd) = %jd\n", (intmax_t)checksum, (intmax_t)n,
     (intmax_t)maximum_Flip_Count);

   return 0;
}

Rust 程序

// The Computer Language Benchmarks Game
// https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
//
// Contributed by Cliff L. Biffle, translated from Jeremy Zerfas's C program.
//
// The C program was based on the Ada program by Jonathan Parker and Georg
// Bauhaus which in turn was based on code by Dave Fladebo, Eckehard Berns,
// Heiner Marxen, Hongwei Xi, and The Anh Tran and also the Java program by Oleg
// Mazurov.

extern crate rayon;

use rayon::prelude::*;
use std::mem::replace;

// This value controls how many blocks the workload is broken up into (as long
// as the value is less than or equal to the factorial of the argument to this
// program) in order to allow the blocks to be processed in parallel if
// possible. PREFERRED_NUMBER_OF_BLOCKS_TO_USE should be some number which
// divides evenly into all factorials larger than it. It should also be around
// 2-8 times the amount of threads you want to use in order to create enough
// blocks to more evenly distribute the workload amongst the threads.
const PREFERRED_NUMBER_OF_BLOCKS_TO_USE: usize = 12;

// One greater than the maximum `n` value. Used to size stack arrays.
const MAX_N: usize = 16;

fn main() {
    let n = std::env::args().nth(1).unwrap().parse().unwrap();

    // This assert eliminates several bounds checks.
    assert!(n < MAX_N);

    // Create and initialize factorial_lookup_table.
    let factorial_lookup_table = {
        let mut table: [usize; MAX_N] = [0; MAX_N];
        table[0] = 1;
        for i in 1..MAX_N {
            table[i] = i * table[i - 1];
        }
        table
    };

    // Determine the block_size to use. If n! is less than
    // PREFERRED_NUMBER_OF_BLOCKS_TO_USE then just use a single block to prevent
    // block_size from being set to 0. This also causes smaller values of n to
    // be computed serially which is faster and uses less resources for small
    // values of n.
    let block_size =
        1.max(factorial_lookup_table[n] / PREFERRED_NUMBER_OF_BLOCKS_TO_USE);
    let block_count = factorial_lookup_table[n] / block_size;

    // Iterate over each block.
    let (checksum, max_flip_count) = (0..block_count)
        .into_par_iter()
        .map(|bn| {
            let initial_permutation_index = bn * block_size;

            let mut count: [usize; MAX_N] = [0; MAX_N];
            let mut current_permutation: [u8; MAX_N] =
                [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];

            // Initialize count and current_permutation.
            {
                let mut temp_permutation: [u8; MAX_N] = [0; MAX_N];
                let mut permutation_index = initial_permutation_index;
                for i in (1..n).rev() {
                    let f = factorial_lookup_table[i];
                    let d = permutation_index / f;

                    count[i] = d;

                    // Rotate the permutation left by d places. This is faster
                    // than using slice::rotate_left.
                    temp_permutation[0..=i - d]
                        .copy_from_slice(&current_permutation[d..=i]);
                    temp_permutation[i - d + 1..=i]
                        .copy_from_slice(&current_permutation[..d]);
                    current_permutation = temp_permutation;

                    permutation_index = permutation_index % f;
                }
            }

            let mut max_flip_count = 0;
            let mut checksum = 0;

            // Iterate over each permutation in the block.
            let last_permutation_index = initial_permutation_index + block_size;
            for permutation_index in
                initial_permutation_index..last_permutation_index
            {
                // If the first value in the current_permutation is not 1 (0)
                // then we will need to do at least one flip for the
                // current_permutation.
                if current_permutation[0] > 0 {
                    // Make a copy of current_permutation[] to work on.
                    let mut temp_permutation = current_permutation;

                    let mut flip_count: usize = 1;

                    // Flip temp_permutation until the element at the
                    // first_value index is 1 (0).
                    let mut first_value = current_permutation[0] as usize & 0xF;
                    while temp_permutation[first_value] > 0 {
                        // Record the new_first_value and restore the old
                        // first_value at its new flipped position.
                        let new_first_value = replace(
                            &mut temp_permutation[first_value],
                            first_value as u8,
                        );

                        // If first_value is greater than 3 (2) then we are
                        // flipping a series of four or more values so we will
                        // also need to flip additional elements in the middle
                        // of the temp_permutation.
                        if first_value > 2 {
                            for (low_index, high_index) in
                                (1..first_value).zip((1..first_value).rev())
                            {
                                temp_permutation.swap(high_index, low_index);

                                if low_index + 3 > high_index {
                                    break;
                                }
                            }
                        }

                        // Update first_value to new_first_value that we
                        // recorded earlier.
                        first_value = new_first_value as usize & 0xF;
                        flip_count += 1;
                    }

                    // Update the checksum.
                    if permutation_index % 2 == 0 {
                        checksum += flip_count;
                    } else {
                        checksum -= flip_count;
                    }

                    // Update max_flip_count if necessary.
                    max_flip_count = max_flip_count.max(flip_count);
                }

                // Generate the next permutation.
                current_permutation.swap(0, 1);
                let mut first_value = current_permutation[0];
                for i in 1..MAX_N - 2 {
                    count[i] += 1;
                    if count[i] <= i {
                        break;
                    }
                    count[i] = 0;

                    let new_first_value = current_permutation[1];

                    for j in 0..i + 1 {
                        current_permutation[j] = current_permutation[j + 1];
                    }

                    current_permutation[i + 1] = first_value;
                    first_value = new_first_value;
                }
            }
            (checksum, max_flip_count)
        })
        .reduce(
            || (0, 0),
            |(cs1, mf1), (cs2, mf2)| (cs1 + cs2, mf1.max(mf2)),
        );

    // Output the results to stdout.
    println!("{}", checksum);
    println!("Pfannkuchen({}) = {}", n, max_flip_count);
}

让我们启动C程序,并使用Linux perf工具收集该程序的性能概况。我们可以通过程序中最热门的代码perf report或看到perf annotate什么:

    0.46 |       movzbl    -0x9(%r15,%rax,1),%ecx
    0.96 |       movzbl    0x9(%r15),%r8d
         |       mov       %r8b,-0x9(%r15,%rax,1)
    2.31 |       mov       %cl,0x9(%r15)
         |       lea       -0xa(%rax),%rcx
   12.76 |       cmp       $0xb,%rdi

性能杀手获得了12.76%的时间是展开循环的一部分

do{
   const int8_t temp=temp_Permutation[high_Index];
   temp_Permutation[high_Index]=
     temp_Permutation[low_Index];
   temp_Permutation[low_Index]=temp;
}while(low_Index+++3<=high_Index-- && low_Index<16);

cmp指令的部分while循环条件。实际上,他的循环只是反转数组中的字节。尽管C实现使用带有数组索引的朴素操作和繁重操作,而Rust实现使用高效的double迭代器

if first_value > 2 {
    for (low_index, high_index) in
        (1..first_value).zip((1..first_value).rev())
    {
        temp_permutation.swap(high_index, low_index);

        if low_index + 3 > high_index {
            break;
        }
    }
}

使用SIMD进行快速阵列反转!介绍了几种提高C程序性能的方法(本文使用C ++)。第一种是只使用一个索引i和迭代仅直到与所述阵列的经置换的部分的中间temp_Permutation[i]temp_Permutation[high_Index - i]。那将与Rust双迭代器非常接近。顺便说一下,提高两个程序性能的更高级的方法是使用PSHUFBSSSE3指令或_mm_shuffle_epi8()内部指令,而不是整个循环。由于混洗掩码的数量很少,因此可以在编译时定义所有混洗掩码,然后将它们立即加载到指令的控制掩码寄存器中。

但是,这不是实现之间的唯一区别。Rust程序利用最大输入数const MAX_N: usize = 16。由于编译器现在可以对循环和静态数组进行更好的优化,因此这种小的改进可能对性能的影响最大。该程序显式使用静态数组初始化

let mut current_permutation: [u8; MAX_N] =
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];

, 而 C 实现在运行时无需输入数据即可进行此操作

for(intnative_t i=0; i<n; ++i)
   current_Permutation[i]=i;

Rust 程序使用内置内存复制功能复制阵列

let mut temp_permutation = current_permutation;

,而 C 程序再次循环执行此操作

for(intnative_t i=0; ++i<n;)
   temp_Permutation[i]=current_Permutation[i];

这些并不是C程序中的所有低效率,在Rust实施中已将其消除(这两个程序都基于相同的初始Ada程序)。在大多数地方,该程序的优化版本不仅会更快,而且会更短。

因此,在这种情况下,当Rust实现的速度快于C时,性能的差异不是关于更好的编译器,而是关于程序的更有效的结构,这使编译器可以更好地优化代码。

Rust 作为系统编程语言?

真正的高级系统编程语言必须与C兼容。仅考虑我们现实生活项目中的2个示例。

第一个是Web应用程序防火墙(WAF)。这种软件通常基于Nginx或HAproxy HTTPS服务器(它们是用C编写)构建的。为Nginx编写 C++ 模块很容易,但是我们需要额外的粘合代码才能在Rust中开发该模块并维护所有补丁。 Nginx的C代码。相同的开发人员可以轻松地在代码的C和C ++部分之间切换。

在第二种情况下,我们的客户希望使用MySQL用户定义函数(UDF)与操作系统进行交互来执行一些外部逻辑。我们可以用任何编程语言开发逻辑,但是有一个限制:我们必须在每个CPU内核上每秒执行5000个程序!即使使用posix_spawnp()Linux中执行程序的最快方法,也无法实现这一点。我们最终为MySQL开发了一个自定义UDF,这是一个加载到MySQL服务器进程中的共享对象。使用C ++非常简单。

将Rust用作Nginx模块的一个相反的示例是CloudFlare的Quiche,这是一种Nginx扩展,支持QUIC和HTTP / 3协议。尽管绝对可以将Rust用于此类任务,但是除了用于C / C ++绑定FFI代码之外,这些家伙仍然必须编写一些C代码来修补Nginx。这意味着:

  • 您必须为 C / C++ 绑定编写一些额外的样板代码
  • 而且您仍然必须处理 C / C++ 第二种语言,这使项目更加复杂。

(顺便说一下,同样适用于D编程语言,它也不能直接包含C标头。)Quiche项目中的FFI和Nginx补丁程序仅约5,000行代码,即整个代码的10%项目,这是40,000行Rust代码。如果该项目是用C或C ++开发的,那么他们也将需要Nginx补丁,但是不需要第二语言。但是在Nginx主代码库中采用代码的机会为零。这就是实际发生的情况:Nginx团队拥有大供应商的生产就绪QUIC实现,因此开发了自己的C实现。很难说“绑定”代码是可以忽略的还是开发人员在样板代码上花费了多少时间。问题是,Rust内存安全性(现代核心C ++,静态分析和地址清理器也可以实现)是否使开发如此高效,以至于额外的代码和以两种不同语言维护的代码库变得可以忽略不计?

总结

我们意识到,在为Tempesta FW开发HTTP解析器时,我们达到了C语言的极限:如果没有在switch语句中进行查找,就无法直接跳到解析器的所需状态,也无法获得令人满意的代码布局。那时我们考虑将内联汇编引入解析器的代码中。零拷贝状态机已经非常复杂,我们对此想法不满意。在编译器扩展中找到计算的标签和热/冷属性真是太令人惊讶了!由于这些功能,编译器为解析器生成了最佳代码。

TIMTOWTDI表示C ++的强大功能是“有多种方法可以做到” 。是的,这是Perl的想法,但是在很多情况下,C ++允许您使用高级STL或经过优化的自定义算法和数据结构,以纯C语言,在模板元编程中编写程序。现代C ++非常复杂,需要多年的经验才能熟练使用该语言,但是它是一种专业工具,可以使专业开发人员创建最快,最可靠的软件。

不仅Rust不成熟,而且语言设计者似乎故意限制了语言。有许多不良的程序在滥用goto,因此它们只是删除了运算符:对初级用户有利,但对专业人员而言太有限了。当您在复杂的技术任务中苦苦挣扎时,语言和编译器不可能给您带来惊喜。取而代之的是,当您需要做一些简单的事情时,很可能是您在C或C ++时代所做的事情,您会感到失望,并开始与编译器抗争。作为一个例子,likelyunlikely编译器提示在Linux内核的年龄和使用它们在用户空间C / C ++编程如此流行,它们被包含在C ++ 20标准(在程序员不得不使用编译器内部函数之前)。但是使用Rust,您会发现该API是试验性的,if仅适用于语句

相关文章

Web应用程序防火墙加速
从我们在开发Web应用程序防火墙(WAF)的自定义核心逻辑方面的经验,我们了解到大多数或什至所有现代WAF典型的一些性能问题,这些问题可能导致高昂的拥有成本和/或拒绝服务。在本文中,我们介绍了WAF加速器,它与Web加速器一样,可以提高WAF的性能并保护其免受DDoS攻击。

回顾 NatSys Lab. 博客
我们回顾了自2011年以来最古老的 NatSys Laboratory 博客中最有趣的帖子:最近的 CPU 漏洞对 Linux 系统调用性能的影响,深入研究HTTP代理功能以及使用 Nginx 和 HAProxy 的 Tempesta FW 的性能比较,快速字符串处理算法,无锁数据结构和内存分配器。很多技术细节!

转载自:http://tempesta-tech.com/blog/fast-programming-languages-c-c++-rust-assembly