为什么这个空操作循环没有被优化掉？

Question

以下代码将从一个被解释为浮点数的零数组复制到另一个数组中，并打印出操作的时间。我曾经看过许多情况下，包括gcc在内的编译器都会优化掉无操作循环，因此我一直期待着在更改我的复制数组程序的某个时刻它将停止进行复制。

#include <iostream>
#include <cstring>
#include <sys/time.h>

static inline long double currentTime()
{
    timespec ts;
    clock_gettime(CLOCK_MONOTONIC,&ts);
    return ts.tv_sec+(long double)(ts.tv_nsec)*1e-9;
}

int main()
{
    size_t W=20000,H=10000;

    float* data1=new float[W*H];
    float* data2=new float[W*H];
    memset(data1,0,W*H*sizeof(float));
    memset(data2,0,W*H*sizeof(float));

    long double time1=currentTime();
    for(int q=0;q<16;++q) // take more time
        for(int k=0;k<W*H;++k)
            data2[k]=data1[k];
    long double time2=currentTime();

    std::cout << (time2-time1)*1e+3 << " ms\n";

    delete[] data1;
    delete[] data2;
}

我使用 g++ 4.8.1 命令 g++ main.cpp -o test -std=c++0x -O3 -lrt 进行编译。此程序在我的机器上打印出6952.17 ms （我需要设置 ulimit -s 2000000 才能避免崩溃）。

我还尝试将数组的创建方式从new更改为自动 VLAs，去除了memset，但这并未改变 g++ 的行为（除了将时间减少了几倍）。

看来编译器认为这段代码不会执行任何有意义的操作，那么为什么它没有优化掉循环呢？

- Ruslan

---

从我们的角度来看，这不是任何操作，但编译器不知道且无法知道data1和data2内存块的内容已经相等。 - pan-

我不能给出明确的答案，但是a) 任何优化都不是必须的。b) 你有两个new但没有delete。 - deviantfan

@pan-：它确实知道data2计算的结果没有被使用。我同意OP的观点，这种代码在我的实践中通常会被优化掉，因此在编写这样的基准测试时，我必须采取特殊措施以确保它不会发生。 - Violet Giraffe

我很好奇。如果它们不是动态的，你会给它更好的战斗机会吗？有点奇怪，但是认真地好奇（我认为这没有任何区别，但值得一试：'static'）。 - WhozCraig

VLAs？这甚至不是可移植的C++..并且保留原始代码（太多了？）如果问题在飞行中更改，那就令人困惑。 - Karoly Horvath

Answer 1

无论如何，这并不是不可能的（clang++版本3.3）：

clang++ main.cpp -o test -std=c++0x -O3 -lrt

该程序在我的电脑上打印出了0.000367毫秒的时间...并查看汇编代码：

...
callq   clock_gettime
movq    56(%rsp), %r14
movq    64(%rsp), %rbx
leaq    56(%rsp), %rsi
movl    $1, %edi
callq   clock_gettime
...

当使用g++编译器时：

...
call    clock_gettime
fildq   32(%rsp)
movl    $16, %eax
fildq   40(%rsp)
fmull   .LC0(%rip)
faddp   %st, %st(1)
.p2align 4,,10
.p2align 3
.L2:
 movl    $1, %ecx
 xorl    %edx, %edx
 jmp     .L5
 .p2align 4,,10
 .p2align 3
 .L3:
 movq    %rcx, %rdx
 movq    %rsi, %rcx
 .L5:
 leaq    1(%rcx), %rsi
 movss   0(%rbp,%rdx,4), %xmm0
 movss   %xmm0, (%rbx,%rdx,4)
 cmpq    $200000001, %rsi
 jne     .L3
 subl    $1, %eax
 jne     .L2
 fstpt   16(%rsp)
 leaq    32(%rsp), %rsi
 movl    $1, %edi
 call    clock_gettime
 ...

编辑（g++ v4.8.2 / clang++ v3.3）

源代码 - 原始版本（1）

...
size_t W=20000,H=10000;

