Geekly articles weekly

lang格式会降低程序速度

今天，我们将测量toupper函数的不同实现的性能，因为这是他们在星期二所做的。

实际上，我并不在乎toupper函数，我最近才写过另一篇文章，我需要某种通用的绘图核心，并且toupper似乎是基准测试的一个有趣且无害的候选者。 我试图选择一种尽可能简单的方法，但不会碰到我，但恰好发生在这次测试中，我遇到了一个奇怪的问题。

这篇文章将很小-很快就会有关于原始的，也许更有趣的话题的更全面的文章。 如果要与我重现结果， 可以在github上获取源代码。

因此，我们将考虑toupper函数的三种实现，该实现将由char类型的元素组成的数组的字符转换为大写字母-即，它以数组为参数并直接更改其元素，以便所有小写字母都大写。

在第一个实现中，我们只需调用C标准库的toupper [1] 函数并执行C风格的循环：

void toupper_rawloop(char* buf, size_t size) { for (size_t i = 0; i < size; i++) { buf[i] = toupper(buf[i]); } }

在第二个实现中，我们使用一种更现代的方法，将原始循环替换为std :: transform ：

 void toupper_transform(char* buf, size_t size) { std::transform(buf, buf + size, buf, ::toupper); }

最后，在第三个实现中，我们使用一种适用于ASCII字符的特殊算法。 它检查字符是否在a-z范围内，如果成功，则将大写字母替换为相同字母，并从字符代码[2]中减去数字32：

 void toupper_branch(char* buf, size_t size) { for (size_t i = 0; i < size; i++) { char c = buf[i]; if (c >= 'a' && c <= 'z') { buf[i] = c - 32; } } }

看起来很简单，对吧？

现在，我们将使用默认设置在gcc 5.5编译器上使用Skylake i7-6700HQ处理器在笔记本电脑上测量这些实现的速度。 结果以散点图的形式给出[3]：


立即我们将处理与我们的任务无关的三个问题。

首先，查看分支算法的图形（以绿色显示）。 根据输入数据的大小，它有很大的不同-其他两个图形几乎保持平坦。 这实际上只是一个测试工件。 输入的ASCII字符是随机选择的[4]，因此，在第三种实现方式中，决定因素是分支预测算法的操作。 使用少量数据，它可以在执行迭代时完全存储元素的顺序，因此未命中的数量少且速度高， 如本注释所示 。 随着数据序列大小的增加，预测算法会记住的次数越来越少，直到最终开始丢失每个大写字母（每个字符0.27个未命中），然后将图形调平。

其次，请注意左上方的绿色斑点组，这与具有toupper_branch分支的变体的较低速度相对应：


这不是孤立的工件：此类斑点在几次发射中出现。 同时，如果仅针对这些数据大小测试算法，则无法复制它们-仅在对所有大小进行测试时它们才会弹出。 但是在这种情况下，它们并不总是出现。 我没有特别研究它，但是我可以假设这是由于分支预测算法中名称或别名的某些冲突或将4 KB内存的物理页面映射到虚拟时造成的（尽管虚拟地址空间的随机性已关闭）。

第三，图上toupper_rawloop的实现（以蓝色显示）看起来像两条不同的线：一条稍微高于每个字符2 个小节的标记，另一条位于每个字符1.5 个小节的水平上。 这两行出现在所有测试人员中。 速度更快的选项（每个周期1.57个字符的速度）实际上会降低下载端口的速度：在端口2和3上读取数据的速度为每个周期1.54微操作，因此它们将占98％的繁忙。 我无法确定“政权”放慢的原因。

当我处理这个问题时，快速的“政权”突然消失了，只有缓慢的“政权”依然存在。 也许处理器意识到我正在尝试做的事情，并秘密下载了微代码的更新程序以消除矛盾，但是我（仍然）有证据-一个带有图形的矢量图像。

在此示例中，我们感兴趣的是什么？

但是让我们感兴趣的是，具有原始循环的版本比具有std :: transform的版本快3-4倍：每个字符1.5-2个周期，而每个字符几个周期则为7。

这是怎么回事 标准算法使我失败了吗？ std :: transform是否有任何缺陷？

