增量向量元素

在哪种情况下，如果std :: vector元素的类型为uint8_t或uint32_t，它们的增量会更快吗？

为了不进行抽象推理，我们考虑两个特定的实现：

void vector8_inc(std::vector<uint8_t>& v) { for (size_t i = 0; i < v.size(); i++) { v[i]++; } } void vector32_inc(std::vector<uint32_t>& v) { for (size_t i = 0; i < v.size(); i++) { v[i]++; } } 

让我们尝试猜测

使用基准测试很容易回答这个问题，稍后我们会这样做，但是首先我们将尝试猜测（这被称为“基于基本原理的推理”-听起来更科学）。

首先，值得提出一个问题： 这些向量的大小是多少？

好吧，让我们选择一些数字。 让每个中有20,000个元素。

此外，众所周知，我们将在Intel Skylake处理器上进行测试-我们将看到具有直接寻址功能的8位和32位操作数加法命令的特征。 事实证明，它们的主要指标是相同的：每个周期1个操作和每个内存访问4个周期的延迟（1）。 在这种情况下，延迟无关紧要，因为每个加法操作都是独立执行的，因此计算的速度是每个周期1个元素，前提是循环上的所有其余工作将并行执行。

您还可以注意到，对于使用uint8_t的版本，20,000个项目对应于20 KB的数据集，对于使用uint32_t的版本，对应于80 KB的数据集 。 在第一种情况下，它们理想地适合于现代基于x86的计算机的L1级缓存，而在第二种情况下-则不然。 事实证明，由于高效的缓存，8位版本会抢先一步吗？

最后，我们注意到我们的任务与自动向量化的经典情况非常相似：在具有已知迭代次数的循环中，对顺序位于内存中的元素执行算术运算。 在这种情况下，8位版本应该比32位版本具有巨大的优势，因为一个向量运算将处理四倍的元素，并且一般而言，英特尔处理器对单字节元素执行向量运算的速度与32位处理器相同。位元素。

好吧，别再抱怨了。 现在该轮到考试了。

基准测试

在具有不同优化级别的gcc 8和clang 8编译器上 ，我得到了20,000个元素的向量的以下计时：


事实证明，除了-O1级别以外，使用uint32_t的版本比使用uint8_t的版本要快，并且在某些情况下是有意义的： -O3级别的gcc的5.4倍， -O2和-的两个级别的clang的准确度是8倍。 O3 。 是的，在具有标准优化设置的流行编译器中， std :: vector中32位整数的增量最多快8倍。

像往常一样，让我们​​看一下汇编程序清单，以希望它能阐明正在发生的事情。

这是gcc 8在-O2级别的清单，其中8位版本“仅”比32位版本（2）慢1.5倍：

8位：

 .L3: inc BYTE PTR [rdx+rax] mov rdx, QWORD PTR [rdi] inc rax mov rcx, QWORD PTR [rdi+8] sub rcx, rdx cmp rax, rcx jb .L3 

32位：

 .L9: inc DWORD PTR [rax] add rax, 4 cmp rax, rdx jne .L9 

32位版本的外观与未开发（3）循环中的预期完全相同：使用地址进行增量（4），然后使用三个循环控制命令： add rax ， 4-归纳变量（5） 的增量以及几个cmp和jne命令检查退出循环的条件以及条件跳转。 一切看起来都很不错-部署将补偿增加计数器和检查条件的成本，并且我们的代码几乎可以达到每个时钟周期1个元素的最大可能速度（6），但对于开源应用程序，它可以做到。 那么8位版本呢？ 除了带有该地址的inc命令之外，还执行了两个用于从内存中读取的附加命令以及子命令，这些命令从任何地方都不可取。

这是带有评论的清单：

8位：

 .L3: inc BYTE PTR [rdx+rax] ;    v[i] mov rdx, QWORD PTR [rdi] ;  v.begin inc rax ; i++ mov rcx, QWORD PTR [rdi+8] ;  v.end sub rcx, rdx ; end - start (.. vector.size()) cmp rax, rcx ; i < size() jb .L3 ; .   i < size() 

这里的vector :: begin和vector :: end是std :: vector的内部指针，它用来指示包含在为其选择的区域中的元素序列的开始和结束（7），这些值基本上是相同的它们用于实现vector :: begin（）和vector :: end（） （尽管它们的类型不同）。 事实证明，所有其他命令仅是vector.size（）计算的结果 。 看起来没什么异常吗？ 但是，毕竟，在32位版本中，当然也要计算size（） ，但是这些命令不在清单中。 size（）的计算仅发生一次-在循环之外。

那怎么了 简短的答案是指针别名 。 我将在下面给出详细的答案。

