Dove ottimizzi?

Dovresti ignorare le piccole efficienze il 95% delle volte. Per prima cosa, fallo funzionare correttamente , quindi analizza ...

Il tuo design.

La scelta degli algoritmi di alto livello può avere un enorme impatto sulle prestazioni complessive del software, al punto che una scelta apparentemente banale può significare la differenza tra l'attesa di 20 minuti per l'avvio del programma e la disponibilità rapida e reattiva UI.

Ad esempio, in un gioco 3D: se inizi con una semplice lista di oggetti per il tuo grafico di scena, vedrai prestazioni estremamente scadenti per un numero relativamente piccolo di oggetti; ma se invece implementi una gerarchia di volume (come un octree o BVH) e parti di albero che si selezionano durante il disegno, vedrai un notevole incremento delle prestazioni.

Quando il tuo design sembra corretto, puoi passare a ...

Logica di basso livello.

Gli algoritmi di livello inferiore possono anche avere un impatto significativo. Quando si esegue l'elaborazione delle immagini, ad esempio, se si legge l'immagine nell'ordine sbagliato, si verificheranno massicci rallentamenti durante l'esecuzione di costanti mancanze della cache L2; riordinare le tue operazioni potrebbe significare un aumento di dieci volte delle prestazioni.

A questo punto, cerca il profilo e trova il posto dove viene speso la maggior parte del tempo del programma e trova un modo per eliminarlo.

Per prima cosa, esegui un profiler per scoprire dove il tuo codice impiega il suo tempo.

Quindi, guarda quei luoghi per vedere quali sono facili da ottimizzare.

Cerca le correzioni più semplici che ti consentiranno di ottenere i maggiori guadagni (vai per il frutto a bassa attaccatura). Non preoccuparti troppo di quanto sia importante, precisamente. Se è facile, aggiustalo. Si sommerà. 25 correzioni semplici potrebbero essere più veloci di 1 correzione grande e i loro effetti cumulativi potrebbero essere maggiori. Se è difficile, fai una nota o file una segnalazione di bug in modo da poter dare la priorità in seguito. Non preoccuparti tanto di "grande" o "piccolo" a questo punto - fallo e basta, finché non arrivi a funzioni che usano pochissimo tempo. Una volta fatto ciò, dovresti avere una migliore idea di quali degli altri problemi che hai scoperto potrebbero ottenere le maggiori vittorie per il minimo investimento.

Non dimenticare di eseguire il profiling dopo le correzioni come una sorta di test di regressione per verificare che le modifiche alle tue prestazioni avessero gli effetti sperati. Inoltre, non dimenticare di eseguire la suite di regressione, per garantire che nessuna funzionalità sia stata interrotta. A volte le cattive prestazioni indicano un aggiramento e provare a correggere le prestazioni interromperà la funzionalità.

Piccole funzioni che non possono essere ottimizzate ma che impiegano molto tempo potrebbero ancora essere suggerimenti su dove ottimizzare. Perché questa funzione viene chiamata così tanto? Esiste una funzione che chiama quella piccola funzione che non ha bisogno di usarla così tanto? Il lavoro viene duplicato o si svolgono lavori non necessari? Cerca lo stack per le volte che viene chiamato fino a quando non sei sicuro che dovrebbe essere chiamato così spesso, e vedi se trovi una funzione più grande con un algoritmo inefficiente.

Modificato per aggiungere: Poiché si dispone di una funzionalità specifica che richiede molto tempo, provare a eseguire i passaggi precedenti con solo la funzione specifica da eseguire circa 10 volte.

È difficile da dire. Questo dipende molto da cosa sta facendo il codice. Esegui un test delle prestazioni, ottieni un profilo delle prestazioni e guarda e vedi quanto tempo effettivo viene speso in varie aree. Le vostre generalizzazioni sono ... generalizzazioni e variano da progetto a progetto.

Ad esempio, il codice che viene chiamato il più potrebbe semplicemente accedere a un file o console. Non ha molto senso ottimizzare che se è già una o due righe di codice che non possono essere rese più semplici, e potrebbe essere che qualsiasi sforzo per ottimizzare qualcosa del genere potrebbe non valere il costo di codificarlo effettivamente. Il codice meno chiamato potrebbe essere una query di dimensioni mostruose usata in una funzione orribilmente complessa. La funzione potrebbe essere richiamata 100 volte su un'intera esecuzione (rispetto a 10000 per la semplice dichiarazione di registrazione), ma se impiegano 20 secondi per ogni ora di chiamata, forse che dovrebbe iniziare l'ottimizzazione ? Oppure potrebbe essere il contrario, con la query di grandi dimensioni la più chiamata e l'istruzione di registrazione chiamata solo una per ogni 100 query ...

