Quali tecniche semplici usi per migliorare le prestazioni?

20

Sto parlando del modo in cui scriviamo routine semplici per migliorare le prestazioni senza rendere più difficile la lettura del codice ... ad esempio, questo è tipico di quanto abbiamo appreso:

for(int i = 0; i < collection.length(); i++ ){
   // stuff here
}

Ma di solito lo faccio quando foreach non è applicabile:

for(int i = 0, j = collection.length(); i < j; i++ ){
   // stuff here
}

Penso che questo sia un approccio migliore dal momento che chiamerà il metodo length una volta sola ... la mia ragazza dice che è criptico però. C'è qualche altro semplice trucco che usi sui tuoi sviluppi?

    
posta Cristian 26.09.2010 - 01:03
fonte

16 risposte

28

inserisci una discussione prematura-is-the-root-of-all-evil

Detto questo, ecco alcune abitudini in cui sono entrato per evitare l'efficienza non necessaria, e in alcuni casi, rendere il mio codice più semplice e più corretto.

Questa non è una discussione sui principi generali, ma su alcune cose da tenere presente per evitare l'introduzione di inutili inefficienze nel codice.

Conosci il tuo big-O

Questo dovrebbe probabilmente essere unito alla lunga discussione di cui sopra. È quasi logico che un ciclo all'interno di un ciclo, in cui il ciclo interno ripete un calcolo, sarà più lento. Ad esempio:

for (i = 0; i < strlen(str); i++) {
    ...
}

Ciò richiederà una quantità di tempo orrenda se la stringa è veramente lunga, poiché la lunghezza viene ricalcolata ad ogni iterazione del ciclo. Nota che GCC effettivamente ottimizza questo caso perché strlen() è contrassegnato come una pura funzione.

Quando si ordina un milione di numeri interi a 32 bit, tipi di bolle sarebbe il modo sbagliato di andare . In generale, l'ordinamento può essere fatto in O (n * log n) tempo (o meglio, nel caso di radix sort), quindi a meno che non si sappia che i dati saranno piccoli, cercare un algoritmo che sia almeno O (n * log n).

Allo stesso modo, quando si ha a che fare con i database, tenere conto degli indici. Se si SELECT * FROM people WHERE age = 20 , e non si ha un indice su persone (età), richiederà una scansione sequenziale O (n) piuttosto che una scansione indice O (log n) molto più veloce.

Gerarchia aritmetica intera

Quando si programma in C, tenere presente che alcune operazioni aritmetiche sono più costose di altre. Per i numeri interi, la gerarchia è simile a questa (prima la meno cara):

  • + - ~ & | ^
  • << >>
  • *
  • /

Certo, il compilatore di solito ottimizza automaticamente cose come n / 2 in n >> 1 se stai prendendo di mira un computer mainstream, ma se stai prendendo di mira un dispositivo incorporato, potresti non ottenere quel lusso.

Inoltre, % 2 e & 1 hanno semantica diversa. La divisione e il modulo di solito arrotonda verso lo zero, ma è definito dall'implementazione. Il buon vecchio >> e il & arrotonda sempre verso l'infinito negativo, il che (secondo me) ha molto più senso. Ad esempio, sul mio computer:

printf("%d\n", -1 % 2); // -1 (maybe)
printf("%d\n", -1 & 1); // 1

Quindi, usa ciò che ha senso. Non pensare di essere un bravo ragazzo usando % 2 quando avresti dovuto scrivere & 1 .

Operazioni costanti in virgola mobile

Evita le operazioni pesanti in virgola mobile come pow() e log() nel codice che non ne ha veramente bisogno, specialmente quando si ha a che fare con numeri interi. Prendi, ad esempio, la lettura di un numero:

int parseInt(const char *str)
{
    const char *p;
    int         digits;
    int         number;
    int         position;

    // Count the number of digits
    for (p = str; isdigit(*p); p++)
        {}
    digits = p - str;

    // Sum the digits, multiplying them by their respective power of 10.
    number = 0;
    position = digits - 1;
    for (p = str; isdigit(*p); p++, position--)
        number += (*p - '0') * pow(10, position);

    return number;
}

