Come documentare e insegnare agli altri il codice computazionalmente intensivo "ottimizzato oltre il riconoscimento"?

11

Occasionalmente c'è l'1% di codice che è abbastanza intensivo dal punto di vista computazionale che richiede il tipo più pesante di ottimizzazione a basso livello. Esempi sono l'elaborazione video, l'elaborazione delle immagini e tutti i tipi di elaborazione del segnale, in generale.

Gli obiettivi sono quelli di documentare e insegnare le tecniche di ottimizzazione, in modo che il codice non diventi non mantenibile e possa essere rimosso dagli sviluppatori più recenti. (*)

(*) Nonostante la possibilità che la particolare ottimizzazione sia completamente inutile in alcune CPU future imprevedibili, in modo tale che il codice venga cancellato comunque.

Considerando che le offerte di software (commerciali o open source) mantengono il loro vantaggio competitivo avendo il codice più veloce e sfruttando la più recente architettura della CPU, i produttori di software spesso devono modificare il loro codice per farlo funzionare più velocemente mentre ottengono lo stesso output per un determinato compito, whlist che tollerano una piccola quantità di errori di arrotondamento.

In genere, uno scrittore di software può conservare molte versioni di una funzione come documentazione di ogni riscrittura di ottimizzazione / algoritmo che si verifica. Come si rendono disponibili queste versioni per gli altri per studiare le loro tecniche di ottimizzazione?

Related:

posta rwong 24.11.2011 - 02:40
fonte

4 risposte

10

Risposta breve

Mantieni ottimizzazioni locali, rendili ovvi, documentale bene e semplifica il confronto tra le versioni ottimizzate e la versione non ottimizzata, sia in termini di codice sorgente che di prestazioni in fase di esecuzione.

Risposta completa

Se tali ottimizzazioni sono così importanti per il tuo prodotto, allora devi sapere non solo perché le ottimizzazioni sono state utili in precedenza, ma anche fornire informazioni sufficienti per aiutare gli sviluppatori a sapere se saranno utili in il futuro.

Idealmente, è necessario archiviare i test delle prestazioni nel processo di compilazione, in modo da scoprire quando le nuove tecnologie invalidano le vecchie ottimizzazioni.

Ricorda:

The First Rule of Program Optimisation: Don't do it.

The Second Rule of Program Optimisation (for experts only!): Don't do it yet."

— Michael A. Jackson

Per sapere se ora è il momento che richiede benchmark e test.

Come accennato, il problema più grande con il codice altamente ottimizzato è che è difficile da mantenere così, per quanto possibile, è necessario mantenere le parti ottimizzate separate dalle parti non ottimizzate. Sia che si faccia questo attraverso il collegamento in fase di compilazione, le chiamate di funzioni virtuali di runtime o qualcosa in mezzo non dovrebbero avere importanza. Ciò che dovrebbe importare è che quando esegui i test, vuoi essere in grado di testare tutti delle versioni che ti interessano al momento.

Sarei propenso a costruire un sistema in modo tale che la versione base non ottimizzata del codice di produzione possa sempre essere utilizzata per comprendere l' intento del codice, quindi costruire diversi moduli ottimizzati insieme a questo contenente la versione o le versioni ottimizzate, che documentano esplicitamente ovunque la versione ottimizzata differisca dalla linea di base. Quando esegui i test (unità e integrazione), esegui la versione non ottimizzata e su tutti i moduli ottimizzati correnti.

Esempio

Ad esempio, supponiamo di avere una funzione Trasformazione di Fourier veloce . Forse hai un'implementazione di base algoritmica in fft.c e prove in fft_tests.c .

Poi arriva il Pentium e decidi di implementare la versione a virgola fissa in fft_mmx.c usando istruzioni MMX . Successivamente arriva il pentium 3 e decidi di aggiungere una versione che utilizza Streaming SIMD Extensions in fft_sse.c .

Ora vuoi aggiungere CUDA , quindi aggiungi fft_cuda.c , ma lo trovi con il set di dati di prova che Ho usato per anni, la versione CUDA è più lenta della versione SSE! Fai qualche analisi e alla fine aggiungi un set di dati che è 100 volte più grande e ottieni la velocità che ti aspetti, ma ora sai che il tempo di installazione per usare la versione CUDA è significativo e che con piccoli set di dati dovresti usare un algoritmo senza il costo di impostazione.

In ognuno di questi casi si sta implementando lo stesso algoritmo, tutti dovrebbero comportarsi allo stesso modo, ma verranno eseguiti con diverse efficienze e velocità su architetture diverse (se verranno eseguite affatto). Dal punto di vista del codice, tuttavia, è possibile confrontare qualsiasi coppia di file sorgente per scoprire perché la stessa interfaccia è implementata in modi diversi e, in genere, il modo più semplice sarà fare riferimento alla versione originale non ottimizzata.

Lo stesso vale per un'implementazione OOP in cui una classe base che implementa l'algoritmo non ottimizzato e le classi derivate implementano diverse ottimizzazioni.