Di solito non mi preoccupo di questo genere di cose (finché non ho bisogno di fare il tuning delle prestazioni) a meno che non abbia qualche idea in anticipo su cosa succederà.

Bene, "noi" di solito non ottimizziamo fino a quando non c'è un'ovvia necessità di ottimizzazione quando qualcosa è inaccettabilmente lento.

E quando questa necessità si manifesta di solito porta con sé buoni suggerimenti su ciò che esattamente richiede l'ottimizzazione.

Quindi la risposta è normale: "Dipende".

Dovresti utilizzare un profiler su una manciata di run tipiche e guardare la spesa tempo totale in ogni parte del codice, indipendentemente da come o quanto spesso ci sei arrivato. L'ottimizzazione di queste parti dovrebbe sempre dare un aumento di velocità.

A seconda di come è basso il linguaggio di implementazione, dovresti anche scoprire quali parti causano la maggior parte dei problemi di cache. Il consolidamento del codice chiamante ti aiuterà qui.

Il problema è la frase "dove viene speso il maggior tempo" è ambiguo.

Se significa "dove si trova il contatore del programma più spesso", ho visto programmi in cui è stata impiegata la maggior parte del tempo in funzioni di confronto tra stringhe, allocazione di memoria e librerie matematiche. In altre parole, funzioni che il programmatore quotidiano non dovrebbe mai toccare.

Se significa "dove nel codice del programmatore sono eseguite le istruzioni che consumano una grande quantità di tempo" è un concetto più utile.

Il problema con il concetto di "codice che è chiamato il più" è, la quantità di tempo che impiega è il prodotto di quanto spesso viene chiamato e quanto tempo ci vuole per chiamata (compresi i callei e I / O) . Poiché la quantità di tempo che impiega può variare su diversi ordini di grandezza, il numero di volte che viene chiamato non ti dice quanto sia un problema. La funzione A può essere chiamata 10 volte e impiega 0,1 secondi, mentre la funzione B può essere chiamata 1000 volte e richiede un microsecondo.

Una cosa che ti ti dirà dove cercare è questa: ogni volta che una linea di codice sta causando il tempo che deve essere speso è nello stack . Quindi, ad esempio, se una linea di codice è un hot spot, o se è una chiamata a una funzione di libreria, o se è la 20a chiamata in un albero di chiamate a 30 livelli, se è responsabile per il 20% di tempo , quindi è in pila il 20% delle volte. I campioni random-time della pila avranno il 20% di probabilità di visualizzarli. Inoltre, se i campioni possono essere presi durante l'I / O, ti mostreranno quali account per l'I / O, che possono essere altrettanto o più sprecati come sprecati cicli della CPU.

E questo è totalmente indipendente dal numero di volte in cui è stato invocato.

