Почему эта программа Rust настолько медленная? Я что-то пропустил?

Question

Я прочитал Minimal distance in Manhattan metric и переписал авторскую «наивную» реализацию в Rust. C++ вариант:

#include <utility> 
#include <cstdio> 
#include <cstdlib> 

std::pair<int, int> pointsA[1000001]; 
std::pair<int, int> pointsB[1000001]; 

int main() { 
    int n, t; 
    unsigned long long dist; 

    scanf("%d", &t); 

    while(t-->0) { 
     dist = 4000000000LL; 
     scanf("%d", &n); 

     for(int i = 0; i < n; i++) { 
      scanf("%d%d", &pointsA[i].first, &pointsA[i].second); 
     } 

     for(int i = 0; i < n; i++) { 
      scanf("%d%d", &pointsB[i].first, &pointsB[i].second); 
     } 

     for(int i = 0; i < n ;i++) { 
      for(int j = 0; j < n ; j++) { 
       if(abs(pointsA[i].first - pointsB[j].first) + abs(pointsA[i].second - pointsB[j].second) < dist) 
        dist = abs(pointsA[i].first - pointsB[j].first) + abs(pointsA[i].second - pointsB[j].second); 
      } 
     } 
     printf("%lld\n", dist); 
    } 
} 

Вариант Ржавчина:

use std::io; 
use std::io::BufReader; 
use std::io::BufRead; 

fn read_array(stdin: &mut BufReader<io::Stdin>, array_len: usize, points: &mut Vec<(i32, i32)>) { 
    let mut line = String::new(); 
    for _ in 0..array_len { 
     line.clear(); 
     stdin.read_line(&mut line).unwrap(); 
     let mut item = line.split_whitespace(); 
     let x = item.next().unwrap().parse().unwrap(); 
     let y = item.next().unwrap().parse().unwrap(); 
     points.push((x, y)); 
    } 
} 

fn manhattan_dist(a: &(i32, i32), b: &(i32, i32)) -> u32 { 
    ((a.0 - b.0).abs() + (a.1 - b.1).abs()) as u32 
} 

fn main() { 
    let mut line = String::new(); 
    let mut stdin = BufReader::new(io::stdin()); 
    stdin.read_line(&mut line).unwrap(); 
    let n_iters = line.trim_right().parse::<usize>().unwrap(); 
    let mut points_a = Vec::with_capacity(10000); 
    let mut points_b = Vec::with_capacity(10000); 
    for _ in 0..n_iters { 
     line.clear(); 
     stdin.read_line(&mut line).unwrap(); 
     let set_len = line.trim_right().parse::<usize>().unwrap(); 
     points_a.clear(); 
     points_b.clear(); 
     read_array(&mut stdin, set_len, &mut points_a); 
     read_array(&mut stdin, set_len, &mut points_b); 
     let mut dist = u32::max_value(); 
     for i in points_a.iter() { 
      for j in points_b.iter() { 
       dist = std::cmp::min(manhattan_dist(i, j), dist); 
      } 
     } 
     println!("{}", dist); 
    } 
} 

Затем я сгенерировал данные при помощи сценария Python:

import random 

ITER = 100 
N = 10000 
MAX_INT = 1000000 

print("%d" % ITER) 

for _ in range(0, ITER): 
    print("%d" % N) 
    for _ in range(0, N): 
     print(random.randrange(-MAX_INT, MAX_INT + 1), random.randrange(1, MAX_INT + 1)) 
    for _ in range(0, N): 
     print(random.randrange(-MAX_INT, MAX_INT + 1), random.randrange(-MAX_INT, 0)) 

И скомпилирован оба варианта с g++ -Ofast -march=native и rustc -C opt-level=3 соответственно , Тайминги являются:

C++

real 0m7.789s 
user 0m7.760s 
sys  0m0.020s 

Rust

real 0m28.589s 
user 0m28.570s 
sys  0m0.010s 

Почему мой Rust код в четыре раза медленнее, чем вариант C++? Я использую Rust 1.12.0-beta.1.

