Procedure di codifica che consentono al compilatore / ottimizzatore di realizzare un programma più veloce

Molti anni fa, i compilatori C non erano particolarmente intelligenti. Come soluzione alternativa, K & R ha inventato la parola chiave register , per suggerire al compilatore, che forse sarebbe una buona idea mantenere questa variabile in un registro interno. Hanno anche fatto l’operatore terziario per aiutare a generare un codice migliore.

Con il passare del tempo, i compilatori sono maturati. Sono diventati molto intelligenti in quanto la loro analisi del stream consente loro di prendere decisioni migliori su quali valori tenere nei registri di quanto si possa fare. La parola chiave del registro non è stata importante.

FORTRAN può essere più veloce di C per alcuni tipi di operazioni, a causa di problemi di alias . In teoria con un’accurata codifica, è ansible aggirare questa restrizione per consentire all’ottimizzatore di generare codice più veloce.

Quali pratiche di codifica sono disponibili che possono consentire al compilatore / ottimizzatore di generare codice più veloce?

  • Identificare la piattaforma e il compilatore che usi, sarebbe apprezzato.
  • Perché la tecnica sembra funzionare?
  • Il codice di esempio è incoraggiato.

Ecco una domanda correlata

[Modifica] Questa domanda non riguarda la procedura generale per il profilo e l’ottimizzazione. Supponiamo che il programma sia stato scritto correttamente, compilato con ottimizzazione completa, testato e messo in produzione. Potrebbero esserci dei costrutti nel codice che impediscono all’ottimizzatore di fare il miglior lavoro ansible. Cosa puoi fare al refactor per rimuovere questi divieti e consentire all’ottimizzatore di generare codice ancora più veloce?

[Modifica] Collegamento correlato all’offset

