[C++] Memorizzare una grande quantità di dati a runtime

[freetom]

Originariamente inviato da GliderKite
In realtà non è proprio un raddoppio delle dimensioni, ma anche fosse ciò non toglie che più cerchi rapidità più ti dovresti allontanare dall'utilizzo di un vector. Senza considerare se se le dimensioni sono piuttosto considerevoli reallocare uno spazio simile richiede risorse davvero eccessive per qualsiasi operazione direi. Ovvio che se conosci a priori il numero di elementi ridimensionare il vettore all'inizio è una valida alternativa, ma anche in questo caso una resize è più dispendiosa di un'allocazione "standard" con new/malloc (inizializzando anche gli elementi del vettore a 0, operazione che se necessaria viene svolta molto più velocemente dalla memset).

In definitiva i vector vanno molto bene per compiti per i quali sono stati pensati, ossia per i casi più generali possibili quindi niente a che vedere con operazioni specifiche e volutamente performanti.

Stack, queue e strutture dati analoghe implementate attraverso l'utilizzo di liste concatenate richiedono una maggior analisi precedente per verificare se effettivamente possono avere vantaggi rispetto all'utilizzo di un vettore. Quindi dipende sempre da cosa si deve effettivamente fare, come sempre d'altronde.

Leggendovi si nota il vostro immenso scibile in questo campo!
Però io che sono molto a digiuno non riesco a "implementare" il vostro sapere.

Potete farmi un. es. banale per velocizzare ad esempio questa operazione:

ritardi.push_back(ritardo);

dove ritardi ha solo 2 posizioni (indici) [0] e [1] e sono tutti valori interi da 0 a 4000.

Come trasformereste questa riga con le vostre spettacolari e praticissime velocizzazioni?

Ancora Grazie Infinite a tutti

[GliderKite]

Se il vettore ha, ed avrà sempre due elementi, qualsiasi operazione che compi per inserirvi gli elementi è praticamente confrontabile con qualsiasi altra sul piano del numero di operazioni, o meglio sul tempo impiegato per effettuarle. Quando ottimizzi il codice devi valutare sempre se ciò comporta un effettivo miglioramento, in questo caso la differenza sarebbe talmente trascurabile che utilizzare un contenitore della STL come vector è sicuramente meglio in C++ rispetto a quello che avevo precedentemente proposto.

Quindi quello che fai va benissimo

[MItaly]

Giusto per mettere in campo qualche numero:

matteo@teoubuntu:~/cpp/vectorbenchmark2$ ./vectorbenchmark2 
Inserire il numero di elementi: 2000000
Inserire il numero di iterazioni: 500
Verranno allocati almeno 8000000 bytes per volta.
Avvio benchmark std::vector<int> (push_back/iterator, senza reserve)... benchmark completato.
Risultati: 32.10 +/- 0.69 ms
Avvio benchmark std::vector<int> (push_back/iterator, con reserve)... benchmark completato.
Risultati: 21.03 +/- 0.23 ms
Avvio benchmark std::vector<int> (dimensioni nel costruttore/operator[])... benchmark completato.
Risultati: 19.57 +/- 0.52 ms
Avvio benchmark new int[]... benchmark completato.
Risultati: 20.02 +/- 0.15 ms
Avvio benchmark malloc+memset... benchmark completato.
Risultati: 20.02 +/- 0.15 ms
Avvio benchmark malloc... benchmark completato.
Risultati: 18.14 +/- 0.37 ms
Avvio benchmark std::list<int>... benchmark completato.
Risultati: 111.2 +/- 3.6 ms
matteo@teoubuntu:~/cpp/vectorbenchmark2$ ./vectorbenchmark2 
Inserire il numero di elementi: 20000000    
Inserire il numero di iterazioni: 10
Verranno allocati almeno 80000000 bytes per volta.
Avvio benchmark std::vector<int> (push_back/iterator, senza reserve)... benchmark completato.
Risultati: 365.8 +/- 5.5 ms
Avvio benchmark std::vector<int> (push_back/iterator, con reserve)... benchmark completato.
Risultati: 261.1 +/- 8.3 ms
Avvio benchmark std::vector<int> (dimensioni nel costruttore/operator[])... benchmark completato.
Risultati: 235.70 +/- 0.67 ms
Avvio benchmark new int[]... benchmark completato.
Risultati: 247.20 +/- 0.63 ms
Avvio benchmark malloc+memset... benchmark completato.
Risultati: 244.30 +/- 0.82 ms
Avvio benchmark malloc... benchmark completato.
Risultati: 238.20 +/- 0.63 ms
Avvio benchmark std::list<int>... benchmark completato.
Risultati: 1207 +/- 142 ms

