编译器可以优化可变长度的循环吗？

Question

如果循环的最后一个索引（下例中的 a 和 b）在编译时未知，编译器能否优化循环？

未优化：

int* arr = new int[a*b];
for (i = 0; i < a; ++i){
    for(j = 0; j < b; ++j){
        arr[i*b+j] *= 8;
    }
}

//delete arr after done.

更优化：（假设 a 和 b 很大...）

int c = a*b;
int* arr = new int[c];
for (i = 0; i < c; ++i){
        arr[c] *= 8;
}

//delete arr after done.

Answer 1

是的，它可能可以，因为大小是恒定的并且不会在您的循环中发生变化，就像这里发生的那样。请阅读 Optimize "for" loop 了解更多。

仅供参考，在你的第一个例子中，这个：

arr[j*a+b] *= 8;

应该是这样的：

arr[j*a+i] *= 8;

Answer 2

现代编译器绝对可以改变两个数组的顺序，以防止不必要的缓存未命中，来自：

for (i = 0; i < a; ++i){
    for(j = 0; j < b; ++j){
        arr[j*a+i] *= 8;
    }
}

对此：

for(j = 0; j < b; ++j){
    for (i = 0; i < a; ++i){
        arr[j*a+i] *= 8;
    }
}

经过此优化后，这两个示例（与您的手动优化相比）在性能上应该没有明显差异。

Answer 3

如果您将数组视为线性数组 space，gcc（可能还有其他）会在编译时不知道范围的情况下进行优化。

此代码：

void by8(int* arr, int a, int b)
{
  auto extent = a * b;
  for (int i = 0; i < extent; ++i)
  {
    arr[i] *= 8;
  }
}

编译成这个（注意循环的内部是如何矢量化的）

by8(int*, int, int):
        imull   %esi, %edx
        testl   %edx, %edx
        jle     .L23
        movq    %rdi, %rax
        andl    , %eax
        shrq    , %rax
        negq    %rax
        andl    , %eax
        cmpl    %edx, %eax
        cmova   %edx, %eax
        cmpl    , %edx
        jg      .L26
        movl    %edx, %eax
.L3:
        sall    , (%rdi)
        cmpl    , %eax
        je      .L15
        sall    , 4(%rdi)
        cmpl    , %eax
        je      .L16
        sall    , 8(%rdi)
        cmpl    , %eax
        je      .L17
        sall    , 12(%rdi)
        cmpl    , %eax
        je      .L18
        sall    , 16(%rdi)
        cmpl    , %eax
        je      .L19
        sall    , 20(%rdi)
        cmpl    , %eax
        je      .L20
        sall    , 24(%rdi)
        cmpl    , %eax
        je      .L21
        sall    , 28(%rdi)
        movl    , %ecx
.L5:
        cmpl    %eax, %edx
        je      .L27
.L4:
        leal    -1(%rdx), %r8d
        movl    %edx, %r9d
        movl    %eax, %r10d
        subl    %eax, %r9d
        subl    %eax, %r8d
        leal    -8(%r9), %esi
        shrl    , %esi
        addl    , %esi
        leal    0(,%rsi,8), %r11d
        cmpl    , %r8d
        jbe     .L7
        leaq    (%rdi,%r10,4), %r10
        xorl    %eax, %eax
        xorl    %r8d, %r8d
.L9:
        vmovdqa (%r10,%rax), %ymm0
        addl    , %r8d
        vpslld  , %ymm0, %ymm0
        vmovdqa %ymm0, (%r10,%rax)
        addq    , %rax
        cmpl    %r8d, %esi
        ja      .L9
        addl    %r11d, %ecx
        cmpl    %r11d, %r9d
        je      .L22
        vzeroupper
.L7:
        movslq  %ecx, %rax
        sall    , (%rdi,%rax,4)
        leal    1(%rcx), %eax
        cmpl    %eax, %edx
        jle     .L23
        cltq
        sall    , (%rdi,%rax,4)
        leal    2(%rcx), %eax
        cmpl    %eax, %edx
        jle     .L23
        cltq
        sall    , (%rdi,%rax,4)
        leal    3(%rcx), %eax
        cmpl    %eax, %edx
        jle     .L23
        cltq
        sall    , (%rdi,%rax,4)
        leal    4(%rcx), %eax
        cmpl    %eax, %edx
        jle     .L23
        cltq
        sall    , (%rdi,%rax,4)
        leal    5(%rcx), %eax
        cmpl    %eax, %edx
        jle     .L23
        cltq
        addl    , %ecx
        sall    , (%rdi,%rax,4)
        cmpl    %ecx, %edx
        jle     .L28
        movslq  %ecx, %rcx
        sall    , (%rdi,%rcx,4)
        ret
.L22:
        vzeroupper
.L23:
        ret
.L27:
        ret
.L26:
        testl   %eax, %eax
        jne     .L3
        xorl    %ecx, %ecx
        jmp     .L4
.L28:
        ret
.L21:
        movl    , %ecx
        jmp     .L5
.L15:
        movl    , %ecx
        jmp     .L5
.L16:
        movl    , %ecx
        jmp     .L5
.L17:
        movl    , %ecx
        jmp     .L5
.L18:
        movl    , %ecx
        jmp     .L5
.L19:
        movl    , %ecx
        jmp     .L5
.L20:
        movl    , %ecx
        jmp     .L5

编译器：gcc 5.4，命令行选项：-std=c++14 -O3 -march=native

Answer 4

您始终可以展开 for 循环。即使您不知道迭代次数，也应该使用一个名为 Duff's device

的技巧

另请参阅此处关于 Whosebug 的解释：How does Duff's device work?

您可以有一个交错的 switch 和 while 循环，并让 while 循环一次处理 4 个项目。如果你想处理 6 个项目，你可以通过跳转到处理 2+4=6 个项目的循环中的倒数第二个项目来作弊：

int  n = 6;
int it = n / 4;
int check = 0;
switch (n % 4) {
  case 0: do { check += 1;
  case 3:      check += 1;
  case 2:      check += 1;
  case 1:      check += 1;
} while (it--);
}
printf("processed %i items\n", check);

Answer 5

如果您使用的是 visual studio 编译器，您可以使用 /Qvec-report 命令行参数，它会告诉您哪些循环 are/are 没有被向量化，并给出原因代码说明原因他们不是

循环矢量化（与展开不同）是编译器使用 SIMD（SSE、SSE2、AVX）指令将循环分解为一系列并行执行的操作

https://msdn.microsoft.com/en-us/library/jj658585.aspx

gcc 和 clang 可能具有相似的功能

编译器可以优化可变长度的循环吗？

Can Compiler Optimize Loop with Variable Length?

c++

optimization

performance

loops

compiler-optimization