Friday, November 24, 2006 

Improving performances in C++ code

As I've mentioned in my previous post, I've been working with one of my clients at improving the performances of a rather large piece of C++ code (by the way, none of the original programmers is still at the company, which doesn't help :-).
What makes the situation peculiar is that there is no Pareto law at work: the overhead seems largely distributed among hundred (if not thousands) of places. There seems to be no way to get a high return through a small investment. Although most of what we've done so far is rather context-dependent, a few general concepts can always be applied. Here is a distilled list of problems we've tackled, and solutions we've applied:

- inefficient algorithms. This is often considered problem #1 but, in this specific case, it accounted for just a fraction. For instance, std::element was used to find the max element in a std::map, where std::map::rbegin would give you an iterator to the last (and therefore max) element in the map. Even worse, sometimes an element had to be removed from the map, by searching for the value and not for the key. That means linear-time lookup. We changed the algorithm so that the removal wasn't needed anymore.

- temporary objects. A lot of temporary objects where created. Some of those objects did dynamic allocations, and then parts of them were cloned into long-lived objects. There are several techniques to avoid or minimize the creation of temporary objects, and I borrowed some ideas from the "dual classes" approach (Robert M. Adams, Temporary Object Management through Dual Classes, C/C++ Users Journal, April 2003) to eliminate all those clones (which in turn removed several new/delete pairs).

- temporary containers. Sounds similar to the above, but is more complex. The new code relied (as usual) upon existing code. The existing code provided some functions to obtain certain sets of data, hiding a complex internal navigation among different data structures. So far, so good.
The existing code returned those set of data inside containers, which seems pretty logical. However, looking at the profiling data, in our case 3,600,000 temporary containers were created. For each one, we did some processing of the contained data, then discarded the container.
It's interesting to observe that some people in the company hold the opinion that OOP is not efficient: in this case, they would say, the abstraction layer provided by those functions, returning simple containers and hiding the intricacies of the internal structures, has to be paid with inefficiency. A simple solution would be to dismiss abstraction and encapsulation, access the intricate structures directly, and enjoy better performances.
Of course, that's very simplistic. We can have encapsulation and efficiency, we just have to think differently.
A simple approach is to change the function returning the data set into a function returning nothing, but taking one more parameter: a functor to be called for each element. The functor should also be able to inform the function itself that no further iteration is needed. In this way, no temporary container is created. A different approach (more complex) would be to turn the function into a custom iterator. This is what Koenig suggested in a little-known article I've often suggested, as it contains an interesting design insight ("Turning an interface inside out", Journal of Object Oriented Programming, May 1997). In both cases, the gain is huge, encapsulation is even improved (we're not even bound to a concrete container class anymore) and efficiency increases. It's also possible to build the previous interface (returning a container) over the new one, just by passing a back-inserter as the functor, so you don't even lose backward compatibility.

- decoupling overhead. This is by far the most difficult aspect to deal with. Decoupling is a good design principle. However, design is always contextual. Blindly following non-contextual design principles is a recipe for failure.
The company suffered a lot because of strongly coupled code in the past, and a wave of "decoupling at any cost" thinking emerged from that pain. However, in this case there is a big layer of dynamically allocated, interface-based, virtual-inheritance laden, smart-pointers managed code where stack-allocated concrete classes would have been just enough (ok, maybe a regular C++ interface here and there could have been useful as well, but just in the right places). There is also a lot of call forwarding going on inside that layer.
This won't be easy to change, and probably we won't change most of it (which is rather unfortunate). Simple lesson: design is a careful balance of several factors. Pushing too much on one side won't give you balance. Following rigid guidelines, outside the problem context, makes a lot of critical thinking disappear, which may be good for your cognitive load :-) but not for the ultimate result (this is also true when you're constrained by overly restrictive frameworks and languages, but that was not the case).

- caching result: that's pretty easy. Because of the way the algorithms work, the same function was called in many cases with the same exact parameters. I didn't need to build a sophisticated cache: just keep the previous parameters and result, do a simple check, and return the cached value when possible. I had some doubts about the simplicity of this caching mechanism, which can be easily invalidated, but trying that on real cases we saw a 99.8% cache hits, which is just excellent :-) and doesn't need any further improvements (actually, trying to improve on that with more sophisticated caching would probably make the overall performance worse).

