Nei titoli e nei testi troverete qualche rimando cinematografico (ebbene si, sono un cinefilo). Se non vi interessano fate finta di non vederli, già che non sono fondamentali per la comprensione dei post...

Di questo blog ho mandato avanti, fino a Settembre 2018, anche una versione in Spagnolo. Potete trovarla su El arte de la programación en C. Buona lettura.

lunedì 6 maggio 2019

2001: Odissea nell'ottimizzazione
considerazioni sull'ottimizzazione del codice in C

HAL9000: Nessun calcolatore 9000 ha mai commesso un errore o alterato un'informazione. Noi siamo, senza possibili eccezioni di sorta, a prova di errore, e incapaci di sbagliare.
In 2001: Odissea nello spazio il computer HAL9000 era così sicuro di essere infallibile che sabotò la missione (oops: spoiler!... va beh, ma è un film del 1968, se non l'avete ancora visto sarà mica colpa mia...). Ecco, in questo articolo tratteremo un argomento spinoso, l'ottimizzazione del codice, che andrà a toccare miti e leggende (urbane) su cui molti colleghi programmatori hanno certezze magari un po' datate. Sarò costretto a dire delle eresie, delle cose poco ortodosse, ma cercherò, come sempre, di usare un linguaggio il più possibile soft, perché non mi sento ancora preparato per finire sul rogo dell'Inquisizione Informatica.
...ottimizzare il codice noonnnn serxyzh!!11wu?ve aaa nizxrn!!11mm-x?ente....
Come ho appena detto: un tema spinoso, su cui ho già scritto in passato. Ma i tempi cambiano, l'informatica avanza, i compilatori crescono e si fanno adulti... e il mio vecchio articolo è diventato obsoleto (anzi, peggio: deprecated), e non ho nessuna difficoltà ad ammetterlo (non sono mica HAL9000!): i risultati dei test di allora (era il 2012) ora non sono più validi. E quindi non sono più valide neanche le conclusioni. Comunque, prima di andare avanti vi spoilero il piano dell'articolo, così nessuno potrà dire che non vi avevo avvertito prima (potete saltare la lettura del piano se vi piacciono le sorprese: attenzione SPOILER):

Piano dell'articolo
  1. Le basi: la descrizione sommaria di cosa è e cosa non è una ottimizzazione.
  2. L'illusione: la descrizione di alcune promettenti forme di ottimizzazione (solo alcune tra le mille disponibili, eh!).
  3. La delusione: il test sperimentale che dimostra l'inutilità del punto 2.
  4. Il Gran Finale: le ultime considerazioni e le parole di un profeta che aveva già previsto tutto questo.
1. Le basi
Chiariamo subito una cosa: le ottimizzazioni di cui parleremo sono quelle strettamente legate al codice, alle istruzioni di base. Non si parla di algoritmi, perché è evidente che quelli si che devono essere ottimizzati: se voglio fare un sort dei valori in un grande array è meglio scrivere un quick-sort che un insertion-sort! E, tornando alle istruzioni di base, anche qui bisogna fare dei distinguo: ad esempio, se devo aggiungere cinque volte lo stesso un valore ad una variabile e lo faccio con un loop non è una ottimizzazione, è semplice senso comune! Quindi vediamo un po' di codice per spiegare meglio l'argomento:
#include <stdio.h>
#include <time.h>

// funzione main
int main(int argc, char ** argv)
{
    int array[5];

    // VERSIONE STUPIDA (senza senso comune)
    int i = 0;
    array[i] = i * 2;
    i++;
    array[i] = i * 2;
    i++;
    array[i] = i * 2;
    i++;
    array[i] = i * 2;
    i++;
    array[i] = i * 2;

    printf("Test 1: array[4] = %d\n", array[4]);

    // VERSIONE BASE (con senso comune)
    int n;
    for (n = 0; n < 5; n++)
        array[n] = n * 2;

    printf("Test 2: array[4] = %d\n", array[4]);

    // VERSIONE OTTIMIZZATA: è la base con shift logico invece di moltiplicazione
    int k;
    for (k = 0; k < 5; k++)
        array[k] = k << 1;

    printf("Test 3: array[4] = %d\n", array[4]);

    return 0;
}
Come si nota nel semplicissimo esempio, abbiamo un problema e lo possiamo risolvere in maniera "stupida", "normale" o "ottimizzata": sulla maniera "stupida" preferisco non commentare, mentre su quella ottimizzata faccio notare che ho usato uno Shift Logico al posto della (dispendiosa) moltiplicazione per due.

E per chiudere questa sezione non posso non citare una tra le tante Leggende Urbane che girano nella comunità C: quella secondo cui è meglio mettere la definizione di una variabile fuori da un loop "se no ogni volta che si entra nel loop viene allocata nuovamente e il programma rallenta"... Quindi, secondo alcuni, quando è stato introdotto nel C il concetto di scope grazie al quale possiamo (tra le altre cose) dichiarare e usare una variabile solo dove serve, si sono dimenticati di dirci di non usare questa caratteristica perché "rallenta il codice"... ma si, continuiamo così, facciamoci del male. Vabbè, vi propongo un piccolo esempio di codice da compilare per estrarre l'assembly (ad esempio con gcc -S): vedrete che le due funzioni (una con variabile dentro il loop e l'altra con la variabile fuori) generano lo stesso codice: Leggenda Urbana, confermato.
#include <stdio.h>

