Newsgroup: it.comp.lang.c++
Titolo: Prestazioni C++/STL di MSVC++6

Salve,
recentemente ho effettuato un porting di un semplice parser xml da
java a c++ con l'idea di includerlo in un progetto MSVC++6.
A casa dispongo solo del DevC++ (con gcc 2.95) e l'implementazione
tramite STL ha portato ad un miglioramento (rispetto java) del 5-20%.
Quando ho avuto la possibilità di compilarlo con il VC++, le
prestazioni mi hanno deluso: oltre il doppio di quanto ci metteva
java!
Da quello che ho capito l'implementazione MS delle STL non è molto
ottimizzata (soprattutto per quanto riguarda le map), soprattutto
rispetto a quella SGI-HP usata dal gcc. La cosa mi ha sorpreso perchè
in altri campi il compilatore MS si è dimostrato *decisamente* più
performante del gcc (sui calcoli intensivi).
Uso i template map<string,string> e vector<char> e le classi string e
filebuf.
Mi sembra che MS non offra alternative per le map (come CString al
posto di string) oppure mi sono sfuggite (sono un po' arruginito di
MFC...)
Qualche consiglio? Nessuno ha avuto esperienze a proposito?
Nota: sui newsgroup ho trovato solo messaggi sulla
difficoltà/impossibilità ad usare le STL della SGI con i compilatore
MS e la già citata scarsa efficenza delle map.

 MS e la già citata scarsa efficenza delle map.
Concordo pienamente sull'argomento difficoltà/impossibilità...
Se proprio vuoi utilizzare MFC esistono dei template sostitutivi dei
contenitori STL. Devi includere il file <afxtempl.h> (o una cosa simile).
I template forniti sono:
CArray == vector
CList == list
CMap == map
Tuttavia in quanto a prestazioni mi sono trovato abbastanza male anche con
queste classi (ma l'ultima volta che le ho usate - MOOOLTO tempo fà -
confondevo ancora liste e vettori, quindi ti consiglio di provare lo
stesso).

 java!
Hai compilato in modalita' release con optimise speed attivato?
Quando apri un progetto, di dafault ti da modalita' debug non ottimizzata!
Tommy

 Quando apri un progetto, di dafault ti da modalita' debug non ottimizzata!
Basta che guardi dove e' l'eseguibile! Se e' in una cartella che si chiama
debug sei in modalita' debug, se si chiama release sei in mod. release! Se
sei in release puoi sempre andare su settings per cambiare i settaggi. Se
sei in mod. debug devi andare su choose active configuration e scegliere
release. Debug e' molto piu' lenta di release.
Tommy

 stesso).
Ho provato con
map<string,string> --> CMapStringToString
string --> CString
vector<char> --> CArray<char,char>
Risultato: dalla padella alla brace...
Grazie comunque.

...

Anche con il compilatore Intel 7.0 i risultati sono deludenti
(ovviamente con tutte le ottimizzazioni possibili)

Risultato: dalla padella alla brace...
Diventa difficile capire quale possa essere il problema
se non si vedono un po' di statement.
In C++ purtroppo e' molto semplice scrivere codice che
sembra bello e che in realta' e' osceno da un punto di
vista di prestazioni. Ci sono alcune aree buie, in cui
l'implementazione fornita dallo standard e' effetivamente
terribilmente meno efficiente del meglio ottenibile, ma
e' raro che un problema simile non si possa isolare e
risolvere nello specifico.
Se tu facessi un esempio concreto con un frammento
di codice che trovi poco performante forse qualcuno
potrebbe comprendere dove sta il problema.
L'ultima volta che un amico mi ha detto di avere un
problema di prestazioni nel salvataggio di un file e'
venuto fuori che per andare a capo usava std::endl
invece di "\n" (!).
Andrea

 invece di "\n" (!).
e questo cosa comportava?



std::endl oltre a mettere un "a-capo" svuota anche
i buffer (flush). Ti sembra una differenza da poco ?
Andrea

 i buffer (flush). Ti sembra una differenza da poco ?
Ora che lo so no :)
grazie

 wrote
Mi trovo perfettamente d'accordo!
Gio, prova a postare il codice!
Tommy

 risolvere nello specifico.