- overall, profiling was invaluable. However, looking at times wasn't really that useful, as the overhead was really distributed among thousands of functions. What I've found really useful is the visit count for each function. Looking at those numbers, we can understand (or guess :-) if we have non-linear computational complexity, and where. We can also see how many temporary objects we have, for each class, by just looking at counts for constructors and destructors. In practice, the profiling tool we used was good enough to be used on a large project, but not so handy when exploring result. However, the tool saved the results in XML (although they didn't say so :-), therefore I wrote a small program to do some useful processing of that XML, export the results to Access, and built some handy queries, so that I could see at a glance (for instance) the cumulative cost of all the member functions of a given class, divided by parent function in a pivot table, and so on. That made some decision-making a whole lot easier.
Un post pieno di spunti interessanti, wow!

Volevo chiederti, a proposito del problema temporary objects, se non si possa fare qualcosa a livello di design per evitare il problema alla radice.
La soluzione esposta da Adams ha il difetto di essere circoscritta alla particolare classe da ottimizzare e non applicabile facilmente a un intero modello.
Mi domando se un diverso modo di modellare le classi, che vada decisamente verso il conteggio d'usi, sia la soluzione ideale a questo problema del C++ (ovvero la creazione di un numero immenso di oggetti temporanei).
Penso a un sistema con smart pointer, niente di piu' nuovo: gli oggetti delle classi del modello sono allocati sempre dinamicamente e riferiti tramite smart pointer, che sono i soli oggetti allocati sullo stack.

A proposito dei temporary containers, certamente la soluzione del functor e' molto elegante, ma io non darei tutti i torti ai sostenitori dei "vecchi tempi": nel caso specifico si poteva usare il functor, ma non sempre si puo'. Penso a quando l'elaborazione del dato N richieda anche di consultare il dato N+x (e N-y), per esempio. Certe volte ci vuole un contenitore e non si scappa.
In tali casi, come procederesti? Riciclando i contenitori usati? A istinto direi che il conteggio d'usi aiuti anche qui, ma non ci ho pensato moltissimo e non sono sicuro.

Sul caching result: ma non se ne sono accorti da soli? ;-)
Sui temporary object, la sostituzione con oggetti condivisi via reference count e' da valutare caso per caso, come sempre (nello stesso progetto, l'overhead del reference counting si fa sentire in modo sensibile).
In generale i temporanei stack-based possono essere largamente piu' efficienti rispetto alle allocazioni / deallocazioni dinamiche. Bisogna vedere caso per caso (dimensioni, utilizzo, numero di "scambi" di proprieta' Vs. numero di utilizzi, ...). Nel caso specifico, il pattern era piuttosto semplice (creazione di temporanei, clonazione dei loro pezzi dentro oggetti long-lived), e l'idea di rubarne le sottoparti, presa dalle classi duali, si implementa facilmente. Siccome lo scambio di proprieta' avviene una sola volta, poter rimanere su puntatori non smart evita altri inutili overhead...

temporary container: sicuramente, se l'algoritmo che usa i dati non e' sequenziale, niente functor (nel caso specifico, se x ed y sono offset fissi, ce la caveremmo comunque :-). Tuttavia, se tu progetti una funzione e non sai come verra' usata, l'alternativa a functor e' migliore: come accennavo, se hai la versione a functor ottieni facilmente la versione a contenitore (basta passare un back inserter come functor). Se hai solo quella a contenitore, non avrai mai le efficienze di quella a functor...
Riusare i container e' problematico, e se la dimensione e' diversa ogni volta, e' difficile guadagnare granche' senza scrivere codice di complessita' sempre crescente...

cache: non essere cattivo con dei poveri innocenti :-). Peraltro sotto sotto sono abbastanza sicuro che ci siano altre funzioni cache-abili, ma temo che nessuno mi offra sufficienti garanzie sugli effetti collaterali...
This post has been removed by a blog administrator.
Non vorrei dire una minch***a, ma i rvalue reference (&&) nel nuovo standard servono proprio in occasioni del genere (e non solo)? Giusto per vedere se ho capito!
nel caso specifico, se x ed y sono offset fissi, ce la caveremmo comunque
Stavo per specificare che x e y erano variabili, ma ho desistito, tanto era chiaro. Poi se uno e' pignolo... ;-)
Comunque, anche con x e y fissi, se la ricerca e' multithreaded il functor puo' non andare bene.