// prototipi locali
int test1(int array[], int nelems);
int test2(int array[], int nelems);

// funzione main
int main(int argc, char ** argv)
{
    int array[5];

    // Test 1
    test1(array, 5);
    printf("Test 1: array[4] = %d\n", array[4]);

    // Test 2
    test2(array, 5);
    printf("Test 2: array[4] = %d\n", array[4]);

    return 0;
}

// funzione test1()
int test1(
    int array[],
    int nelems)
{
    // riempio array
    int n;  // n dichiarato fuori dal loop
    int i;
    for (i = 0; i < nelems; i++) {
        n = i * 2;
        array[i] = n;
    }
}

// funzione test2()
int test2(
    int array[],
    int nelems)
{
    // riempio array
    int i;
    for (i = 0; i < nelems; i++) {
        int n;  // n dichiarato dentro il loop
        n = i * 2;
        array[i] = n;
    }
}
2. L'illusione
Allora, stiamo parlando di ottimizzazione del codice, quindi di un argomento vastissimo (ci sono moltissime tecniche e moltissimi casi), ma visto che il tempo e la dimensione dell'articolo hanno dei limiti cercheremo di ottimizzare (!?) focalizzandoci solo su un tipo classico, anche perché il risultato finale (come vedremo nel punto 3) dovrebbe essere sempre (più o meno) lo stesso. E quale è la principale fonte di lentezza in una applicazione? ma è lui, è il (grande) loop! Quindi ho scritto sei piccoli esempi che riprendono i casi "base" e "ottimizzato" dell'esempio nel punto 1, vediamoli:

// TEST 1 - versione con moltiplicazione, array e indice
int array[1000];
int i;
for (i = 0; i < 1000; i++)
    array[i] = i * 2;

// TEST 2 - versione con calcolo incrementale invece di moltiplicazione
int array[1000];
int i, incr;
for (i = 0, incr = 0; i < 1000; i++) {
    array[i] = incr;
    incr += 2;
}

// TEST 3 - versione con calcolo incrementale e pointer invece di array
int array[1000];
int *ptr = array;
int i, incr;
for (i = 0, incr = 0; i < 1000; i++, ptr++) {
    *ptr = incr;
    incr += 2;
}

// TEST 4 - versione con calcolo incrementale, pointer e senza indice
int array[1000];
int *ptr = array;
int limit = 1000 * 2;
int incr;
for (incr = 0; incr < limit; incr += 2, ptr++)
    *ptr = incr;

// TEST 5 - versione con shift logico invece di moltiplicazione
int array[1000];
int i;
for (i = 0; i < 1000; i++)
    array[i] = i << 1;

// TEST 6 - versione con shift logico e pointer invece di array
int array[1000];
int *ptr = array;
int i;
for (i = 0; i < 1000; i++, ptr++)
    *ptr = i << 1;
Evidentemente la funzione Test 1 (già vista all'inizio dell'articolo) è semplicissima, però contiene un loop, e se la dimensione dell'array è molto grande potrebbe diventare dispendiosa. Ho provato a ottimizzarla usando due tecniche, la Strength Reduction e la Induction Variable, e attraverso vari passaggi (Test 2 e Test 3) si arriva alla versione super-ottimizzata in Test 4. Dato che c'ero ho riproposto in Test 5 la versione semplice ma con shift logico al posto della moltiplicazione e, infine, in Test 6 troviamo un ibrido con pointer al posto dell'array e shift logico al posto della moltiplicazione.

E a questo punto è doveroso uscire dalla teoria ed entrare nella pratica, quindi ho scritto un piccolo benchmark per analizzare i risultati delle varie versioni. Ho usato un grandissimo loop (se no i risultati sarebbero stati impossibili da valutare) e... vediamo i risultati (con GCC 7.4.0/Linux 4.15.0/Intel I7):

