Programming Languages Hacks

Importanti regole per linguaggi di programmazione rilevanti come Java, C, C++, C#…

  • Subscribe

  • Lettori

    I miei lettori abituali

  • Twitter

Performance in Left Join e Condizioni Multiple (COALESCE)

Posted by Ricibald on 25th February 2014

A volte SQL Server produce degli execution plan, come dire… discutibili??

Un esempio è dato dall’operatore COALESCE e LEFT JOIN. Quando si lavora con tabelle molto grandi la query si traduce in un TableScan di milioni di righe laddove non previsto.

Esempio concreto:

SELECT *
    FROM BigTable X
    LEFT JOIN BigTable Y ON X.Id = COALESCE(Y.ParentId, Y.Id)
    WHERE X.Name = 'Something'

La query produce un execution plan che prevede un TableScan su una tabella di milioni di record. Il risultato sono minuti e minuti di attesa…

La stessa query potrebbe essere riscritta come segue per migliorare il risultato:

SELECT *
    FROM BigTable X
    LEFT JOIN BigTable Y ON 
        (Y.ParentId IS NOT NULL AND X.Id = Y.ParentId)      -- condizione 1
        OR
        (Y.ParentId IS NULL AND X.Id = Y.Id)                -- condizione 2
    WHERE X.Name = 'Something'

A volte questo workaround funziona, altre volte no. In questi casi sfortunati dovremmo scrivere la query come segue:

SELECT *
    FROM BigTable X                                         -- condizione 1
    JOIN BigTable Y ON Y.ParentId IS NOT NULL AND X.Id = Y.ParentId
    WHERE X.Name = 'Something'
UNION ALL
SELECT *
    FROM BigTable X                                         -- condizione 2
    JOIN BigTable Y ON Y.ParentId IS NULL AND X.Id = Y.Id
    WHERE X.Name = 'Something'
UNION ALL
SELECT X.*, Y1.*                                            -- no match
    FROM BigTable X
    LEFT JOIN BigTable Y1 ON Y.ParentId IS NOT NULL AND X.Id = Y1.ParentId
    LEFT JOIN BigTable Y2 ON Y.ParentId IS NULL AND X.Id = Y2.Id
    WHERE X.Name = 'Something' AND Y1.Id IS NULL AND Y2.Id IS NULL

Riscrivendo in questo modo (semplicissimo) la query avremo delle ottime performance. E meno male che dicono che SQL è un linguaggio dichiarativo…!!

Posted in .net | 1 Comment »

Approcci in .NET e Windows Server 2003 per Ottenere la Scalabilità delle Applicazioni

Posted by Ricibald on 22nd January 2008

In .NET è spesso necessario ottenere la scalabilità delle applicazioni. Immaginiamo di aver scritto un bellissimo software che richiede a un sistema esterno il permesso per richiedere un mutuo aziendale. Saranno presenti numerosi scambi di messaggi tra il nostro sistema e il sistema esterno in questione, che possono comportare dei lunghi tempi di attesa.

Immaginiamo ora che in questo lasso di tempo avvengano 100.000 richieste verso la nostra applicazione. Possiamo immaginare soluzioni più o meno eleganti, come pool di thread o gerarchie di processi ma queste hanno efficacia solo con molteplici processori. Anche se è una soluzione che solo ora sta diventando praticabile per un computer “normale”, grazie ai processori multi core, non è comunque una soluzione “altamente” scalabile: è infatti subordinata all’architettura del sistema che esegue la nostra applicazione.

Si utilizzano quindi normalmente diversi approcci di computer clustering. Tra i possibili tipi di clustering, esistono:

  • Fail-over clustering: il funzionamento delle macchine è continuamente monitorato, e quando uno dei due host smette di funzionare l’altra macchina subentra. Lo scopo è garantire un servizio continuativo
  • Load-balancing clustering: sistema nel quale le richieste di lavoro sono inviate alla macchina con meno carico
  • High Performance Computing clustering: le macchine suddividono i processi di un job su più macchine, al fine di guadagnare in prestazioni