不完全是 更确切地说，一点也不。

事实证明，在不同文件中编译函数时会出现这种结果。 如果将它们放在同一文件中，则它们的性能将同样降低。

不，对齐与之无关。

但这还不是全部：带有原始循环的快速版本在单独的文件中编译时，如果仅将<algorithm>头文件附加到该文件中，则会降低速度。 是的，没错：只需连接此文件，该文件将永远不会使用，并且不会在最终目标文件中生成任何代码，并且“原始”循环的速度将降低3-4倍。 相反，如果从<algorithm>文件复制并粘贴std :: transform的实现 ，但不包括此文件，则带有std :: transform的版本将加速到极限。

怪异并不止于此（我保证不会有更多）：包括<algorithm>文件并不总是导致所描述的效果。 如果<algorithm>早于<ctype.h>连接，则会发生速度下降，但是如果交换它们，则不会：

慢速代码：

 #include <algorithm> #include <ctype.h>

快速代码：

 #include <ctype.h> #include <algorithm>

实际上，当clang-format自动对包含的头文件进行排序并将<algorithm>放在列表所属的列表的开头时，这种异常出现在我（在另一个项目中）中（因此该文章的clickbait标题）。

自然，我们迟早不得不涉足汇编程序的上市。 我们不会延迟这一令人不快的时刻。

函数[5]的快速和慢速版本如下所示，小循环带有注释：

<algorithm>首先连接：

 toupper_rawloop(char*, unsigned long): push rbp push rbx lea rbp, [rdi+rsi] sub rsp, 8 test rsi, rsi je .L1 mov rbx, rdi .L5: movsx edi, BYTE PTR [rbx] ;  char-  *buf add rbx, 1 ; buf++ call toupper ;  toupper(c) mov BYTE PTR [rbx-1], al ;    buf[-1] cmp rbp, rbx ;  buf == buf_end jne .L5 ; .L1: add rsp, 8 pop rbx pop rbp ret

<algorithm>连接第二：

 toupper_rawloop(char*, unsigned long): test rsi, rsi je .L7 push rbp push rbx mov rbp, rsi mov rbx, rdi sub rsp, 8 call __ctype_toupper_loc lea rsi, [rbx+rbp] mov rdi, rbx .L4: ;  char-  buf movsx rcx, BYTE PTR [rdi] ;      toupper ; (   __ctype_toupper_loc) mov rdx, QWORD PTR [rax] ; buf++ add rdi, 1 ;   toupper  , ;       mov edx, DWORD PTR [rdx+rcx*4] mov BYTE PTR [rdi-1], dl ;   cmp rsi, rdi ;  buf == end_buf jne .L4 ; add rsp, 8 pop rbx pop rbp .L7: rep ret

主要区别在于，在慢速版本中，toupper函数仅在循环中被简单地调用，而在快速版本中，函数调用完全不存在，并且在对应表中仅存在搜索[6]，即 函数std :: toupper的主体在调用位置被替换。

如果看一下glibc库的源代码 ，我们会在这里找到toupper函数的实现：

 __extern_inline int // __NTH –  , ,      __NTH (toupper (int __c)) { return __c >= -128 && __c < 256 ? (*__ctype_toupper_loc ())[__c] : __c; }

如我们所见， toupper被定义为extern内联函数，该函数首先检查char字符的大小是否适合一个字节[7]，然后在__ctype_toupper_loc（）函数返回的对应表中搜索该字符。 该函数返回一个本地流指针（类型为const int ** ），该指针进而指向一个对应表，响应于对我们符号的请求，该表将返回其大写形式[8]。

现在清楚清单中正在发生什么。 在该算法的快速版本中，编译器替换了toupper函数的主体，但无法替换对__ctype_toupper_loc（）函数的调用[9]。 但是，此调用被声明为__attribute __（（const）） ，这意味着返回值仅取决于参数（此处不存在）。 编译器知道此函数每次都返回相同的值，因此将其调用带到循环之外，并且在循环本身中，只有很少的读取操作与访问对应表，将新值写入缓冲区以及循环控制相关。