Riusare i container e' problematico, e se la dimensione e' diversa ogni volta, e' difficile guadagnare granche' senza scrivere codice di complessita' sempre crescente
Non so se si poteva applicare anche a questo caso, ma mi e' tornato in mente un giochetto che puo' fare davvero la differenza.
Supponiamo di avere la necessita' di creare un gran numero di contenitori di oggetti dello stesso tipo, con dimensione variabile (magari piu' o meno prevedibile). Creiamo un bel contenitore grande e lo sfruttiamo per annientare i tempi di allocazione dei contenitori temporanei. L'idea e' quella di far puntare i contenitori temporanei a zone di memoria del contenitore grande. In pratica si fa il lavoro di un allocatore ottimizzato, col vantaggio di conoscere in partenza le statistiche sulla dimensione dei contenitori.
Non ho numeri interessanti da proporre, posso solo dire che nelle prove "di laboratorio" saltavano fuori risultati promettenti, poi bisogna vedere in un programma vero.

Sul decoupling overhead dici: "There is also a lot of call forwarding going on inside that layer". Che se non sbaglio vuol dire: un po' di tempo viene perso solo per ricevere una chiamata a un metodo e inviarla, percorrendo piu' livelli di interfaccia, alla classe che esegue concretamente la chiamata.
Non ho nulla di particolare da aggiungere a cio' che tu hai gia' detto, che condivido in pieno, solo vorrei commentare che molto spesso si pensa ad astrarre, incapsulare, seguire pattern, fare cose "eleganti", e si dimenticano i tre aspetti di base: complessita' del codice e dell'architettura, velocita' di esecuzione, occupazione di memoria. Questi tre aspetti secondo me sono il 90% del valore di un programma agli occhi di chi sviluppa.
Mi viene anche da dire che i nuovi linguaggi hanno molte caratteristiche che aiutano lo sviluppatore, ma lo allontanano dal silicio. Temo che le valutazioni sull'impatto in termini di velocita' e memoria, tante volte trascurate, saranno sempre meno facili (e sempre piu' trascurate).
Noto che Carlo non cita un eventuale analisi delle query. Allora, o il sw in questione non accede (o non accede significativamente) ad un db o Carlo ci sta ancora lavorando. Nella mia esperienza spesso nei "pressi" del db si trovano cose molto interessanti. .. E spesso si riesce ad ottimizzare il tutto con il giusto meccanismo di chaching (magari precaricando un po' di cose nella fase di startup del sw) per ciò che è non modificabile (barattando la cosa con un po' di memoria fino al giusto punto di equilibrio... la vita non è mai facile :-) )

x Fulvio: si, rvalue reference dovrebbe servire anche a ciò. Faranno molto probabilmente parte del nuovo standard del C++, ma dobbiamo avere pazienza...

X Citrullo: non sono affatto d'accordo con l'ultima tua affermazione: "Questi tre aspetti...". Quando scriviamo del sw stiamo comunicando con qualcun altro (pensa allo specifico caso di Carlo che sta facendo manutenzione senza nessuna persona originariamente appartenuta al team di sviluppo). Dobbiamo sforzarci di farlo nel miglior modo possibile. E non sto a sindacare sulla parola pattern :-) che spesso ci aiutano proprio a fare meglio quel 90% di cui parli :-)
Michele, non intendo affatto sostenere che i pattern siano inutili perdite di tempo, cosi' come un design di buon livello. Anzi, sono fondamentali!
Dici "quando scriviamo del sw stiamo comunicando con qualcun altro": hai ragione, mica penso diversamente. Architetture balzane e codice confuso sono da evitare.
Pero' attenzione a non dimenticare che il codice verra' eseguito da un computer! Se non si fa attenzione all'impatto che la bella soluzione di turno avra' sull'esecuzione, ci si trova in un attimo con "a big layer of dynamically allocated, interface-based, virtual-inheritance laden, smart-pointers managed code where stack-allocated concrete classes would have been just enough". ;-)
Credo che sia importante perche', proprio come nel caso di Carlo, i singoli pezzetti di codice si possono ottimizzare, mentre le architetture sono quasi immutabili, con le loro inefficienze.
Tutto qui...
La mia obiezione era sul fatto che, a mio avviso, astrarre, incapsulare, seguire pattern, fare cose "eleganti" ci aiuta ad ottenere quanto anche tu sostieni essere fondamentale, ossia una buona architettura.
Direi, quindi, che sebbene in termini diversi siamo d'accordo su tutto (o quasi :-) )
Michele: in effetti il programma e' proprio DB-free :-), altrimenti [come giustamente dici] sarebbe uno dei punti in cui guardare. Poi potrei dire che tutte quelle incasinatissime strutture dati non fanno altro che creare un database [non relazionale] in memoria, ma qui diventa una storia lunga e controversa...

