L'esecuzione del famoso esempio di previsione delle diramazioni a volte provoca tempi strani

Question

Ho provato a duplicare l'esempio in this famous question. Il mio codice è simile al seguente:

#![feature(test)] 
extern crate rand; 
extern crate test; 

use test::Bencher; 
use rand::{thread_rng, Rng}; 

type ItemType = u8; 
type SumType = u64; 
const TEST_SIZE: usize = 32_768; 

#[bench] 
fn bench_train(b: &mut Bencher) { 
    let numbers = get_random_vec(); 
    b.iter(|| calc_sum(&numbers)); 
} 

#[bench] 
fn bench_train_sort(b: &mut Bencher) { 
    let mut numbers = get_random_vec(); 
    numbers.sort();  // <-- the magic difference 
    b.iter(|| calc_sum(&numbers)); 
} 

fn get_random_vec() -> Vec<ItemType> { 
    thread_rng().gen_iter().take(TEST_SIZE).collect() 
} 

fn calc_sum(numbers: &Vec<ItemType>) -> SumType { 
    let mut sum = 0; 
    for &num in numbers { 
     if num < ItemType::max_value()/2 { 
      sum += num.into(); 
     } 
    } 

    sum 
} 

Se io punto di riferimento il codice esatto dall'alto ottengo risultati ragionevoli (come per la questione legata):

test bench_train  ... bench:  148,611 ns/iter (+/- 8,445) 
test bench_train_sort ... bench:  21,064 ns/iter (+/- 1,980) 

Tuttavia, se cambio SumType a u8 entrambe le versioni correre altrettanto veloce e molto più velocemente:

test bench_train  ... bench:  1,272 ns/iter (+/- 64) 
test bench_train_sort ... bench:  1,280 ns/iter (+/- 170) 

Innanzitutto: naturalmente, il sum traboccherà tutto il tempo, ma in rilascio modalità i controlli di overflow di Rust sono disabilitati, quindi calcoliamo semplicemente un risultato errato senza panico. Potrebbe essere questo il motivo per il tempo sorprendentemente breve?

Ancora più strano: quando cambio l'implementazione di calc_sum in qualcosa di più idiomatico, i risultati cambiano di nuovo. La mia seconda implementazione:

fn calc_sum(numbers: &Vec<ItemType>) -> SumType { 
    numbers.iter() 
     .filter(|&&num| num < ItemType::max_value()/2) 
     .fold(0, |acc, &num| acc + (num as SumType)) 
} 

Con questa implementazione il SumType non importa più. Con u8 così come con u64 ottengo questi risultati:

test bench_train  ... bench:  144,411 ns/iter (+/- 12,533) 
test bench_train_sort ... bench:  16,966 ns/iter (+/- 1,100) 

Così abbiamo ancora ottenere i numeri ci aspettiamo. Quindi la domanda è:

Qual è il motivo degli strani tempi di corsa?

---

PS: ho provato con cargo bench che compila nella modalità di rilascio.

PPS: Ho appena notato che nella prima implementazione del calc_sum utilizzo into() per colata, mentre io uso as nel secondo esempio. Quando si utilizza anche as nel primo esempio, ottengo numeri più strani. Con SumType = u64:

test bench_train  ... bench:  39,850 ns/iter (+/- 2,355) 
test bench_train_sort ... bench:  39,344 ns/iter (+/- 2,581) 

Con SumType = u8:

test bench_train  ... bench:  1,184 ns/iter (+/- 339) 
test bench_train_sort ... bench:  1,239 ns/iter (+/- 85) 

Answer 1

Ho dato un'occhiata veloce al codice assembler, e sembra che se si utilizza SumType = u8 poi LLVM genera le istruzioni SSE2 per fare operazioni vettoriali, che è più veloce. In teoria, LLVM dovrebbe essere in grado di ottimizzare lo filter(...).fold(...) con lo stesso codice, ma in pratica non può sempre rimuovere il sovraccarico dell'astrazione. Spero che quando verrà aggiunto MIR, Rust non si affidi a LLVM per eseguire ottimizzazioni specifiche di Ruggine.