Nove regole per l’accelerazione SIMD del tuo codice Rust (Parte 2)

Nove strategie per ottimizzare il tuo codice Rust utilizzando SIMD (Parte 2)

Lezioni generali sull’aumento dell’ingestione dei dati nel Crate range-set-blaze del 7x

Grazie a Ben Lichtman (B3NNY) al Seattle Rust Meetup per avermi indirizzato nella giusta direzione su SIMD.

Questo è il Parte 2 di un articolo su come creare codice SIMD in Rust. (Vedi Parte 1.) Esamineremo le regole dal 7 al 9:

• 7. Utilizzare il benchmarking di Criterion per scegliere un algoritmo e scoprire che LANES dovrebbe essere (quasi) sempre 32 o 64.
• 8. Integrare il miglior algoritmo SIMD nel tuo progetto con as_simd, codice speciale per i128/u128, e benchmarking aggiuntivo nel contesto.
• 9. Estrarre il miglior algoritmo SIMD dal tuo progetto (per ora) con una feature cargo opzionale.

Ricordiamo le regole dal 1 al 6:

1. Utilizzare Rust nightly e core::simd, il modulo SIMD standard sperimentale di Rust.
2. CCC: Controllare, Controllare e Scegliere le capacità SIMD del tuo computer.
3. Imparare core::simd, ma selettivamente.
4. Brainstorming di algoritmi candidati.
5. Utilizzare Godbolt e AI per comprendere l’assembly del tuo codice, anche se non si conosce il linguaggio assembly.
6. Generalizzare a tutti i tipi e LANES con generici in linea, (e quando ciò non funziona) macro, e (quando ciò non funziona) tratti.

Queste regole sono basate sulla mia esperienza nel cercare di velocizzare range-set-blaze, un crate Rust per la manipolazione di insiemi di interi “simili a grumi”.

• Confronto delle impostazioni del compilatore Rust con Criterion
• Segmentazione dei clienti più che solo clustering
• Quanta dati abbiamo bisogno? Bilanciare l’apprendimento automatico con le considerazioni sulla sicurezza

Ricordiamo che la Regola 6, da Parte 1, mostra come rendere gli algoritmi SIMD di Rust completamente generici per tipo e LANES. Dobbiamo ora scegliere il nostro algoritmo e impostare LANES.

Regola 7: Utilizzare il benchmarking di Criterion per scegliere un algoritmo e scoprire che LANES dovrebbe (quasi) sempre essere 32 o 64.

In questa regola, vedremo come utilizzare il popolare crate criterion per testare le prestazioni ed valutare i nostri algoritmi e opzioni. Nel contesto di range-set-blaze, valuteremo:

• 5 algoritmi – Regular, Splat0, Splat1, Splat2, Rotate
• 3 livelli di estensione SIMD – sse2 (128 bit), avx2 (256 bit), avx512f (512 bit)
• 10 tipi di elementi – i8, u8, i16, u16, i32, u32, i64, u64, isize, usize
• 5 numeri di lane – 4, 8, 16, 32, 64
• 4 lunghezze di input – 1024; 10,240; 102,400; 1,024,000
• 2 CPU – AMD 7950X con avx512f, Intel i5–8250U con avx2

Il benchmark misura il tempo medio per eseguire ogni combinazione. Calcoliamo quindi la velocità di trasferimento in Mbyte/secondo.

Vedi questo nuovo articolo di accompagnamento su come iniziare con Criterion. Quell’articolo mostra anche come spingere (abusare?) Criterion per misurare gli effetti delle impostazioni del compilatore, come il livello di estensione SIMD.

Eseguendo i benchmark si ottiene un file *.csv di 5000 righe che inizia così:

Gruppo,Id,Parametro,Media(ns),StdErr(ns)vector,regolare,avx2,256,i16,16,16,1024,291.47,0.080141vector,regolare,avx2,256,i16,16,16,10240,2821.6,3.3949vector,regolare,avx2,256,i16,16,16,102400,28224,7.8341vector,regolare,avx2,256,i16,16,16,1024000,287220,67.067vector,regolare,avx2,256,i16,16,32,1024,285.89,0.59509...

Questo file è adatto per l’analisi tramite tabelle pivot di fogli di calcolo o strumenti di frame di dati come Polars.