Citrullo: torno un attimo sul riuso dei container. La strategia che citi ha senso principalmente per un tipo di container (il vector), se il contenitore e' una lista finiamo nel solito small block allocator, se e' una mappa anche, ma in questi casi dire che "riusiamo i container" e' un overstatement. Sugli small block allocator tutti abbiamo prima o poi riposto i nostri sogni :-). In un vecchio post sui wise pointer (che non ho mai finito, mi manca l'idea geniale risolutiva dell'inlining) facevo notare che l'incremento di velocita' non e' particolarmente rilevante, e che se non si fanno le cose proprio per bene si rischia il crash.

Rimaniamo sul vector: in fondo anche il tuo e' un allocatore custom, un large block allocator. Quindi, per farlo piu' performante rispetto a quello di libreria, abbiamo "solo" due ragionevoli possibilita':

- come accennavi, conosciamo a fondo il comportamento del nostro programma, e riusciamo a trasformarlo in una euristica di allocazione. Non e' proprio semplice semplice su programmi complessi, perche' anche i vector non hanno sempre le stesse dimensioni (e neppure lo stesso ordine di grandezza in molti casi).

- siamo disposti a legarci piu' a fondo alla piattaforma. Ad es. se sappiamo di aver bisogno di matrici / vettori sparsi, o vogliamo dei vector in grado di crescere senza pagare l'overhead di copia, ed utilizziamo ad es. Windows, possiamo utilizzare per il nostro allocatore le primitive di gestione della memoria virtuale, riservare le pagine senza commit, fare un commit al page fault, eccetera. Questo ha un suo senso in situazioni particolari, ma di nuovo, non e' una soluzione generale.

Sull'allontanarsi dal metallo, con la conseguente difficolta' di prevedere gli aspetti prestazionali: e' decisamente vero, una volta che ho tempo ci torno su con un esempio piuttosto sorprendente di comparazione C++ / C#.
Come mai non si parla di allocazione dinamica sullo stack per i temporanei? C'e' qualche grave controindicazione?
Non so se ho capito benissimo la domanda :-), provo comunque a scrivere qualcosa che mi pare correlato e che spero possa vagamente interessare chi legge.

Esistono estensioni non-standard del C++ (nel caso specifico implementate dal GCC) che permettono di allocare array a dimensione variabile sullo stack.

Da un punto di vista concettuale, l'operazione e' molto semplice: si riaggiusta lo stack pointer anziche' allocare memoria dinamicamente, dopodiche' si ricade nel solito caso della costruzione di oggetti: ho un pezzo di memoria a disposizione, devo trasformarlo in un array di oggetti chiamando i diversi costruttori. La distruzione e' altrettanto semplice ed altrettanto efficiente.