Il problema è che lo stesso codice, compilato con il devc++ (gcc
2.95), dà ottime prestazioni. A spanne: gcc 1.3 secondi, java 1.7,
vc++6 >9, vc++6 con MFC >10.
Credo che un codice ragionevole, anche se non ottimizzato al massimo,
debba fornire prestazioni migliori di quelle ottenute con il vc++.
Tanto per fare un esempio, in un primo momento avevo usato string +=
(non molto ragionevole :-) al posto del vector<char> (con reserve), e
le prestazioni col gcc erano di 1.6 sec!
Il problema è sicuramente nella divisione in token e nella creazione
delle map conteneti le coppie key,value.
Ci sono due aspetti da considerare:
1) flessibilità:
Ad esempio un codice del tipo:
string getNextToken() {
   vector<char> buffer; 
   // tutti i tag nel file di prova
   // sono più corti di 128 caratteri
   buffer.reserve(128);
   while (...) {
      ...
      buffer.push_back(ch);
   }
   return string(buffer.begin(),buffer.end());
}
mi permette di evitare errori di overflow nel caso un tag fosse più
lungo di 128 caratteri (così come il corrispondente codice java che
usa StringBuffer)
2) funzionalità:
Potrei pensare ad altri modi per immagazzinare le coppie nome=valore
degli attributi dei tag xml, ma se in java posso usare un codice
"comodo" del tipo:
value = attr.get(key);
e le map del c++ (fatte apposta, mi sembra) mi permettono di usare:
value = attr[key];
mi aspetto almeno prestazioni simili!
Ripeto che quello che mi ha lasciato perplesso è la differenza di
prestazioni dello stesso codice fra la compilazione gcc e vc++ poichè,
in altre occasioni, si era dimostrato il contrario: è un segno
evidente che la MS supporta solo formalmente le STL, ma anche con le
MFC non ho ottenuto risultati migliori (per quanto cane possa essere a
scrivere codice, mi aspettavo un tempo di esecuzione di al massimo 5
sec.)

...

class XmlParser
{
   map<string,string> attr;
   vector<char> buffer;
   filebuf file;
   ...
};
XmlParser::parseTag()
{
   attr.clear();
   while(...) {
      string key = getNextToken();
      string value = getNextToken();
      attr[key] = value;
   }
   ...
}
string XmlParser::getNextToken()
{
   while(...) {
      ch = file.sbumpc();
      buffer.push_back(ch);
   }
   return string(buffer.begin(), buffer.end());
}
Alcune piccole modifiche (ad esempio il buffer dichiarato in
getNextToken) portano a delle differenze minime dei tempi di
esecuzione: 1.6-1.3 sec., contro di >9 sec dello stesso codice in vc++

esecuzione: 1.6-1.3 sec., contro di >9 sec dello stesso codice in vc++
Credo che il tuo problema con VC++ sia un altro...
io ad esempio in passato ho avuto terribili sorprese con
la funzione atof che su VC e' insipegabilmente lenta.
Io ho provato a scrivere una versione che invece di
usare std::map<std::string,std::string> utilizzasse
due vector paralleli manipolati in modo da tenere
le coppie ordinate per chiave evitando di chiamare
l'allocazione dinamica...
class XmlParser
{
  private:
    std::vector<std::string> keys;
    std::vector<std::string> values;
    std::vector<char> buffer;
    std::filebuf f;
    std::string getNextToken();
  public:
    XmlParser(const char *fname)
    { 
      f.open(fname,std::ios::in);
    }
    bool parseTag();
    void dump() const;
};
bool XmlParser::parseTag()
{
  keys.clear();
  values.clear();
  for(;;)
  {
    std::string key=getNextToken();
    if (key.size()==0) break;
    std::string value=getNextToken();
    // Ricerca punto di inserimento
    std::vector<std::string>::iterator
      i=std::lower_bound(keys.begin(),keys.end(),key);
    if (i!=keys.end() && *i==key)
    {
      // Trovato, esegui update
      values[i-keys.begin()].swap(value);
    }
    else
    {
      // Inserisci la nuova coppia al punto giusto
      int p=i-keys.begin();
      keys.resize(1+keys.size());
      values.resize(1+values.size());
      int j=values.size()-1;
      values.back().swap(value);
      keys.back().swap(key);
      while (j>p)
      {
        keys[j-1].swap(keys[j]);
        values[j-1].swap(values[j]);
        --j;
      }
    }
  }
  return !keys.empty();
}
Questa versione impiega su un file di prova da 2Mb
contenente cose come
  campo74191=valore74191
  campo80670=valore80670
  campo7962=valore7962
  campo57458=valore57458
  campo86795=valore86795
  campo44915=valore44915
  campo69906=valore69906
  campo7684=valore7684
  campo24707=valore24707
  campo23269=valore23269
  campo86001=valore86001
  campo39785=valore39785
  campo527=valore527
  campo1824=valore1824
  campo84988=valore84988
