Warum ist der Zugriff auf ein Element eines großen Vektors von Strukturen im Debug-Modus langsamer als der Zugriff auf ein kleiner?

Question

Wenn ich diesen Code ausführen:

#[derive(Copy, Clone)] 
pub struct Element { 
    pub key: u64, 
} 

pub fn test1(u: usize) { 
    let now = std::time::SystemTime::now(); 

    let tt = vec![Element { key: 0 }; u]; 
    for _ in 0..10000000 as u64 { 
     if tt[155].key == 893472348628 {} 
    } 

    match now.elapsed() { 
     Ok(elapsed) => { 
      println!(
       "With struct, size of vec={}: Time elapsed: {}.{} seconds", 
       u, 
       elapsed.as_secs(), 
       elapsed.subsec_nanos() 
      ); 
     } 
     Err(e) => { 
      println!("Error: {:?}", e); 
      panic!(); 
     } 
    } 
} 

pub fn test2(u: usize) { 
    let now = std::time::SystemTime::now(); 

    let tt = vec![0u64; u]; 
    for _ in 0..10000000 as u64 { 
     if tt[155] == 893472348628 {} 
    } 

    match now.elapsed() { 
     Ok(elapsed) => { 
      println!(
       "With u64, size of vec={}: Time elapsed: {}.{} seconds", 
       u, 
       elapsed.as_secs(), 
       elapsed.subsec_nanos() 
      ); 
     } 
     Err(e) => { 
      println!("Error: {:?}", e); 
      panic!(); 
     } 
    } 
} 

fn main() { 
    test1(100000); 
    test1(100000000); 
    test2(100000); 
    test2(100000000); 
} 

ich diese Ergebnisse:

With struct, size of vec=100000: Time elapsed: 1.268881822 seconds 
With struct, size of vec=100000000: Time elapsed: 12.470818140 seconds 
With u64, size of vec=100000: Time elapsed: 1.171180429 seconds 
With u64, size of vec=100000000: Time elapsed: 1.230393828 seconds 

Ich sehe keinen Grund, warum der zweite Funktionsaufruf 10-mal langsamer als die ersten sein soll. Ich habe es in Debug-Modus kompilieren seit Release-Modus diese Zeilen ignoriert:

if tt[155].key == 893472348628 {} 

Ich habe eine 64-Bit-Linux-Rechner mit 8 GB RAM, vielleicht hat es etwas damit zu tun?

Answer 1

Es wird nicht auf das Element zugegriffen, das Zeit braucht, sondern den Vektor initialisiert. Tatsächlich mit Ihrem Beispiel erhalte ich:

With struct, size of vec=100000: Time elapsed: 0.594704815 seconds 
With struct, size of vec=100000000: Time elapsed: 5.789152687 seconds 
With u64, size of vec=100000: Time elapsed: 0.584137362 seconds 
With u64, size of vec=100000000: Time elapsed: 0.586343084 seconds 

Wenn ich initialisieren now nach tt ich folgendes:

With struct, size of vec=100000: Time elapsed: 0.589499628 seconds 
With struct, size of vec=100000000: Time elapsed: 0.583244899 seconds 
With u64, size of vec=100000: Time elapsed: 0.584675666 seconds 
With u64, size of vec=100000000: Time elapsed: 0.583518382 seconds 

Initialisierung des Vektors nimmt die lineare Zeit, da jedes Element zu 0 initialisiert werden muss (oder Element { key: 0 }).

Warum ist es schneller mit 0 als , schauen wir uns an, wie vec! funktioniert. We can see it just calls vec::from_elem, die wiederum just calls <T as SpecFromElem>::from_elem. Was ist das für ein Merkmal? Nun, seine Default-Implementierung im Grunde wie folgt aussieht:

let mut v = Vec::with_capacity(n); 
v.extend_with(n, ExtendElement(elem)); 

Aber es gibt auch eine bunch of special cases darunter einen für 0u64! Dieser verwendet RawVec::with_capacity_zeroed(n). Zweifellos ist dieser spezielle Fall, wo die Geschwindigkeit herkommt.