Algoritmi e Lane

Ecco una tabella pivot di Excel che mostra, per ogni algoritmo, la velocità di trasferimento (MByte/sec) vs. le Lane SIMD. La tabella calcola la media della velocità di trasferimento tra diversi livelli di estensione SIMD, tipi di elementi e lunghezza di input.

Sul mio computer desktop AMD:

Su un computer portatile Intel:

Le tabelle mostrano che Splat1 e Splat2 si comportano meglio. Mostrano anche che più Lane sono sempre migliori fino a 32 o 64.

Come può, ad esempio, sse2 (largo 128 bit) elaborare 64 Lane di i64 (largo 4096 bit)? Il modulo core::simd di Rust rende possibile questa magia suddividendo automaticamente ed efficientemente i 4096 bit in 32 blocchi di 128 bit ciascuno. Elaborando insieme i 32 blocchi di 128 bit (apparentemente) si ottengono ottimizzazioni che vanno oltre l’elaborazione indipendente dei blocchi di 128 bit.

Livelli di Estensione SIMD

Impostiamo LANES su 64 e confrontiamo diversi livelli di estensione SIMD sul computer AMD. La tabella calcola la media della velocità di trasferimento tra tipi di elementi e lunghezza di input.

Sul mio computer AMD, utilizzando 64 Lane, sse2 è il più lento. Confrontando avx2 con avx512f, i risultati sono misti. Ancora una volta, gli algoritmi Splat1 e Splat2 si comportano meglio.

Tipi di Elementi

Impostiamo quindi il livello di estensione SIMD su avx512f e confrontiamo diversi tipi di elementi. Manteniamo LANES a 64 e calcoliamo la media della velocità di trasferimento tra diverse lunghezze di input.

Vediamo che gli elementi bit-per-bit, a 32 bit e a 64 bit vengono elaborati più velocemente. (Tuttavia, per elemento, i tipi più piccoli sono più veloci.) Splat1 e Splat2 sono gli algoritmi più veloci, con Splat1 che è leggermento migliore.

Lunghezza dell’input

Infine, impostiamo il nostro tipo di elemento su i32 e vediamo la lunghezza dell’input rispetto alla velocità di trasmissione.

<pvediamo 1="" a="" algoritmi="" altri="" brevi.

Sembra anche che il più breve sia più veloce del più lungo. Questo potrebbe essere il risultato della memorizzazione nella cache o potrebbe essere un artefatto dei benchmark che eliminano i dati non allineati.

Conclusioni del benchmark

Sulla base di questi benchmark, useremo l’algoritmo Splat1. Per ora, impostiamo LANES su 32 o 64, ma vediamo la regola successiva per una complicazione. Infine, consigliamo agli utenti di impostare il livello di estensione SIMD su almeno avx2.

Regola 8: Integra il tuo miglior algoritmo SIMD nel tuo progetto con as_simd, codice speciale per i128/u128 e ulteriori benchmark contestuali.

as_simd

Prima di aggiungere il supporto SIMD, il costruttore principale di RangeSetBlaze era from_iter:

let a = RangeSetBlaze::from_iter([1, 2, 3]);

Tuttavia, le operazioni SIMD funzionano meglio su array che sugli iteratori. Inoltre, costruire un RangeSetBlaze da un array è spesso una cosa naturale da fare, quindi ho aggiunto un nuovo costruttore from_slice:

#[inline]    pub fn from_slice(slice: impl AsRef<[T]>) -> Self {        T::from_slice(slice)    }

Il nuovo costruttore effettua una chiamata in linea al metodo from_slice di ogni intero. Per tutti i tipi interi, ad eccezione di i128/u128, ciò significa effettuare queste chiamate:

let (prefix, middle, suffix) = slice.as_simd();

Il metodo as_simd di Rust converte in modo sicuro e rapido il slice in:

1. un prefix non allineato, che elaboriamo con from_iter, come prima.
2. middle, un array allineato di chunk di struttura Simd
3. Un suffix non allineato, che elaboriamo con from_iter, come prima.

