Perché il mio codice viene eseguito più lentamente quando rimuovo i controlli sui limiti?

Question

Sto scrivendo una libreria di algebra lineare in Rust.

Ho una funzione per ottenere un riferimento ad una cella di matrice a una data riga e colonna. Questa funzione inizia con un paio di affermazioni che la riga e la colonna sono entro limiti:

#[inline(always)] 
pub fn get(&self, row: usize, col: usize) -> &T { 
    assert!(col < self.num_cols.as_nat()); 
    assert!(row < self.num_rows.as_nat()); 
    unsafe { 
     self.get_unchecked(row, col) 
    } 
} 

In cicli stretti, ho pensato che potrebbe essere più veloce di saltare controllare i limiti, quindi fornire un metodo get_unchecked:

#[inline(always)] 
pub unsafe fn get_unchecked(&self, row: usize, col: usize) -> &T { 
    self.data.get_unchecked(self.row_col_index(row, col)) 
} 

La cosa strana è, quando uso questi metodi per implementare moltiplicazione matriciale (tramite iteratori riga e colonna), miei benchmark mostrano che in realtà va circa 33% più velocemente quando controllare i limiti. Perché sta succedendo?

Ho provato questo su due computer diversi, uno con Linux e l'altro OSX, ed entrambi mostrano l'effetto.

Il codice completo è on github. Il file pertinente è lib.rs. Funzioni di interesse sono:

• get alla riga 68
• get_unchecked alla riga 81
• next alla riga 551
• mul a alla riga 1038

linea 796

matrix_mul (benchmark)

Si noti che sto usando i numeri di tipo a livello di parametrizzare il mio matrici (con l'opzione per le dimensioni dinamiche anche tramite tipi con tag dummy), quindi il benchmark sta moltiplicando due matrici 100x100.

UPDATE:

ho significativamente semplificato il codice, eliminando roba non utilizzati direttamente nel benchmark e la rimozione di parametri generici. Ho anche scritto un'implementazione della moltiplicazione senza l'utilizzo di iteratori, e che la versione non provoca lo stesso effetto. Vedi here per questa versione del codice. La clonazione del ramo minimal-performance e l'esecuzione di cargo bench eseguiranno il benchmark delle due diverse implementazioni di moltiplicazione (si noti che le affermazioni sono commentate per iniziare in quel ramo).

Degna di nota è che se cambio le get* funzioni per restituire copie dei dati invece di riferimenti (f64 invece di &f64), l'effetto scompare (ma il codice è leggermente più lento tutto).

Answer 1

Non è una risposta completa perché non ho testato le mie affermazioni, ma questo potrebbe spiegarlo. In entrambi i casi, l'unico modo per sapere con certezza è generare l'IR LLVM e l'output dell'assembler. Se hai bisogno di un manuale per LLVM IR, puoi trovarlo qui: http://llvm.org/docs/LangRef.html.

In ogni modo, basta parlare di questo.Diciamo che avete questo codice:

#[inline(always)] 
pub unsafe fn get_unchecked(&self, row: usize, col: usize) -> &T { 
    self.data.get_unchecked(self.row_col_index(row, col)) 
} 

Il compilatore qui cambia questo in un carico indiretta, che probabilmente sarà ottimizzato in un loop stretto. È interessante notare che ogni carico ha la possibilità di sbagliare: se i tuoi dati non sono disponibili, attiverà un fuori limite.

Nel caso con il controllo dei limiti combinato con il circuito chiuso, LLVM fa un piccolo trucco. Poiché il carico è in un ciclo stretto (una moltiplicazione di matrice) e poiché il risultato del controllo dei limiti dipende dai limiti del ciclo, rimuoverà il controllo dei limiti dal ciclo e lo inserirà nel ciclo attorno allo. In altre parole, il ciclo stesso rimarrà esattamente lo stesso, ma con un controllo extra bound.

In altre parole, il codice è esattamente lo stesso, con alcune piccole differenze.

Quindi cosa è cambiato? Due cose:

Se abbiamo il controllo dei limiti aggiuntivi, non c'è più possibilità per un carico fuori limite. Questo potrebbe innescare un'ottimizzazione che prima non era possibile. Tuttavia, considerando come questi controlli vengono di solito implementati, questa non sarebbe la mia ipotesi.

1. Un'altra cosa da considerare è che la parola "non sicuro" potrebbe innescare un comportamento, come una condizione aggiuntiva, bloccare i dati o disabilitare il GC, ecc. Non sono sicuro di questo comportamento esatto in Rust; l'unico modo per scoprire questi dettagli è quello di guardare il LLVM IR.