Ottimizzazioni - STB1019/SkullOfSummer GitHub Wiki

Introduzione

In questa sezione andremo ad analizzare come si può ottimizzare il programma rendendolo più veloce. Un avvertimento prima di continuare: in informatica è molto facile sbagliare e creare codice incomprensibile scrivendo codice fin da subito velocissimo. Quindi è pratica buona e giusta, scrivere prima codice corretto (anche lento) e poi ottimizzarlo. Detto questo il compilatore fornisce dei mezzi per ottimizzare in maniera automatica e semiautomatica il proprio codice.

Elenco dei vari metodi per ottimizzare

Ci sono diversi modi per ottimizzare il proprio codice, sia in modo automatico, che semi automatico, che totalmente manuale.

Flag di compilazione

Di default è possibile compilare il proprio codice sorgente con vari livelli di ottimizzazione: ad ogni livello il compilatore attiverà o meno alcune ottimizzazioni del codice macchina. Più ottimizzazioni attivi, più tempo il compilatore impiegherà per compilare. Tuttavia quel tempo lo spenderà a ricercare modi per evitare di eseguire istruzioni macchina. Dato un programma main.c, per ottimizzare automaticamente il proprio programma sono disponibile vari livelli di ottimizzazione:

gcc -c -O1 main.c
gcc -c -O2 main.c
gcc -c -O3 main.c //massima ottimizzazione possibile
gcc -c -Os main.c //ottimizza in modo da ridurre lo spazio occupato dal tuo programma (dimensioni piccole)

Assicurati di attivare queste flag solo quando sei sicuro della correttezza del programma: le flag di ottimizzazione automatica non vanno affatto d'accordo con le flag di debug -g, quindi se hai un problema con il codice, non potrai debuggarlo con gdb o valgrind. Nota molto importante è che le ottimizzazioni sono modifiche che possono alterare il comportamento del tuo programma se non hai programmato correttamente: quindi occhio!

Variabili register

Se hai una variabile che usi veramente spesso (sia in lettura che in scrittura) e che sia abbastanza piccola, puoi esplicitamente dire al compilatore di allocare quella variabile non in RAM, ma direttamente in un registro della CPU: fare ciò consente di leggere e scrivere quella variabile alla massima velocità possibile. Puoi dichiarare una qualunque variabile abbastanza piccola in questo modo. Per esempio:

void bigAnalysis() {
    register int i = 0;
    //the function reads and writes i thousands of times!
}

Si usa poco perché solitamente il compilatore (almeno il GCC) riesce ad individuare le migliori variabili da posizionare automaticamente nei registri.

Restrict reserved word

Restrict è una parola chiave (almeno da C99) da abbinare con una dichiarazione di un puntatore.

int* p; //dichiarazione normale di un puntatore
int* restrict p; //dichiarazione ristretta di una puntatore

In generale un puntatore si riferisce ad un particolare valore. Consideriamo una funzione che accetta vari puntatori:

int increase(int* a, int* b, int* c) {
    *a = *a + *c;
    *b = *b + *c;
}

Se generiamo il codice assembly della funzione tramite il comando:

gcc -S -O3 -o increase.s increase.c

Quello che otteniamo è una cosa simile a quella specificata in Assembler output. Si può notare come il compilatore sia stato forzato ad aggiungere un'istruzione in più all'interno del codice assembly generato perché è possibile che il puntatore a ed il puntatore c puntino allo stesso valore. Ipotizziamo ora che noi (come sviluppatori) vogliamo dire al compilatore che per noi quei 3 puntatori saranno sempre 3 puntatori che riferiscono a 3 aree di memoria diverse. Per esempio la funzione increase è usata da noi solo per incrementare a e b, che sono 2 contatori all'interno di 2 cicli while. Normalmente non ci sarebbe alcun modo per trasmettere questa informazione al compilatore. Con la reserved word restrict possiamo fare ciò:

non appena il compilatore vede un puntatore qualificato con "restrict", esso assume che l'area di memoria puntata da quel particolare puntatore non sia puntata da nessun altro puntatore nello scope considerato. Per esempio non può avvenire la situazione in figura:

alias

In altre parole, non ci sono altri alias per quel particolare valore. Se modifichiamo quindi la nostra funzione increase con "restrict" otteniamo:

int increase(int* restrict a, int* restrict b, int* restrict c) {
    *a = *a + *c;
    *b = *b + *c;
}

Ora abbiamo detto che i 3 puntatori non sono alias di altri puntatori nello scope (in questo caso lo scope è formato solo dai 3 parametri locali della funzione). Il compilatore, sapendo ciò, può quindi generare codice macchina più compatto. Il codice generato è disponibile qui (generato tramite gcc -S -O3 -o withrestrict.s withrestrict.c).

