Newsgroup: it.comp.lang.c++
Titolo: Il C++ e` piu` lento del C?

Sino a pochi giorni fa pensavo che l'overhead imposto dal C++ rispetto al 
C fosse poco o nullo; anzi, in certe situazioni il C++ dovrebbe essere 
piu` veloce grazie, ad esempio, ad un migliore inlining: si pensi ad 
esempio a std::sort, in cui il compilatore puo` espandere inline i 
confronti rispetto a qsort, in cui ogni confronto costa una chiamata a 
funzione.
Tuttavia un esperimento che ho fatto mi sta facendo cambiare idea: ho 
preso un problema e l'ho implementato in vari linguaggi (tra cui C e 
C++) per valutare efficienza, numero di linee necessarie, semplicita`, 
ecc.
Il problema e` questo: dato in input un file di testo restituire l'elenco 
delle 10 parole piu` usate; per semplicita` con parola si intende una 
sequenza di caratteri separate da whitespaces; ovviamente l'elaborazione 
deve essere case-insensitive.
Per prima cosa ho scritto il programma in C++: dato che la libreria 
standard offre molti strumenti utili il sorgente e` venuto molto corto: 
ecco la parte "centrale"
  typedef std::pair<std::string, int> mapItem;
  std::ifstream f(filename);
  std::map<std::string, int> wordCount;
  std::string s;
  while(f >> s)
    wordCount[tolower(s)]++;
  std::vector<mapItem> wordList(wordCount.begin(), wordCount.end());
  std::partial_sort(wordList.begin(), wordList.begin()+10, 
wordList.end(), cmpWord);
  typedef std::vector<mapItem>::const_iterator it;
  for(it i=wordList.begin(); i != wordList.begin()+10; ++i)
    std::cout << i->first << "\t" << i->second << "\n";
tolower e` una funzione che converte una stringa in minuscolo e cmpWord 
e` una funzione che si occupa di confrontare due coppie (parola, 
frequenza).
Ho provato ad osservare il tempo impiegato ad elaborare un file di circa 
8 MB, ed ecco il risultato:
[anto@anto c++]$ time -p ./word_count ../test.txt > /dev/null
real 5.16
user 4.91
sys 0.06
L'eseguibile e` stato prodotto da g++ 3.1 con le ottimizzazioni al 
massimo (-O3). Da notare che senza ottimizzazioni impiega circa 11 
secondi ad elaborare lo stesso file.
In secondo luogo ho scritto lo stesso programma in C: e` stato piu` 
faticoso in quanto ho dovuto implementarmi una tabella hash ad-hoc, ma 
questo e` il risultato:
[anto@anto c]$ time -p ./word_count ../test.txt > /dev/null
real 1.27
user 1.21
sys 0.02
Come vedete la versione in C e` circa 4.5 volte piu` veloce di quella 
C++: e dire che non ho neppure ottimizzato allo spasimo la tabella di 
hash!
Subito credevo che la differenza in negativo fosse rappresentata da 
std::map: dato che e` implementata come un albero binario le operazioni 
di inserimento/ricerca sono O(logN) contro O(1) delle tabella hash. Tra 
l'altro "a naso" la versione C++ dovrebbe essere piu` veloce in quanto 
abbiamo a disposizione partial_sort che fa il minimo indispensabile, al 
contrario di qsort del C che ordina tutto l'array.
Utilizzando un profiler ho visto che in effetti piu` di meta` del tempo 
era speso in una funzione di inserimento/ricerca nell'albero con cui e` 
implementata std::map.
A questo punto ho provato a vedere qual era l'effetto di una tabella hash 
sulle prestazioni: anziche` usare std::map ho usato l'estesione non 
standard hash_map e questo e` stato il risultato:
[anto@anto c++-hash]$ time -p ./word_count ../test.txt > /dev/null
real 4.06
user 3.94
sys 0.05
Come vedete le prestazioni sono sempre molto inferiori a quelle del C.
Parte del "ritardo" puo` essere spiegato tenuto conto che io sapevo qual 
era l'uso della hashmap scritta in C e quindi ho potuto scrivere una 
versione in qualche modo piu` efficiente di quella general-purpose 
rappresentata da hash_map. Ma una differenza del 320% mi pare 
oggettivamente troppo!
Voi cosa ne pensate?
ciao Anto
-- 
"Computer science is not about computers any more than astronomy
is about telescopes." -- EW Dijkstra

 Voi cosa ne pensate?