L'importante è mantenere le stesse cose che sono uguali , in modo che le differenze siano ovvie .

    
risposta data 24.11.2011 - 17:04
fonte
7

In particolare, dato che hai preso l'esempio dell'elaborazione di video e immagini, puoi mantenere il codice come parte della stessa versione ma attivo o inattivo a seconda del contesto.

Anche se non hai menzionato, sto assumendo C qui.

Il modo più semplice nel codice C , uno fa l'ottimizzazione (e si applica anche quando si tenta di rendere le cose portatili) è quello di mantenere

 
#ifdef OPTIMIZATION_XYZ_ENABLE 
   // your optimzied code here... 
#else  
   // your basic code here...

Quando abiliti #define OPTIMIZATION_XYZ_ENABLE durante la compilazione in Makefile, tutto funziona di conseguenza.

Di solito, tagliando alcune righe di codice nel mezzo delle funzioni potrebbe diventare complicato quando ci sono troppe funzioni ottimizzate. Quindi, in questo caso si definiscono diversi puntatori di funzioni per eseguire una funzione specifica.

il codice principale viene sempre eseguito tramite un puntatore a funzione come


   codec->computed_idct(blocks); 

Ma i puntatori di funzione sono definiti in base al tipo di esempio (ad esempio, la funzione idct è ottimizzata per diverse architetture della CPU.



if(OPTIMIZE_X86) {
  codec->computed_idct = compute_idct_x86; 
}
else if(OPTIMZE_ARM) {
  codec->computed_idct = compute_idct_ARM;
}
else {
  codec->computed_idct = compute_idct_C; 
}

dovresti vedere il codice libjpeg e libmpeg2 codice e potrebbe essere ffmpeg per tali tecniche.

    
risposta data 24.11.2011 - 03:28
fonte
6

Come ricercatore finisco per scrivere un bel po 'di codice "bottleneck". Tuttavia, una volta che è stato messo in produzione, l'onere di integrarlo nel prodotto e fornire il successivo supporto spetta agli sviluppatori. Come puoi immaginare, comunicare chiaramente cosa e come dovrebbe funzionare il programma è della massima importanza.

Ho scoperto che ci sono tre ingredienti essenziali nel completare questo passo con successo

  1. L'algoritmo utilizzato deve essere assolutamente chiaro.
  2. Lo scopo di ogni linea di implementazione deve essere chiaro.
  3. Le deviazioni dai risultati attesi devono essere identificate il prima possibile.

Per il primo passo, scrivo sempre un breve white paper che documenta l'algoritmo. L'obiettivo qui è di scriverlo effettivamente in modo che un'altra persona possa implementarlo da zero usando solo il whitepaper. Se è un noto algoritmo pubblicato è sufficiente dare i riferimenti e ripetere le equazioni chiave. Se è un lavoro originale, dovrai essere un po 'più esplicito. Questo ti dirà cosa il codice è dovrebbe fare .

L'effettiva implementazione che è passata allo sviluppo deve essere documentata in modo tale che tutte le sottigliezze siano rese esplicite. Se si acquisiscono blocchi in un ordine particolare per evitare situazioni di stallo, aggiungere un commento. Se si esegue l'iterazione sulle colonne anziché sulle righe di una matrice a causa di problemi di coerenza della cache, aggiungere un commento. Se fai qualcosa di leggermente intelligente, commentalo. Se è possibile garantire il white paper e il codice non verrà mai separato (tramite VCS o sistema simile), è possibile fare riferimento al white paper. Il risultato può facilmente superare il 50% di commenti. Va bene. Questo ti dirà perché il codice fa quello che fa.

Infine, devi essere in grado di garantire la correttezza di fronte alle modifiche. Fortunatamente siamo uno strumento utile nelle piattaforme testing automatico e integrazione continua . Questi ti diranno cosa il codice sta effettivamente facendo .

La mia raccomandazione più calorosa non sarebbe quella di eludere i passaggi. Ne avrai bisogno in seguito;)

    
risposta data 29.11.2011 - 12:10
fonte
5

Credo che ciò possa essere risolto al meglio attraverso commenti completi sul codice, fino al punto in cui ogni significativo blocco di codice ha in anticipo un commento esplicativo.

I commenti dovrebbero includere citazioni alle specifiche o al materiale di riferimento dell'hardware.

Utilizza i nomi di algoritmi e terminologia a livello di settore laddove appropriato, ad es. 'architettura X genera trap della CPU per letture non allineate, quindi questo dispositivo di Duff si riempie fino al prossimo limite di allineamento'.

Userei la denominazione delle variabili in-your-face per garantire l'assenza di equivoci su ciò che sta accadendo. Non ungherese, ma cose come "stride" per descrivere la distanza in byte tra due pixel verticali.

Vorrei anche integrare questo con un documento breve, umanamente leggibile che ha diagrammi di alto livello e progettazione di blocchi.

    
risposta data 24.11.2011 - 09:50
fonte

Leggi altre domande sui tag