In realtà, i clustering descritti sono figli di due pattern (presi da POSA):

  • Broker (o la sua versione “leggera” Client-Dispatcher-Server): supporta il coordinamento e la comunicazione tra sistemi distribuiti eterogenei. Consente di mantenere trasparente la localizzazione dei Server, in modo da poterli cambiare dinamicamente per ottenere un bilanciamento di carico
  • Master-Slave: supporta tolleranza d’errore, calcolo parallelo e accuratezza computazionale tramite ridondanza. Esiste un componente Master che suddivide e distribuisce il lavoro a componenti Slave identici. Gli Slave calcolano il risultato parziale e lo restituiscono al Master, il quale assembla i risultati parziali ottenuti per ottenere quello definitivo

Il protocollo con cui questi sistemi dialogano non è un problema, se si combina anche il pattern Forward-Receiver, che consente di definire un protocollo di comunicazione trasparente.

Nel nostro caso, risulta eccessivo dividere il lavoro in più sottolavori: quello che vorremmo è semplicemente smistare la richiesta al server più libero in modo da ottenere una scalabilità. Vorremmo quindi implementare il pattern Broker.

Fortunatamente, .NET ci viene incontro e ci fornisce un pattern Broker “pronto all’uso”: il .NET remoting. In MSDN esiste infatti la guida su come implementare il pattern Broker utilizzando .NET remoting.

Ma se si utilizza Microsoft Windows Server 2003, allora è possibile utilizzare una grande scorciatoia per il Load-Balancing clustering (oltre a quella appena vista): le Windows Server 2003 Clustering Services. Consentono di costruire un cluster di server. Il cluster è dotato di un indirizzo IP virtuale (xxx.yyy.zzz.kkkk), che quando richiesto trova corrispondenza con un indirizzo IP reale della macchina fisica più libera. In questo modo, è sufficiente creare in alternativa:

  • una dll acceduta tramite .NET remoting
  • un web service

e replicarlo in tutte le macchine fisiche. A questo punto, quando accederemo all’indirizzo IP xxx.yyy.zzz.kkkk e richiederemo il servizio interessato, il sistema operativo ci smisterà automaticamente alla macchina più libera. Non c’è bisogno di alcuna modifica nel nostro codice, stupefacente no??

Per maggiori informazioni, si veda l’ottimo articolo su come scrivere applicazioni “clusterizzate” in c# di Gerald Gibson Jr.

Posted in .net | No Comments »

Virtual proxy: una trappola senza uscita?

Posted by Ricibald on 20th July 2007

I virtual proxy forniscono un rappresentante di un oggetto in modo da gestirne il caricamento su richiesta, anche noto come lazy initialization.

Se immaginiamo un file word di 500 pagine, con più di 1000 immagini, il caricamento dovrebbe impegnare molto tempo e molte risorse. In realtà quel che succede è che ogni immagine non viene caricata, ma solo “dichiarata”. Nel nostro file “PROVA.DOC” ci saranno informazioni utili come width/height dell’immagine in modo che la “dichiarazione” dell’immagine consenta la corretta impaginazione.

Fin qui tutto bene, ma ora immaginiamo di aver fatto scorrere tutte le 500 pagine e di aver visto tutte le 1000 immagini. Cosa succede? Semplice: tutte le immagini sono state effettivamente caricate e abbiamo consumato molta, molta RAM (aaarghhh!!) .

Il problema (quì molto romanzato…) sembra però più serio del previsto. Citiamo il pattern Proxy:

Il design pattern Proxy fornisce un surrogato o un segnaposto di un altro oggetto per controllare l’accesso a tale oggetto.

Il client che utilizza il Proxy ne è inconsapevole: sa solamente che il comportamento atteso della classe deve essere rispettato. L’indirezione introdotta dal Proxy deve quindi essere trasparente e l’utente non può intervenire su di essa. Il clean quindi non può (e non deve) essere gestito manualmente.

Abbiamo quindi il seguente schema:

  • una classe R reale
  • un virtual proxy V che gestisce il caricamento su richiesta di R
  • un client, che utilizza V ma che in realtà è convinto di utilizzare R