详细答案

向量v通过引用传递给函数，实际上，它是一个掩码指针。 编译器必须转到向量的成员v ::开始和v ::结束以计算其大小size（） ，在我们的示例中， size（） 在每次迭代时计算。 但是，编译器没有义务盲目地遵守源代码：它很可能带有在循环外调用size（）函数的结果，但前提是必须确定知道程序的语义不会改变 。 从这个角度来看，循环中唯一有问题的地方是增量v [i] ++ 。 记录发生在一个未知的地址。 这样的操作可以改变size（）的值吗？

如果记录发生在std :: vector <uint32_t>中 （即通过uint32_t *指针），则否，它不能更改size（）值。 写入uint32_t类型的对象只能修改uint32_t类型的对象，并且计算size（）所涉及的指针具有不同的类型（8）。

但是，对于uint8_t ，至少在流行的编译器（9）上，答案是这样的：是的，理论上size（）的值可能会更改 ，因为uint8_t是unsigned char的别名，并且unsigned char （和char ）类型的数组可以任何其他类型的别名 。 这意味着，根据编译器，写入uint8_t指针可以修改任何地址（10）处来源未知的内存的内容。 因此，假设每个增量操作v [i] ++都可以更改size（）值，因此在每次循环迭代时都必须重新计算它。

我们都知道，写入std :: vector指向的内存永远不会更改其自身的size（） ，因为这将意味着该向量本身已以某种方式分配在其自己的堆中，这实际上是不可能并且类似于鸡肉和鸡蛋的问题（11）。 但是不幸的是，编译器对此并不了解！

其余的结果呢？

好了，我们发现了为什么在-O2级别上使用uint8_的版本比在gcc上的uint32_t的版本要慢一些。 但是，为什么要解释在clang上或在-O3上具有相同gcc的巨大差异（最多8倍）？

一切都很简单：在uint32_t的情况下， clang可以执行循环自动矢量化：

 .LBB1_6: ; =>This Inner Loop Header: Depth=1 vmovdqu ymm1, ymmword ptr [rax + 4*rdi] vmovdqu ymm2, ymmword ptr [rax + 4*rdi + 32] vmovdqu ymm3, ymmword ptr [rax + 4*rdi + 64] vmovdqu ymm4, ymmword ptr [rax + 4*rdi + 96] vpsubd ymm1, ymm1, ymm0 vpsubd ymm2, ymm2, ymm0 vpsubd ymm3, ymm3, ymm0 vpsubd ymm4, ymm4, ymm0 vmovdqu ymmword ptr [rax + 4*rdi], ymm1 vmovdqu ymmword ptr [rax + 4*rdi + 32], ymm2 vmovdqu ymmword ptr [rax + 4*rdi + 64], ymm3 vmovdqu ymmword ptr [rax + 4*rdi + 96], ymm4 vmovdqu ymm1, ymmword ptr [rax + 4*rdi + 128] vmovdqu ymm2, ymmword ptr [rax + 4*rdi + 160] vmovdqu ymm3, ymmword ptr [rax + 4*rdi + 192] vmovdqu ymm4, ymmword ptr [rax + 4*rdi + 224] vpsubd ymm1, ymm1, ymm0 vpsubd ymm2, ymm2, ymm0 vpsubd ymm3, ymm3, ymm0 vpsubd ymm4, ymm4, ymm0 vmovdqu ymmword ptr [rax + 4*rdi + 128], ymm1 vmovdqu ymmword ptr [rax + 4*rdi + 160], ymm2 vmovdqu ymmword ptr [rax + 4*rdi + 192], ymm3 vmovdqu ymmword ptr [rax + 4*rdi + 224], ymm4 add rdi, 64 add rsi, 2 jne .LBB1_6 

该周期被部署了8次，通常这是您可以获得的最大性能：L1缓存每个时钟周期一个向量（8个元素）（由于每个时钟周期限制一次写入操作（12），因此不再起作用）。

不对uint8_t执行矢量化 ，因为它需要计算size（）来检查每次迭代的循环条件，因此会受到阻碍。 滞后的原因仍然相同，但是滞后本身要大得多。

最低的时间由自动矢量化解释：gcc仅在-O3级别应用它，而clang默认在-O2和-O3级别应用。 -cc级gcc编译器生成的代码比clang稍慢，因为它不会扩展自动向量化的循环。

纠正情况

我们发现了问题所在-我们该如何解决？

首先，让我们尝试一种无法使用的方法，即，我们将基于迭代器编写一个更加惯用的循环：

 for (auto i = v.begin(); i != v.end(); ++i) { (*i)++; } 