Scrivi su variabili locali e non genera argomenti! Questo può essere di grande aiuto per aggirare i rallentamenti alias. Ad esempio, se il tuo codice è simile

 void DoSomething(const Foo& foo1, const Foo* foo2, int numFoo, Foo& barOut) { for (int i=0; i 

il compilatore non sa che foo1! = barOut, e quindi deve ricaricare foo1 ogni volta attraverso il ciclo. Inoltre non può leggere foo2 [i] finché la scrittura su barOut non è terminata. Potresti iniziare a scherzare con puntatori limitati, ma è altrettanto efficace (e molto più chiaro) a farlo:

 void DoSomethingFaster(const Foo& foo1, const Foo* foo2, int numFoo, Foo& barOut) { Foo barTemp = barOut; for (int i=0; i 

Sembra sciocco, ma il compilatore può essere molto più intelligente con la variabile locale, dal momento che non può sovrapporsi alla memoria con nessuno degli argomenti. Questo può aiutarti ad evitare il temibile load-hit-store (menzionato da Francis Boivin in questa discussione).

Ecco una pratica di codifica per aiutare il compilatore a creare codice veloce: qualsiasi lingua, qualsiasi piattaforma, qualsiasi compilatore, qualsiasi problema:

Non usare trucchi intelligenti che costringano o addirittura incoraggiano il compilatore a porre le variabili in memoria (inclusa la cache e i registri) come meglio credi. Prima scrivi un programma che sia corretto e mantenibile.

Successivamente, profila il tuo codice.

Quindi, e solo dopo, potresti voler iniziare a indagare sugli effetti di dire al compilatore come usare la memoria. Apporta 1 cambio alla volta e ne misura l’impatto.

Aspettatevi di essere delusi e di dover lavorare molto duramente per ottenere piccoli miglioramenti delle prestazioni. I compilatori moderni per le lingue mature come Fortran e C sono molto, molto buoni. Se leggi un resoconto di un “trucco” per ottenere prestazioni migliori dal codice, tieni presente che anche gli scrittori di compilatori ne hanno letto e, se vale la pena farlo, probabilmente lo hanno implementato. Probabilmente hanno scritto quello che hai letto in primo luogo.

L’ordine che attraversi la memoria può avere un impatto profondo sulle prestazioni e i compilatori non sono davvero bravi a capirlo e correggerlo. Devi essere coscienzioso delle preoccupazioni relative alla localizzazione della cache quando scrivi codice se ti interessi delle prestazioni. Ad esempio, le matrici bidimensionali in C sono allocate nel formato riga-maggiore. Gli array di attraversamento nel formato principale della colonna tendono a farti perdere più cache e rendono il tuo programma più legato alla memoria rispetto al processore:

 #define N 1000000; int matrix[N][N] = { ... }; //awesomely fast long sum = 0; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ sum += matrix[i][j]; } } //painfully slow long sum = 0; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ sum += matrix[j][i]; } } 

Ottimizzazioni generiche

Ecco come alcune delle mie ottimizzazioni preferite. Ho effettivamente aumentato i tempi di esecuzione e ridotto le dimensioni del programma utilizzando questi.

Dichiarare piccole funzioni come inline o macro

Ogni chiamata a una funzione (o metodo) incorre in un sovraccarico, come spingere le variabili nello stack. Alcune funzioni potrebbero inoltre comportare un sovraccarico al momento del reso. Una funzione o un metodo inefficiente ha meno istruzioni nel suo contenuto rispetto al sovraccarico combinato. Questi sono buoni candidati per l’inlining, che si tratti di macro #define o funzioni inline . (Sì, so che in inline è solo un suggerimento, ma in questo caso lo considero come un promemoria per il compilatore.)

Rimuovi il codice morto e ridondante

Se il codice non viene utilizzato o non contribuisce al risultato del programma, eliminarlo.

Semplifica la progettazione degli algoritmi

Una volta ho rimosso un sacco di codice assembly e tempo di esecuzione da un programma scrivendo l’equazione algebrica che stava calcolando e quindi semplificando l’espressione algebrica. L’implementazione dell’espressione algebrica semplificata occupava meno spazio e tempo rispetto alla funzione originale.

Loop Svolgimento

Ogni ciclo ha un sovraccarico di controllo di incremento e terminazione. Per ottenere una stima del fattore di rendimento, conta il numero di istruzioni nel sovraccarico (minimo 3: incremento, verifica, inizio del ciclo) e dividi per il numero di istruzioni all’interno del ciclo. Più basso è il numero, meglio è.

Modifica: fornire un esempio di svolgimento del ciclo Prima:

 unsigned int sum = 0; for (size_t i; i < BYTES_TO_CHECKSUM; ++i) { sum += *buffer++; } 

Dopo lo srotolamento:

 unsigned int sum = 0; size_t i = 0; **const size_t STATEMENTS_PER_LOOP = 8;** for (i = 0; i < BYTES_TO_CHECKSUM; **i = i / STATEMENTS_PER_LOOP**) { sum += *buffer++; // 1 sum += *buffer++; // 2 sum += *buffer++; // 3 sum += *buffer++; // 4 sum += *buffer++; // 5 sum += *buffer++; // 6 sum += *buffer++; // 7 sum += *buffer++; // 8 } // Handle the remainder: for (; i < BYTES_TO_CHECKSUM; ++i) { sum += *buffer++; } 

In questo vantaggio, si ottiene un vantaggio secondario: più istruzioni vengono eseguite prima che il processore debba ricaricare la cache delle istruzioni.

Ho avuto risultati sorprendenti quando ho srotolato un ciclo a 32 istruzioni. Questo era uno dei colli di bottiglia dal momento che il programma doveva calcolare un checksum su un file da 2 GB. Questa ottimizzazione combinata con la lettura dei blocchi ha migliorato le prestazioni da 1 ora a 5 minuti. Lo srotolamento del loop forniva prestazioni eccellenti anche in linguaggio assembly, la mia memcpy era molto più veloce della memcpy del compilatore. - TM

Riduzione delle dichiarazioni if

I processori odiano i rami, o salti, poiché costringono il processore a ricaricare la coda di istruzioni.

Aritmetica booleana ( Modificato: formato di codice applicato per codificare il frammento, esempio aggiunto)

Converti le istruzioni in assegnazioni booleane. Alcuni processori possono eseguire istruzioni in modo condizionale senza diramazioni:

 bool status = true; status = status && /* first test */; status = status && /* second test */; 

Il cortocircuito dell'operatore AND logico ( && ) impedisce l'esecuzione dei test se lo status è false .

Esempio:

 struct Reader_Interface { virtual bool write(unsigned int value) = 0; }; struct Rectangle { unsigned int origin_x; unsigned int origin_y; unsigned int height; unsigned int width; bool write(Reader_Interface * p_reader) { bool status = false; if (p_reader) { status = p_reader->write(origin_x); status = status && p_reader->write(origin_y); status = status && p_reader->write(height); status = status && p_reader->write(width); } return status; }; 

Factor Assegnazione variabile al di fuori dei loop

Se una variabile viene creata al volo all'interno di un ciclo, spostare la creazione / allocazione su prima del ciclo. Nella maggior parte dei casi, la variabile non deve essere allocata durante ogni iterazione.

Fattore di espressioni costanti al di fuori dei cicli

Se un calcolo o un valore variabile non dipende dall'indice del ciclo, spostalo all'esterno (prima) del ciclo.

I / O in blocchi

Leggere e scrivere dati in blocchi di grandi dimensioni (blocchi). Piu 'grande e', meglio 'e. Ad esempio, leggere un octetto alla volta è meno efficiente della lettura di 1024 ottetti con una lettura.
Esempio:

 static const char Menu_Text[] = "\n" "1) Print\n" "2) Insert new customer\n" "3) Destroy\n" "4) Launch Nasal Demons\n" "Enter selection: "; static const size_t Menu_Text_Length = sizeof(Menu_Text) - sizeof('\0'); //... std::cout.write(Menu_Text, Menu_Text_Length); 

L'efficacia di questa tecnica può essere dimostrata visivamente. 🙂

Non usare la famiglia printf per dati costanti

I dati costanti possono essere emessi usando una scrittura di blocco. La scrittura formattata perderà tempo durante la scansione del testo per la formattazione dei caratteri o l'elaborazione dei comandi di formattazione. Vedi esempio di codice sopra.

Formattare sulla memoria, quindi scrivere

Formattare su un array di char utilizzando più sprintf , quindi utilizzare fwrite . Ciò consente inoltre di suddividere il layout dei dati in "sezioni costanti" e sezioni variabili. Pensa alla fusione in serie .

Dichiara il testo costante (stringhe letterali) come static const

Quando le variabili vengono dichiarate senza static , alcuni compilatori possono allocare spazio nello stack e copiare i dati dalla ROM. Queste sono due operazioni non necessarie. Questo può essere risolto utilizzando il prefisso static .

Infine, codice come il compilatore

A volte, il compilatore può ottimizzare diverse piccole affermazioni meglio di una versione complicata. Inoltre, anche la scrittura di codice per aiutare il compilatore a ottimizzare aiuta. Se voglio che il compilatore usi le istruzioni speciali per il trasferimento a blocchi, scriverò un codice che dovrebbe usare le istruzioni speciali.

L’ottimizzatore non ha realmente il controllo delle prestazioni del tuo programma, lo sei. Utilizzare algoritmi e strutture appropriati e profilo, profilo, profilo.

Detto questo, non si dovrebbe eseguire il loop interno su una piccola funzione da un file in un altro file, poiché ciò impedisce di essere in linea.

Evita di prendere l’indirizzo di una variabile se ansible. Chiedere un puntatore non è “libero” in quanto significa che la variabile deve essere mantenuta in memoria. Anche un array può essere tenuto nei registri se si evitano i puntatori: questo è essenziale per la vettorizzazione.

Che porta al punto successivo, leggi il manuale ^ # $ @ ! GCC può vectorizzare il codice C semplice se si spruzza un __restrict__ qui e un __attribute__( __aligned__ ) lì. Se desideri qualcosa di molto specifico dall’ottimizzatore, potresti dover essere specifico.

Nella maggior parte dei processori moderni, il collo di bottiglia più grande è la memoria.

Aliasing: Load-Hit-Store può essere devastante in un ciclo stretto. Se stai leggendo una posizione di memoria e scrivi a un altro e sai che sono disgiunti, mettere accuratamente una parola chiave alias sui parametri della funzione può davvero aiutare il compilatore a generare codice più veloce. Tuttavia, se le regioni di memoria si sovrappongono e si utilizza “alias”, si ha una buona sessione di debug dei comportamenti non definiti!

Cache-miss: Non è proprio sicuro come si possa aiutare il compilatore dal momento che è per lo più algoritmico, ma ci sono elementi intrinseci per il precaricamento della memoria.

Inoltre, non provare a convertire troppo i valori in virgola mobile in int e viceversa perché utilizzano registri diversi e la conversione da un tipo all’altro significa chiamare l’effettiva istruzione di conversione, scrivere il valore in memoria e leggerlo nel set di registri corretto .

La stragrande maggioranza del codice che le persone scrivono sarà vincasting all’I / O (credo che tutto il codice che ho scritto per soldi negli ultimi 30 anni sia stato così vincolato), quindi le attività dell’ottimizzatore per la maggior parte delle persone saranno accademiche.

Tuttavia, vorrei ricordare alla gente che per ottimizzare il codice devi dire al compilatore di ottimizzarlo – un sacco di persone (incluso me quando dimentico) post benchmark C ++ qui che sono prive di significato senza che l’ottimizzatore sia abilitato.

usa la correttezza const il più ansible nel tuo codice. Permette al compilatore di ottimizzare molto meglio.

In questo documento ci sono molti altri suggerimenti per l’ottimizzazione: ottimizzazioni CPP (un po ‘vecchio documento)

mette in risalto:

  • utilizzare gli elenchi di inizializzazione del costruttore
  • utilizzare operatori di prefissi
  • utilizzare costruttori espliciti
  • funzioni inline
  • evitare oggetti temporanei
  • essere consapevoli del costo delle funzioni virtuali
  • restituire oggetti tramite parametri di riferimento
  • considerare per l’allocazione di class
  • considerare gli allocatori di container stl
  • l’ottimizzazione del ‘membro vuoto’
  • eccetera

Tentare di programmare il più ansible utilizzando l’assegnazione singola statica. SSA è esattamente la stessa cosa che si ottiene con la maggior parte dei linguaggi di programmazione funzionali, ed è quello che la maggior parte dei compilatori convertono il tuo codice a fare le sue ottimizzazioni perché è più facile lavorare con. In questo modo vengono messi in luce i luoghi in cui il compilatore potrebbe essere confuso. Inoltre fa sì che tutti gli allocatori di registro tranne il peggiore funzionino come i migliori allocatori di registro e ti permetta di eseguire il debug più facilmente perché non ti devi quasi mai chiedere da dove una variabile ha ottenuto il suo valore in quanto vi era un solo posto assegnato.
Evita le variabili globali.

Quando lavori con i dati per riferimento o con il puntatore, trascinalo nelle variabili locali, fai il tuo lavoro e poi copialo. (a meno che tu non abbia una buona ragione per non farlo)

Utilizza il confronto quasi gratuito con 0 che la maggior parte dei processori ti fornisce quando esegui operazioni matematiche o logiche. Ottieni quasi sempre un flag per == 0 e <0, da cui puoi facilmente ottenere 3 condizioni:

 x= f(); if(!x){ a(); } else if (x<0){ b(); } else { c(); } 

è quasi sempre più economico del test per altre costanti.

Un altro trucco consiste nell'utilizzare la sottrazione per eliminare un confronto nel test dell'intervallo.

 #define FOO_MIN 8 #define FOO_MAX 199 int good_foo(int foo) { unsigned int bar = foo-FOO_MIN; int rc = ((FOO_MAX-FOO_MIN) < bar) ? 1 : 0; return rc; } 

Questo può molto spesso evitare un salto in linguaggi che causano cortocircuiti sulle espressioni booleane ed evita che il compilatore debba cercare di capire come gestire il mantenimento del risultato del primo confronto mentre si fa il secondo e poi combinarli. Questo potrebbe sembrare che abbia il potenziale per usare un registro extra, ma non lo fa quasi mai. Spesso non hai più bisogno di foo, e se lo fai rc non è ancora usato così può andare lì.

Quando si usano le funzioni di stringa in c (strcpy, memcpy, ...) ricorda cosa restituiscono - la destinazione! Puoi spesso ottenere codice migliore "dimenticando" la tua copia del puntatore a destinazione e riprendendola dal ritorno di queste funzioni.

Non trascurare mai l'opportunità di restituire esattamente la stessa cosa restituita dall'ultima funzione che hai chiamato. I compilatori non sono così bravi a raccoglierlo:

 foo_t * make_foo(int a, int b, int c) { foo_t * x = malloc(sizeof(foo)); if (!x) { // return NULL; return x; // x is NULL, already in the register used for returns, so duh } x->a= a; x->b = b; x->c = c; return x; } 

Ovviamente, potresti invertire la logica su questo se e solo avere un punto di ritorno.

(trucchi che ho ricordato più tardi)

Dichiarare le funzioni statiche quando puoi è sempre una buona idea. Se il compilatore può dimostrare a se stesso che ha contabilizzato ogni chiamante di una particolare funzione, allora può rompere le convenzioni di chiamata per quella funzione nel nome dell'ottimizzazione. I compilatori possono spesso evitare di spostare i parametri in registri o impilare le posizioni che in genere le funzioni chiamate si aspettano i loro parametri (deve deviare sia nella funzione chiamata sia nella posizione di tutti i chiamanti per farlo). Il compilatore può anche spesso trarre vantaggio dal sapere quale memoria e registra la funzione chiamata e deve evitare di generare codice per preservare valori variabili che si trovano in registri o posizioni di memoria che la funzione chiamata non disturba. Ciò funziona particolarmente bene quando ci sono poche chiamate a una funzione. Ciò ottiene gran parte del vantaggio del codice inlining, ma senza in realtà la definizione.

Ho scritto un compilatore C ottimizzante e qui ci sono alcune cose molto utili da considerare:

  1. Rendi statiche la maggior parte delle funzioni. Ciò consente alla propagazione costante interprocedurale e all’analisi alias di svolgere il proprio lavoro, altrimenti il ​​compilatore deve presumere che la funzione possa essere chiamata dall’esterno dell’unità di traduzione con valori completamente sconosciuti per i parametri. Se si guardano le librerie open source ben note, tutte contrassegnano le funzioni statiche ad eccezione di quelle che hanno veramente bisogno di essere esterne.

  2. Se si utilizzano variabili globali, contrassegnarle statiche e costanti, se ansible. Se sono inizializzati una sola volta (di sola lettura), è meglio usare un elenco di inizializzazione come const const static [] = {1,2,3,4}, altrimenti il ​​compilatore potrebbe non scoprire che le variabili sono in realtà costanti inizializzate e non riuscirà a sostituire i carichi dalla variabile con le costanti.

  3. MAI utilizzare un goto all’interno di un ciclo, il loop non verrà più riconosciuto dalla maggior parte dei compilatori e nessuna delle ottimizzazioni più importanti verrà applicata.

  4. Utilizzare i parametri del puntatore solo se necessario e contrassegnarli restringendo se ansible. Questo aiuta molto l’analisi alias perché il programmatore garantisce che non ci sia alias (l’analisi dell’alias interprocedurale è solitamente molto primitiva). Gli oggetti struct molto piccoli devono essere passati per valore, non per riferimento.

  5. Usa matrici invece di puntatori quando ansible, specialmente all’interno di loop (a [i]). Un array di solito offre più informazioni per l’analisi degli alias e dopo alcune ottimizzazioni verrà generato lo stesso codice (cercare la riduzione della forza del loop se curioso). Ciò aumenta anche la possibilità di applicare il movimento del codice loop-invariante.

  6. Prova a issare all’esterno delle chiamate ad anello a grandi funzioni o funzioni esterne che non hanno effetti collaterali (non dipende dall’iterazione del loop corrente). Piccole funzioni sono in molti casi in linea o convertite in elementi intrinseci facili da sollevare, ma potrebbero sembrare funzioni di grandi dimensioni che il compilatore abbia effetti collaterali quando in realtà non lo fanno. Gli effetti collaterali per le funzioni esterne sono completamente sconosciuti, ad eccezione di alcune funzioni della libreria standard che sono talvolta modellate da alcuni compilatori, rendendo ansible il movimento del codice loop-invariante.

  7. Quando si scrivono test con più condizioni, posizionare il più probabile per primo. se (a || b || c) dovrebbe essere se (b || a || c) se b è più probabile che sia vero rispetto agli altri. I compilatori di solito non sanno nulla dei possibili valori delle condizioni e di quali rami vengono presi di più (potrebbero essere conosciuti usando le informazioni del profilo, ma pochi programmatori lo usano).

  8. Usare un interruttore è più veloce di un test come se (a || b || … || z). Controlla prima se il compilatore lo fa automaticamente, alcuni lo fanno ed è più leggibile avere l’ if se.

Un piccolo consiglio stupido, ma che ti farà risparmiare quantità microscopiche di velocità e codice.

Passa sempre gli argomenti della funzione nello stesso ordine.

Se hai f_1 (x, y, z) che chiama f_2, dichiara f_2 come f_2 (x, y, z). Non dichiararlo come f_2 (x, z, y).

La ragione di ciò è che la piattaforma C / C ++ ABI (AKA calling convention) promette di passare argomenti in particolari registri e posizioni di stack. Quando gli argomenti sono già nei registri corretti, non devono spostarli.

Durante la lettura del codice smontato ho visto un ridicolo registro mescolarsi perché la gente non ha seguito questa regola.

Nel caso di sistemi embedded e codice scritto in C / C ++, cerco di evitare l’allocazione dynamic della memoria il più ansible. The main reason I do this is not necessarily performance but this rule of thumb does have performance implications.

Algorithms used to manage the heap are notoriously slow in some platforms (eg, vxworks). Even worse, the time that it takes to return from a call to malloc is highly dependent on the current state of the heap. Therefore, any function that calls malloc is going to take a performance hit that cannot be easily accounted for. That performance hit may be minimal if the heap is still clean but after that device runs for a while the heap can become fragmented. The calls are going to take longer and you cannot easily calculate how performance will degrade over time. You cannot really produce a worse case estimate. The optimizer cannot provide you with any help in this case either. To make matters even worse, if the heap becomes too heavily fragmented, the calls will start failing altogether. The solution is to use memory pools (eg, glib slices ) instead of the heap. The allocation calls are going to be much faster and deterministic if you do it right.

Two coding technics I didn’t saw in the above list:

Bypass linker by writing code as an unique source

While separate compilation is really nice for compiling time, it is very bad when you speak of optimization. Basically the compiler can’t optimize beyond compilation unit, that is linker reserved domain.

But if you design well your program you can can also compile it through an unique common source. That is instead of compiling unit1.c and unit2.c then link both objects, compile all.c that merely #include unit1.c and unit2.c. Thus you will benefit from all the compiler optimizations.

It’s very like writing headers only programs in C++ (and even easier to do in C).

This technique is easy enough if you write your program to enable it from the beginning, but you must also be aware it change part of C semantic and you can meet some problems like static variables or macro collision. For most programs it’s easy enough to overcome the small problems that occurs. Also be aware that compiling as an unique source is way slower and may takes huge amount of memory (usually not a problem with modern systems).

Using this simple technique I happened to make some programs I wrote ten times faster!

Like the register keyword, this trick could also become obsolete soon. Optimizing through linker begin to be supported by compilers gcc: Link time optimization .

Separate atomic tasks in loops

This one is more tricky. It’s about interaction between algorithm design and the way optimizer manage cache and register allocation. Quite often programs have to loop over some data structure and for each item perform some actions. Quite often the actions performsd can be splitted between two logically independent tasks. If that is the case you can write exactly the same program with two loops on the same boundary performing exactly one task. In some case writing it this way can be faster than the unique loop (details are more complex, but an explanation can be that with the simple task case all variables can be kept in processor registers and with the more complex one it’s not possible and some registers must be written to memory and read back later and the cost is higher than additional flow control).

Be careful with this one (profile performances using this trick or not) as like using register it may as well give lesser performances than improved ones.

I’ve actually seen this done in SQLite and they claim it results in performance boosts ~5%: Put all your code in one file or use the preprocessor to do the equivalent to this. This way the optimizer will have access to the entire program and can do more interprocedural optimizations.

Most modern compilers should do a good job speeding up tail recursion , because the function calls can be optimized out.

Esempio:

 int fac2(int x, int cur) { if (x == 1) return cur; return fac2(x - 1, cur * x); } int fac(int x) { return fac2(x, 1); } 

Of course this example doesn’t have any bounds checking.

Late Edit

While I have no direct knowledge of the code; it seems clear that the requirements of using CTEs on SQL Server were specifically designed so that it can optimize via tail-end recursion.

Don’t do the same work over and over again!

A common antipattern that I see goes along these lines:

 void Function() { MySingleton::GetInstance()->GetAggregatedObject()->DoSomething(); MySingleton::GetInstance()->GetAggregatedObject()->DoSomethingElse(); MySingleton::GetInstance()->GetAggregatedObject()->DoSomethingCool(); MySingleton::GetInstance()->GetAggregatedObject()->DoSomethingReallyNeat(); MySingleton::GetInstance()->GetAggregatedObject()->DoSomethingYetAgain(); } 

The compiler actually has to call all of those functions all of the time. Assuming you, the programmer, knows that the aggregated object isn’t changing over the course of these calls, for the love of all that is holy…

 void Function() { MySingleton* s = MySingleton::GetInstance(); AggregatedObject* ao = s->GetAggregatedObject(); ao->DoSomething(); ao->DoSomethingElse(); ao->DoSomethingCool(); ao->DoSomethingReallyNeat(); ao->DoSomethingYetAgain(); } 

In the case of the singleton getter the calls may not be too costly, but it is certainly a cost (typically, “check to see if the object has been created, if it hasn’t, create it, then return it). The more complicated this chain of getters becomes, the more wasted time we’ll have.

  1. Use the most local scope possible for all variable declarations.

  2. Use const whenever possible

  3. Dont use register unless you plan to profile both with and without it

The first 2 of these, especially #1 one help the optimizer analyze the code. It will especially help it to make good choices about what variables to keep in registers.

Blindly using the register keyword is as likely to help as hurt your optimization, It’s just too hard to know what will matter until you look at the assembly output or profile.

There are other things that matter to getting good performance out of code; designing your data structures to maximize cache coherency for instance. But the question was about the optimizer.

Align your data to native/natural boundaries.

I was reminded of something that I encountered once, where the symptom was simply that we were running out of memory, but the result was substantially increased performance (as well as huge reductions in memory footprint).

The problem in this case was that the software we were using made tons of little allocations. Like, allocating four bytes here, six bytes there, etc. A lot of little objects, too, running in the 8-12 byte range. The problem wasn’t so much that the program needed lots of little things, it’s that it allocated lots of little things individually, which bloated each allocation out to (on this particular platform) 32 bytes.

Part of the solution was to put together an Alexandrescu-style small object pool, but extend it so I could allocate arrays of small objects as well as individual items. This helped immensely in performance as well since more items fit in the cache at any one time.

The other part of the solution was to replace the rampant use of manually-managed char* members with an SSO (small-string optimization) string. The minimum allocation being 32 bytes, I built a string class that had an embedded 28-character buffer behind a char*, so 95% of our strings didn’t need to do an additional allocation (and then I manually replaced almost every appearance of char* in this library with this new class, that was fun or not). This helped a ton with memory fragmentation as well, which then increased the locality of reference for other pointed-to objects, and similarly there were performance gains.

A neat technique I learned from @MSalters comment on this answer allows compilers to do copy elision even when returning different objects according to some condition:

 // before BigObject a, b; if(condition) return a; else return b; // after BigObject a, b; if(condition) swap(a,b); return a; 

If you’ve got small functions you call repeatedly, i have in the past got large gains by putting them in headers as “static inline”. Function calls on the ix86 are surprisingly expensive.

Reimplementing recursive functions in a non-recursive way using an explicit stack can also gain a lot, but then you really are in the realm of development time vs gain.

Here’s my second piece of optimisation advice. As with my first piece of advice this is general purpose, not language or processor specific.

Read the compiler manual thoroughly and understand what it is telling you. Use the compiler to its utmost.

I agree with one or two of the other respondents who have identified selecting the right algorithm as critical to squeezing performance out of a program. Beyond that the rate of return (measured in code execution improvement) on the time you invest in using the compiler is far higher than the rate of return in tweaking the code.

Yes, compiler writers are not from a race of coding giants and compilers contain mistakes and what should, according to the manual and according to compiler theory, make things faster sometimes makes things slower. That’s why you have to take one step at a time and measure before- and after-tweak performance.

And yes, ultimately, you might be faced with a combinatorial explosion of compiler flags so you need to have a script or two to run make with various compiler flags, queue the jobs on the large cluster and gather the run time statistics. If it’s just you and Visual Studio on a PC you will run out of interest long before you have tried enough combinations of enough compiler flags.

Saluti

marchio

When I first pick up a piece of code I can usually get a factor of 1.4 — 2.0 times more performance (ie the new version of the code runs in 1/1.4 or 1/2 of the time of the old version) within a day or two by fiddling with compiler flags. Granted, that may be a comment on the lack of compiler savvy among the scientists who originate much of the code I work on, rather than a symptom of my excellence. Having set the compiler flags to max (and it’s rarely just -O3) it can take months of hard work to get another factor of 1.05 or 1.1

When DEC came out with its alpha processors, there was a recommendation to keep the number of arguments to a function under 7, as the compiler would always try to put up to 6 arguments in registers automatically.

For performance, focus first on writing maintenable code – componentized, loosely coupled, etc, so when you have to isolate a part either to rewrite, optimize or simply profile, you can do it without much effort.

Optimizer will help your program’s performance marginally.

You’re getting good answers here, but they assume your program is pretty close to optimal to begin with, and you say

Assume that the program has been written correctly, compiled with full optimization, tested and put into production.

In my experience, a program may be written correctly, but that does not mean it is near optimal. It takes extra work to get to that point.

If I can give an example, this answer shows how a perfectly reasonable-looking program was made over 40 times faster by macro-optimization . Big speedups can’t be done in every program as first written, but in many (except for very small programs), it can, in my experience.

After that is done, micro-optimization (of the hot-spots) can give you a good payoff.

i use intel compiler. on both Windows and Linux.

when more or less done i profile the code. then hang on the hotspots and trying to change the code to allow compiler make a better job.

if a code is a computational one and contain a lot of loops – vectorization report in intel compiler is very helpful – look for ‘vec-report’ in help.

so the main idea – polish the performance critical code. as for the rest – priority to be correct and maintainable – short functions, clear code that could be understood 1 year later.

One optimization i have used in C++ is creating a constructor that does nothing. One must manually call an init() in order to put the object into a working state.

This has benefit in the case where I need a large vector of these classs.

I call reserve() to allocate the space for the vector, but the constructor does not actually touch the page of memory the object is on. So I have spent some address space, but not actually consumed a lot of physical memory. I avoid the page faults associated the associated construction costs.

As i generate objects to fill the vector, I set them using init(). This limits my total page faults, and avoids the need to resize() the vector while filling it.

One thing I’ve done is try to keep expensive actions to places where the user might expect the program to delay a bit. Overall performance is related to responsiveness, but isn’t quite the same, and for many things responsiveness is the more important part of performance.

The last time I really had to do improvements in overall performance, I kept an eye out for suboptimal algorithms, and looked for places that were likely to have cache problems. I profiled and measured performance first, and again after each change. Then the company collapsed, but it was interesting and instructive work anyway.

I have long suspected, but never proved that declaring arrays so that they hold a power of 2, as the number of elements, enables the optimizer to do a strength reduction by replacing a multiply by a shift by a number of bits, when looking up individual elements.

Put small and/or frequently called functions at the top of the source file. That makes it easier for the compiler to find opportunities for inlining.