4

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
4

1 に答える 1

8

はい、コンパイラは1 + ... + n = n*(n+1)/2最適化を使用してループを削除します。また、合計変数の累乗に対しても同様のトリックがあります。たとえば、 k 1は三角数、k 2は角錐数、k 3は 2 乗三角数などです。一般に、任意のpに対して∑<sub> 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両方のコンパイラで）。

于 2013-06-01T00:07:49.157 に答える