Il diff tra i 2 output assembler (senza commenti) è il seguente:

1c1
< 	.file	"baserestrict.c"
---
> 	.file	"withrestrict.c"
14d13
< 	movl	(%rdx), %eax

Nell'esempio non abbiamo compattato molto, ma è fondamentale per capire l'idea alla base. Puoi provare a usare lo script nella repository per testare restrict:

./compileTestRestrict.bash
./testWithRestrict 18 && ./testWithoutRestrict 18

Il contratto di restrict

Usare restrict implica che lo sviluppatore stipuli un contratto con il compilatore e che prometta che non inserirà alias di puntatori ristretti. Fondamentalmente deve accettare il seguente contratto:

THE RESTRICT CONTRACT I, [insert your name], a PROFESSIONAL or AMATEUR [circle one] programmer recognize that there are limits to what a compiler can do. I certify that, to the best of my knowledge, there are no magic elves or monkeys in the compiler which through the forces of fairy dust can always make code faster. I understand that there are some problems for which there is not enough information to solve. I hereby declare that given the opportunity to provide the compiler with sufficient information, perhaps through some key word, I will gladly use said keyword and not bitch and moan about how "the compiler should be doing this for me."

In this case, I promise that the pointer declared along with the restrict qualifier is not aliased. I certify that writes through this pointer will not effect the values read through any other pointer available in the same context which is also declared as restricted.

  • Your agreement to this contract is implied by use of the restrict keyword ;)

Esempi di incoerenza con il contratto di restrict

Cosa succede se noi non rispettiamo il contratto di restrict? Problematiche veramente complicate da debuggare!. Ne diamo un esempio qui (ispirato all'esempio fornito da Fasselt).

Inline reserved word

Uno dei metodi più usati per programmare è quello del dividere task complessi in task via via sempre più piccoli e semplici in modo da gestire la complessità del task iniziale. Questo approccio spesso codifica i sottoproblemi in funzioni c. Scrivere funzioni che richiamano altre funzioni per risolvere il problema è ottimo, ma ha uno svantaggio spesso ignorato: ogni chiamata a funzione ha un costo: vengono posizionati dati sullo stack, si effettuano dei salti di puntatore. Questo spesso non è rilevante, ma se noi abbiamo codificato una funzione semplicissima (una riga o 2), ma chiamata un sacco di volte, queste operazioni potrebbero incidere sulle prestazioni. inline tenta di risolvere questa problematica.

Definizione

Una funzione è inline se, dopo la fase di compilazione, essa non ha più una sezione dedicata nel codice assembly, ma il suo codice è stato inserito all'interno del codice del chiamante direttamente. Il gcc, normalmente, spesso riesce a trovare funzioni papabili per diventare funzioni inline più o meno da solo. Per esempio, dato il codice:

#include <stdio.h>
int fInline(int a, int b) {
return a + b;
}
int main() {
int a = 7;
int b = 42;
int c = fInline(a, b);
printf("%d\n", c);
}

Proviamo a vedere cosa succede quando compiliamo senza ottimizzazioni e cosa succede quando compiliamo con ottimizzazioni (i file ed i risultati sono disponibili in testInline.c, compilazione senza ottimizzazioni e compilazione con ottimizzazioni: se proviamo a guardare testInlineOO.s ci accorgeremo che nella funzione main viene effettivamente chiamata una funzione fInline. Tuttavia, in testInlienO3.s questa chiamata a funzione non compare: il codice di fInline è stato ritenuto dal compilatore degno di essere incorporato all'interno della funzione chiamante, leggasi main.

La reserved word

E' possibile non lasciar fare tutto al compilatore ma dargli dei suggerimenti su quali funzioni, secondo te, meritino di essere incorporate nelle funzioni chiamanti. Chiaramente sono solo dei suggerimenti: il compilatore può, se lo ritiene necessario, ignorarli. Questi suggerimenti sono realizzati dalla reserved word inline. Per esempio:

inline int fInline(int a, int b) {
    return a + b;
}

Quando si usa?

Inline può essere usato:

  1. su una definizione di una funzione statica;
  2. su una definizione di una funzione che è stata precedentemente dichiarata non "inline".

Per il primo caso:

static inline int fInline(int a, int b) {
    return a + b;
}

Per il secondo caso:

int fInline(int a, int b); //dichiarazione
inline fInline(int a, int b) { //definizione
    return a + b;
}

Questo secondo caso è ottimo quando si lavora con le libreria (la dichiarazione è nell'header, mentre la definizione è nel source code).

Riferimenti

Vai alla Home della Skull of Summer

⚠️ **GitHub.com Fallback** ⚠️