TEST con array di dimensione 0xfffffff

TEST con compilazione gcc senza ottimizzazioni
Test 1: Tempo trascorso: 0.903985 secondi
Test 2: Tempo trascorso: 0.881661 secondi
Test 3: Tempo trascorso: 0.863433 secondi
Test 4: Tempo trascorso: 0.844027 secondi
Test 5: Tempo trascorso: 0.899836 secondi
Test 6: Tempo trascorso: 0.896226 secondi

TEST con compilazione gcc con ottimizzazione -O1
Test 1: Tempo trascorso: 0.366814 secondi
Test 2: Tempo trascorso: 0.365151 secondi
Test 3: Tempo trascorso: 0.352550 secondi
Test 4: Tempo trascorso: 0.351188 secondi
Test 5: Tempo trascorso: 0.366156 secondi
Test 6: Tempo trascorso: 0.356479 secondi

TEST con compilazione gcc con ottimizzazione -O2
Test 1: Tempo trascorso: 0.359824 secondi
Test 2: Tempo trascorso: 0.363385 secondi
Test 3: Tempo trascorso: 0.362589 secondi
Test 4: Tempo trascorso: 0.356611 secondi
Test 5: Tempo trascorso: 0.361608 secondi
Test 6: Tempo trascorso: 0.362675 secondi

TEST con compilazione gcc con ottimizzazione -O3
Test 1: Tempo trascorso: 0.299029 secondi
Test 2: Tempo trascorso: 0.286266 secondi
Test 3: Tempo trascorso: 0.290292 secondi
Test 4: Tempo trascorso: 0.287927 secondi
Test 5: Tempo trascorso: 0.305653 secondi
Test 6: Tempo trascorso: 0.316873 secondi
Allora: effettivamente la versione Test 4 va meglio delle altre, ma il miglioramento è irrisorio, e i risultati con le ottimizzazioni del compilatore... beh, forse è meglio passare al punto 3.

3. La delusione
Ebbene si: dai risultati dei test si evince che:
  • le "ottimizzazioni manuali" sono poco effettive.
  • il compilatore ottimizza molto meglio di noi (ma che strano!), perfino usando la blanda opzione -O1.
  • il compilatore ottimizza un po' anche senza dirglielo, vedi il risultato (senza ottimizzazioni) di Test 1 rispetto a quello di Test 5, ad esempio.
Il fatto è (e bisogna farsene una ragione) che le ottimizzazioni descritte (Strength Reduction, Induction Variable, e mille altre) le usa già il compilatore, nei punti e nelle maniere che ritiene più opportune, e quindi, se noi cerchiamo di ottimizzare già a livello di scrittura delle istruzioni base, stiamo perdendo tempo e energie per un lavoro che non è compito nostro (questo magari non era vero in passato ma ora lo è). Ed è altamente probabile che il compilatore farà questo lavoro meglio di noi. Ovviamente qui abbiamo visto solo una minima parte delle possibili "ottimizzazioni manuali" ma, in generale, il discorso fatto vale per tutte.

Solo mi preme precisare che le ottimizzazioni forzate (con GCC sono indicate con -O1, -O2 e -O3) bisogna usarle con cautela crescente in base al numero: -O1 si può usare quasi sempre, mentre -O2 in alcuni casi particolari può provocare comportamenti strani e -O3 è ancora più critico: infatti bisogna ricordarsi che un compilatore, anche se buono, è stato scritto da persone (non da HAL9000!) quindi può anche contenere bugs, e poi il processo di ottimizzazione interno è abbastanza complicato, anche perché contiene delle "decisioni" interne del compilatore che con un codice possono funzionare perfettamente mentre con un altro codice non funzionano altrettanto bene. Detto questo credo che ora siamo pronti per il punto 4.

4. Il Gran Finale
Nel mio vecchio articolo chiedevo: "Quando scrivo codice devo farlo in maniera naturale, o meglio, istintiva (beh, sempre se si possiede l'istinto del Programmatore...) o devo seguire linee un po' astruse ed ermetiche per rendere il programma più efficiente?". E chiedevo anche: "Vale la pena di trasformare un codice leggibile e chiaro come quello di Test 1 in uno molto più criptico, come ad esempio quello di Test 4, solo perché non ci fidiamo del compilatore?". La risposta è evidente: lasciamo questo lavoro al compilatore e concentriamoci sullo scrivere del buon codice, chiaro, leggibile, manutenibile, ben strutturato, con una architettura coerente e solida, ecc., ecc.: vivremo più tranquilli e faremo anche un bel favore a chi dovrà, un giorno, mettere le mani sul nostro lavoro. 