Я добавил измерения времени:

let now = SystemTime::now(); 
line.clear(); 
stdin.read_line(&mut line).unwrap(); 
let set_len = line.trim_right().parse::<usize>().unwrap(); 
points_a.clear(); 
points_b.clear(); 
read_array(&mut stdin, set_len, &mut points_a); 
read_array(&mut stdin, set_len, &mut points_b); 
io_time += now.elapsed().unwrap(); 

let now = SystemTime::now(); 
let mut dist = u32::max_value(); 
for i in points_a.iter() { 
    for j in points_b.iter() { 
     dist = std::cmp::min(manhattan_dist(i, j), dist); 
    } 
} 
calc_time += now.elapsed().unwrap(); 

И writeln!(&mut std::io::stderr(), "io_time: {}, calc_time: {}", io_time.as_secs(), calc_time.as_secs()).unwrap(); отпечатки io_time: 0, calc_time: 27.

Я попробовал каждую ночь rustc 1.13.0-nightly (e9bc1bac8 2016-08-24):

$ time ./test_rust <data.txt> test3_res 
io_time: 0, calc_time: 19 

real 0m19.592s 
user 0m19.560s 
sys  0m0.020s 
$ time ./test1 <data.txt> test1_res 

real 0m7.797s 
user 0m7.780s 
sys  0m0.010s 

Так что на сейчас ~ разность 2.7x на моем Core i7.

Answer 1

Разница конечно -march=native ... вид. У Rust есть это до -C target_cpu=native, но это не дает того же преимущества скорости. Это связано с тем, что LLVM не желает вставлять в этот контекст, в то время как GCC делает. Вы можете отметить, что используя Clang, компилятор C++, который также использует LLVM, также производит относительно медленный код.

Чтобы стимулировать LLVM к векторизации, вы можете переместить основной цикл в отдельную функцию. Кроме того, вы можете использовать локальный блок. Если вы пишете код внимательно, как

let dist = { 
    let mut dist = i32::max_value(); 
    for &(a, b) in &points_a[..n] { 
     for &(c, d) in &points_b[..n] { 
      dist = std::cmp::min(((a - c).abs() + (b - d).abs()), dist); 
     } 
    } 
    dist 
} as u32; 

разницу между Rust и C++ является то почти ничтожна (~ 4%).

Answer 2

Я определенно не вижу разницы во времени выполнения. На моей машине,

C++:

real 0m19.672s 
user 0m19.636s 
sys  0m0.060s 

Ржавчина:

real 0m19.047s 
user 0m19.028s 
sys  0m0.040s 

Я скомпилировал код Rust с rustc -O test.rs -o ./test и кодом C++ с g++ -Ofast test.cpp -o test.

Я запускаю Ubuntu 16.04 с ядром Linux 4.6.3-040603-generic. На ноутбуке, на котором я работал, есть процессор Intel Core i5-6200U и 8 ГБ оперативной памяти, ничего особенного.

Answer 3

Подавляющее большинство характеристик, которые вы видите на C++, связано с флагом -march=native.

Этот флаг не является эквивалентным флагом для Rust's --release. Он использует инструкции процессора, специфичные для процессора, на котором он скомпилирован, поэтому математика в частности будет способ быстрее.

Снятие этого флага ставит код C++ на 19 секунд.

Тогда в коде на C++ присутствует небезопасная информация. Ни один вход не установлен.Код Rust делает это проверить, вы используете .unwrap() - unwrap имеет стоимость исполнения, есть утверждение, то код, необходимый для размотки и т.д.

Использование if let сек вместо сырых unwrap с, или игнорировать результаты, где это возможно, приносит код ржавчины снова падает.

Ржавчина: 22 секунды

С ++: 19 секунд

Где в 3 секунды приходят? Немного поиграть заставляет меня поверить, что это println! против printf, но у меня нет жестких номеров для кода на C++. Я могу сказать, что код Rust падает до 13 секунд, когда я выполняю печать за пределами теста.

TLDR: Ваши флаги вашего компилятора различны, а ваш код на C++ небезопасен.