Dopo tanto patire, senza ulteriori preliminari, questa è la soluzione che mi sembra più corretta (vi apparirà forse scontata ora che la leggete, ma vi garantisco che cercando e ricercando su Google nessuno ne parla…). Il nuovo contesto è il seguente:

  • una classe R reale
  • un cache proxy C, che memorizza fino a n classi reali R
  • un virtual proxy V, che se necessario richiede a C di ottenere la classe reale R
    • C restituisce la cache entry se esiste, o crea il corrispondente R memorizzando il risultato in cache
    • se nella memorizzazione del nuovo cache entry viene superato il limite n di cache:
      • viene liberata la cache eliminando l’elemento meno richiesto (least frequently used)
      • vengono notificati tutti gli V che ne facevano uso, che impostano a null la classe reale R utilizzata richiamando funzioni di liberazione della memoria come la garbage collection. La notifica si deve basare su un protocollo condiviso tra V e C, utilizzando ad esempio il design pattern Observer.
  • un client, che utilizza V ma che in realtà è convinto di utilizzare R

Un modo semplice di implementare la tecnica “least frequently used” è la strategia “move-to-front” descritta in Pattern Oriented Software Architecture: a ogni richiesta di una cache entry l’elemento viene spostato alla testa di una lista. Quando è necessario liberare memoria possono essere eliminati gli elementi alla coda della lista. Questo può essere implementato (ad es. in Java) estendendo i metodi get() e put() di una Map.

Questa (da quanto ne so) è una soluzione “casalinga”, che non si basa su tecniche o pattern noti. Perciò qualunque suggerimento/critica sarà più che apprezzata…

Posted in pattern | 2 Comments »

Memory Leak in C++ – Le Cinque (Semplici) Regole d’Oro Per Un Software “Leggero”

Posted by Ricibald on 30th December 2006

I Memory Leak avvengono quando aree di memoria non più utilizzabili rimangono in memoria. Tali errori derivano dal mancato rispetto della seguente regola:

ogni oggetto allocato nello heap – con new T/new T[]/malloc – deve essere esplicitamente deallocato – con delete/delete[]/free – secondo le regole di corrispondenza indicate con il delimitatore ‘/’

Infatti, lo scope di una area heap coincide con quella dell’ultimo puntatore che ne contiene l’indirizzo, ma il suo lifetime coincide con l’intera durata del programma a meno dell’invocazione di delete/delete[]/free.
Se non è stato invocato il corrispondente delete/delete[]/free e l’ultimo puntatore disponibile va out of scope, l’area non è più accessibile ma continua a occupare memoria inutilmente generando l’errore di memory leak.

Si nota subito quindi che il problema riguarda esclusivamente l’area heap. Nello stack questo non è possibile poiché il lifetime di una variabile allocata nello stack coincide con il suo scope: quando la variabile è out of scope viene automaticamente deallocata.

Innanzitutto la regola base è quindi quella di rispettare le corrispondenze di allocazione/deallocazione: il new T deve essere seguito dal delete, il new T[] deve essere seguito dal delete[], la mallocdeve essere seguito da una free.

Spesso la causa più frequente di memory leak è omettere di deallocare le risorse quando non sono più necessarie. Immaginiamo ad esempio di avere la classe factory WindowFactory che crea oggetti con tipo base Window (supponiamo quindi che esistano sottoclassi di Window):

class WindowFactory {
    public:
        static Window* createWindow();
}

la funzione createWindow() restituisce un puntatore a un oggetto allocato dinamicamente di tipo base Window. Ci ricordiamo che restituire un puntatore in questo contesto è necessario per evitare il problema dello slicing. Quindi chi utilizza una Window deve:

  1. creare la Window con createWindow()
  2. usare la Window
  3. cancellare la Window con delete

Questo comporta che l’utilizzatore di Window è responsabile di deallocare la Window. Forse è un rischio che non vogliamo correre… La soluzione consiste nel creare una classe che funge da resource manager:

class WindowManager {
    private:
        Window* w;
    public:
        WindowManager() {
            w = WindowFactory::createWindow();
        }
        Window* getWindow() {
            return w;
        }
        ~WindowManager() {
            delete w;
        }
}
class TestWindow {
    void disegna() {
        WindowManager m;
        Window* w = m.getWindow();
        /* utilizza w... */
    } /* ora m è out of scope: w è deallocata */
}