E, come promesso, concludo con le parole di un profeta, uno di quelli che hanno scritto la storia dell'informatica e da cui c'è sempre qualcosa da imparare, anche a distanza di molti anni:
"The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming" [Donald Ervin Knuth, "Computer Programming as an Art", 1974]
Ciao e al prossimo post!

lunedì 8 aprile 2019

Callback Lucky
come funzionano le Callback in C

(...una premessa: questo post è un remake di un mio vecchio post (anzi, di due). L'ho riadattato e "modernizzato" per pubblicarlo su quell'altro bel blog collettivo dove scrivo. Visto che le modifiche sono molte e (forse) interessanti, lo ripubblico anche qui. Questo potrebbe ripetersi in futuro...)
Jimmy Logan: Noi abbiamo bisogno di un mago del computer.
Fish Bang: So tutto quello che c'è da sapere sui computer, okay? Tutti i Twitters, io li conosco.
Nel bel Logan Lucky c'è un momento di Metacinema in cui si cita il titolo di un altro film (diciamo) della stessa famiglia, e cioè Ocean's Eleven. Ecco, per fare un parallelo, le callback sono il Metacinema del C, perché lavorano in un universo parallelo, quello in cui si usa (si cita) una cosa che funziona e basta, il come importa fino a un certo punto. Orbene: è giunto il momento di squarciare il velo di mistero sulle callback...
...ragazzi, vi è chiaro ora come funzionano le callback?...

Cominciamo: è evidente che le le funzioni callback sono un argomento un po' particolare fin dall'origine. Perché particolare? Beh, tanto per cominciare, sulla bibbia del C (il K&R) non se ne parla mai, per cui un C-ista radicale potrebbe anche affermare che "le callback non esistono!". In realtà nel K&R si parla ampliamene degli zii delle callback, e cioè i puntatori a funzione (di cui le callback sono un caso particolare): quindi le callback esistono.

Non ho intenzione di scrivere un trattato di uso delle callback (sento già i vostri sospiri di sollievo), né di spiegare come, quando, perché e (soprattutto) se usarle: in rete ci sono molte fonti interessanti e ben scritte. Eventualmente sarebbe una buona cosa scrivere un post sugli zii, ma, visto l'argomento ostico e il probabile mal di stomaco che mi verrebbe durante la scrittura, lo rimando a data futura (tanto per intenderci: perfino Kernighan & Ritchie parlando dei Pointers to Functions hanno intitolato il capitolo 5.12 del K&R "Complicated Declarations", e se erano complicate per loro due...).

