Quali sono i tuoi trucchi di ottimizzazione del codice di basso livello preferiti?

Question

So che dovresti ottimizzare le cose solo quando è ritenuto necessario. Ma, se è ritenuto necessario, quali sono i tuoi trucchi di ottimizzazione preferiti a basso livello (al contrario di livello algoritmico).

Ad esempio: loop unrolling.

Answer 1

gcc -O2 

I compilatori fanno molto più lavoro di quanto si possa.

Answer 2

++i può essere più veloce di i++, perché evita la creazione di una temporanea.

Se questo è ancora valido per i compilatori C/C++/Java/C# moderni, non lo so. Potrebbe essere diverso per i tipi definiti dall'utente con operatori sovraccaricati, mentre nel caso di numeri interi semplici probabilmente non ha importanza.

Ma a me è piaciuta la sintassi ... si legge come "incrementa i" che è un ordine ragionevole.

Answer 3

Sollevare una potenza di due per filtri, tamponi circolari ecc

Quindi molto, molto comodo.

-Adam

Answer 4

Conto alla rovescia un ciclo. E 'più economico da confrontare con 0 di N:

for (i = N; --i >= 0;) ... 

spostamento e mascheramento per potenze di due è più conveniente di divisione e resto,/e%

#define WORD_LOG 5 
#define SIZE (1 << WORD_LOG) 
#define MASK (SIZE - 1) 

uint32_t bits[K] 

void set_bit(unsigned i) 
{ 
    bits[i >> WORD_LOG] |= (1 << (i & MASK)) 
} 

Modifica

(i >> WORD_LOG) == (i/SIZE) and 
(i & MASK) == (i % SIZE) 

perché SIZE è 32 o 2^5.

Answer 5

• Riciclaggio del frame-pointer all'improvviso
• Pascal chiamante convenzione
• riscrittura stack frame di chiamata coda optimizarion (anche se talvolta pasticci con quanto sopra)
• Utilizzando vfork() anziché fork() prima exec()
• E quello che sto ancora cercando, una scusa per usare: i dati guidata di generazione di codice a runtime

Answer 6

Ispeziona l'output del compilatore, quindi prova a forzarlo a fare qualcosa più velocemente.

Answer 7

Perché, bit twiddling hacks, ovviamente!

Answer 8

Allocazione con nuovo su un buffer preassegnato utilizzando il posizionamento di C++ nuovo.

Answer 9

Utilizzo della metaprogrammazione del modello per calcolare le cose in fase di compilazione anziché in fase di esecuzione.

Answer 10

Uno dei più utili nel codice scientifico è quello di sostituire pow(x,4) con x*x*x*x.Pow è quasi sempre più costoso della moltiplicazione. Questo è seguito da

for(int i = 0; i < N; i++) 
    { 
    z += x/y; 
    } 

a

double denom = 1/y; 
    for(int i = 0; i < N; i++) 
    { 
    z += x*denom; 
    } 

Ma il mio preferito di ottimizzazione a basso livello è quello di capire quali calcoli possono essere rimossi da un ciclo. È sempre più veloce eseguire il calcolo una volta anziché N volte. A seconda del compilatore, alcuni di questi potrebbero essere fatti automaticamente per te.

Answer 11

In SQL, se avete solo bisogno di sapere se esiste o meno tutti i dati, non perdere tempo con COUNT(*):

SELECT 1 FROM table WHERE some_primary_key = some_value 

Se la clausola WHERE è probabile tornare più righe, aggiungere un LIMIT 1 troppo.

(Ricordate che i database non possono vedere che cosa il vostro codice sta facendo con i loro risultati, in modo che non possono ottimizzare queste cose via da soli!)

Answer 12

Ho scoperto che il passaggio da un puntatore ad accesso indicizzato può fare la differenza; il compilatore ha diverse forme di istruzione e registra gli usi tra cui scegliere. Viceversa, anche. Questo è estremamente basso livello e dipendente dal compilatore, però, e va bene solo quando serve l'ultimo percento.

E.g.

for (i = 0; i < n; ++i) 
    *p++ = ...; // some complicated expression 

vs.

for (i = 0; i < n; ++i) 
    p[i] = ...; // some complicated expression 

Answer 13

anni fa con un compilier non-così-intelligente, ho ricevuto grande distanza in miglia dalla funzione inline, camminando puntatori invece di array di indicizzazione, e l'iterazione fino a zero, invece di up al massimo.

