Der Versuch, ein berühmtes Beispiel für eine Verzweigungsvorhersage zu erstellen, führt manchmal zu seltsamen Zeiten.

Question

Ich habe versucht, das Beispiel in this famous question zu duplizieren. Mein Code sieht wie folgt aus:

#![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 
} 

Wenn ich Benchmark die genauen Code von oben ich vernünftige Ergebnisse (wie in der verknüpften Frage):

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

Wenn ich jedoch SumType zu u8 beide Versionen ändern laufen gleich schnell und viel schneller Gesamt:

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

Zunächst: natürlich die sum die ganze Zeit überlaufen, aber in Release Modus sind die Überlaufprüfungen von Rust deaktiviert, also berechnen wir einfach ein falsches Ergebnis, ohne in Panik zu geraten. Könnte das der Grund für die überraschend kurze Zeit sein?

Noch seltsamer: wenn ich die Implementierung von calc_sum zu etwas idiomatischen ändern, ändern sich die Ergebnisse wieder. Meine zweite Implementierung:

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

Mit dieser Implementierung die SumType spielt keine Rolle mehr. Mit u8 sowie mit u64 bekomme ich diese Ergebnisse:

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

So haben wir wieder die Zahlen bekommen wir erwarten. Also die Frage ist:

Was ist der Grund für die seltsamen Laufzeiten?

---

PS: I mit cargo bench getestet, die im Freigabemodus kompiliert.

PPS: Ich habe gerade bemerkt, dass in der ersten Implementierung von calc_sum verwende ich into() zum Gießen, während I as in dem zweiten Beispiel. Wenn ich im ersten Beispiel auch as verwende, bekomme ich mehr komische Zahlen. Mit SumType = u64:

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

mit SumType = u8:

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

Answer 1

nahm ich einen kurzen Blick auf die Assembler-Code, und es scheint, dass, wenn Sie SumType = u8 verwenden dann LLVM SSE2 Instruktionen Vektoroperationen zu tun erzeugt, das ist viel schneller. In der Theorie sollte LLVM in der Lage sein, filter(...).fold(...) zu demselben Code zu optimieren, aber in der Praxis kann es nicht immer den Overhead der Abstraktion entfernen. Ich hoffe, wenn MIR hinzugefügt wird, wird sich Rust nicht darauf verlassen, dass LLVM Rust-spezifische Optimierungen durchführt.