Ottimizza dove viene speso il tempo più lungo a meno che non ci sia una ragione particolare per non farlo (cioè la maggior parte del tempo viene speso facendo un'elaborazione asincrona che gli umani non si preoccupano veramente se finisce in 5 minuti o 10 minuti). Il codice che viene chiamato il più, naturalmente, tenderà a accumulare una porzione relativamente grande del tempo trascorso totale semplicemente perché anche i tempi di esecuzione più brevi si sommano quando lo fai migliaia di volte.

Devi lavorare sul codice che impiega più tempo. Migliorare il codice che rappresenta solo una piccola percentuale del tempo di esecuzione può solo migliorare leggermente.

Hai effettuato misurazioni in modo da sapere quale codice impiega più tempo?

Ero abituato a fare benchmark e marketing per un venditore di supercomputer, quindi battere la concorrenza in senso orario non era la cosa più importante, era l'UNICA cosa. Questo tipo di risultato richiedeva l'utilizzo di una combinazione di buon algoritmo e una struttura dati che consentisse alle porzioni più intensive della CPU di eseguire un picco in modo efficiente. Ciò significava che dovevi avere una buona idea di quali sarebbero state le operazioni più impegnative dal punto di vista computazionale e quale tipo di strutture dati avrebbe consentito loro di correre più velocemente. Quindi si trattava di costruire l'applicazione attorno a quei kernel ottimizzati / strutture dati.

In senso più generale, il tipico dopo il fatto tuning. Il tuo profilo, guarda i punti caldi, e i punti caldi che pensi di poter accelerare sono quelli su cui lavori. Ma raramente questo approccio ti darà qualcosa vicino all'implementazione più veloce possibile.

Più in generale però, (errori algoritmici non resistono), per le macchine moderne si deve pensare che le prestazioni siano determinate da tre fattori: accesso ai dati, accesso ai dati e accesso ai dati! Scopri la gerarchia della memoria (registri, cache, TLB, pagine, ecc.) E progetta le tue strutture dati per utilizzarle al meglio. In genere, ciò significa che si desidera poter eseguire cicli all'interno di un footprint di memoria compatto. Se invece si limita a scrivere (o viene data) un'applicazione e quindi si tenta di ottimizzarla, si viene solitamente caricati con strutture dati che fanno un uso inadeguato della gerarchia di memoria, e la modifica delle strutture di dati di solito comporta un esercizio di refactoring importante, quindi si è spesso bloccato.

Se desideri un ritorno sullo sforzo di ottimizzazione, devi guardare il codice che impiega più tempo. Il mio obiettivo generale è qualcosa che richiede almeno l'80% delle volte. In genere obiettivo un guadagno di prestazioni 10 volte. Questo a volte richiede un grande cambiamento nel modo in cui questo codice è stato progettato. Questo tipo di cambiamento ti procura qualcosa che dura all'incirca quattro volte più velocemente.

Il mio miglior guadagno prestazionale di sempre sta riducendo il tempo di esecuzione da 3 giorni a 9 minuti. Il codice che ho ottimizzato è passato da 3 giorni a 3 minuti. L'applicazione che ha sostituito quella applicazione ha ridotto questo a 9 secondi, ma ciò ha richiesto un cambio di lingua e una completa riscrittura.

L'ottimizzazione di un'applicazione già veloce può essere una commissione stupida. Preferirei comunque che la zona impiegasse più tempo. Se puoi prendere qualcosa usando il 10% delle volte per tornare istantaneamente, hai ancora bisogno del 90% delle volte. Hai rapidamente colpito la regola dei rendimenti decrescenti.

A seconda di cosa si sta ottimizzando, la regola rimane valida. Cerca i principali utenti di risorse e ottimali. Se la risorsa che stai ottimizzando è il collo di bottiglia dei sistemi, potresti scoprire che tutto ciò che fai è cambiare il collo di bottiglia in un'altra risorsa.

In genere nella maggior parte dei casi saranno funzioni più carnose, non le funzioni chiamate più spesso un miliardo di volte in un ciclo.

Quando esegui il profiling basato su campioni (con uno strumento o manualmente), spesso i più grandi hotspot si trovano in piccole chiamate fogliari che fanno cose semplici, come una funzione per confrontare due numeri interi.

Questa funzione spesso non trarrà vantaggio dall'ottimizzazione, se non del caso. Per lo meno questi hotspot granulari sono raramente la massima priorità. È la funzione che chiama la funzione foglia che potrebbe essere la causa del problema, o la funzione che chiama la funzione che chiama la funzione, come un algoritmo di ordinamento sub-ottimale. Con buoni strumenti puoi eseguire il drill down da chiamata a chiamante e anche vedere chi trascorre più tempo chiamando il callee.

Spesso è un errore ossessionare i callee e non guardare i chiamanti lungo il grafico delle chiamate in una sessione di profilazione, a meno che non si stiano facendo cose molto inefficienti a livello micro. Altrimenti potresti sudare eccessivamente le piccole cose e perdere di vista il quadro generale. Solo avere un profiler in mano non ti protegge dall'ossessione per cose banali. È solo un primo passo nella giusta direzione.

Inoltre devi assicurarti di eseguire operazioni di profilazione che siano in linea con le cose che gli utenti vogliono realmente fare, altrimenti essere totalmente disciplinato e scientifico nelle tue misurazioni e benchmark è inutile dal momento che non si allinea con ciò che i clienti fanno con il prodotto. Una volta ho avuto un collega che si è sintonizzato da un algoritmo di suddivisione per suddividere un cubo in un miliardo di faccette e ne ha fatto un sacco di orgoglio ... eccetto che gli utenti non suddividono cubetti di 6 poligoni semplici in un miliardo sfaccettature. Il tutto ha rallentato fino alla corsa quando ha provato a girare su un modello di auto di produzione con oltre 100.000 poligoni da suddividere, ea quel punto non poteva nemmeno eseguire 2 o 3 livelli di suddivisione senza rallentare la scansione. In poche parole, ha scritto un codice ottimizzato per dimensioni di input irrealisticamente piccole che non sono state adattate per gestire casi di utilizzo reali, in parte perché era un brillante matematico, ma non conosceva il modo in cui gli utenti utilizzavano effettivamente il prodotto.

Devi ottimizzare casi d'uso reali allineati con gli interessi dei tuoi utenti oppure è peggio che inutile, dal momento che tutte quelle ottimizzazioni che tendono ad alterare almeno in parte la manutenibilità del codice hanno scarso vantaggio per l'utente e solo tutti quei negativi per il codice base .