Di cosa parleremo allora? Beh, io (come molti altri, immagino) ho usato varie volte le callback e ho letto codice che le usava (codice che era, il più delle volte, illeggibile e di difficile interpretazione, in rapporto direttamente proporzionale alla frequenza d'uso delle callback, sigh). Ebbene, fino al giorno in cui ho scritto una implementazione completa (e cioè ho scritto, oltre alla callback, anche la funzione a cui passarla) non mi sono reso conto di alcuni dettagli nascosti. Ovviamente, se per voi le callback non hanno dettagli nascosti, potete saltare la lettura del seguito e arrivederci al prossimo post.

Siete ancora qua? Ok, prima di cominciare vediamo una definizione delle callback presa pari pari dalla Wikipedia: "una funzione che viene richiamata da un'altra funzione" e aggiungo io: "e, spesso e/o normalmente, la funzione chiamante è una funzione di libreria". L'esempio più classico e familiare che si cita in letteratura è relativo all'uso della qsort():
#include <stdio.h>
#include <stdlib.h>

// funzione callback di comparazione per la qsort()
static int cbCmpFunc(const void *elem_a, const void *elem_b)
{
    // ritorno il risultato della comparazione
    return *(int*)elem_a > *(int*)elem_b;
}

// funzione main
int main(void)
{
    int array[] = {34,12,32,9,10,72,82,23,14,7,94};
    int nelems = sizeof(array) / sizeof(int);

    // eseguo sort array con qsort()
    qsort(array, nelems, sizeof(int), cbCmpFunc);

    // mostro i risultati
    int i;
    for (i = 0; i < nelems; i++)
        printf("%d - ", array[i]);

    printf("\n");

    // esco
    return 0;
}
La qsort() è una funzione della libc che implementa l'algoritmo di ordinamento quicksort, e necessita di una funzione di callback che gli specifichi il tipo di ordinamento voluto. Siamo, quindi, in un caso classico: qsort() è una funzione di libreria, e noi, localmente, la usiamo passandogli una callback che, nel nostro esempio, serve per ordinare in modo ascendente i numeri dell'array.

E ora veniamo al dunque: in un altra epoca, quando non era facile come ora reperire documentazione ed esempi, mi era capitato di leggere e scrivere codice come quello mostrato sopra e mi domandavo (magari solo inconsciamente): "ma da dove saltano fuori i due parametri elem_a e elem_b della cbCmpFunc()?" e ancora: "Se io chiamo la callback e non gli passo esplicitamente parametri, come funziona il tutto?" Beh, come scoprii dopo, stavo ragionando rovesciando il rapporto causa-effetto: non ero io che chiamavo la callback, era la qsort() che la chiamava! Ok, mi vergogno un po' a raccontare una scoperta così lapalissiana, ma, effettivamente, lo compresi a fondo solo il giorno in cui ebbi la necessità di scrivere una funzione di libreria che usava una callback. Certo, ora con tutte le informazioni in rete è molto più facile...

Quindi, per chiarire, vediamo un esempio completo (N.B. l'esempio si potrebbe scrivere tutto in un file, ma, come evidenziato negli opportuni commenti, dovrebbe essere diviso su tre file in un progetto reale):
#include <stdio.h>

/* parte che dovrebbe essere nel file mysort.h
*/
// prototipi per mySort()
typedef int (*mycallback)(int, int);
void mySort(int *array, int nelems, mycallback cmpFunc);

/* parte che dovrebbe essere nel file mysort.c
 */
// mySort() - funzione di sort che usa l'algoritmo bubblesort
void mySort(int *array, int nelems, mycallback cmpFunc)
{
    // loop su tutti gli elementi di array
    while (nelems > 0) {
        // loop interno con lunghezza calante
        int i;
        for (i = 0; i < (nelems - 1); i++) {
            // eseguo callback di comparazione
            if (cmpFunc(array[i], array[i + 1])) {
                // eseguo swap di array[i] e array[i+1]
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
        }

        // decremento nelems
        nelems--;
    }
}

/* parte che dovrebbe essere nel file mymain.c
*/
// cbCmpFunc() - funzione di comparazione
static int cbCmpFunc(int elem_a, int elem_b)
{
    // ritorno il risultato della comparazione
    return elem_a > elem_b;
}

// funzione main
int main(void)
{
    int array[] = {34,12,32,9,10,72,82,23,14,7,94};
    int nelems = sizeof(array) / sizeof(int);

    // eseguo sort array
    mySort(array, nelems, cbCmpFunc);

    // mostro i risultati
    int i;
    for (i = 0; i < nelems; i++)
        printf("%d - ", array[i]);

    printf("\n");

    // esco
    return 0;
}
Come vedete è molto simile all'esempio della qsort(), però, invece di usare una funzione della libc, usa una funzione di ordinamento scritta ad-hoc, la mySort(). Per quest'esempio ho usato, per non complicare troppo il codice, un algoritmo di tipo bubblesort, che è (lo so) un po' una schifezza, ma per fare un test semplice basta e avanza. Come noterete è la mySort() che si occupa di scrivere gli argomenti per la callback, processando opportunamente gli altri parametri che le vengono passati (array e nelems), e così, magicamente, appaiono dei valori in elem_a ed elem_b.

E visto che vogliamo abbondare (ma si, Punto! Due punti!... ma sì, fai vedere che abbondiamo... Abbondandis in abbondandum...) vi propongo un piccolo (e utile) trucco: supponiamo di avere bisogno di passare un altro parametro alla callback, un parametro esterno disponibile solo a livello della chiamata base, e che la mysort() non può generare internamente.

Come possiamo fare? Vediamo subito il nuovo codice (presentato come un blocco unico, ma, di nuovo, da dividere su tre file):
#include <stdio.h>

/* parte che dovrebbe essere nel file mysort.h
*/
// prototipi per mySort()
typedef int (*mycallback)(int, int, void *);
void mySort(int *array, int nelems, mycallback cmpFunc, void *newarg);

/* parte che dovrebbe essere nel file mysort.c
 */
// mySort() - funzione di sort che usa l'algoritmo bubblesort
void mySort(int *array, int nelems, mycallback cmpFunc, void *newarg)
{
    // loop su tutti gli elementi di array
    while (nelems > 0) {
        // loop interno con lunghezza calante
        int i;
        for (i = 0; i < (nelems - 1); i++) {
            // eseguo callback di comparazione
            if (cmpFunc(array[i], array[i + 1], newarg)) {
                // eseguo swap di array[i] e array[i+1]
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
        }

        // decremento nelems
        nelems--;
    }
}

/* parte che dovrebbe essere nel file mymain.c
*/
// cbCmpFunc() - funzione di comparazione
static int cbCmpFunc(int elem_a, int elem_b, void *newarg)
{
    // scrivo risultati parziali in un file
    FILE *fp = (FILE *)newarg;
    fprintf(fp, "%d > %d = %d\n", elem_a, elem_b, elem_a > elem_b);

    // ritorno il risultato della comparazione
    return elem_a > elem_b;
}

// funzione main
int main(void)
{
    int array[] = {34,12,32,9,10,72,82,23,14,7,94};
    int nelems = sizeof(array) / sizeof(int);

    // eseguo sort array scrivendo i risultati parziali in un file
    FILE *fp = fopen("result.txt", "w");
    mySort(array, nelems, cbCmpFunc, fp);

    // chiudo il file
    fclose(fp);

    // mostro i risultati
    int i;
    for (i = 0; i < nelems; i++)
        printf("%d - ", array[i]);

    printf("\n");

    // esco
    return 0;
}
Come vedete è molto simile all'esempio precedente, solo che ora, a livello del main(), apriamo un file per registrare dei dati di elaborazione e dobbiamo passare il file descriptor alla mysort(), già che non possiamo certo pensare di scrivere una funzione di libreria che porti schiantato nel codice il nome del file di log: è l'applicazione chiamante che deve passarlo.

E come lo passiamo? È abbastanza semplice: si aggiunge un parametro (del tipo opportuno) alla mysort() e alla callback, e, nella chiamata base (nel main(), nel nostro caso) si passa il valore alla mysort(), che si occuperà i propagarlo fino alla callback, che è l'utilizzatrice del nuovo parametro; la mysort() non lo usa, lo trasporta solamente. Con questo metodo possiamo passare tutti i parametri che vogliano: nell'esempio ne ho aggiunto uno, ma se ne possono aggiungere a piacere.

Ovviamente tutto quanto sopra è valido per funzioni che implementiamo noi: non si può certo pensare di aggiungere parametri a funzioni di libreria di cui non abbiamo il controllo: ad esempio la qsort() ha bisogno solo della callback con due parametri, e così ce la dobbiamo tenere.

Qualcuno si chiederà perché il parametro newarg è un void* e non un tipo più specifico (in questo caso un FILE*): l'ho scritto così per dimostrare che, con questo metodo, si può passare qualsiasi cosa (ad esempio in C++ si usa per passare il pointer this): anzi, ho visto codice in cui si aggiungono dei void* alle callback (in fase di progetto) solo per usi futuri, in maniera di poter scrivere, in seguito, delle callback molto personalizzate senza modificare la funzione base (che, come detto, e solo trasportatrice di questi parametri).

Che ve ne sembra? Si, tutto un po' lapalissiano e ingenuo (forse), ma alzi la mano chi non ha mai avuto dubbi nella sua storia di programmatore (uhmm... vedo poche mani alzate).  E se questo post è servito a ampliare le conoscenze anche a solo uno dei lettori sono stra-contento così. E per gli altri, quelli che sapevano già tutto sulle callback: perché siete arrivati ugualmente fino in fondo al post ?

Ciao e al prossimo post!

mercoledì 13 marzo 2019

1997: Fuga da Bitwise
Come funzionano le operazioni di Bitwise in C

(...una premessa: questo post è un remake di un mio vecchio post (anzi, di due). L'ho riadattato e "modernizzato" per pubblicarlo su quell'altro bel blog collettivo dove scrivo. Visto che le modifiche sono molte e (forse) interessanti, lo ripubblico anche qui. Questo potrebbe ripetersi in futuro...)
Bob Hauk: Mi ucciderai ora, Jena?
Jena (Snake) Plissken: Sono troppo stanco... Forse più tardi...
Nel capolavoro 1997: Fuga da New York il grande John Carpenter ci mostrava come scappare da una tristissima New York trasformata in prigione federale. Ecco, l’argomento di questo articolo è uno di quegli argomenti che inducono alla fuga molti valorosi Programmatori C/C++… “ehm… oggi non ho tempo, puoi occupartene tu delle operazioni di bitwise? Poi domani mi farai vedere…
...a me Bitwise non me l'ha mai detto nessuno...
Cominciamo con un piccolo gioco: alzi la mano chi ha scritto recentemente codice che usa le operazioni bit a bit. Oppure, alzi la mano, senza prima andare a rileggersi un manuale del C/C++, chi di voi sa usare e/o descrivere perfettamente le operazioni bit a bit. Uhm… vedo poche mani alzate. Il fatto è che le bitwise operations sono una di quelle parti del C/C++ un po’ misconosciute, di uso dubbio e infrequente, insomma una di quelle parti di cui, per mancanza di pratica ci si scorda.

E, oltretutto, devo dire che sulle operazioni di bitwise il fantastico K&R non è particolarmente chiaro e dettagliato, le tratta (come sono) come un argomento di nicchia, e non ti coinvolge con decine di divertenti esempi che ti aiutano a memorizzare definitivamente l’argomento, anzi, per quel che ricordo dell’ultima volta che lo lessi, sono un paio di pagine che scivolano via e che hai già dimenticato quando passi al prossimo capitolo. Beh anche la bibbia K&R (che io considero sacra) ha alcuni punti non proprio coinvolgenti.

Rinfreschiamo: gli operatori di bitwise (che operano sui singoli bit) sono:
"&"  AND
"|"  OR
"^"  XOR
"~"  NOT (complemento a 1)
"<<" SHIFT a sinistra
">>" SHIFT a destra  
     
N.B.:
- il NOT e' un operatore unario: opera su un solo argomento indicato sulla destra.
- gli shift sono operatori unari: operano su un solo argomento indicato sulla sinistra.
Adesso, senza dilungarci in noiosi sproloqui, passiamo a una piccola tabella e ad alcuni semplici esempi pratici. Ecco la tabella:
"&": il risultato è 1 se i due operandi valgono 1. Altrimenti 0.
"|": il risultato è 0 se i due operandi valgono 0. Altrimenti 1.
"^": il risultato è 1 se i due operandi sono diversi. Altrimenti 0.
"~": il risultato è 1 se l'operando vale 0. Altrimenti 0. 
"<< n": il risultato è l'operando con tutti i bit spostati a sinistra di n posizioni. 
">> n": il risultato è l'operando con tutti i bit spostati a destra di n posizioni.
Ed ecco i semplici esempi pratici:
AND
int a = 74;       // 0 1 0 0 1 0 1 0
int b = 174;      // 1 0 1 0 1 1 1 0
int c = a & b;    // 0 0 0 0 1 0 1 0 risultato c=10

OR
int a = 74;       // 0 1 0 0 1 0 1 0
int b = 174;      // 1 0 1 0 1 1 1 0
int c = a | b;    // 1 1 1 0 1 1 1 0 risultato c=238

XOR
int a = 74;       // 0 1 0 0 1 0 1 0
int b = 174;      // 1 0 1 0 1 1 1 0
int c = a & b;    // 1 1 1 0 0 1 0 0 risultato c=228

NOT
int a = 74;       // 0 1 0 0 1 0 1 0
int b = ~b;       // 1 0 1 1 0 1 0 1 risultato c=181

SHIFT a sinistra
int a = 74;       // 0 1 0 0 1 0 1 0
int b = a << 2;   // 0 0 1 0 1 0 0 0 risultato c=296

SHIFT a destra
int a = 74;       // 0 1 0 0 1 0 1 0
int b = a >> 2;   // 0 0 0 1 0 0 1 0 risultato c=18
Notare che nelle operazioni di shift i bit nuovi che entrano a destra (nello shift a sinistra) valgono 0, e i bit nuovi che entrano a sinistra (nello shift a destra) valgono 0.
Notare anche che lo shift a destra equivale a una divisione per multipli di 2 (>>1  è una divisione per 2,  >>2  è una divisione per 4, ecc.), mentre lo shift a sinistra equivale a una moltiplicazione per multipli di 2 (<<1  è una moltiplicazione per 2, <<2  è una moltiplicazione per 4, ecc.). Queste operazioni di moltiplicazione e divisione sono molto veloci, e si potrebbe essere tentati a usarle per velocizzare il codice: beh, prima di farlo rileggetevi (o leggetevi) questo.

E aggiungo un avvertimento: in base alla dimensione del tipo del operando e alla presenza o meno del bit di segno, le moltiplicazioni e divisioni con shift possono dare risultati inaspettati. Anzi, andiamoci subito alle dolenti note,  togliamoci il pensiero: vediamo un esempio:
#include <stdio.h>

void main()
{
    // 1) SHIFT a sinistra con unsigned int
    unsigned int a, b;
    a = 74;           // 0 0 1 0 0 1 0 1 0
    b = a << 2;       // 1 0 0 1 0 1 0 0 0 risultato b=296
    printf("var = %d; var << 2 = %d\n", a, b);

    // 2) SHIFT a sinistra con unsigned char
    unsigned char c, d;
    c = 74;           // 0 1 0 0 1 0 1 0
    d = c << 2;       // 0 0 1 0 1 0 0 0 risultato d=40
    printf("var = %d; var << 2 = %d\n", c, d);

    // 3) SHIFT a destra con signed char (o int)
    char e, f;
    e = -4;           // 1 1 1 1 1 1 0 0
    f = e >> 2;       // 1 1 1 1 1 1 1 1 risultato f=-1
    printf("var = %d: var >> 2 = %d\n", e, f);
    // N.B.: senza estensione di segno sarebbe:
    // e = -4;        // 1 1 1 1 1 1 0 0
    // f = e >> 2;    // 0 0 1 1 1 1 1 1 risultato f=63
}
Il caso 1 è, evidentemente il caso funzionante: un int è molto più grande degli 8 bit usati per rappresentare il numero di partenza (74), per cui lo shift non perde nessun 1 sulla sinistra (è questo il possibile problema) e il risultato è corretto (74×4=296). Se usiamo però (caso 2) un char (8 bit) durante lo shift perdiamo un 1 e il risultato va in overflow (74×4=40 ??). Quindi attenzione!

Il caso 3, poi, è ancora più subdolo: facendo operazioni con segno (nei casi 1 e 2 ho usato variabili unsigned proprio in preparazione al punto 3) e usando valori negativi, possono succedere cose strane: per la rappresentazione stessa dei numeri negativi in binario (complemento a 2) il bit più a sinistra (MSB) è il bit di segno, e, in questo caso l’operazione di shift è machine-dependent: in base al tipo di CPU possiamo disporre o no dell’estensione di segno (di default, ad esempio, su macchine Intel), per cui lo shift dell’esempio può dare il risultato aspettato (-4/4=-1) o un risultato completamente diverso (-4/4=63 ??). Di nuovo: attenzione!

E adesso è il momento di mostrare alcuni esempi pratici di uso di quanto esposto, che altrimenti, sarebbe know-how  fine a se stesso: vediamo come leggere lo stato dei singoli bit di una word usando una maschera:
#include <stdio.h>

void main()
{
    // uso di una maschera per leggere i bit di una word
    unsigned char mask = 1;     // 0 0 0 0 0 0 0 1
    unsigned char word = 74;    // 0 1 0 0 1 0 1 0

    // loop di lettura
    int i;
    for (i = 0; i < 8; i++)
        printf("il bit %d della word è %s\n", i, (word & mask<<i) ? "ON" : "OFF");
}
semplice no? E la stessa operazione si può fare con una macro:
#include <stdio.h>

#define INPUT(w, i)    (w & 0x01<<i)

void main()
{
    // uso di una macro per leggere i bit di una word
    unsigned char i_word = 74;    // 0 1 0 0 1 0 1 0

    // loop di lettura
    int i;
    for (i = 0; i < 8; i++)
        printf("il bit %d della word è %s\n", i, INPUT(i_word, i) ? "ON" : "OFF");
}
E poi, visto che lo stile è sempre molto importante, vediamo un modo con una una buona estetica per leggere degli input di un dispositivo, per esempio i fine corsa di un sistema elettromeccanico che dobbiamo controllare col nostro amato C:
#include <stdio.h>

#define INPUT_FC1    (in_word & 0x01<<0)
#define INPUT_FC2    (in_word & 0x01<<1)

void main()
{
    // uso di una define per ogni bit da leggere di una word
    unsigned char in_word = 74;    // 0 1 0 0 1 0 1 0

    // lettura
    printf("il bit FC1 della word è %s\n", INPUT_FC1 ? "ON" : "OFF");
    printf("il bit FC2 della word è %s\n", INPUT_FC2 ? "ON" : "OFF");
}
Ecco, l’esempio appena mostrato indica una maniera, semplice ed elegante, per descrivere degli input (usando dei mnemonici auto-esplicativi) che può risultare utile per scrivere del Software di controllo di dispositivi Hardware, facile da leggere e da manutenere.

Facile da leggere e da manutenere: questa l’ho già sentita… ah si: è come dovrebbe essere tutto il S/W che scrive un Analista Programmatore (…ma questa è un’altra storia…).

Ciao e al prossimo post!