La classe WindowManager ha la sola funzione di avvolgere Window per garantirne la deallocazione. L’utilizzo di WindowManager viene spesso chiamato Resource Acquisition Is Initialization (RAII) poiché è un idioma consolidato in C++ il fatto che nella stessa espressione un oggetto venga contemporaneamente dichiarato e inizializzato. Le classi RAII potrebbero essere viste come:

“So che i memory leak derivano dalla differenza concettuale tra heap e stack. Sarebbe bello se tutti gli oggetti che l’utilizzatore deve creare rispettassero le semplici regole di visibilità dello stack! In questo modo sarebbe impossibile generare memory leak! Ma come ottenere questo? Semplice: creo classi RAII

Stavolta infatti l’utilizzatore finale non crea nulla nello heap. La deallocazione segue esclusivamente le semplici regole dello stack: la deallocazione della Window è basata solo sullo scope di WindowManager.

Se generalizziamo questo approccio attraverso i template otteniamo gli smart pointer. I più utilizzati sono i reference-counting smart pointer (RCSP), che tengono traccia del numero di puntatori alla risorsa gestita e permettono di garantire una garbage collection per una particolare risorsa. In C++ gli RCSP coincidono con std::tr1::shared_ptr<T>.

Tornando al nostro problema, ricordiamo che l’obbiettivo sarebbe quello di creare una nuova Window senza delegare la responsabilità di cancellare la Window all’utilizzatore. In parte l’abbiamo ottenuto tramite il WindowManager, ma l’utilizzatore potrebbe comunque invocare WindowFactory::createWindow() a proprio piacimento e il problema rimarrebbe.

Sarebbe comodo che la stessa funzione WindowFactory::createWindow() restituisse un “qualcosa” che rispetti l’idioma RAII. E’ possibile ottenere questo comportamento avvolgendo la Window in uno smart pointer RCSP:

typedef boost::shared_ptr<Window> WindowPtr;
class WindowFactory {
    public:
        static WindowPtr createWindow();
}
class TestWindow {
    void disegna() {
        WindowPtr wp = WindowFactory::createWindow();
        wp->onClose(Window::EXIT);
        wp->view();
    } /* ora wp è out of scope: wp è deallocato */
}

Utilizzare classi RAII si rileva l’approccio migliore anche per prevenire i memory leak causati da eccezioni. Ad esempio:


class TestWindow {
    private:
        Window* w;
        Image* i;
    void disegna() {
        w = WindowFactory::createWindow();
        w->view();
        /* La creazione di Image potrebbe sollevare una eccezione */
        i = new Image("/home/ricibald/image.png");
        w->setImage(i);
        w->refresh();
        w->close();
        delete w;
    }
}

Se il costruttore di Image solleva una eccezione allora la Window puntata da w non verrà mai deallocata! Se invece utilizziamo classi RAII, il comportamento sarà corretto:

typedef boost::shared_ptr<Window> WindowPtr;
class TestWindow {
    private:
        WindowPtr w;
        Image* i;
    void disegna() {
        wp = WindowFactory::createWindow();
        wp->view();
        /* La creazione di Image potrebbe sollevare una eccezione */
        i = new Image("/home/ricibald/image.png");
        wp->setImage(i);
        wp->refresh();
        wp->close();
    }
}

Se viene sollevata una (qualsiasi) eccezione, wp diventa out of scope e la deallocazione avviene correttamente. Viene infatti invocato il distruttore di shared_ptr che a sua volta invocherà il delete di w.

Rispettare la regola RAII consente di prevenire la maggior parte degli errori, ma esistono anche memory leak causati da comportamenti indefiniti del compilatore, pena possibili memory leak “molto sottili“.

Esistono tre possibili comportamenti indefiniti del compilatore.

Il primo comportamento indefinito si può verificare con gli smart pointer. Si consideri infatti il seguente codice:

processaFinestra(boost::shared_ptr<Window>(new Window),priority());

il compilatore deve eseguire le tre seguenti cose

  • Invocare priority
  • Eseguire “new Window
  • Invocare il costruttore di boost::shared_ptr