gcc在-O2级别生成的代码会比带有size（）的选项稍微好一点：

 .L17: add BYTE PTR [rax], 1 add rax, 1 cmp QWORD PTR [rdi+8], rax jne .L17 

两个额外的读取操作变成一个，因为我现在与向量的结束指针进行比较，而不是重新计算size（） ，从结束指针中减去向量的开始指针。 根据指令的数量，此代码被uint32_t追上了，因为额外的读取操作与比较操作合并了。 但是，问题并没有解决，自动向量化仍然不可用，因此uint8_t仍然远远落后于uint32_t-在提供自动向量化的水平上，gcc和clang都超过5倍。

让我们尝试其他事情。 我们不会再成功，或者，我们将找到另一种无效的方法。

在此版本中，我们仅在循环之前计算一次size（）并将结果放入局部变量中：

 for (size_t i = 0, s = v.size(); i < s; i++) { v[i]++; } 

好像在工作吗？ 问题是size（） ，现在我们命令编译器在循环开始时将size（）的结果提交给局部变量s ，正如您所知，局部变量不与其他数据相交。 实际上，我们做了编译器做不到的事情。 而且它将生成的代码实际上会更好（与原始代码相比）：

 .L9: mov rdx, QWORD PTR [rdi] add BYTE PTR [rdx+rax], 1 add rax, 1 cmp rax, rcx jne .L9 

只有一个额外的读取操作，没有子命令。 但是，如果额外的命令（ rdx，QWORD PTR [rdi] ）不参与大小计算，该怎么办？ 它从v读取data（）指针！

表达式v [i]被实现为*（v.data（）+ i） ，而由data（）返回的成员（实际上是一个常规的begin指针）与size（）存在相同的问题。 没错，我没有在原始版本中注意到此操作，因为它是“免费的”，因为它仍然必须执行才能计算出大小。

忍受多一点，我们几乎找到了解决方案。 您只需要从循环中删除对std :: vector内容的所有依赖关系即可。 最简单的方法是用迭代器修改我们的习惯用法：

 for (auto i = v.begin(), e = v.end(); i != e; ++i) { (*i)++; } 

现在一切都发生了巨大的变化（这里我们仅将版本与uint8_t进行比较-在一个版本中，我们将迭代器末尾保存在循环之前的局部变量中，在另一个版本中，否）：


这个小小的变化使我们在自动矢量化水平上的速度提高了20倍。 此外，使用uint8_t的代码不仅赶上了使用uint32_t的代码-它像gcc -O3和clang -O2和-O3一样 ，几乎完全超过了它四倍，这是我们一开始就依靠矢量化实现的：最后，正好超过四倍元素可以通过向量运算来处理，并且我们需要的带宽要少四倍-不管缓存级别如何（13）。

如果您读到这个地方，那您一定一直在对自己大喊：

但是，在C ++ 11中引入的带遍历for循环又如何呢？

我赶紧取悦你：它有效！ 实际上，这是语法糖，后面带有迭代器的版本几乎以相同的形式隐藏，在此之前，我们在循环开始之前将结束指针固定在局部变量中。 所以他的速度是一样的。

如果我们突然决定回到古老的洞穴时代并编写一个类似于C的函数，那么这样的代码也将同样有效：

 void array_inc(uint8_t* a, size_t size) { for (size_t i = 0; i < size; i++) { a[i]++; } } 

在这里，指向数组a的指针和大小变量按值传递给函数，因此，由于写入指针a （14）的结果，它们不能更改-就像局部变量一样。 该代码的性能与以前的选项相同。

最后，在可以使用此选项的编译器上，可以使用__restrict （15）声明向量：

 void vector8_inc_restrict(std::vector<uint8_t>& __restrict v) { for (size_t i = 0; i < v.size(); i++) { v[i]++; } } 

__restrict关键字不是C ++标准的一部分，而是自C99以来C标准的一部分（作为strict ）。 如果在编译器中将其实现为C ++扩展，则很可能它将遵循C的语义。当然，C中没有链接，因此您可以在思维上用指向矢量的指针替换指向矢量的链接。

请注意，strict不具有传递属性 ： __restrict说明符的操作（用于声明指向std :: vector的链接）仅适用于矢量本身的成员，而不适用于v.data（）引用的堆区域。 在我们的例子中，不需要更多，因为（就局部变量而言）足以使编译器确信，指向向量开头和结尾的术语本身不与任何东西相交。 但是，关于limit的子句仍然有用 ，因为通过v.data（）进行写操作可能仍会由于别名而导致函数中的其他对象发生更改。

失望的