Ci sono indubbi vantaggi nel fare questo, e pochi svantaggi (direi piu' filosofici che pratici):

- di solito lo stack segment e' piuttosto limitato. Se facciamo pasticci, andiamo in stack overflow. Mentre (teoricamente) con un array di dimensione fissa si puo' fare qualche verifica compile-time [poca roba, dovremmo eliminare la ricorsione per fare verifiche certe] qui non c'e' alcun modo di controllare alcunche'.

- siccome un array decade implicitamente nel puntatore al suo primo elemento, c'e' il solito rischio di ritrovarsi dei dangling pointers a variabili locali.

- l'array dovrebbe occupare una dimensione superiore a sizeof(T)*N, perche' deve avere un posto per memorizzare N (altrimenti non si riescono a chiamare i distruttori, essendo N variabile).

A occhio non vedo altri problemi, e come dicevo, sono problemi piuttosto marginali, perche' siamo in C++, a queste cose occorre stare attenti comunque.

Per quel che mi riguarda, passerei volentieri l'estensione nello standard e poi, nell'ottica di un linguaggio a 2 livelli, ci costruirei su una classe AutoVector o simili che limiti almeno il problema dei dangling pointers.
Idealmente, la classe dovrebbe controllare in modo platform-dependent se c'e' spazio nello stack prima di sfasciare tutto, ma questa la vedo piuttosto dura...
This post has been removed by a blog administrator.
Provo a spiegare meglio cosa intendo per "riuso dei container". Per il momento mi limito ai vector, ai quali pensavo all'inizio, ma credo che anche gli altri tipi di contenitore si possa fare qualcosa.
Dalla tua frase "in our case 3,600,000 temporary containers were created. For each one, we did some processing of the contained data, then discarded the container" io deduco che il ciclo di vita del singolo contenitore temporaneo sia piuttosto semplice. Del tipo:

vector temp;

Puo' anche essere un po' piu' complesso, ma il succo e' che si possono individuare iterazioni nelle quali viene eseguito codice del genere.
La mia supposizione, che puo' anche essere inappropriata per il tuo caso, e' che ad ogni iterazione vengono creati un numero fisso, o largamente prevedibile, di vector temporanei. Di conseguenza ad ogni iterazione vengono distrutti tali vector.
Se cio' e' vero, ecco che torna utile avere un grande vector gia' allocato. All'inizio dell'iterazione e' libero, poi sue porzioni vengono assegnate ai diversi vector temporanei usati nell'iterazione, e alla fine viene liberato nuovamente.
Ma forse il tuo caso e' piu' complesso, e i temporanei non hanno una vita cosi' schematica. Allora si puo' tentare di raggrupparli per affinita' di data di nascita e morte, e attribuirne la responsabilita' ad un vector dedicato: il caso piu' elementare e' quello di tutti i vector temporanei che nascono e muoiono in una data funzione.
Credo che la statistica piu' determinante sia: mediamente quanti vector temporanei sono vivi contemporaneamente? Saputo questo (un bel contatore in costruttore e distruttore e via), si fanno tante deduzioni di conseguenza.
Si, direi che era abbastanza chiaro quel che intendevi. Forse non e' chiaro quello che io intendevo :-).

- se non usi un vector ma altri container (list, map, ecc) la tua strategia "del grande blocco" non funziona, e finisci nei soliti small block allocator (perche' ogni nodo del container viene allocato individualmente).

- se usi vector, stai creando un large block allocator (quello che descrivi e' un large block allocator). Da qui quanto dicevo: devi essere MOLTO piu' furbo dell'allocatore di libreria, altrimenti non vale la pena, considerando che il custom allocator dovra' essere "riallineato" a fronte di alcuni interventi di manutenzione / modifica del codice. Vale quanto visto storicamente per gli small block allocator: via via che gli allocatori general purpose migliorano, quelli custom diventano sempre meno interessanti.

Tieni sempre presente che costruire un vector significa anche chiamare un tot di costruttori di copia per infilarci dentro gli oggetti, mentre in una versione ad iteratore (che e' piu' bella ma piu' complicata) o a funtore (piu' facile) questa copia non esiste.
Significa anche sapere quanti elementi hai sin dall'inizio, per allocare il vector gia' della giusta dimensione, cosa ancora piu' importante nella tua versione con custom allocator (e comunque per evitare altri costruttori di copia).

Inoltre le versioni lazy (sia quella ad iteratore che quella a funtore possono essere viste come lazy) sono particolarmente indicate per i casi in cui quella che tu chiami ProcessVector puo' fermarsi quando ha raggiunto un certo risultato, non noto ad una FillVector riusabile.

Ovviamente ci sono casi in cui all'algoritmo serve tutto il container (banalmente un sort). Ma sono tantissimi i casi in cui si puo' ideare una versione che non ha bisogno del container. L'articolo di Koenig che citavo mostra alcuni interessanti esempi...
This post has been removed by a blog administrator.
This post has been removed by a blog administrator.
This post has been removed by a blog administrator.
This post has been removed by a blog administrator.
This post has been removed by a blog administrator.
This post has been removed by a blog administrator.
This post has been removed by a blog administrator.
This post has been removed by a blog administrator.
commentators: speak english or die ;-)
Post a Comment

<< Home