Non solo questo uso di pow() (e le int < - > double conversioni necessarie per usarlo) è piuttosto costoso, ma crea un'opportunità per la perdita di precisione (per inciso, il codice sopra non avere problemi di precisione). Ecco perché mi diverto quando vedo questo tipo di funzione usata in un contesto non matematico.

Inoltre, nota come l'algoritmo "intelligente" di seguito, che moltiplica per 10 per ogni iterazione, è in realtà più conciso del codice sopra:

int parseInt(const char *str)
{
    const char *p;
    int         number;

    number = 0;
    for (p = str; isdigit(*p); p++) {
        number *= 10;
        number += *p - '0';
    }

    return number;
}
    
risposta data 26.09.2010 - 06:36
fonte
13

Dalla tua domanda e dal thread dei commenti, sembra che tu "pensi" che questo cambiamento di codice migliori le prestazioni, ma non sai davvero se lo fa o no.

Sono un fan della filosofia di Kent Beck :

"Make it work, make it right, make it fast."

La mia tecnica per migliorare le prestazioni del codice, è prima ottenere il codice che passa i test unitari e ben fattorizzato e quindi (in particolare per le operazioni di ciclo) scrivere un test unitario che controlla le prestazioni e quindi ridefinisce il codice o pensa ad un algoritmo diverso se il quello che ho scelto non funziona come previsto.

Ad esempio, per testare la velocità con il codice .NET, utilizzo l'attributo Timeout di NUnit per scrivere asserzioni secondo cui una chiamata ad un particolare metodo verrà eseguita entro un certo periodo di tempo.

Usando qualcosa come l'attributo timeout di NUnit con l'esempio di codice che hai fornito (e un gran numero di iterazioni per il ciclo), potresti effettivamente dimostrare se il tuo "miglioramento" del codice aiutasse realmente o meno la perfomance di quel ciclo .

Una dichiarazione di non responsabilità: sebbene sia efficace a livello "micro", non è certamente l'unico modo per testare le prestazioni e non tiene conto dei problemi che potrebbero sorgere a livello "macro" - ma è un buon inizio .

    
risposta data 26.09.2010 - 01:52
fonte
11

Ricorda che il tuo compilatore potrebbe girare:

for(int i = 0; i < collection.length(); i++ ){
   // stuff here
}

in:

int j = collection.length();
for(int i = 0; i < j; i++ ){
   // stuff here
}

o qualcosa di simile, se collection è invariato sul ciclo.

Se questo codice si trova in una sezione temporale della tua applicazione, varrebbe la pena scoprire se questo è il caso o se è possibile modificare le opzioni del compilatore per farlo.

Ciò manterrà la leggibilità del codice (poiché il primo è ciò che la maggior parte delle persone si aspetterà di vedere), guadagnando nel contempo quei pochi cicli macchina extra. Sei quindi libero di concentrarti sulle altre aree in cui il compilatore non può aiutarti.

Nota a margine: se si modifica collection all'interno del ciclo aggiungendo o rimuovendo elementi (sì, so che è una cattiva idea, ma succede), il secondo esempio non eseguirà il loop su tutti gli elementi o tenterà di accedere oltre la fine dell'array.

    
risposta data 26.09.2010 - 18:18
fonte
9

Questo tipo di ottimizzazione di solito non è raccomandato. Quel pezzo di ottimizzazione può essere fatto facilmente dal compilatore, stai lavorando con un linguaggio di programmazione di livello superiore invece di assemblare, quindi pensa allo stesso livello.

    
risposta data 26.09.2010 - 05:40
fonte
4

Bene, il primo consiglio sarebbe di evitare tali premature ottimizzazioni finché non saprai esattamente cosa sta accadendo al codice, in modo da essere sicuro che lo stai rendendo più veloce, e non più lento.