在这里，我们得出最后一个-非常令人失望的结论。 事实是，当向量在理论上可以干扰自身时，以上显示的所有解决方案仅适用于此特定情况。 解决方案是摆脱循环或隔离调用向量的size（）或end（）的结果 ，而不是告诉编译器写入向量的数据不会影响其他数据。 随着功能的增长，此类代码将难以扩展。

别名问题还没有解决，写命令仍然可以“随处可见”-此函数中根本没有其他数据可以受到影响...。 一旦出现新代码，便会重复所有操作。 这是一个例子 。 如果在小循环中写入uint8_t类型的元素数组，则必须与编译器战斗直到最后（16）。

留言

我将很高兴收到任何反馈。 我还没有评论系统（17），因此，像往常一样，我们将在此线程上HackerNews上进行讨论 。

1. 通过在此处访问内存，可以理解，依赖关系链通过了内存：在同一地址的写命令应该读取在那里最后写入的值，因此，此类操作是依赖的（实际上，如果记录足够，将使用加载重定向（STLF）经常）。 当访问内存时， add命令的依赖关系可能会以其他方式出现，例如，通过计算地址，但是对于我们而言，这是无关紧要的。
2. 这里只显示一个小周期； 安装代码很简单，并且可以快速运行。 要查看完整清单， 请将代码上传到godbolt 。
3. 也许应该简称为“最小化”？ 尽管如此，gcc编译器即使在-O2和-O3级别也通常不会循环，除非在特殊情况下迭代次数很小并且在编译阶段是已知的 。 因此，与clang相比，gcc的测试结果更低，但可以节省很多代码大小。 您可以通过应用配置文件优化或打开-funroll-loops标志来强制gcc展开循环 。
4. 实际上，gcc中的inc DWORD PTR [rax]命令是错过的优化：使用add [rax]，1命令几乎总是更好，因为它仅包含2个组合的微操作，而inc是3个。 在这种情况下，差异仅约为6％，但是如果稍微扩展一下循环以便仅重复记录操作，则差异会更大（进一步的扩展将不再起作用，因为我们将达到1的极限记录每个周期的操作，这不取决于微操作的总数）。
5. 我将此变量称为归纳变量，而不仅仅是在源代码中称为i ，因为编译器将增量i的单位运算转换为rax寄存器中存储的指针的4字节增量，并因此纠正了循环条件。 循环以其原始形式处理向量的元素，并且在此转换之后，循环增加了指针/迭代器，这是降低操作成本的一种方法。
6. 实际上，如果启用-funroll-loops ，则在gcc上，每个元素的速度为1.08小节，展开次数为8倍 。 但是即使带有该标志，他也不会扩展具有8位元素的版本的循环，因此速度的滞后将更加明显！
7. 这些成员有一个私有修饰符，它们的名称取决于实现，但是在stdlibc ++中，它们并不像gcc那样真正地称为start和finish 。 它们分别称为_Vector_base :: _ Vector_impl :: _ M_start和_Vector_base :: _ Vector_impl :: _ M_finish ，即 输入_Vector_impl结构，该结构是_Vector_base类的_M_impl （也是唯一的一个） 成员 ，并且又是std :: vector的基类。 好吧，好吧！ 幸运的是，编译器可以轻松应对这一堆抽象。
8. 该标准没有规定std :: vector成员的内部类型应该是什么，但是在libstdc ++库中，它们仅定义为Alloc：指针 （其中Alloc是向量的分配器），对于默认的std :: allocated对象，它们将简单地定义为类型T *的指针 指向对象的常规指针-在这种情况下为uint32_t * 。
9. 我进行此保留是有原因的。 有人怀疑uint8_t可能被视为char ， signed char和unsigned char以外的类型。 由于别名适用于字符类型 ，因此从原则上讲这不适用于uint8_t ，其行为应类似于其他任何非字符类型。 但是，我所知的所有编译器都没有这样认为： typedef uint8_t都是unsigned char的别名，因此即使他们愿意使用它们，编译器也看不到它们之间的区别。
10. “未知来源”在这里仅是指编译器不知道内存内容指向何处或如何显示。 这包括传递给函数的任意指针，以及全局和静态变量。 , , , , , ( - ). , malloc new , , , , : , , . , malloc new .
11. , std::vector - ? , std::vector<uint8_t> a a.data() placement new b . std::swap(a, b) , – , b ? , b . : - (, ), , .
12. 8 , .. 32 . , std::vector .
13. - 4 : , , – . : 8- L1, 32- – L2 , .
14. , – : . , , «».
15. v[i] , .
16. . , «» , uint8_t . , , , uint8_t , . , clang, gcc , , uint8_t . - gcc , . , , - __restrict .
17. - , , ( Disqus), ( ), .

. : Travis Downs. Incrementing vectors .