personalmente penso che le prestazioni dipendano molto dalla qualità
dell'implementazione delle librerie che usi, in questo caso le STL. E'
una banalità, lo so, ma penso sia l'unico motivo. Se tu prendi il
programma che hai scritto in C molto probabilmente questo è anche un
programma valido in C++, e se lo compili ti darà gli stessi risultati.
Risultato: il C++ è efficiente quanto il C. Il nocciolo della
questione è questo:
"Per prima cosa ho scritto il programma in C++: dato che la libreria
standard offre molti strumenti utili il sorgente e` venuto molto
corto"
quindi:
-1: hai perso poco tempo;
-2: poco codice, poca probabilità di bug.
e
"In secondo luogo ho scritto lo stesso programma in C: e` stato piu`
faticoso in quanto ho dovuto implementarmi una tabella hash ad-hoc".
perciò:
-1: hai perso più tempo (e il programmatore va pagato!);
-2: probabilità di codice buggato più alta.
In sostanza, con la libreria STL risparmi sui tempi, avendo delle
soluzioni già pronte, ma queste non sono ottimizzate per questo o quel
problema. Se è più importante scrivere codice che sia il più veloce
possibile una soluzione ad hoc (riscritta da zero) è quasi necessaria,
se è più importante rispamiare il tempo del programmatore (il tuo) usi
soluzioni già pronte, già testate ma non ottimali (cito: "Parte del
"ritardo" puo` essere spiegato tenuto conto che io sapevo qual era
l'uso della hashmap scritta in C e quindi ho potuto scrivere una
versione in qualche modo piu` efficiente di quella general-purpose
rappresentata da hash_map").
Poi bisogna sempre considerare la qualità del compilatore (magari con,
chessò, il compilatore C++ dell'Intel i tempi sono gli stessi...), la
quantità di copie di oggetti temporanei che vengono introdotte (vedere
l'articolo di Alexandrescu su 
www.cuj.com
 online) che nel tuo
programma sembrano parecchie, exception handling e rtti abilitato, etc
etc etc...

 una banalità, lo so, ma penso sia l'unico motivo. Se tu prendi il
Secondo me infatti, STL va usata e molto perché solida e potente ma non
usata comunque e sempre.
Per andare alla velocità massima (massime prestazioni del codice), spesso
conviene scriversi di proprio pugno tutto, fino ai minimi dettagli.
Anche se ovviamente ci s'impiega molto più tempo e spesso è facile incappare
in bug seri.

Voi cosa ne pensate?
Hai provato anche PERL ? io ho visto che questo programma
"pulito" gira gia' abbastanza veloce:
  while(<>){ $count{lc($1)}++ while(/(\S+)/g) }
  for(sort {$count{$b}<=>$count{$a}} keys %count)
  {
    print"$_ --> $count{$_}\n";
    last if ++$n==10;
  }
(la prima riga fa il conteggio, la seconda parte stampa
 il risultato)
e se poi si "ottimizza" facendo in modo di leggere tutto
il file in una stringa per poi analizzarla per contare
le parole con
  undef $/; $_=<>;
  $count{lc($1)}++ while(/(\S+)/g);
  for(sort {$count{$b}<=>$count{$a}} keys %count)
  {
    print"$_ --> $count{$_}\n";
    last if ++$n==10;
  }
i tempi scendono ancora di un bel po' e si avvicinano
a quelli del C, da cui si conclude che persino PERL e'
piu' veloce del C++ :-)
Dove sta il problema ? Il problema e' che l'intera
libreria del C++ e' stata pensata basandosi sul concetto
che copiare gli elementi contenuti in un container costa
poco. Questo, nel caso delle stringhe o in altri casi
in cui si tirano in ballo parti allocate dinamicamente,
e' tutto tranne che vero.
Per farti un esempio che della parte di "prestazioni"
importa poco alla libreria standard C++ considera che
quando scrivi
   if (s == "Ok")
e s ha come tipo std::string quello che fa il compilatore
e' creare un oggetto std::string partendo dal literal
(chiamando quindi l'allocatore di memoria dinamica,
magari con un bel lock di sincronizzazione se l'ambiente
prevede il multithreading) per poi chiamare la routine
di confronto per poi disfarsi della stringa temporanea
costruita chiamando ancora il gestore memoria (con un altro
potenziale lock). Prova a scrivere invece:
   if (strcmp(s.c_str(),"Ok")==0)
misura la differenza e capirai cosa intendo (con BCC55 sul
mio PC ad esempio c'e' un miglioramento del 6233% !)
Inoltre in alcuni casi ci sono scelte secondo me abbastanza
discutibili (come il basare std::map su oggetti di tipo
pair) che comportano problemi non eliminabili di
operazioni di inutile duplicazione e di creazione di
temporanei per colpa della *interfaccia* dei metodi
(indipendentemente dall'implementazione).
Poi in particolare proprio l'operatore std::map::operator[]
che usi, nella versione originale dello standard era a
dir poco scandaloso e comportava la creazione di diverse
copie della chiave e di istanze temporanee e vuote del
dato contenuto anche nel caso che l'elemento gia' fosse
presente (caso in cui nessuna copia o creazione e'
da un punto di vista logico necessaria).
Per fortuna, almeno su quel punto, e' stata accettata
una correzione che ho proposto qualche tempo fa e che
permette agli implementatori di realizzare un accesso
piu' efficiente senza violare lo standard; soluzione
ottenuta facendo in modo che in quel punto lo standard
non presentasse una soluzione basata su insert... che
e' inefficiente "by design".
Ovviamente questo non autorizza a dire che il C++ e'
piu' lento del C... visto che se rinomini il programma
C e gli dai come estensione "cpp", se aggiungi qualche
typecast sulle allocazioni malloc o se passi a new e
se aggiusti qualche altro dettaglio quello che ottieni
e' un programma C++, che certamente non ha alcun motivo
di essere piu' lento di quello C (anzi... ha modo di
essere piu' veloce).
Quello che si puo' dire e' che pretendere che la
libreria faccia sempre tutto e solo quello che
serve a me in quel caso specifico e lo faccia nel
modo piu' efficiente e sicuro possibile e' abbastanza
utopistico. In questo non credo ci sia nulla di cui
meravigliarsi.
Se usi il C++ facendo finta che le std::string
siano dei tipi nativi e ignorando i loro dettagli
implementativi, se programmi facendo finta che i
container siano perfetti e facciano solo e sempre
quello che serve a te allora corri il rischio di
scrivere delle schifezze (sempre che per te un
programma che sia il 320% piu' lento del necessario
sia una schifezza).
Corri il rischio di scrivere codice che e' piu'
lento di codice *interpretato* il cui interprete
e' stato scritto in C (che sberleffo!).
HTH
Andrea

 Voi cosa ne pensate?
hai ovviamente tolto le eccezione e gli rtti, visto che non mi sembra li 
usi nel codice, dal poco che ne hai postato?
inoltre l'overhead potrebbe stare nella creazione degli oggetti, piu' 
che nel codice: prova a mettere delle routine di timing all'interno del 
codice, solo per la parte che realmente fa il lavoro.
Inoltre dai uno sguardo alle pagine relative a queste prove di alex 
vinokur
http://alexvn.freeservers.com/s1/alexvn.html#label_Algo
alla sez. "STL vs. C"
si vede dai risultati che sono proprio la creazione degli oggetti e le 
chiamate a new/delete a danneggiare maggiormente le performance del C++, 
mentre per molti altri aspetti e' piu' veloce quest'ultimo

 faticoso in quanto ho dovuto implementarmi una tabella hash ad-hoc,
[...]
ecco, appunto. Avresti dovuto usare una hash table anche in C++. Vedere 
le estensioni SGI (non standard) hash, hash_set e hash_map. Se alla tua 
STL mancano, usa STLPort. Personalmente, per tagliare sulle dipendenze, 
uso map indicizzate con hash prodotti da PERL_HASH (man perlguts)
-- 
 < 
http://www.reactos.com/
 >  Open source clone of Windows NT. Current
     Don't stand, REACT!      version 0.0.20. C, C++ and ASM developers
                              and beta testers are welcome!

 -2: probabilità di codice buggato più alta.
su questo concordo pienamente: sto pensando di scrivere un articolo per 
Programmazione.it proprio per valutare questi tradeoff e confrontare 
vari linguaggi; nello specifico ho implementato questo programma in C, 
C++, C++ con hash_map non standard, Java, Python, Python + Psyco (che e` 
un ottimizzatore JIT per python) e Awk; questi sono i risultati in 
termini di efficienza:
c:             1.29
c++:           5.01
awk:           4.32
java:          12.84
c++-hash:      4.03
python:        11.14
python-psyco:  6.36
Il numero di linee varia tremendamente da linguaggio a linguaggio: si va 
dalle 283 linee del C alle 2 (!!!) di Awk, passando per le 47 del C++, 
le 23 di python e le 95 (!!) di Java.
Tra i linguaggi general-purpose direi che python e` quello che offre il 
miglior tradeoff, ma ad impressionarmi di piu` e` stato Awk: 2 linee di 
codice e prestazioni ottime.


 e' stato scritto in C (che sberleffo!).
Vero: in Awk ottengo prestazioni migliori del C++ con map e paragonabili 
a quelle del C++ con hash_map, il tutto in 2 righe di codice e una 
catena di pipe (ed e` stato a quel punto che ho apprezzato veramente 
tutta la meravigliosita` del mondo unix).
Il programma in Awk e` risultato 160 volte piu` corto e 3.5 volte piu` 
lento: un bel rapporto!