un dimezzamento dei tempi di elaborazione.
Un altro grosso miglioramento (2.5:1, portando il totale
a circa 5:1 rispetto al codice originale) l'ho ottenuto
usando un approccio ancora piu' radicale in cui tutti i
dati di un singolo blocco erano letti in un unico
std::vector<char> e le coppie chiave-valore erano
codificate tramite indici interi in questo vector.
Cosi' facendo infatti le allocazioni dinamiche
richieste si riducono ancora e anche la lettura
puo' essere fatta direttamente nel vector finale
senza richiedere una copia.
E' chiaro che cosa sia un effettivo miglioramento
e cosa sia invece uno stravolgimento inaccettabile
dipende dal contesto. Se a te serve per forza una
std::map<std::string,std::string> allora non puoi
fare a meno di costruirla, e questo purtroppo comporta
un certo numero di allocazioni in eccesso rispetto
al minimo teorico. Se ti servono solo alcune delle
funzionalita' (ad esempio accedere ai valori usando
operator[]) allora sono possibili molte altre
soluzioni alternative.
HTH
Andrea


-- 
  < 
http://www.reactos.com/
 >  Open source clone of Windows NT. Current
      Don't stand, REACT!      version 0.1.0. C, C++ and ASM developers
                               and beta testers are welcome!

 Andrea
Ancora grazie mille.


Con "difficoltà/impossibilità" intenedevo dire che è *molto*
difficile, abbastanza da creare più problemi che vantaggi. Cmq, questo
è quello che ho letto nei msg, non un'esperienza personale.
Effettivamente sembra che STLport sia compatibile con il VC++ (almeno
da quello che ho letto sul loro forum): provero'.
Grazie della segnalazione!

sarebbe molto lungo e forse OT.
Questa cosa lascia perplesso anche me. Non riesci a
mostrare o fornire un link con un esempio completo e
compilabile (senza "..." in cui si potrebbe nascondere
di tutto) del codice C++ in cui trovi le prestazioni
molto scadenti, magari con un link ad un file dati di
esempio da prendere come riferimento ?
Personalmente non credo affatto che una discussione
sulle prestazioni di codice C++ standard sia OT.
Andrea

 MS e la già citata scarsa efficenza delle map.
Ti consiglio di scaricare le stlport da 
http://www.stlport.org/
Funzionano alla grande con MSVC 6, non hanno mezzo bug e sono MOLTO
performanti (configurale bene mi raccomando).
Fammi sapere come ti vanno :-)

Sorry non avevo notato che te le avevano già consigliate, m'era sfuggito il
mex.

 sulle prestazioni di codice C++ standard sia OT.
Io mi riferifo più che altro al fatto che le differenze con Java non
siano così eclatanti a fronte dei molti vantaggi del linguaggio di
Sun.

Per i test utilizzo un file di 25 MB con elementi del tipo:
<object attr1="value1" attr2="value2">
	<item x="1" y="2"/>
	<item x="1" y="2"/>
	<object attr1="value1" attr2="value2">
		<item x="1" y="2"/>
		<item x="1" y="2"/>
	</object>
