为什么 GCC 不能假设 std::vector::size 在这个循环中不会改变？

Question

我向一位同事声称if (i < input.size() - 1) print(0);会在此循环中得到优化，因此input.size()不会在每次迭代中读取，但事实证明并非如此！

void print(int x) {
    std::cout << x << std::endl;
}

void print_list(const std::vector<int>& input) {
    int i = 0;
    for (size_t i = 0; i < input.size(); i++) {
        print(input[i]);
        if (i < input.size() - 1) print(0);
    }
}

根据带有 gcc 选项的编译器资源管理器，-O3 -fno-exceptions我们实际上是在读取input.size()每次迭代并lea用于执行减法！

        movq    0(%rbp), %rdx
        movq    8(%rbp), %rax
        subq    %rdx, %rax
        sarq    $2, %rax
        leaq    -1(%rax), %rcx
        cmpq    %rbx, %rcx
        ja      .L35
        addq    $1, %rbx

有趣的是，在 Rust 中确实发生了这种优化。看起来像i被替换j为每次迭代递减的变量，并且测试i < input.size() - 1被替换为类似j > 0.

        movq    0(%rbp), %rdx
        movq    8(%rbp), %rax
        subq    %rdx, %rax
        sarq    $2, %rax
        leaq    -1(%rax), %rcx
        cmpq    %rbx, %rcx
        ja      .L35
        addq    $1, %rbx

在Compiler Explorer 中，相关程序集如下所示：

        cmpq    %r12, %rbx
        jae     .LBB0_4

我检查，我敢肯定r12是xs.len() - 1和rbx是计数器。早些时候有一个addforrbx和一个mov循环外的 into r12。

为什么是这样？好像如果GCC能够内联size()和operator[]，因为它没有，它应该能够知道，size()不会改变。但也许GCC的优化器判断不值得把它拉出来变成一个变量？或者也许还有其他一些可能的副作用会使这不安全——有人知道吗？

Answer 1

非内联函数调用 cout.operator<<(int)优化器来说是一个黑匣子（因为库只是用 C++ 编写的，优化器看到的只是一个原型；请参阅评论中的讨论）。它必须假设全局变量可能指向的任何内存都已被修改。

（或者std::endl电话。顺便说一句，为什么在那个时候强制刷新 cout 而不是仅仅打印一个'\n'？）

例如，就它所知，std::vector<int> &input是对全局变量的引用，并且这些函数调用之一修改了该全局变量。（或者vector<int> *ptr某处有一个全局变量，或者有一个函数返回指向static vector<int>某个其他编译单元中的，或者函数可以获得对该向量的引用而无需我们传递对它的引用的其他方式。

如果您有一个从未使用过地址的局部变量，则编译器可以假定非内联函数调用无法改变它。因为任何全局变量都无法保存指向该对象的指针。（这称为逃逸分析）。这就是为什么编译器可以size_t i跨函数调用保存在寄存器中的原因。(int i可以只是优化掉，因为它被遮蔽了，size_t i而不是用其他方式）。

它可以对本地做同样的事情 vector（即对于 base、end_size 和 end_capacity 指针）。

ISO C99 针对这个问题有一个解决方案：int *restrict foo. 许多C ++编译支持int *__restrict foo，以保证内存指向的foo是只通过该指针访问。在采用 2 个数组的函数中最常用，并且您希望向编译器保证它们不会重叠。因此它可以自动矢量化而无需生成代码来检查并运行回退循环。

OP评论：

在 Rust 中，非可变引用是一种全局保证，即没有其他人正在改变您所引用的值（相当于 C++ restrict）

这就解释了为什么 Rust 可以进行这种优化而 C++ 不能。

优化你的 C++

显然你应该使用 auto size = input.size();在函数顶部一次，以便编译器知道它是一个循环不变式。C++ 实现不会为您解决这个问题，因此您必须自己解决。

您可能还需要const int *data = input.data();从std::vector<int>“控制块”中提升数据指针的负载。 不幸的是，优化可能需要非常不习惯的源更改。

Rust 是一种更现代的语言，它是在编译器开发人员了解编译器在实践中的可能性之后设计的。它也确实以其他方式显示出来，包括可移植地公开 CPU 可以通过i32.count_ones、旋转、位扫描等执行的一些很酷的东西。 ISO C++ 仍然没有可移植地公开任何这些，除了std::bitset::count().