什么优化技术应用于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

该计划几乎立即结束.我还在C中使用for循环编写了一个等效代码,但它运行了很长时间.我想知道是什么让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代码并使用编译-OC代码-O3.C代码运行速度很慢,尚未停止.

在修复了visibleman和Sandeep发现的bug后,两个程序几乎立即打印了相同的数字.我试图减少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 bug,编译器将在两种情况下优化掉这些循环.

Answer 2

你的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 生成完全相同的程序集(不出所料).但是,GCC似乎并不了解这种优化,并且几乎可以生成您期望的组件(循环).
• 在Rust中,编写代码的方式更简单,更惯用(0..num).sum().尽管使用了更多层的抽象(即迭代器),编译器生成的代码与上面完全相同.
• 要Duration在Rust中打印,可以使用{:?}格式说明符.println!("{:.2?}", d);在最合适的单位打印持续时间,精度为2.这是打印几乎所有类型基准测试时间的好方法.

Answer 3

你的代码陷入无限循环.

比较i < NUM_LOOP将始终返回true,因为int i将在到达之前回绕NUM_LOOP