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

问题描述

问题解决，其实是神奇的 -O2 优化~

有如下代码，执行一个简单的表达式 a = b - (c+c);

   int64_t start = currentTimeMicro();

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

    int64_t end = currentTimeMicro();

    std::cout << "elapsed: " << (end-start) << "us";

循环执行 10000000 耗时 6505 微秒，大概为 6 毫秒。

然后我设计了一个静态数组实现的计算栈，模拟逆波兰表达式的运算

template<typename Type>
class EvalSlot
{
public:

    enum {
        Size = 8
    };

    inline void add(){
        mData[index-1] = mData[index] + mData[index-1];
        --index;
    }

    inline void sub() {
        mData[index-1] = mData[index] - mData[index-1];
        --index;
    }

    inline void push(const Type& value) {
        mData[++index] = value;
    }

    inline void clear() {
        index = -1;
    }

protected:
    int index = -1;
    Type mData[Size] = {0};
};

测试代码如下

   int64_t start = currentTimeMicro();

    EvalSlot<int> e;

    int step = 10000000;

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

    int64_t end = currentTimeMicro();

    std::cout << "top: " << e.top() << std::endl;

    qDebug() << "elapsed: " << (end-start) << "us";

也是同样运行10000000 次，耗时竟然是 0 微秒，可能是系统的测时精度的问题，但是应该是低于 1 毫秒的。

这是为何？

a = b - (c + c);   // 耗时多于下面的函数调用？

e.clear();
e.push(10);
e.push(10);
e.add();
e.push(1);
e.sub();

如果是内联函数的展开，那么展开后的逆波兰表达式的栈操作的指令应该也是多于表达式的指令吧。

编译配置和环境

Using QtTest library 5.7.0, Qt 5.7.0 (i386-little_endian-ilp32 shared (dynamic) release build; by GCC 5.3.0)

currentTimeMicro 的实现如下：

#include <sys/time.h>

static int64_t currentTimeMicro() {
   struct timeval tv;
   gettimeofday(&tv, nullptr);
   return (int64_t)(tv.tv_sec )* 1000 * 1000 + tv.tv_usec ;
}

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

俺来打个酱油说几点。

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

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修一下它…