In caso di dubbio, un po 'di conoscenza di assemblea vi permetterà di guardare a ciò che il compilatore sta producendo e attaccare le parti inefficienti (nella lingua di partenza, utilizzando le strutture più amichevole per il vostro compilatore.)

Answer 14

non lo farei necessariamente lo definisco un'ottimizzazione di basso livello, ma ho risparmiato ordini di grandezza di più cicli attraverso un'applicazione giudiziosa del caching di quante ne abbia in tutte le mie applicazioni di trucchi di basso livello combinati. Molti di questi metodi sono specifici per le applicazioni.

• Avere una cache LRU di query di database (o qualsiasi altra richiesta basata su IPC).
• Memorizzare l'ultima query del database non riuscita e restituire un errore se richiesto nuovamente entro un determinato intervallo di tempo.
• Ricordare la posizione in una struttura di dati di grandi dimensioni per garantire che se la richiesta successiva è per lo stesso nodo, la ricerca è gratuita.
• Risultati del calcolo di memorizzazione nella cache per impedire il doppio lavoro. Oltre agli scenari più complessi, questo si trova spesso nelle dichiarazioni if o for.

CPU e compilatori cambiano continuamente. Qualunque trucco di codice di basso livello che avesse senso 3 chip della CPU fa con un compilatore diverso potrebbe in effetti essere più lento nell'architettura corrente e ci potrebbero essere buone probabilità che questo trucco possa confondere chiunque stia mantenendo questo codice in futuro.

Answer 15

valori di calcolo preliminare.

Ad esempio, invece di sin (a) o cos (a), se l'applicazione non ha necessariamente bisogno di angoli per essere molto precisi, forse si rappresentano gli angoli in 1/256 di un cerchio e si creano matrici di galleggianti seno [] e coseno [] precalcolano il peccato e il cos di quegli angoli.

E, se è necessario frequentemente un vettore con un certo angolo di una determinata lunghezza, è possibile calcolare preventivamente tutti quei seni e coseni già moltiplicati per quella lunghezza.

Oppure, per dirla in modo più generale, scambia la memoria per la velocità.

O, anche, più in generale, "Tutta la programmazione è un esercizio di caching" - Terje Mathisen

Alcune cose sono meno evidenti. Per esempio attraversare una matrice bidimensionale, si potrebbe fare qualcosa di simile

 
    for (x=0;x<maxx;x++) 
     for (y=0;y<maxy;y++) 
      do_something(a[x,y]); 

Si potrebbe trovare la cache del processore piace meglio se lo fai:

 
    for (y=0;y<maxy;y++) 
     for (x=0;x<maxx;x++) 
      do_something(a[x,y]); 

o viceversa.

Answer 16

Non eseguire cicli di srotolamento. Non fare il dispositivo di Duff. Rendi il tuo loop il più piccolo possibile, qualsiasi altra cosa inibisce le prestazioni x86 e le prestazioni dell'ottimizzatore gcc.

L'eliminazione dei rami può essere utile, tuttavia, eliminare completamente i loop è una buona cosa, e quei trucchi matematici senza rami funzionano davvero. Oltre a ciò, cerca di non uscire mai dalla cache L2 - questo significa che si dovrebbe evitare un sacco di precalcolo/memorizzazione nella cache se si spreca spazio nella cache.

E, soprattutto per x86, provare a mantenere il numero di variabili in uso in qualsiasi momento. È difficile dire cosa faranno i compilatori con quel genere di cose, ma di solito con meno variabili di iterazione di loop/indici di array si otterrà un output di asm migliore.

Naturalmente, questo è per le CPU desktop; una CPU lenta con accesso veloce alla memoria può precalcolare molto di più, ma in questi giorni potrebbe essere un sistema integrato con poca memoria totale comunque ...

Answer 17

Jon Bentley Writing Efficient Programs è una grande fonte di tecniche di livello basso e alto - se riesci a trovare una copia.

Answer 18