lento: un bel rapporto!
Non capisco cosa hai scritto... con questo ragionamento
allora il programma piu' corto in assoluto e' uno script
bash composto da "do_it" (che richiama un programmino che
fa esattamente quello che intendi e che e' stato scritto
in assembler da una gang di finlandesi ed e' ottimizzato
per una sessantina di configurazioni hw con un codice che
dopo aver investito 4 microsecondi di test stabilisce
quale delle versioni usare sul tuo hardware specifico).
Non e' fantastico bash ?
Con questo intendo dire che pensavo che lo scopo fosse
scrivere il programma senza usare nulla se non le
librerie standard del linguaggio.
Se poi intendi fare un confronto di espressivita' e
prestazioni dovresti a mio parere usare un problema
piu' originale (awk e' praticamente stato *progettato*
per fare *esattamente* quel tipo di lavoro...).
Andrea

 (indipendentemente dall'implementazione).
A proposito di copie, temporanei e problemi di efficienza, per quelli
che non hanno seguito le recenti discussioni sulla libreria Mojo di
Alexandrescu, suggerisco questo articolo:
 
http://www.cuj.com/experts/2102/alexandr.htm
Max

 le estensioni SGI (non standard) hash, hash_set e hash_map. 
ehm... ti faccio un copia-incolla dal mio primo messaggio:
<repost>
A questo punto ho provato a vedere qual era l'effetto di una tabella hash 
sulle prestazioni: anziche` usare std::map ho usato l'estesione non 
standard hash_map e questo e` stato il risultato:
</repost>
tra l'altro ho usato proprio l'hash_map di sgi...


 per fare *esattamente* quel tipo di lavoro...).
