ps4 - rust traduccion

¿Por qué este programa Rust es tan lento? ¿Me he perdido algo?

Question

Leí la métrica Distancia mínima en Manhattan y reescribí la implementación "ingenua" del autor en Rust . La variante de C ++ es:

#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);
    }
}

La variante de Rust es:

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);
    }
}

Luego, generé datos con un script de 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))

Y compiló ambas variantes con g++ -Ofast -march=native y rustc -C opt-level=3 respectivamente. Los horarios son:

C ++

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

Moho

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

¿Por qué mi código Rust es cuatro veces más lento que la variante de C ++? Estoy usando Rust 1.12.0-beta.1.

Agregué medidas de tiempo:

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();

Y writeln!(&mut std::io::stderr(), "io_time: {}, calc_time: {}", io_time.as_secs(), calc_time.as_secs()).unwrap(); imprime io_time: 0, calc_time: 27 .

rustc 1.13.0-nightly (e9bc1bac8 2016-08-24) todas las 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

Así que ahora hay una diferencia de ~ 2.7x en mi Core i7 .

Answer 1

Definitivamente no estoy viendo ninguna diferencia en el tiempo de ejecución. En mi máquina,

C ++:

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

Moho:

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

rustc -O test.rs -o ./test código Rust con rustc -O test.rs -o ./test y el código C ++ con g++ -Ofast test.cpp -o test .

Estoy ejecutando Ubuntu 16.04 con Linux Kernel 4.6.3-040603-generic. La computadora portátil en la que ejecuté esto tiene una CPU Intel (R) Core (TM) i5-6200U y 8 GB de RAM, nada especial.

Answer 2

La diferencia es, por supuesto, -march=native ... algo así. El óxido tiene esto a través de -C target_cpu=native , pero esto no da el mismo beneficio de velocidad. Esto se debe a que LLVM no está dispuesto a vectorizarse en este contexto, mientras que GCC hace. Puede observar que el uso de Clang , un compilador de C ++ que también utiliza LLVM, también produce un código relativamente lento.

Para alentar a LLVM a vectorizar, puede mover el bucle principal a una función separada. Alternativamente, puede utilizar un bloque local. Si escribes el código cuidadosamente como

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;

la diferencia entre Rust y C ++ es entonces casi insignificante (~ 4%).

Answer 3

La gran mayoría del rendimiento que se ve en C ++ se debe a la -march=native .

Esta bandera no es la bandera equivalente a la --release de Rust. Utiliza instrucciones de la CPU específicas de la CPU en la que se compila, por lo que las matemáticas en particular serán mucho más rápidas.

Al quitar ese indicador, el código C ++ se coloca en 19 segundos.

Luego está la inseguridad presente en el código C ++. Ninguna de las entradas está marcada. El código Rust sí lo comprueba, usted usa .unwrap() : el .unwrap() unwrap tiene un costo de rendimiento, hay una aserción, luego el código necesario para desenrollar, etc.

if let usa if let lugar de raw unwrap s, o se ignoran los resultados cuando sea posible, se vuelve a bajar el código Rust.

Roya: 22 segundos.

C ++: 19 segundos

¿De dónde vienen los 3 segundos? ¡Un poco de juego me lleva a creer que está println! vs printf , pero no tengo números para el código C ++. Lo que puedo decir es que el código de Rust se reduce a 13 segundos cuando realizo la impresión fuera del punto de referencia.

TLDR: Las banderas de su compilador son diferentes y su código C ++ no es seguro.