时间戳

首页 > 解决方案 > 似乎缺少在循环条件下调用 const-vector size() 的优化

c++ - 似乎缺少在循环条件下调用 const-vector size() 的优化

问题描述

考虑以下代码：

int g(std::vector<int>&, size_t);

int f(std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0; i < v.size(); i++)
      res += g(v, i);
   return res;
}

编译器无法优化v.size()循环内的评估，因为它无法证明大小不会改变 inside g。使用 GCC 9.2 -O3、 和 x64 生成的程序集是：

.L3:
    mov     rsi, rbx
    mov     rdi, rbp
    add     rbx, 1
    call    g(std::vector<int, std::allocator<int> >&, unsigned long)
    add     r12d, eax
    mov     rax, QWORD PTR [rbp+8] // load a poniter
    sub     rax, QWORD PTR [rbp+0] // subtract another pointetr
    sar     rax, 2                 // result * sizeof(int) => size()
    cmp     rbx, rax
    jb      .L3

如果我们知道g不改变v.size()，我们可以重写循环如下：

for (size_t i = 0, e = v.size(); i < e; i++)
   res += g(v);

这会生成更简单（因此更快）的汇编，而无需那些mov、sub和sar指令。的值size()只是保存在寄存器中。

我希望通过制作向量可以达到相同的效果const（我知道它正在改变程序的语义，因为g现在不能改变向量的元素，但这应该与问题无关）：

int g(const std::vector<int>&, size_t);

int f(const std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0; i < v.size(); i++)
      res += g(v, i);
   return res;
}

现在，编译器应该知道在每次循环迭代中加载的那些指针不能改变，因此，

    mov     rax, QWORD PTR [rbp+8] 
    sub     rax, QWORD PTR [rbp+0] 
    sar     rax, 2

总是一样的。尽管如此，这些指令还是存在于生成的程序集中；现场演示在这里。

我还尝试过 Intel 19、Clang 9 和 MSVC 19，结果完全相同。由于所有主流编译器的行为方式都如此统一，我想知道是否有一些规则不允许这种优化，即将size()for a constant vector 的求值移出循环。

标签： c++loopsoptimizationvectorconstants

解决方案

添加const并不意味着g不能改变向量的大小。可悲的是。

如果您修改本身的对象，您将获得 UB const。const只要原始（即引用的）对象不是 UB，修改您引用的对象就不是 UB const。

换句话说，这是一个有效的程序：

int g(const std::vector<int>& v, size_t)
{
    const_cast<std::vector<int>&>(v).clear();
    return 0;
}

int f(const std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0; i < v.size(); i++)
      res += g(v, i);
   return res;
}

void test()
{
    std::vector<int> v;
    f(v);
}

请注意，如果我们看不到 的定义g，const即使我们不允许 ，也无关紧要const_cast：

std::vector<int> global_v;

int g(const std::vector<int>& v, size_t)
{
    global_v.clear();
    return 0;
}

int f(const std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0; i < v.size(); i++)
      res += g(v, i);
   return res;
}

void test()
{
    f(global_v);
}

考虑const将引用作为对您自己（和其他人）的提醒和编译器强制保护，但与其说是对编译器的优化机会。然而，将值/对象标记为const它们本身有很大的机会改进优化 - 将实际值传递const Something给不透明的函数可以保证Something之后保持相同的东西（但请注意，这const不是通过指针或引用成员传递的）。

推荐阅读