Ma l’ordine delle operazioni è indefinito! Chiaramente il costruttore di shared_ptr dovrà essere invocato dopo “new Window“, ma priority() può essere invocato per primo, secondo o terzo! Consideriamo questa possibile sequenza di operazioni:

  1. Eseguire “new Window
  2. Invocare priority
  3. Invocare il costruttore di boost::shared_ptr

Ma se la funzione priority() sollevasse un’eccezione? In questo caso il puntatore restituito da “new Window” sarebbe perduto e l’oggetto Window referenziato non verrebbe deallocato: memory leak!! Come evitare questo comportamenti anomalo? Semplice: basta memorizzare gli smart pointer in istruzioni isolate. L’esempio precedente diventa quindi:

boost::shared_ptr<Window> wp(new Window);
processaFinestra(wp,priority());

Il secondo comportamento indefinito si può verificare nella deallocazione di classi polimorfiche. In classi base polimorfiche è necessario dichiarare il distruttore virtual. Se non viene rispettata questa regola, il programma funzionerà lo stesso, ma il comportamento della deallocazione è indefinito. Tipicamente le sottoclassi non sono distrutte, scatenando seri memory leak.

Il terzo comportamento indefinito si può verificare se i distruttori sollevano eccezioni. Se ciò dovesse avvenire, potrebbero attivarsi più eccezioni contemporaneamente, e in tal caso il risultato è indefinito. Ad esempio:

  1. il mio distruttore di una classe “Test” cancella una lista “finestre” che contiene N oggetti “Finestra
  2. il distruttore della classe “Finestra potrebbe generare un’eccezione in caso di errori in chiusura
  3. la deallocazione della lista “finestre” potrebbe generare più eccezioni contemporaneamente
  4. il risultato è indefinito: i rimanenti oggetti Finestra vengono deallocati? Ho memory leak?

è logico che non ci possiamo basare su risultati indefiniti! Quindi quali soluzioni adottare? Tre possibilità

  1. termina il programma in modo anomalo con std::abort()
  2. gestisci l’eccezione nel distruttore con try-catch, ma questo non consente di intervenire sull’errore
  3. fornisci una normale funzione close() che (1) deallochi oggetti Finestra e (2) sollevi l’eventuale eccezione. Tale funzione deve essere invocata esplicitamente dall’utilizzatore di Finestra.
    Il distruttore di Finestra, invece, verifica se tale funzione è stata invocata manualmente dall’utente (tramite una variabile booleana closed). Se la funzione close() non è stata ancora invocata, il distruttore garantisce comunque l’esecuzione di close(), con la differenza che stavolta l’ eventuale eccezione di close() deve essere gestita all’interno del costruttore, in modo analogo al precedente punto.
    Tutto questo si traduce in:

    class WindowException: public exception {
        virtual const char* what() const {
            return "Errore nella chiusura della finestra";
        }
    }
    class Finestra {
        private:
            Window w;
            boolean closed;
        public:
            ...
            void close() throw(WindowException) {
                w.close();
                if(!w.closed()) {
                    throw WindowException();
                }
                closed = true;
            }
            ~Finestra() {
                if( !closed ) {
                    try {
                        w.close();
                    } catch(WindowException& e) {
                        cerr << e.what << endl;
                        /* Se necessario esegui std::abort() */
                    }
                }
            }
    }
    

Concludendo, per prevenire (o addirittura impedire) memory leak bisogna rispettare le seguenti regole:

  • rispettare le corrispondenze: new T/new T[]/malloc corrisponde a delete/delete[]/free
  • restituire all’utilizzatore solo classi RAII tramite smart pointer o resource manager creati appositamente
  • creare smart pointer in istruzioni isolate
  • dicharare virtual i distruttori di classi polimorfiche
  • costruire distruttori privi di eccezioni. In caso di errori da gestire occorre fornire una funzione regolare che dia la possibilità di intervenire sull’eventuale eccezione (il comportamento del distruttore deve essere comunque garantito in caso di mancata invocazione di tale funzione regolare)

Questo lavoro è basato soprattutto sul libro di Scott Meyers “Effective C++ – Third Edition”.

Un’ altro riferimento molto interessante è l’articolo di George Belotsky.

Posted in c++, performance | 6 Comments »