In effetti awk in origine non era neppure contemplato tra i linguaggi di 
riferimento (anche perche` non lo conoscevo); dopo aver scritto i 
programmi in c++, java e python ho letto qualcosina su awk (per la 
precisione "More Programming Pearls" di Bentley) e mi sono accorto che 
era l'ideale per quel problema; con una conoscenza *molto* sommaria di 
awk ho scritto due righe di script e una pipeline per ottenere il 
risultato che volevo.
Penso che anche l'articolo ricalchera` questo percorso: prima presento le 
implementazioni nei linguaggi general purpose e poi faccio una 
digressione sullo script in awk; la morale della storia dovrebbe 
risultare del tipo "attenti che non ci sono solo i grossi linguaggi; 
spesso uno o piu` tool mirati (specie se siete su unix ;-) possono 
risolvere velocemente un problema". IMHO e` anche un buon consiglio per 
quelli che sono convinti che il C vada bene per fare tutto...
In ogni caso il problema di cui stiamo parlando non e` il solo che ho 
provato ad implementare su piu` linguaggi; idealmente il ventaglio di 
problemi dovrebbe essere di questo tipo:
1) un problema per misurare l'efficienza: ho scelto il crivello di 
eratostene in quanto e` facile da capire, facile da implementare e non 
richiede nessuna struttura dati complessa
2) un problema che faccia uso di quelle strutture dati fondamentali che 
ogni linguaggio dovrebbe avere: mi sembra che "word_count" vada bene in 
questo senso
3) un problema in cui la libreria standard faccia la differenza: mi 
sembra d'obbligo far notare come la libreria standard di C e C++ sia 
notevolmente piu` povera di quelle di altri linguaggi (in questo caso 
python e java); purtroppo non e` facile trovare un problema di questo 
tipo che sia risolvibile in C/C++ utilizzando solo la lib std. Avevo 
pensato ad una elaborazione di file html ma non so bene cosa fare: 
qualche idea?


 ehm... ti faccio un copia-incolla dal mio primo messaggio:
oh. Letto di fretta :-)
