Rust能够优化掉循环吗？

Question

我正在进行一些非常简单的基准测试，比较C和Rust的性能。我使用了一个将整数相加的函数1 + 2 + ... + n（我可以通过手动计算来验证），其中n = 10^10。

Rust代码如下：

fn main() {
  let limit: u64 = 10000000000;
  let mut buf: u64 = 0;
  for u64::range(1, limit) |i| {
    buf = buf + i;
  }
  io::println(buf.to_str());
}

以下是C代码：

#include <stdio.h>
int main()
{
  unsigned long long buf = 0;
  for(unsigned long long i = 0; i < 10000000000; ++i) {
    buf = buf + i;
  }
  printf("%llu\n", buf);
  return 0;
}

我编译并运行它们：

$ rustc sum.rs -o sum_rust
$ time ./sum_rust
13106511847580896768

real        6m43.122s
user        6m42.597s
sys 0m0.076s
$ gcc -Wall -std=c99 sum.c -o sum_c
$ time ./sum_c
13106511847580896768

real        1m3.296s
user        1m3.172s
sys         0m0.024s

然后我尝试使用优化标志，同时测试C和Rust：

$ rustc sum.rs -o sum_rust -O
$ time ./sum_rust
13106511847580896768

real        0m0.018s
user        0m0.004s
sys         0m0.012s
$ gcc -Wall -std=c99 sum.c -o sum_c -O9
$ time ./sum_c
13106511847580896768

real        0m16.779s
user        0m16.725s
sys         0m0.008s

这些结果让我感到惊讶。我确实期望优化会产生一些效果，但是经过优化的Rust版本要快100000倍：）。

我尝试改变n（唯一的限制是u64，运行时间仍然几乎为零），甚至尝试了另一个问题（1^5 + 2^5 + 3^5 + ... + n^5），结果相似：使用rustc -O编译的可执行文件比没有标志的文件快几个数量级，并且也比使用gcc -O9编译的同样算法快得多。

那么我的问题是：发生了什么？ :) 我可以理解编译器对1 + 2 + .. + n = (n*n + n)/2进行优化，但我无法想象任何编译器如何推导出1^5 + 2^5 + 3^5 + .. + n^5的公式。另一方面，据我所见，结果必须以某种方式被计算出来（并且似乎是正确的）。

哦，还有：

$ gcc --version
gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3
$ rustc --version
rustc 0.6 (dba9337 2013-05-10 05:52:48 -0700)
host: i686-unknown-linux-gnu

- Jan Špaček

---

只是一个数据点，对于简单的加法，clang 在这里生成 movabsq $-5340232226128654848, %rsi，而对于 i*i*i*i*i 则生成 movabsq $1667352834054815744, %rsi，因此 Rust 消除循环并不那么特别（我有点惊讶 gcc 没有这样做）。 - Daniel Fischer

Answer 1

是的，编译器确实使用1 + ... + n = n*(n+1)/2优化来消除循环，并且对于任何幂次的求和变量都有类似的技巧。例如，k¹是三角数, k²是金字塔数, k³是平方三角数等。一般来说，甚至有一个公式可以计算任意

p次幂的k的总和∑_k k^p。

---

您可以使用更复杂的表达式，以使编译器无法消除循环的任何技巧。例如：

fn main() {
  let limit: u64 = 1000000000;
  let mut buf: u64 = 0;
  for u64::range(1, limit) |i| {
    buf += i + i ^ (i*i);
  }
  io::println(buf.to_str());
}

并且

#include <stdio.h>
int main()
{
  unsigned long long buf = 0;
  for(unsigned long long i = 0; i < 1000000000; ++i) {
    buf += i + i ^ (i * i);
  }
  printf("%llu\n", buf);
  return 0;
}

这给了我

real    0m0.700s
user    0m0.692s
sys     0m0.004s

并且

real    0m0.698s
user    0m0.692s
sys     0m0.000s

分别使用两个编译器（都带有-O选项）。

- huon

---

谢谢，我低估了编译器 :). 但是为什么LLVM包含这样一个特殊的优化呢？ - Jan Špaček