</object>
Dovrebbe andare bene qualsiasi file xml ma non garantisco!
// XmlParser.cpp: /////////////////////////////////////////////////////////////
#include <string>
#include <iostream>
#include <vector>
#include <map>
#include <fstream>
// serve solo per GetTickCount()
#include <windows.h>
using namespace std;
typedef map<string,string> XmlAttributes;
class XmlHandler
{
public:
    void startTag(const string& sTagName, XmlAttributes& attr) {};
    void endTag(const string& sTagName) {};
};
class XmlParser
{
protected:
    vector<char> m_buffer;
	filebuf m_file;
    string m_sTag;
    XmlHandler *m_pXH;
    XmlAttributes m_attributes;
public:
    XmlParser(XmlHandler *pXH);
    void parse(const char* szFilename);
protected:
    inline string getToken(const char endFlag);
    inline void parseTag();
    inline void stripComment();
};
int main(int argc, char *argv[])
{
	cout << "XML Parser Test (C++)\n";
	if (argc == 2) {
		XmlHandler xh;
		XmlParser* pXP = new XmlParser(&xh);
		DWORD dwStart = GetTickCount();
		pXP->parse(argv[1]);
		DWORD dwEnd = GetTickCount();
		cout << "Parsing done in " << (dwEnd-dwStart) << " ms\n";
	}
	return 0;
}
XmlParser::XmlParser(XmlHandler *pXH)
{
    m_pXH = pXH;
    m_buffer.reserve(128);
}
void XmlParser::parse(const char* cszFilename)
{
    m_file.open(cszFilename, ios::in|ios::binary);
    while (true) {
        int ch = m_file.sbumpc();
        if (ch == EOF) {
            break;
        } else if (ch == '<') {
            m_sTag = getToken(' ');
            if (m_sTag.find("!--") == 0) {
                stripComment();
            } else if (m_sTag[0] == '/') {
                m_pXH->endTag(m_sTag.substr(1));
            } else {
                m_file.sungetc();
                parseTag();
            }
        }
    }
    m_file.close();
}
string XmlParser::getToken(const char endFlag)
{
    m_buffer.clear();
    while (true) {
        int ch = m_file.sbumpc();
        if (ch == EOF || ch == '>' || ch == endFlag)
            break;
        m_buffer.push_back(ch);
    }
    return string(m_buffer.begin(), m_buffer.end());
}
void XmlParser::parseTag()
{
    bool bEndTag=false;
    m_attributes.clear();
    while (true) {
        int ch = m_file.sbumpc();
        if (ch == '>') {
            break;
        } else if (ch == '/') {
            bEndTag = true;
            break;
        }
        string sKey = getToken('=');
        ch = m_file.sbumpc();
        if (ch != '\"')
            break;
        string sValue = getToken('\"');
        //m_attributes[sKey] = sValue;
        m_attributes.insert(pair<const string,string>(sKey,sValue));
    }
    m_pXH->startTag(m_sTag, m_attributes);
    if (bEndTag) {
        m_pXH->endTag(m_sTag);
    }
}
void XmlParser::stripComment()
{
    int iFound = 0;
    while (true) {
        int ch = m_file.sbumpc();
		if ((ch == EOF)||(ch == '>' && iFound == 2)) {
			break;
        } else if (ch == '-') {
            if (iFound == 0 || iFound == 1)
                iFound++;
        } else {
            iFound = 0;
        }
    }
}

    attr[key] = value;
Se l'uso diretto di insert() "appare"  più efficiente di operator[] è
probabile che operator[] non sia implementato nel modo originariamente
proposto dallo Standard (cfr. quello che ha detto Andrea in proposito
qualche giorno fa). 
Ciò non implica però che operator[] sia sempre meno efficiente di
insert(). Mi aspetterei, invece, che abbia prestazioni migliori nei casi
in cui la chiave già esista nella mappa.
Max

</object>
Compilando il tuo programma con VC++ e utilizzando un file
di 19Mb ottenuto replicando l'esempio che hai fatto ho
visto che g++ e' circa il doppio piu' veloce di VC++ che
a sua volta e' leggermente piu' veloce di BCC55.
Sostituendo l'allocatore standard con un l'allocatore
custom VC++ e' diventato piu' veloce di g++ (1.6sec contro
2.14 sec). Il cambio di allocatore non ha avuto invece
effetti sul codice BCC55 e g++ (una volta g++ semplicemente
ignorava allocatori custom nella sua implementazione di
STL e allocava la memoria con chiamate sue... forse lo
stesso vale ancora per la versione 3.2).
L'allocatore che ho usato e' estremamente brutale: tiene
una lista libera per ogni dimensione di blocco sino a 4Kb;
ad ogni richiesta prima controlla la lista e se c'e'
qualcosa da riusare la riusa, altrimenti chiama malloc.
Andrea

 Andrea
Grazie, 
Giovanni