float* data1=new float[W*H];
float* data2=new float[W*H];
...

源代码 - 修改版（2）

...
const size_t W=20000;
const size_t H=10000;

float data1[W*H];
float data2[W*H];
...

现在，未经优化的情况是 (1) + g++。

- manlio

Answer 2

这个问题中的代码已经有了很大的改变，使正确答案失效。本答案适用于第5版：由于代码尝试读取未初始化的内存，优化器可能合理地假设发生了意外情况。

许多优化步骤具有类似的模式：有一个匹配当前编译状态的指令模式。如果在某个点上匹配成功，则匹配的模式会（参数化地）替换为更有效的版本。这样一个模式的非常简单的例子是定义一个随后没有使用的变量；在这种情况下，替换只是删除该变量。

这些模式是针对正确的代码设计的。对于错误的代码，这些模式可能只是不能匹配，也可以以完全意想不到的方式匹配。前一种情况不会进行优化，后一种情况可能会导致完全不可预测的结果（特别是如果修改过的代码进一步优化）。

- MSalters

Answer 3

为什么你期望编译器对此进行优化呢？通常很难证明对任意内存地址的写入是“无操作”的。在你的情况下，这是可能的，但需要编译器通过new跟踪堆内存地址（这又是一件困难的事情，因为这些地址是在运行时生成的），而且真的没有动力去这样做。

毕竟，你明确地告诉编译器你想要分配内存并写入它。可怜的编译器怎么知道你一直在欺骗它呢？

特别是，堆内存可能与许多其他内容别名。它恰好是私有的，只属于你的进程，但正如我上面所说的，证明这一点对编译器来说是很费力的，不像函数本地内存那样简单。

- Konrad Rudolph

---

这段内存没有进一步的引用。 - Violet Giraffe

在这种情况下，它真的非常简单。 - Karoly Horvath

@MarkusMayr volatile 的意思是任何对它的写操作必须按照规定的顺序和次数进行。它可能是指向 MMIO 区域的指针。 - Ruslan

@KonradRudolph 无论如何，你对于 new 的担忧似乎并不完全正确。我已经更新了问题，删除了 memset 和 new 运算符。 - Ruslan

@Ruslan 我简直不敢相信它能够正常工作而且没有段错误。这个数组太大了，栈无法处理。 - freakish

Answer 4

唯一的方法让编译器知道这是一个无操作（no-op）的方式就是它必须知道 memset 函数的作用。为了实现这个目标，该函数必须在头文件中定义（但通常没有这样做），或者被编译器视为特殊内置函数。但是如果没有这些技巧，编译器只会看到对一个未知函数的调用，它“可能”具有副作用，并且对于两个调用可能会执行不同的操作。

- jalf

---

我认为问题的重点不在于 memset，而在于 data2[k] = data1[k] 循环（因为在此之后不再访问 data2）。 - Angew is no longer proud of SO

将memset调用注释掉不会改变行为（尽管由于某种原因，6950毫秒变为了5500毫秒）。 - Ruslan

同样的论点也适用于 operator new。并且没有真正的动机使内存分配成为编译器内在函数，因此编译器可能不知道操作系统内存分配过程的所有复杂性。 - Konrad Rudolph

@KonradRudolph：实际上，除了使用内置函数之外，编译器也会作弊。例如，在LLVM中，“malloc”和“free”（以及“new”和“delete”的混淆名称）已知于优化器，因此如果它意识到内存未使用（例如在优化后），则还会优化分配/释放。当然，这违反了任何依赖副作用的实现（并且使用“LD_LIBRARY_PRELOAD”时他们无法知道它），但这是一种被使用的策略。 - Matthieu M.

@MatthieuM。当然会。我的意思是你不能期望他们作弊。我有点惊讶LLVM会打入malloc和free，但没关系。 - Konrad Rudolph

@KonradRudolph：我也有些惊讶，我不知道标准中是否有特定的措辞允许它们的省略（比如复制构造函数），我肯定从未见过任何提到的东西。我还知道LLVM也可以将堆分配更改为栈分配。 - Matthieu M.