Pensa a middle come a un suddivisione dei nostri interi di input in chunk di dimensione 16 (o qualsiasi dimensione impostata su LANES). Successivamente, iteriamo i chunk attraverso la nostra funzione is_consecutive, cercando sequenze di valori true. Ogni sequenza diventa un singolo intervallo. Ad esempio, una sequenza di 160 interi individuali consecutivi da 1000 a 1159 (inclusi) verrebbe identificata e sostituita con un singolo intervallo di Rust RangeInclusive 1000..=1159. Questo intervallo viene quindi elaborato da from_iter molto più velocemente rispetto a come from_iter avrebbe elaborato i 160 interi individuali. Quando is_consecutive restituisce false, torniamo a elaborare gli interi individuali del chunk con from_iter.

i128/u128

Come gestiamo gli array di tipi che core::simd non gestisce, ovvero i128/u128? Per ora, li elaboro semplicemente con il più lento from_iter.

Benchmark contestuali

Come ultimo passaggio, esegui il benchmark del tuo codice SIMD nel contesto del tuo codice principale, idealmente su dati rappresentativi.

La crate range-set-blaze include già benchmark. Un benchmark misura la performance nell’assorbimento di 1.000.000 di interi con diversi livelli di agglomerazione. La dimensione media dell’agglomerazione varia da 1 (nessuna agglomerazione) a 100.000 agglomerazioni. Eseguiamo quel benchmark con LANES impostato a 4, 8, 16, 32 e 64. Utilizzeremo l’algoritmo Splat1 e il livello di estensione SIMD avx512f.

Per ogni dimensione di agglomerazione, le barre mostrano la velocità relativa nell’assorbimento di 1.000.000 di interi. Per ogni dimensione di agglomerazione, la migliore LANES viene impostata al 100%.

Vediamo che per le agglomerazioni di dimensione 10 e 100, LANES=4 è la migliore. Tuttavia, con le agglomerazioni di dimensione 100.000, LANES=4 è 4 volte peggiore della migliore. All’altro estremo, LANES=64 sembra buono con agglomerazioni di dimensione 100.000, ma è 1,8 e 1,5 volte peggiore della migliore per 100 e 1000, rispettivamente.

Ho deciso di impostare LANES su 16. È il migliore per le agglomerazioni di dimensione 1000. Inoltre, non è mai più di 1,25 volte peggiore della migliore.

Con questa impostazione, possiamo eseguire altri benchmark. Il grafico qui sotto mostra diverse librerie di set di intervalli (inclusa range-set-blaze) che lavorano sullo stesso compito: assorbimento di 1.000.000 di interi con varie agglomerazioni. L’asse y indica i millisecondi, dove meno è meglio.

Con agglomerazioni di dimensione 1000, il metodo esistente RangeSetBlaze::into_iter (rosso) era già 30 volte più veloce rispetto a HashSet (arancione). Notare che la scala è logaritmica. Con avx512f, il nuovo algoritmo RangeSetBlaze::into_slice potenziato da SIMD (azzurro chiaro) è 230 volte più veloce di HashSet. Con sse2 (blu scuro), è 220 volte più veloce. Con avx2 (giallo), è 180 volte più veloce. In confronto a RangeSetBlaze::into_iter, avx512f RangeSetBlaze::into_slice è 7 volte più veloce su questo benchmark.

Dovremmo considerare anche il caso peggiore, ovvero, l’assorbimento di dati senza agglomerazioni. Ho eseguito quel benchmark. Ha mostrato che il metodo esistente RangeSetBlaze::into_iter è circa 2,2 volte più lento di HashSet. Il nuovo RangeSetBlaze::into_slice è 2,4 volte più lento di HashSet.

Quindi, tutto sommato, il nuovo codice SIMD offre un enorme vantaggio per i dati che si presume essere agglomerati. Se l’ipotesi è errata, è più lento, ma non catastroficamente.

Con il codice SIMD integrato nel nostro progetto, siamo pronti per la spedizione, giusto? Sfortunatamente, no. Poiché il nostro codice dipende da Rust nightly, dovremmo renderlo opzionale. Vedremo come fare nella prossima regola.

Regola 9: Estrai il tuo miglior algoritmo SIMD dal tuo progetto (per ora) con una caratteristica cargo opzionale.

