对简单算术序列求和的 Rust 代码应用了哪些优化技术？

Question

代码很幼稚：

use std::time;

fn main() {
    const NUM_LOOP: u64 = std::u64::MAX;
    let mut sum = 0u64;
    let now = time::Instant::now();
    for i in 0..NUM_LOOP {
        sum += i;
    }
    let d = now.elapsed();
    println!("{}", sum);
    println!("loop: {}.{:09}s", d.as_secs(), d.subsec_nanos());
}

输出为：

$ ./test.rs.out
9223372036854775809
loop: 0.000000060s
$ ./test.rs.out
9223372036854775809
loop: 0.000000052s
$ ./test.rs.out
9223372036854775809
loop: 0.000000045s
$ ./test.rs.out
9223372036854775809
loop: 0.000000041s
$ ./test.rs.out
9223372036854775809
loop: 0.000000046s
$ ./test.rs.out
9223372036854775809
loop: 0.000000047s
$ ./test.rs.out
9223372036854775809
loop: 0.000000045s

节目马上就要结束了。我还使用 for 循环在 C 中编写了等效代码，但它运行了很长时间。我想知道是什么让 Rust 代码如此之快。

C代码：

#include <stdint.h>
#include <time.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

double time_elapse(struct timespec start) {
    struct timespec now;
    clock_gettime(CLOCK_MONOTONIC, &now);
    return now.tv_sec - start.tv_sec +
           (now.tv_nsec - start.tv_nsec) / 1000000000.;
}

int main() {
    const uint64_t NUM_LOOP = 18446744073709551615u;
    uint64_t sum = 0;
    struct timespec now;
    clock_gettime(CLOCK_MONOTONIC, &now);

    for (int i = 0; i < NUM_LOOP; ++i) {
        sum += i;
    }

    double t = time_elapse(now);
    printf("value of sum is: %llu\n", sum);
    printf("time elapse is: %lf sec\n", t);

    return 0;
}

Rust 代码使用 -O 编译，C 代码使用 -O3 编译。 C代码运行慢到还没停

修复 visibleman 和 Sandeep 发现的错误后，两个程序几乎立即打印出相同的数字。我试图将 NUM_LOOP 减一，考虑到溢出，结果似乎是合理的。此外，使用 NUM_LOOP = 1000000000，两个程序都不会溢出并立即产生正确答案。这里使用了哪些优化？我知道我们可以使用像 (0 + NUM_LOOP - 1) * NUM_LOOP / 2 这样的简单方程来计算结果，但我不认为这种计算是由编译器在溢出情况下完成的...

Answer 1

因为 int 永远不可能和你的 NUM_LOOP 一样大，程序将无限循环。

const uint64_t NUM_LOOP = 18446744073709551615u;

for (int i = 0; i < NUM_LOOP; ++i) { // Change this to an uint64_t

如果您修复了 int 错误，编译器将在这两种情况下优化掉这些循环。

Answer 2

您的代码陷入了死循环。

比较 i < NUM_LOOP 将始终 return 为真，因为 int i 会在到达 NUM_LOOP

之前环绕

Answer 3

您的 Rust 代码（没有打印和计时）编译为 (On Godbolt):

movabs rax, -9223372036854775807
ret

LLVM 只是对整个函数进行常量折叠并为您计算最终值。

让我们将上限设为动态（非常数）以避免这种激进的常数折叠：

pub fn foo(num: u64) -> u64 {
    let mut sum = 0u64;
    for i in 0..num {
        sum += i;
    }

    sum
}

这导致 (Godbolt):

  test rdi, rdi            ; if num == 0
  je .LBB0_1               ; jump to .LBB0_1
  lea rax, [rdi - 1]       ; sum = num - 1
  lea rcx, [rdi - 2]       ; rcx = num - 2
  mul rcx                  ; sum = sum * rcx
  shld rdx, rax, 63        ; rdx = sum / 2
  lea rax, [rdx + rdi]     ; sum = rdx + num
  add rax, -1              ; sum -= 1
  ret
.LBB0_1:
  xor eax, eax             ; sum = 0
  ret

如您所见，优化器了解您对从 0 到 num 的所有数字求和，并用常量公式替换循环：((num - 1) * (num - 2)) / 2 + num - 1。至于上面的例子，优化器大概是先把代码优化成这个常量公式，然后再做常量折叠。

补充说明

其他两个答案已经指出了您在 C 程序中的错误。修复后，clang generates exactly the same assembly (unsurprisingly). However, GCC doesn't seem to know about this optimization and generates pretty much the assembly you would expect (a loop).
在 Rust 中，一种更简单、更惯用的代码编写方式是 (0..num).sum()。尽管使用了更多的抽象层（即迭代器），编译器生成的代码与上面完全相同。
要在 Rust 中打印 Duration，您可以使用 {:?} 格式说明符。 println!("{:.2?}", d); 以最合适的单位打印持续时间，精度为 2。这是打印几乎所有类型基准测试时间的好方法。

对简单算术序列求和的 Rust 代码应用了哪些优化技术？

What optimization techniques are applied to Rust code that sums up a simple arithmetic sequence?

c

rust

llvm-codegen

补充说明