In C #, ad esempio, il compilatore ottimizzerà il codice se si esegue il looping della lunghezza di un array, poiché sa che non è necessario controllare l'indice quando si accede all'array. Se si tenta di ottimizzarlo inserendo la lunghezza dell'array in una variabile, si interromperà la connessione tra il loop e l'array e in effetti il codice diventerà molto più lento.

Se hai intenzione di micro-ottimizzare, dovresti limitarti a cose che sono conosciute per utilizzare molte risorse. Se c'è solo un leggero aumento delle prestazioni, dovresti usare il codice più leggibile e manutenibile. Come cambia il lavoro del computer nel tempo, quindi qualcosa che scopri è leggermente più veloce ora, potrebbe non rimanere così.

    
risposta data 28.09.2010 - 01:26
fonte
3

Questo potrebbe non essere valido per la codifica generica, ma al giorno d'oggi lo sviluppo è per lo più incorporato. Abbiamo uno specifico processore di destinazione (che non diventerà più veloce - sembrerà curiosamente obsoleto dal momento in cui ritireranno il sistema tra 20 anni), e scadenze temporali molto restrittive per gran parte del codice. Il processore, come tutti i processori, ha alcune stranezze riguardo a quali operazioni sono veloci o lente.

Abbiamo una tecnica utilizzata per garantire che stiamo generando il codice più efficiente, pur mantenendo la leggibilità per l'intero team. In quei luoghi in cui la costruzione del linguaggio più naturale non genera il codice più efficiente, abbiamo creato macro che garantiscono l'utilizzo del codice ottimale. Se facciamo un progetto successivo per un processore diverso, possiamo aggiornare i macro per il metodo ottimale su quel processore.

Come esempio specifico, per il nostro attuale processore, le filiali svuotano la pipeline, bloccando il processore per 8 cicli. Il compilatore prende questo codice:

 bool isReady = (value > TriggerLevel);

e lo trasforma nell'equivalente dell'assieme di

isReady = 0
if (value > TriggerLevel)
{
  isReady = 1;
}

Questo richiederà 3 cicli, o 10 se salta sopra isReady=1; . Ma il processore ha un'istruzione max a ciclo singolo, quindi è molto meglio scrivere codice per generare questa sequenza che è sempre garantita per 3 cicli:

diff = value-TriggerLevel;
diff = max(diff, 0);
isReady = min(1,diff);

Ovviamente, l'intento qui è meno chiaro dell'originale. Quindi abbiamo creato una macro, che usiamo ogniqualvolta vogliamo un confronto-maggiore di booleano:

#define BOOL_GT(a,b) min(max((a)-(b),0),1)

//isReady = value > TriggerLevel;
isReady = BOOL_GT(value, TriggerLevel);

Possiamo fare cose simili per altri confronti. Per un estraneo, il codice è un po 'meno leggibile rispetto a quando usassimo solo il costrutto naturale. Tuttavia diventa subito chiaro dopo aver trascorso un po 'di tempo a lavorare con il codice, ed è molto meglio che lasciare che ogni programmatore sperimenta con le proprie tecniche di ottimizzazione.

    
risposta data 26.09.2010 - 23:45
fonte
3

Ho una tecnica molto semplice.

  1. Rendo il mio codice funzionante.
  2. Lo proverò per la velocità.
  3. Se è veloce, torno al passaggio 1 per qualche altra funzione. Se è lento, lo registro per trovare il collo di bottiglia.
  4. Ho risolto il collo di bottiglia. Torna al passaggio 1.

Ci sono molte volte in cui si risparmia tempo per aggirare questo processo, ma in generale saprai se questo è il caso. Se c'è il dubbio, mi attengo a questo di default.

    
risposta data 01.11.2010 - 11:37
fonte
2

Approfitta del cortocircuito:

if(someVar || SomeMethod())

richiede tanto tempo per il codice ed è leggibile quanto:

if(someMethod() || someVar)

tuttavia lo valuterà più rapidamente nel tempo.

    
risposta data 30.10.2010 - 19:43
fonte
1