rami Eliminare (se/qualcun'altro) utilizzando la matematica booleana:

if(x == 0) 
    x = 5; 

// becomes: 

x += (x == 0) * 5; 
// if '5' was a base 2 number, let's say 4: 
x += (x == 0) << 2; 

// divide by 2 if flag is set 
sum >>= (blendMode == BLEND); 

Questo velocizza veramente le cose, soprattutto quando questi IFS sono in un ciclo o da qualche parte che viene chiamato un sacco.

Answer 19

Uso libero di __restrict per eliminare le bancarelle di carico-hit-store.

Answer 20

Quello da Assembler:

xor ax, ax 

invece di:

mov ax, 0 

ottimizzazione classica per le dimensioni e le prestazioni del programma.

Answer 21

Ottimizzazione della località cache, ad esempio quando si moltiplicano due matrici che non si adattano alla cache.

Answer 22

Rolling up loop.

Seriamente, l'ultima volta che avevo bisogno di fare qualcosa di simile era in una funzione che richiedeva l'80% del tempo di esecuzione, quindi valeva la pena provare a micro-ottimizzare se potessi ottenere un notevole aumento delle prestazioni.

La prima cosa che ho fatto è stato di arrotolare il ciclo. Questo mi ha dato un aumento di velocità molto significativo. Credo che questa fosse una questione di località cache.

La prossima cosa che ho fatto è stato aggiungere uno strato di riferimento indiretto e inserire un po 'di logica nel loop, che mi ha permesso di scorrere solo le cose di cui avevo bisogno. Questo non era un aumento di velocità, ma valeva la pena farlo.

Se si esegue un'ottimizzazione micro, è necessario avere un'idea ragionevole di due elementi: l'architettura che si sta effettivamente utilizzando (che è molto diversa dai sistemi con cui sono cresciuto, almeno per i micro- scopi di ottimizzazione) e cosa farà il compilatore per te.

Molte delle tradizionali micro-ottimizzazioni scambiano spazio per il tempo. Oggigiorno, usare più spazio aumenta le possibilità di perdere la cache, e ci sono le tue prestazioni. Inoltre, molti di questi sono ora realizzati da compilatori moderni, e in genere migliori di quanto sia probabile che li facciano.

Attualmente, è necessario (a) un profilo per vedere se è necessario eseguire l'ottimizzazione micro, e quindi (b) provare a scambiare il calcolo per lo spazio, nella speranza di conservare il più possibile nella cache. Infine, esegui alcuni test, così sai se hai migliorato le cose o le hai rovinate. I moderni compilatori e chip sono troppo complessi per poter mantenere un buon modello mentale e l'unico modo per sapere se l'ottimizzazione funziona o meno è testare.

Answer 23

Oltre al commento di Joshua sulla generazione di codice (una grande vittoria), e altri buoni suggerimenti, ...

non sono sicuro se si desidera chiamare "a basso livello", ma (e questo è downvote-bait) 1) stai lontano dall'usare altri livelli di astrazione di quanto assolutamente necessario, e 2) stai lontano dalla programmazione in stile notifica event-driven, se possibile.

1. Se un computer esecuzione di un programma è come una macchina che corre una gara, una chiamata di metodo è come una deviazione. Questo non è necessariamente negativo, tranne che c'è una forte tentazione di annidare quelle cose, perché una volta che hai scritto una chiamata al metodo, tendi a dimenticare ciò che questa chiamata potrebbe costarti.

2. Se ti affidi a eventi e notifiche, è perché hai più strutture dati che devono essere mantenute d'accordo. Questo è costoso e dovrebbe essere fatto solo se non puoi evitarlo.

Nella mia esperienza, i più grandi assassini di prestazioni sono troppa struttura dati e troppa astrazione.

Answer 24

Sono rimasto stupito l'aumento di velocità ho ottenuto sostituendo una per i numeri di loop sommando in struct:

const unsigned long SIZE = 100000000; 

typedef struct { 
    int a; 
    int b; 
    int result; 
} addition; 

addition *sum; 

void start() { 
    unsigned int byte_count = SIZE * sizeof(addition); 

    sum = malloc(byte_count); 
    unsigned int i = 0; 

    if (i < SIZE) { 
     do { 
      sum[i].a = i; 
      sum[i].b = i; 
      i++; 
     } while (i < SIZE); 
    }  
} 

void test_func() { 
    unsigned int i = 0; 

    if (i < SIZE) { // this is about 30% faster than the more obvious for loop, even with O3 
     do { 
      addition *s1 = &sum[i]; 
      s1->result = s1->b + s1->a; 
      i++; 
     } while (i<SIZE); 
    } 
} 

void finish() { 
    free(sum); 
} 

Perché non gcc ottimizzare i cicli for in questo? O c'è qualcosa che ho perso? Qualche effetto cache?