Какие методы оптимизации применяются к коду Rust, который суммирует простую арифметическую последовательность? - PullRequest
Новая
       46

Какие методы оптимизации применяются к коду Rust, который суммирует простую арифметическую последовательность?

0 голосов
/ 24 октября 2018

Код наивный: 

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 компилируется с использованием -O, а код C компилируется с использованием -O3,Код C работает так медленно, что он еще не остановился.

После исправления ошибки, обнаруженной visibleman и Sandeep, обе программы печатали одно и то же число практически мгновенно.Я пытался уменьшить NUM_LOOP на один, результаты казались разумными, учитывая переполнение.Более того, с NUM_LOOP = 1000000000 обе программы не будут переполнены и выдают правильные ответы в кратчайшие сроки.Какие оптимизации используются здесь?Я знаю, что мы можем использовать простые уравнения, такие как (0 + NUM_LOOP - 1) * NUM_LOOP / 2, для вычисления результата, но я не думаю, что такие вычисления выполняются компиляторами в случае переполнения ...

Ответы [ 3 ]

0 голосов
/ 24 октября 2018

Ваш код застрял в бесконечном цикле.

Сравнение i < NUM_LOOP всегда будет возвращать true, поскольку int i обернется до достижения NUM_LOOP

0 голосов
/ 24 октября 2018

Ваш код Rust (без отпечатков и времени) компилируется в ( На Годболт ): 

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. Это прекрасный способ напечатать время практически для всех видов тестов.
0 голосов
/ 24 октября 2018

Поскольку int никогда не может быть таким же большим, как ваш NUM_LOOP, программа будет зацикливаться вечно. 

const uint64_t NUM_LOOP = 18446744073709551615u;

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

Если вы исправите ошибку int, компилятор оптимизирует эти циклы в обоихслучаи.

...