Il nostro bellissimo nuovo codice SIMD dipende da Rust nightly, che può e cambia nottetempo. Richiedere agli utenti di dipendere da Rust nightly sarebbe crudele. (Inoltre, sarebbe fastidioso ricevere lamentele quando le cose si rompono.) La soluzione è nascondere il codice SIMD dietro una caratteristica cargo.

Caratteristica, Caratteristica, Caratteristica — Nel contesto del lavoro con SIMD e Rust, la parola “caratteristica” viene utilizzata in tre modi diversi. Primo, “caratteristiche CPU/target” — queste descrivono le capacità di una CPU, inclusa la supporto alle estensioni SIMD. Vedi target-feature e is_x86_feature_detected!. Secondo, “porte delle caratteristiche notturne” — Rust controlla la visibilità delle nuove caratteristiche del linguaggio in Rust notturno con porte delle caratteristiche. Ad esempio, #![feature(portable_simd)]. Terzo, “caratteristiche cargo” — queste permettono a qualsiasi crate o libreria Rust di offrire/limitare l’accesso a parte delle sue capacità. Le vedi nel tuo Cargo.toml quando, ad esempio, aggiungi dipendenza a itertools/use_std.

Ecco i passaggi che la crate range-set-blaze compie per rendere il codice SIMD dipendente da Rust notturno facoltativo:

• In Cargo.toml, definisci una caratteristica di cargo relativa al codice SIMD:

[features]from_slice = []

• Nel file lib.rs, al suo inizio, fai la porta delle caratteristiche notturne portable_simd dipendente dalla caratteristica di cargo from_slice:

#![cfg_attr(feature = "from_slice", feature(portable_simd))]

• Usa l’attributo di compilazione condizionale, ad esempio, #[cfg(feature = "from_slice")], per includere selettivamente il codice SIMD. Ciò include anche i test.

/// Crea un [`RangeSetBlaze`] a partire da una collezione di interi. In genere, è molto/// più veloce di [`from_iter`][1]/[`collect`][1]./// In un benchmark rappresentativo, l'accelerazione è stata di 6×.////// **Attenzione: Richiede il compilatore notturno. Inoltre, devi abilitare la caratteristica `from_slice`/// nel tuo `Cargo.toml`. Ad esempio, con il comando:**/// ```bash///  cargo add range-set-blaze --features "from_slice"/// ```////// **Attenzione**: Compilare con `-C target-cpu=native` ottimizza il binario per l'architettura della CPU attuale,/// il che potrebbe causare problemi di compatibilità su altre macchine con architetture diverse./// Ciò è particolarmente importante per distribuire il binario o eseguirlo in ambienti variabili./// [1]: struct.RangeSetBlaze.html#impl-FromIterator<T>-for-RangeSetBlaze<T>#[cfg(feature = "from_slice")]#[inline]pub fn from_slice(slice: impl AsRef<[T]>) -> Self {    T::from_slice(slice)}

• Come mostrato nella documentazione sopra, aggiungi avvisi e precauzioni alla documentazione.
• Usa --features from_slice per verificare o testare il tuo codice SIMD.

cargo check --features from_slicecargo test --features from_slice

• Usa --all-features per eseguire tutti i test, generare tutta la documentazione e pubblicare tutte le caratteristiche cargo:

cargo test --all-features --doccargo doc --no-deps --all-features --opencargo publish --all-features --dry-run

Conclusioni

Ecco quindi nove regole per aggiungere operazioni SIMD al tuo codice Rust. La facilità di questo processo riflette l’eccellente design della libreria core::simd. Dovresti sempre utilizzare SIMD quando possibile? Alla fine, sì, quando la libreria passerà da Rust notturno a stabile. Per ora, utilizza SIMD quando i suoi vantaggi in termini di prestazioni sono fondamentali, o rendine l’uso opzionale.

Idee per migliorare l’esperienza SIMD in Rust? La qualità di core::simd è già elevata; la principale necessità è quella di stabilizzarla.

Grazie per esserti unito a me in questo percorso nella programmazione SIMD. Spero che se hai un problema adatto a SIMD, questi passaggi ti aiuteranno ad accelerarlo.

Per favore seguite Carl su VoAGI. Scrivo su programmazione scientifica in Rust e Python, apprendimento automatico e statistica. Solitamente scrivo circa un articolo al mese.