在慢速版本中，对toupper（）的调用保留在循环的主体中。 循环本身仅需一条命令即可缩短，但是，当然，现在您仍然必须执行toupper函数中的所有代码。 在我的系统上，它看起来像这样：

  lea edx,[rdi+0x80] ; edx = rdi + 0x80 movsxd rax,edi ;    c cmp edx,0x17f ; ,  c     -128  255 ja 2a ;  ,   mov rdx,QWORD PTR [rip+0x395f30] ;    ;   mov rdx,QWORD PTR fs:[rdx] ;     ;     mov rdx,QWORD PTR [rdx] ;    ;    mov rdx,QWORD PTR [rdx+0x48] ;     toupper mov eax,DWORD PTR [rdx+rax*4+0x200] ;  c   2a: ret

由于这是非嵌入式调用，因此该程序会执行更多工作。 至少有五个连续的访问内存的操作（所谓的指针追逐 ， 指针追逐 ）。 在快速版本中，仅剩下其中两个，因为所有其他都从循环中删除。 从调用函数到退出函数之间的延迟应该约为25个周期，并且大约有7个周期出现-这意味着处理器能够并行化调用，在这种情况下，这是相当不错的。

为什么会这样呢？

在包含文件的长长链中，C ++头文件（例如<algorithm>）依次包含<bits / os_defines.h>文件，该文件包含以下行：

 //      isanum  .  //   . #define __NO_CTYPE 1

最终连接文件<ctype.h>时 ，由于此指令，不能包含将toupper定义为extern inline的代码：

 #if !defined __NO_CTYPE # ifdef __isctype_f __isctype_f (alnum) //  ..  .. __isctype_f (xdigit) # elif defined __isctype # define isalnum(c) __isctype((c), _ISalnum) # define isalpha(c) __isctype((c), _ISalpha) //  ..  .. # endif //      # ifdef __USE_EXTERN_INLINES __extern_inline int __NTH (tolower (int __c)) { return __c >= -128 && __c < 256 ? (*__ctype_tolower_loc ())[__c] : __c; } __extern_inline int __NTH (toupper (int __c)) { return __c >= -128 && __c < 256 ? (*__ctype_toupper_loc ())[__c] : __c; } # endif //   tolower     # if __GNUC__ >= 2 && defined __OPTIMIZE__ && !defined __cplusplus # define tolower(c) __tobody (c, tolower, *__ctype_tolower_loc (), (c)) # define toupper(c) __tobody (c, toupper, *__ctype_toupper_loc (), (c)) # endif /* Optimizing gcc */ #endif /* Not __NO_CTYPE. */

请注意，连接<ctype.h>时， toupper 的 C ++版本永远不会定义为宏-最大值作为extern 内联 -因为宏的定义受！Defined __cplusplus检查的保护，因此永远不会生效。

总的来说，我不确定在这种情况下__NO_CTYPE是否应排除声明为extern inline的tolower和toupper函数的主体，但这确实是发生了-因此循环速度显着下降。 总之，我可以说，如果您包含<cctype>而不是<ctype.h> （即C ++是将函数放在std :: namespace中的C头文件的版本），那么在这种情况下，代码将运行缓慢因为<cctype>最终包括<bits / os_defines.h> 。

那重要吗？ 不不

toupper函数不适用于使用不同语言的字符的严肃工作，因此，如果您只需要处理ASCII字符，则可以编写自己的更快的实现。 如果您需要认真处理文本，则很可能会使用UTF-8，并且必须使用某种ICU来支持区域设置，或者等到C ++中出现Unicode支持（可能需要很长时间才能等待） 。 因此，“ clang-format可能导致4倍的性能下降”这样的语句仅适合用作clickbait标头。

在所有版本的libc中都观察到这种效果吗？ 是的，几乎所有的东西，但即使在这里，也不是那么简单。

上面显示的结果对于gcc 5.5和glibc 2.23是正确的，因为我使用了这些版本，但是新版本中发生了一些新变化（从glibc 2.27开始）。 在那里，在<ctype.h >之前打开<algorithm>仍然会产生相同的效果，但是现在<stdlib.h> [10]也会产生问题：如果在<ctype.h>之前打开它，性能也会下降，这不是在早期版本中观察到。 显然，在较新的版本中， <stdlib.h>文件还包含__NO_CTYPE定义。 至少，现在不可能指责clang格式进行排序-在这里它可以帮助解决问题（如果连接文件列表中没有其他问题文件）。