Ciascun benchmark consiste nell'allocare la struttura dati, aggiungerci tanti numeri casuali quanti specificati nella prima richiesta (tramite push_back nel caso dei container STL, con operator[] in un caso per il vector, "viaggiando" via puntatore sugli array allocati con new/malloc) e rileggerli (in una variabile dichiarata volatile, in modo che il compilatore non ottimizzi via il ciclo di rilettura).
Ciascun benchmark è eseguito tante volte quanto indicato nel secondo dato richiesto dal programma, e i risultati di ciascun test sono memorizzati in un vector<double>; i dati mostrati derivano dall'applicazione di media e deviazione standard sui vari dataset, e sono espressi in millisecondi.

Dai dati emerge che, almeno per quantità di dati paragonabili a quelle di cui parla freetom, un std::vector è solo leggermente più lento di un array stile C allocato nell'heap. In particolare, la configurazione migliore per il vector è dimensionarlo fin dall'inizio nel costruttore (il che equivale a richiamare resize) e poi usare operator[] per l'accesso agli elementi. Credo che la configurazione reserve/push_back sia leggermente più lenta perché il push_back deve anche aggiornare il numero di elementi presenti nel vector, mentre l'operator[] fornisce proprio accesso grezzo alla memoria.

Delle alternative, l'unica con cui il vector nella configurazione migliore trova avversari all'altezza è la malloc semplice (senza inizializzazione), che in genere vince ma di molto poco; quando gli elementi aumentano ho notato che le prestazioni sono pressoché identiche, forse perché aumentando il numero di elementi sparisce il costo fisso delle operazioni di inizializzazione del vector.

La lista è talmente lenta rispetto a tutte le alternative (compreso il vettore autoespandente) che non vale neanche la pena di parlarne. Tra l'altro la sua deviazione standard nel secondo caso è particolarmente grande, credo perché alla prima iterazione si è verificato un page fault o roba del genere.

Informazioni sull'ambiente di test:

matteo@teoubuntu:~/cpp/vectorbenchmark2$ g++ --version
g++ (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5
Copyright (C) 2010 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

matteo@teoubuntu:~/cpp/vectorbenchmark2$ uname -a
Linux teoubuntu 2.6.35-24-generic #42-Ubuntu SMP Thu Dec 2 02:41:37 UTC 2010 x86_64 GNU/Linux
matteo@teoubuntu:~/cpp/vectorbenchmark2$ make
g++ -O3 -Wall -Wextra -ansi -pedantic   -MMD -MF BenchmarkFunctors.o.d -c -o BenchmarkFunctors.o BenchmarkFunctors.cpp
g++ -O3 -Wall -Wextra -ansi -pedantic   -MMD -MF main.o.d -c -o main.o main.cpp
g++ -O3 -Wall -Wextra -ansi -pedantic   -MMD -MF Utils.o.d -c -o Utils.o Utils.cpp
g++ -O3 -Wall -Wextra -ansi -pedantic   BenchmarkFunctors.o main.o Utils.o -o vectorbenchmark2

Il PC di prova ha processore AMD Phenom x4 955 (3.2 GHz x 4), con 4 GB di DDR3.

Comunque, per chi fosse interessato al codice (warning: è praticamente privo di commenti, ci sono template a palate perché volevo fare un piccolo framework di benchmarking riutilizzabile), qui c'è il tar.gz; per poterlo compilare è necessario avere installate le librerie boost. La classe Cronometer è pensata per sistemi POSIX (usa gettimeofday), ma su Windows la si può reimplementare facilmente con la QueryPerformanceCounter.

Per inciso, tutti i tempi misurati per 2 milioni di elementi sono attorno ai 20 ms (salvo il vector non predimensionato che va attorno ai 32 e la lista che si aggira sui 110), per cui non vedo come ci possa essere un problema di prestazioni su tempi così brevi.

[MacApp]

Originariamente inviato da freetom
Io dovrei memorizzare in run time molti dati.. (ritardi x ambo) ca 2 milioni quante sono le quartine generabili con 90 numeri. Ora ci sono riuscito mediante l'uso dei vector... di tipo <int> ma...
chiedo agli/alle esperti/e se c'e' un modo e se si quale per velocizzare notevolmente la cosa dato che con il modo da me trovato passa molto (troppo) tempo.

I test di velocità falli in modalità NON debug. In genere i vector, se ben utilizzati non hanno problemi di prestazioni.

[GliderKite]

Originariamente inviato da MacApp
I test di velocità falli in modalità NON debug. In genere i vector, se ben utilizzati non hanno problemi di prestazioni.

Sarà che io sono abituato a prediligere la performance utilizzando spesso e volentieri codice C-style, ma ho sempre notato che i vector hanno effettivamente problemi di prestazioni se sono le prestazioni che si cercano come aspetto fondamentale di un'applicazione.

Anche io ho voluto provare a fare qualche "misura" per testare alcune metodologie, e, a meno che il mio computer non menta, i risultati confermano quanto mi aspettavo, vediamo qualche esempio.

Test effettuato per 2 milioni di elementi. I tempi sono stati ricavati tramite le funzioni clock da libreria standatd C (ctime) e GetTickFunction (Windows.h). E' stata riportata una media per 100 ripetizioni.

Iniziamo dall'approccio meno efficiente: inserimento degli elementi uno ad uno tramite ciclo e chiamata al metodo push_back dei vector:

for( unsigned i = 0; i != size; ++i )
	std_vector.push_back( 1 );

Tempo impiegato:
clock = 1903 ms
GetTickFunction = 1923 ms


Resize + inserimento delgli elementi tramite l'operatore []:

std_vector.resize( size );

for( unsigned i = 0; i != size; ++i )
	std_vector[ i ] = 1;

Tempo impiegato:
clock = 377 ms
GetTickFunction = 344 ms



Semlice resize (elementi inizializzati a 0):

Tempo impiegato:
clock = 35 ms
GetTickFunction = 31 ms



Allocazione dinamica di un array C-style tramite new e inserimento tramite operatore []:

C_array = new int [ size ];

for( unsigned i = 0; i != size; ++i )
	C_array[ i ] = 1;

Tempo impiegato:
clock = 28 ms
GetTickFunction = 16 ms


Ora quella che soggerisco di principio se si vuole inizializzare l'array a 0 (va bene anche per -1). Allocazione tramite operatore new e chiamata alla funzione memset:

C_array = new int [ size ];

memset( C_array, 0, sizeof(int) );

Tempo impiegato:
clock = 0 ms
GetTickFunction = 0 ms



I tempi parlano da soli. Ma ripeto ancora una volta: dipende sempre da quello che si deridera fare (per fare quello che chiedeva freetom tutte queste considerazioni sono inutili).

@MItaly: tu hai utilizzato il contenitore della STL per verificare i tempi su una lista. Ti assicuro che se l'avessi implementata tu stessa utilizzando i classici puntatori avresti potuto ottenere uno stack tramite lista concatenata sicuramente più performente. Senza contare che i tuoi test sono stati fatti con un ottimo processore, non voglio pensare quanto tempo ci sarebbe voluto per farli su un nemmeno tanto vecchio netbook da 500 mb di RAM e 1 Gh, con magari 500 milioni di elementi.

[shodan]

Solo un'annotazione.
L'ultimo codice dovrebbe essere:

C_array = new int [ size ];
memset( C_array, 0, sizeof(int) * size);

[GliderKite]

Si hai perfettamente ragione, scrivendo il codice qui me ne sono scordato. Ovviamente i tempi non cambiano, in quanto il test è stato effettuato con il codice corretto

[freetom]

Il massimo che sono riuscito a fare con ritardi.push_back(ritardo) e 2 soli spazi... previsti [0] e [1] è un'elaborazione che per completarsi impiegherà ca 23 gg!

L'operazione includerà:

verifica x 2 o + valori uguali di 2.000.000 di quartine VS 4000 cinquine
quindi 90x90x90x90 x 4.000 operazioni...

(ho verificato che con quanto da me fatto ogni singola quartina impiega infatti 1 sec per essere analizzata...) e 2.000.000 di secondi equivalgono salvo errori a 23 gg ca

Qualcuno sarebbe capace di ridurmi l'attesa... almeno di qualche giorno?



Grazie!

[MItaly]

Originariamente inviato da GliderKite
[...]

Che compilatore hai usato, e con che opzioni di ottimizzazione? Perché lì si gioca tantissimo, dato che basta che il compilatore non effettui l'inlining di qualche metodo STL e le performance crollano.
Questo perché i miei risultati sono piuttosto diversi, e non credo dipenda tanto dal processore (nel senso, il valore effettivo dipende sicuramente da processore e RAM, ma le differenze percentuali tra i vari metodi dovrebbero restare più o meno costanti); non mi spiego perché un vector dovrebbe essere più lento di una normale new se usato con resize+operator[], dato che in fin dei conti la resize iniziale non è altro che una new+l'inizializzazione di default, e operator[] non è altro che una somma di puntatori che dovrebbe essere ottimizzata inline.

Aggiungo: per ottenere dei risultati precisi ti conviene usare QueryPerformanceCounter ed effettuare più volte ogni test, estraendo alla fine media e deviazione standard; in questa maniera sei sicuro che un eventuale ritardo casuale dovuto a cache miss/page fault (sia che riguardi i dati in memoria, sia che riguardi il codice dell'eseguibile) sia ammortizzato nel calcolo della media, ottenendo risultati realistici.
Se hai già installato boost e hai voglia di riscrivere la classe Cronometer magari fai qualche prova con il mio codice e posta i risultati che saltano fuori.

[GliderKite]

Ho utilizzato l'IDE Visual Studio 2010, Windows 7, 4 Gb RAM Intel Core i3, 2.27 Gh, 64 bit.
Ottimizzazione? Nessuna /Od.