C++ 执行表达式的耗时为何多于逆波兰表达式的栈操作?

问题解决,其实是 神奇的 -O2 优化~ 有如下代码,执行一个简单的表达式 a = b - (c+c); int64_t start = curr
关注者
16
被浏览
3010

其实题主的问题题主自己尚未完全解决,只是不知道题主发现了没有。

俺来打个酱油说几点。

把题主的例子稍微打磨一下,把记时的操作省略掉,变成下面这样的话:

int foo() {
  int step = 10000000;
  int a;
  int b = 1;
  int c = 10;
  while (step--) {
    a = b - (c + c);
  }

  return a;
}

template<typename Type>
class EvalSlot {
public:
  static const int MaxStackSize = 8;

  void add() {
    Type right = pop();
    Type left = pop();
    push(left + right);
  }

  void sub() {
    Type right = pop();
    Type left = pop();
    push(left - right);
  }

  void push(const Type& value) {
    data_[++index_] = value;
  }

  Type pop() {
    return data_[index_--];
  }

  void clear() {
    index_ = -1;
  }

protected:
  int index_ = -1;
  Type data_[MaxStackSize] = {0};
};

int bar() {
  EvalSlot<int> e;

  int step = 10000000;

  while (step--) {
    e.clear();
    e.push(1);
    e.push(10);
    e.push(10);
    e.add();
    e.sub();
  }

  return e.pop();
}

extern "C" int printf(const char* fmt, ...);

int main() {
  int f = foo();
  int b = bar();
  printf("foo() = %d, bar() = %d\n", f, b);
  return f - b;
}

交给Clang trunk(5.0.0)以 -O2 或 -O3编译,在Linux/x86-64上会看到 foo() 与 bar() 都被优化为:(给GCC以 -O2 / -O3 编译也是一样的结果)

int foo() {
  return -19;
}

int bar() {
  return -19;
}

也就是说整个运算过程都被完全优化掉了。所以如果对它们俩计时的话,肯定要得到一样的结果——几乎不耗时间。如果结果不一样,那都只能算是计时方式的偏差,而不能算是这两种计算方式的性能差异。


但在这么短小的例子里,其实有很多很多有趣的小细节。

例如说,题主原本的逆波兰表达式是:

push 10
push 10
add
push 1
sub

题主可能没发现自己的 EvalSlot<Type>::sub() 函数写错了,所以以为这个序列是正确的。

题主实现的 sub() 如果抽象起来其实是:

  void sub() {
    Type left = pop();
    Type right = pop();
    push(left - right);
  }

而正确的实现应该是先 pop() 出右操作数再 pop() 出左操作数。所以正确的逆波兰表达式应该是这样的序列:

push 1
push 10
push 10
add
sub

也就是我这边修改过的版本所实现的。


其次是题主原本的计时循环中做的计算都可以看作是“无副作用”的——运算出来的结果没有被任何方式感知到。编译器最喜欢这种代码了,一股脑全给彻底优化为空,渣都不剩,连那个常量-19都没必要留下。

以题主的第一个例子为例,如果要至少保留住一次的运算结果,那至少得在计时循环之后使用一次局部变量a,例如说也把a的值在循环后输出一下。这也就是我的修改版代码里要把结果return出去的意图。

但光这样做的话也只足以保留住一次运算的结果,而不足以保留住那个循环——因为循环里的运算完全是循环不变量(loop invariant),编译器可以将它提取到循环外面先算好,然后就会发现循环的内容是空的了,就可以把循环干掉。


再次是请留意本回答开头我给出的 foo() 的代码:

int foo() {
  int step = 10000000;
  int a;
  int b = 1;
  int c = 10;
  while (step--) {
    a = b - (c + c);
  }

  return a;
}

如果改一行,让a带有初值,改为:

int foo() {
  int step = 10000000;
  int a = 0;
  int b = 1;
  int c = 10;
  while (step--) {
    a = b - (c + c);
  }

  return a;
}

然后再交给Clang或者GCC以 -O2 / -O3来编译,就会发现 foo() 里的循环会被保留下来。

例如说 GCC 4.9.2 或者 6.1 以 -O3 来编译后面这个 foo() 会得到:

int foo() {
  int step = 10000001;
  int a = 0;
  while (--step) {
    a = -19;
  }
  return a;
}  

用Clang trunk(5.0.0) 以 -O3 来编译也是相似的结果:

int foo() {
  int step = -10000000;
  while (++step) { }
  return -19;
}

就差一行,这个循环就神奇地被保留下来了。这些编译器都还有待努力啊哈哈。

这里暴露出来的Clang与GCC优化的弱点是个有趣的地方。具体是什么就留给同学们作为课后习题啦。我看我能不能在LLVM修一下它…