我在libc中发布了一个错误报告 ，因此该错误很可能会得到修复，但是毫无疑问，与头文件连接顺序有关的错误将进一步困扰我们。

留言


我的网站上没有评论系统，但我正在使用它（也就是说，经常抱怨，很难在静态网站上发表评论）。

同时，您可以在Hacker News网站或lobste.rs上讨论此文章。

致谢


感谢Hacker News的ufo用户，他指出没有必要使用lambda函数来将std :: toupper改用于std :: transform中 ，也感谢乔纳森·穆勒（Jonathan Muller），他解释说仍然需要lambda函数。

  1. 是的， <ctype.h>头文件中的toupper（3）函数不适用于大多数非ASCII字符，因为 不能处理大于一个字节的字符，但是它适合我们的任务，因为我们只会将ASCII字符的字符串传递给它。
  2. 在ASCII表中，小写和大写字符的位置非常方便-彼此之间的距离为32个位置，这意味着您可以简单地通过将32个字符相减或相加来将字符从一种情况转移到另一种情况。通常，如果我们确定知道所有输入如果数据是ASCII字母，我们可以不进行任何检查就重置第5位（例如c＆0b11011111 ），以便将任何大写字母都转换为小写字母，而这不会反映为小写字母。 但是我们可能不知道，所以我们必须检查字符是否为字母，以免意外破坏char等非字母字符。
  3. 应该将其称为散点图，并在点的位置上加上“噪声”。 实际上，这是一个普通的散点图，其中我们感兴趣的参数（输入数据的大小）绘制在x轴上，工作速度在y轴上（每个符号的度量- 值越低，速度越高 ）。 该图的主要特征是，对于x轴上的每个参数值，都会执行几次采样：在这种情况下，对于每种数组大小，测试都会重复10次。
  4. 即，字符是从[32，127]范围内随机且均匀地选择的，因此该函数中的条件在大约27％的情况下为真。
  5. 这两个清单均引用原始循环实现，并且仅在包含<algorithm>和<ctype.h>文件的顺序上有所不同。 所生成的源代码对于所有实现都是相同的-无论是快速版本还是慢版本。 例如，如果包含<algorithm>文件，则使用std :: transform的实现将生成相同的慢汇编程序代码，如果仅复制函数定义而不包含文件，则将生成相同的快速代码。
  6. 但是，此快速循环比它慢，因为在循环内部读取对应表的指针的次数过多（ mov rdx，QWORD PTR [rax] ）。 该指针可能因区域设置而异，但是在执行循环期间不会更新，因此可以将其移出循环。 一定是编译器认为没有足够的理由这样做，因为我们正在写入char类型的元素数组，并且它们原则上可以用作[rax]的别名，即 指向表的指针。 无论如何，即使__restrict__在这里也无济于事。 但是在另一个版本的循环中，仅添加了toupper值，而没有任何内容写入数组， 因此应用了这种优化 -在循环外部读取指针。
  7. 该检查未反映在可替换的汇编程序代码中，因为编译器已经知道char值始终在[-128，255]范围内。 该检查仅是必需的，因为toupper©函数的API接受一个int类型的值而不是char ，以便用户可以将任何熟悉的int类型的数传递给它 ，而对应表仅用于char类型的值，因此该检查有助于避免在缓冲区外读取。
  8. 顺便说一句，这解释了为什么std :: toupper过程独立于输入数据的大小：它们不使用分支（除了范围检查，这是非常可预测的），而是使用独立于分支的对应表。 ↵
  9. 即使有非常强烈的愿望，也无法替换此调用：该函数的主体在头文件中不可用。
  10. 我绝不会发现stdlib.h （或<algorithm> ）有问题-很有可能许多其他C头文件和所有C ++头文件也导致此现象，我只是没有对其进行测试。 我连接stdlib.h只是为了确定size_t 。

注意事项 本文最初在Performance Matters网站上发布。 经作者许可，翻译的文章将发布在此处。

Source: https://habr.com/ru/post/zh-CN480012/

More articles:


All Articles