Aspetta sei mesi, fai in modo che il tuo capo acquisti tutti i nuovi computer. Sul serio. Il tempo del programmatore è molto più costoso dell'hardware a lungo termine. I computer ad alte prestazioni consentono ai programmatori di scrivere codice in modo semplice senza preoccuparsi della velocità.

    
risposta data 26.09.2010 - 02:22
fonte
1

Cerca di non ottimizzare troppo in anticipo, quindi quando ottimizzi preoccupati un po 'meno della leggibilità.

C'è poco odio più della complessità non necessaria, ma quando si colpisce una situazione complessa è spesso richiesta una soluzione complessa.

Se scrivi il codice nel modo più ovvio, scrivi un commento per spiegare perché è stato modificato quando apporti modifiche complesse.

In particolare, tuttavia, a mio avviso, trovo che molte volte l'opposto booleano dell'approccio predefinito a volte aiuti:

for(int i = 0, j = collection.length(); i < j; i++ ){
// stuff here
}

può diventare

for(int i = collection.length(); i > 0; i-=1 ){
// stuff here
}

In molte lingue, purché si apportino le opportune modifiche alla parte "roba" ed è ancora leggibile. Semplicemente non si avvicina al problema come la maggior parte della gente penserebbe di farlo prima perché conta all'indietro.

in c # per esempio:

        string[] collection = {"a","b"};

        string result = "";

        for (int i = 0, j = collection.Count() - 1; i < j; i++)
        {
            result += collection[i] + "~";
        }

potrebbe anche essere scritto come:

        for (int i = collection.Count() - 1; i > 0; i -= 1)
        {
            result = collection[i] + "~" + result;
        }

(e sì, dovresti farlo con un join o un stringbuilder, ma sto cercando di fare un semplice esempio)

Ci sono molti altri trucchi che è possibile utilizzare che non sono difficili da seguire, ma molti di essi non si applicano a tutti i linguaggi come l'utilizzo di metà sul lato sinistro di un compito nel vecchio vb per evitare la penalità di riassegnazione della stringa o la lettura di file di testo in modalità binaria in .net per superare la penalità di buffering quando il file è troppo grande per un readtoend.

L'unico altro caso veramente generico che posso pensare che si applicherebbe ovunque sarebbe applicare dell'algebra booleana a condizionali complessi per cercare di trasformare l'equazione in qualcosa che ha una migliore possibilità di sfruttare un cortocircuito condizionale o trasforma un insieme complesso di istruzioni nidificate if-then o case in un'equazione interamente. Nessuno di questi funziona in tutti i casi, ma possono essere significativi risparmiatori di tempo.

    
risposta data 26.09.2010 - 04:55
fonte
1
  1. Profilo. Abbiamo persino un problema? Dove?
  2. Nel 90% dei casi in cui è in qualche modo correlato all'IO, applica il caching (e forse ottieni più memoria)
  3. Se è correlato alla CPU, applica la memorizzazione nella cache
  4. Se le prestazioni sono ancora un problema, abbiamo lasciato il regno delle semplici tecniche: fai i conti.
risposta data 30.01.2011 - 23:11
fonte
1

Utilizza gli strumenti migliori che puoi trovare - buon compilatore, buon profiler, buone librerie. Ottieni gli algoritmi corretti, o meglio ancora - usa la libreria giusta per farlo per te. Le ottimizzazioni del ciclo sono piccole patate, inoltre non sei intelligente come il compilatore di ottimizzazione.

    
risposta data 31.01.2011 - 03:51
fonte
1

Il più semplice per me è usare la pila quando possibile ogni volta che un modello di utilizzo del caso comune si adatta a un intervallo di, ad esempio, [0, 64) ma ha casi rari senza limite superiore.

Esempio C semplice (prima):

void some_hotspot_called_in_big_loops(int n, ...)
{
    // 'n' is, 99% of the time, <= 64.
    int* values = calloc(n, sizeof(int));

    // do stuff with values
    ...
    free(values);
}

E dopo:

void some_hotspot_called_in_big_loops(int n, ...)
{
    // 'n' is, 99% of the time, <= 64.
    int values_mem[64] = {0}
    int* values = (n <= 64) ? values_mem: calloc(n, sizeof(int));

    // do stuff with values
    ...
    if (values != values_mem)
        free(values);
}

L'ho generalizzato in questo modo dato che questi tipi di hotspot si presentano molto in fase di profilazione:

void some_hotspot_called_in_big_loops(int n, ...)
{
    // 'n' is, 99% of the time, <= 64.
    MemFast values_mem;
    int* values = mf_calloc(&values_mem, n, sizeof(int));

    // do stuff with values
    ...

    mf_free(&values_mem);
}

Quanto sopra utilizza lo stack quando i dati allocati sono abbastanza piccoli in questi casi del 99,9% e utilizza altrimenti l'heap.

In C ++ ho generalizzato questo con una piccola sequenza conforme agli standard (simile alle implementazioni SmallVector là fuori) che ruota attorno allo stesso concetto.

Non è un'ottimizzazione epica (ho ottenuto riduzioni da, diciamo, 3 secondi per completare un'operazione fino a 1,8 secondi), ma richiede un tale sforzo banale da applicare. Quando riesci a ottenere qualcosa da 3 secondi a 1,8 secondi semplicemente introducendo una riga di codice e cambiandone due, è un bel colpo per un dollaro così piccolo.

    
risposta data 10.12.2017 - 23:13
fonte
0

Bene, ci sono molte modifiche alle prestazioni che puoi fare quando accedi ai dati che avranno un impatto enorme sulla tua applicazione. Se si scrivono query o si utilizza un ORM per accedere a un database, è necessario leggere alcuni manuali di ottimizzazione delle prestazioni per il back-end del database che si utilizza. È probabile che tu stia utilizzando tecniche con prestazioni scarse. Non c'è motivo di fare questo tranne l'ignoranza. Non si tratta di un'ottica prematura (maledico chi ha detto questo perché è stato interpretato in modo così estensivo da non preoccuparsi mai delle prestazioni), questo è un buon design.

Solo un rapido esempio di miglioramento delle prestazioni per SQL Server: Utilizza indici appropriati, evita i cursori - usa logica basata su set, usa clausole sargable dove, non impilare le viste sulla sommità delle viste, non restituisce più dati del necessario o più colonne del necessario, non utilizzare subquery correlate .

    
risposta data 04.10.2010 - 16:08
fonte
0

Se questo è C ++, dovresti prendere l'abitudine di ++i piuttosto che i++ . ++i non sarà mai peggiore, significa esattamente lo stesso di un'istruzione autonoma e in alcuni casi potrebbe essere un miglioramento delle prestazioni.

Non vale la pena cambiare il codice esistente nella remota possibilità che possa essere d'aiuto, ma è una buona abitudine entrare.

    
risposta data 01.11.2010 - 21:33
fonte
0

Ho un approccio leggermente diverso. Semplicemente seguire i consigli che ottieni qui non farà molta differenza, perché ci sono alcuni errori che devi fare, che devi poi aggiustare, da cui poi devi imparare.

L'errore che devi fare è progettare la struttura dei dati come fanno tutti. Cioè, con dati ridondanti e molti livelli di astrazione, con proprietà e notifiche che si propagano in tutta la struttura cercando di mantenerlo coerente.

Quindi devi eseguire il tuning delle prestazioni (profilazione ) e mostrarti come, in molti modi, ciò che ti costa una gran quantità di cicli sono i molti strati di astrazione, con proprietà e notifiche che si propagano in tutta la struttura cercando di mantenerlo coerente.

Potresti riuscire a correggere questi problemi senza apportare modifiche importanti al codice.

Quindi, se sei fortunato, puoi imparare che una struttura dei dati inferiore è migliore e che è meglio tollerare l'incoerenza temporanea piuttosto che cercare di mantenere molte cose strettamente in accordo con le ondate di messaggi.

Il modo in cui scrivi i loop non ha nulla a che fare con questo.

    
risposta data 19.11.2010 - 03:53
fonte

Leggi altre domande sui tag