[C, C++] Allocazione dinamica e statica e velocità del codice

[Unrue]

Ciao a tutti,

è un pò che mi pongo la seguente domanda. In generale, se alloco una matrice staticamente o dinamicamente, ed in seguito su tale matrice compio svariate operazioni magari in un ciclo, è possibile stabilire quale delle due allocazioni convenga fare in termini di performances?

Mi spiego meglio, da un punto di vista teorico, sapere in anticipo le dimensioni di una matrice potrebbe aiutare il compilatore ad ottimizzare meglio gli accessi. Così non è con una matrice dinamica.

Che ne pensate? :stordita:

[DanieleC88]

Da buon profano quale sono penso che un'allocazione statica sia più performante per una serie di motivi (tra cui il fatto di dover semplicemente fare una sottrazione sullo stack invece che un'allocazione magari costosa sull'heap, e una più stretta applicazione del principio di località del codice).

Certo però che le differenze diventano davvero trascurabili IMHO se le allocazioni sono poche. Non so se c'è veramente una convenienza... :)

ciao ;)

[Unrue]

No aspetta, non intendevo performances nel senso di tempo speso per allocare. Ma tempo speso negli accessi alla matrice.;

Piccolo esempio che non ha alcun senso, ma tanto per capire:


matrice[i][j] = matrice[i-1][j]*matrice[i][j] + 2^matrice[i][j-3]

Sarebbe più performante se matrice fosse nello stack o nello heap? :stordita:

Nei vari codici che mi sono capitati tra le mani non ho mai rilevato differenze significative, quindi sembrerebbe che il compilatore non sfrutti le informazioni sulla dimensioni della matrice note a priori, e ciò mi pare molto strano.

[Teo@Unix]

Sarebbe più performante se matrice fosse nello stack o nello heap?

Ciao, ho trovato stimolante la tua domanda ...
pensandoci un attimo direi che è uguale perchè sono sempre indirizzi e la velocità della memoria è sempre uguale, in più a parità di operazioni fatte, che sia nello heap o nello stack, la CPU fa le medesime cose, carica scarica registri ecc....

ma da buon san Tommaso ho voluto provare.... chissà mai scopro qualcosa di nuovo... ma niente....

ecco infatti il test che ho fatto...

Ho preso in considerazione una matrice di 50x50 elementi come mi hai suggerito.
Il test è per windows.

(tieni in considerazione che sono stato sotto il secondo per il tempo di elaborazione, per non dovermi calcorare il riporto dei tempi stampati se ci mettevo più di un secondo)

// This is a simple test ;)

#include <iostream>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <windows.h>

using namespace std;

const short N = 50;

void calc(double[][N]);

double matrix_on_heap[N][N];

SYSTEMTIME tv;
SYSTEMTIME tv_later;

int main(void)
{
int j = 10;
double matrix_on_stack[N][N];

cout << "Stack allocation:" << endl;
while(j--) {
GetSystemTime(&tv);
calc(matrix_on_stack);
GetSystemTime(&tv_later);
cout << 10-j << " Time spent: " << tv_later.wMilliseconds-tv.wMilliseconds << " MilliSeconds" << endl;
}
cout << endl;
j = 10;
cout << "Heap allocation:" << endl;
while(j--) {
GetSystemTime(&tv);
calc(matrix_on_heap);
GetSystemTime(&tv_later);
cout << 10-j << " Time spent: " << tv_later.wMilliseconds-tv.wMilliseconds << " MilliSeconds" << endl;
}

return(0);
}

void calc(double matrix[][N])
{
srand(time(NULL));
int x,y;
// Matrix randomization
for(x=0;x<N;x++)
{
for(y=0;y<N;y++)
{
matrix[x][y] = rand();
}
}
srand(time(NULL)+1);
for(x=0;x<N;x++)
{
for(y=0;y<N;y++)
{
matrix[x][y] = sqrt(pow(matrix[x][y],2)); // is a useless thing :)
}
}
}



Output:

Stack allocation:
1 Time spent: 0 MilliSeconds
2 Time spent: 2 MilliSeconds
3 Time spent: 0 MilliSeconds
4 Time spent: 3 MilliSeconds
5 Time spent: 2 MilliSeconds
6 Time spent: 0 MilliSeconds
7 Time spent: 0 MilliSeconds
8 Time spent: 2 MilliSeconds
9 Time spent: 0 MilliSeconds
10 Time spent: 3 MilliSeconds

Heap allocation:
1 Time spent: 0 MilliSeconds
2 Time spent: 3 MilliSeconds
3 Time spent: 0 MilliSeconds
4 Time spent: 2 MilliSeconds
5 Time spent: 0 MilliSeconds
6 Time spent: 0 MilliSeconds
7 Time spent: 3 MilliSeconds
8 Time spent: 0 MilliSeconds
9 Time spent: 0 MilliSeconds
10 Time spent: 0 MilliSeconds

Process returned 0 (0x0) execution time : 0.037 s

Sinceramente, può essere che il risultato del test non aiuti poi molto, come vedi a volte è 0 a volte è 3 millisecondi... ma d'altronde più dei millisecondi non possiamo andare, o meglio non saprei come fare....

In conclusione credo che l'unica controindicazione dell'allocazione nello stack piuttosto che nello heap è che lo stack è più limitato per quanto riguarda la dimensione della memoria allocabile.

[Unrue]

Mm,

forse è necessario aumentare di più la dimensione della matrice, che so, 1000 x 1000. Proverei anche ad aumentare il tempo di esecuzione facendogli fare più conti, in modo da farlo "macinare" per circa un minuto. Domani faccio una prova.

[DanieleC88]

In teoria se non fai accessi troppo casuali non hai di che misurare, perché la velocità di accesso è sempre la stessa. Sia stack che heap risiedono nella RAM, quindi il tempo di accesso è sostanzialmente identico. L'importante è rispettare il principio di località (http://it.wikipedia.org/wiki/Principio_di_località_(informatica)), per non svuotare troppo spesso la cache della CPU.

[Teo@Unix]

forse è necessario aumentare di più la dimensione della matrice, che so, 1000 x 1000.

questo non si può fare, con 1000x1000 esaurisci lo stack disponibile ed hai SIGSEGV.

Come detto, forse è l'unica controindicazione di usare lo stack piuttosto che lo heap.
Inoltre se la dimensione della nostra ipotetica matrice diventa variabile bè allora a maggior ragione meglio usare lo heap, altrimenti hai un programma che, alla vista dell'utilizzatore, dopo una certa dimensione non funziona.

Quel che si può provare a fare è aumentare il tempo di calcolo, così prendiamo nota dei secondi...
più tardi aggiorno il test..... ma il risultato non credo proprio che cambierà:)

[gugoXX]

Uno dei problemi della mancata differenza prestazionale e' che il C non e' "conscio" della dimensione fissa della matrice allocata staticamente.
Mentre per quella dinamica e' plausibile che non la tenga in considerazione per diversi motivi, per quella statica e' meno intuitivo.

Le due situazioni sono quindi analoghe.

[Tommo]

Al massimo per matrici particolarmente piccole il compilatore fa l'unrolling dei loop se la dimensione è statica...
ma credo che i processori moderni lo facciano già da se con il branch prediction eccetera.

Magari serviva prima, ad oggi è difficile che otterrai risultati coerenti...

[Unrue]

questo non si può fare, con 1000x1000 esaurisci lo stack disponibile ed hai SIGSEGV.



Perché no? Basta aumentare la dimensione dello stack :)

Allora, ho fatto diverse prove. Inanzi tutto ho impostato lo stack a 20 mb con ulimit -s.

I codici sono compilati con il compilatore Intel 11. Questi sono i sorgenti:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char *argv[]){

double matrice[1000][1000];

int seed;

seed = 10000;
srand(seed);


for( int i=0; i< 1000; i++)
for( int j=0; j< 1000; j++)
{
matrice[i][j] = (double)rand();
}


for ( int iter=0; iter< 10000; iter++)
{
for( int i=1; i< 1000; i++)
for( int j=1; j< 1000; j++)
{
matrice[i-1][j] = matrice[i][j-1]*pow(matrice[i][j], 3) + sin(matrice[i-1][j])/cos(matrice[i][j-1]) + (double)rand();
}

}

return 0;

}


#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char *argv[]){

double** matrice;

int seed, i, j;

seed = 10000;
srand(seed);

int dim_1 = atoi(argv[1]);
int dim_2 = atoi(argv[2]);

matrice = (double**)malloc(dim_1*sizeof(double*));

for ( i=0; i< dim_1; i++)
matrice[i] = (double*)malloc(dim_2*sizeof(double));


for( i=0; i< dim_1; i++)
for( j=0; j< dim_2; j++)
{
matrice[i][j] = (double)rand();
}


for ( int iter=0; iter< 10000; iter++)
{
for( i=1; i< dim_1; i++)
for( j=1; j< dim_2; j++)
{
matrice[i-1][j] = matrice[i][j-1]*pow(matrice[i][j], 3) + sin(matrice[i-1][j])/cos(matrice[i][j-1]) + (double)rand();
}

}

for ( i=0; i< dim_1; i++)
free(matrice[i]);

free(matrice);

return 0;

}


Ho compilato con -O2 e -O3, facendo tre prove per caso. Questi sono i risultati:


***intel -02 static***

real 4m6.477s
user 4m6.479s
sys 0m0.006s

real 4m9.876s
user 4m9.883s
sys 0m0.002s

real 4m6.608s
user 4m6.615s
sys 0m0.003s

***intel -03 static***

real 4m14.665s
user 4m14.659s
sys 0m0.006s


real 4m12.640s
user 4m12.644s
sys 0m0.005s

real 4m14.278s
user 4m14.281s
sys 0m0.006s


***intel -02 dynamic***

real 3m57.196s
user 3m57.193s
sys 0m0.007s

real 3m52.174s
user 3m52.167s
sys 0m0.005s

real 3m56.752s
user 3m56.752s
sys 0m0.006s

***intel -03 dynamic***

real 3m56.296s
user 3m56.301s
sys 0m0.004s

real 3m49.180s
user 3m49.179s
sys 0m0.004s

real 3m56.351s
user 3m56.354s
sys 0m0.005s


Ricapitolando, non solo con le matrici statiche non si guadagna, ma addirittura sono leggermente più lente di quelle dinamiche! :confused: Non capisco, forse dipende anche dal compilatore e dai flags di ottimizzazione. Appena ho tempo faccio altre prove con gcc.

[Unrue]

Uno dei problemi della mancata differenza prestazionale e' che il C non e' "conscio" della dimensione fissa della matrice allocata staticamente.


Mm, perché ?

[gugoXX]

Una matrice scritta cosi' e' comunque un vettore di puntatori a vettore

double matrice[1000][1000];
E l'accesso ad ogni singola cella prevede 2 operazioni di memoria.

diverso sarebbe scrivere la seguente
double matrice[1000*1000];
dove siamo sicuri che la zona di memoria allocata sia contigua indipendentemente dal compilatore.

Una situazione come questa permetterebbe di risolvere l'accesso alla singola cella con una singola operazione di memoria.
Una volta compilato pero' il C non e' piu' in grado di "ricordare" (non gliel'abbiamo mai detto in realta') che c'e' una relazione bidimensionale nella zona di memoria.
Possiamo scrivere noi la modalita' di accesso veloce

#define GetCell(mat,X,Y) mat[Y*1000+X]

In questo modo potremmo sfruttare la staticita' delle dimensioni.

[Unrue]

Una matrice scritta cosi' e' sempre un vettore di puntatori a vettore

double matrice[1000][1000];
E l'accesso ad ogni singola cella prevede 2 operazioni di memoria.

diverso sarebbe scrivere la seguente
double matrice[1000*1000];
dove siamo sicuri che la zona di memoria allocata sia contigua indipendentemente dal compilatore.

Una situazione come questa permetterebbe di risolvere l'accesso alla singola cella con una singola operazione di memoria.
Una volta compilato pero' il C non e' piu' in grado di "ricordare" (non gliel'abbiamo mai detto in realta') che c'e' una relazione bidimensionale nella zona di memoria.
Possiamo scrivere noi la modalita' di accesso veloce

#define GetCell(mat,X,Y) mat[Y*1000+X]

In questo modo potremmo sfruttare la staticita' delle dimensioni.

Ok, quindi suggerisci di linearizzare la matrice in un vettore, ed in effetti per avere migliori performances si fa sempre così. Ma questo si può fare anche con la matrice allocata dinamicamente, quindi si ritorna al punto di partenza.

[DanieleC88]

Una matrice scritta cosi' e' sempre un vettore di puntatori a vettore

double matrice[1000][1000];
:wtf:

Non mi risulta. :)

[Tommo]

In effetti c'era da aspettarsela una maggiore lentezza delle matrici statiche...

se ipotizziamo che i progettisti Intel abbiano seguito la massima "optimize the common case" è possibile che lo stack sia ottimizzato per trasferimenti di piccoli dati molto frequenti (es mem->registri) mentre invece l'heap è ottimizzato tramite cache per il caricamento di grosse moli di dati, che è il suo uso tipico.
Poi, il resto è segreto industriale :D

[gugoXX]

No ho sbagliato.
Questo e' il vettore di vettori
double mat[][100];

[Teo@Unix]

Perché no? Basta aumentare la dimensione dello stack :)

a bè ok.

cmq per i risultati, può essere in effetti il compilatore io ho allungato i tempi per le elaborazioni e la matrice allocata nell'heap è un pelo più lenta....

può benissimo essere il compilatore, ho usato codeblocks su Win7, quindi tutta un'altra storia.

[Unrue]

Questi sono i risultati con gcc 4.3:


***gcc -O2 static***

real 7m21.909s
user 7m21.886s
sys 0m0.009s

real 7m38.066s
user 7m38.069s
sys 0m0.005s

***gcc -O2 dynamic***

real 7m40.072s
user 7m40.072s
sys 0m0.010s

real 7m40.459s
user 7m40.471s
sys 0m0.005s

***gcc -O3 static***

real 7m22.046s
user 7m22.031s
sys 0m0.006s

real 7m22.086s
user 7m22.059s
sys 0m0.003s


***gcc -O3 dynamic***

real 7m34.964s
user 7m34.947s
sys 0m0.018s

real 7m40.501s
user 7m40.516s
sys 0m0.003s


Inanzi tutto si nota che Intel straccia gcc ( ma questo me lo aspettavo, compilatore Intel su processore Intel non c'è storia). Ma la cosa curiosa è che la situazione si inverte: gcc pare essere più performante anche se di poco con l'allocazione statica..

[Teo@Unix]

quindi possiamo dire che il tutto è molto dipendente dall'ambiente di compilazione?

Ma io non credo he vi sia una differenza per dinamica o statica per quanto riguarda le performance di lettura/scrittura a priori.

[Unrue]

quindi possiamo dire che il tutto è molto dipendente dall'ambiente di compilazione?


A quanto pare si. Ho sentito dire che su AIX e compilatore xlc ( di IBM ) l'allocazione statica è più performante di un 30%. (Farò delle prove). Per fare un'analisi più approfondita andrebbe analizzato l'assembly generato, ma visto le differenze minime non ne vale proprio la pena :D

[Teo@Unix]

si esatto, poi l'assembly generato dipende anche questo dal compilatore, diciamo che se vuoi maggiori performance bè allora è il caso che scrivi in assembly direttamente in modo da ottimizzare tempo spazio ecc. ecc...

[!k-0t1c!]

si esatto, poi l'assembly generato dipende anche questo dal compilatore, diciamo che se vuoi maggiori performance bè allora è il caso che scrivi in assembly direttamente in modo da ottimizzare tempo spazio ecc. ecc...
Piano a consigliare di scrivere in assembly. Il tempo per produrre codice equivalente aumenta drasticamente, così come aumenta il costo per mantenere il codice. Diminuiscono invece sicurezza e leggibilità. Infine spesso il compilatore produce un assembly molto più efficiente di quello scritto a mano (salvo forse da qualche esperto).
Basti pensare ai classici

mov eax, 0

contro

xor eax, eax


o


cmp eax, 0
jXX ...


test eax, eax
jXX ...


Infine compilatori come ICC spesso gestiscono più efficientemente stack e registri di quanto la maggior parte dei programmatori saprebbe fare a mano, quindi salvo per poche (brevi) funzioni, solitamente di calcolo numerico dove si utilizzano magari le SSE, conviene scrivere in C piuttosto che in assembly.

[marco.r]

Piccolo esempio che non ha alcun senso, ma tanto per capire:


matrice[i][j] = matrice[i-1][j]*matrice[i][j] + 2^matrice[i][j-3]


Sarebbe più performante se matrice fosse nello stack o nello heap? :stordita:


Mi vengono in mente due motivi per i quali una matrice statica possa risultare più efficiente
- Sono note le dimensioni per cui il compilatore riesce a fare più facilmente l'unrolling del loop
- Le matrici dichiarate staticamente sono allocate come un unico blocco di memoria, mentre nel caso dinamico si tratta di un array di array. Nel caso dinamico c'è quindi una doppia dereferenziazione e minore località.

Questo due aspetti non dovrebbero più di tanto influenzare i casi di matrici grandi, soprattutto se la computazione è dominata da conti in virgola mobile (con -ffast-math gcc ci mette un quarto del tempo...)

Però per matrici piccole la differenza si può sentire.
Se provi a rifare il tuo test con matrici piccole dovresti notare una sensibilie differenza. Nel mio portatile ad esempio con matrici 4x4 e 10000000 di iterazioni, ottengo tempi nell'ordine dei 28-29 secondi per il caso statico e 34-35 secondi per il caso dinamico.

[Unrue]

Per curiosità ho effettuato delle prove su processore Power6 e sistema operativo AIX. I risultati sono molto interessanti:

-O3 static

real 1m57.639s
user 1m57.416s
sys 0m0.002s

real 1m57.035s
user 1m56.802s
sys 0m0.002s

-O3 dynamic

real 8m26.404s
user 4m18.526s
sys 0m0.001s

real 8m26.584s
user 4m18.038s
sys 0m0.001s

Analizzando con il tool hpmcount si nota un enorme tasso di page fault nella versione a matrici dinamiche. Quindi ricapitolando contano tre fattori: compilatore, allocatori del sistema operativo e dimensione delle pagine.

[Teo@Unix]

real 1m57.639s
user 1m57.416s
sys 0m0.002s

real 1m57.035s
user 1m56.802s
sys 0m0.002s


Analizzando con il tool hpmcount si nota un enorme tasso di page fault nella versione a matrici dinamiche. Quindi ricapitolando contano tre fattori: compilatore, sistema operativo e dimensione delle pagine.

:eek:

è piuttosto veloce...

[Unrue]

:eek:

è piuttosto veloce...

Eh si, i Power6 sono delle belle bestiole :)

Dimenticavo, il compilatore utilizzato è xlc di IBM

[DanieleC88]

Analizzando con il tool hpmcount si nota un enorme tasso di page fault nella versione a matrici dinamiche.

:)

[||ElChE||88]

I risultati su MIPS (gcc 4.3.3) sono simili a quelli su x86 (Matrice 100x100 e 100 iterazioni, altrimenti il poveraccio fonde :asd:).

static

real 0m 35.88s
user 0m 35.79s
sys 0m 0.02s

real 0m 36.03s
user 0m 35.92s
sys 0m 0.03s

dynamic

real 0m 35.75s
user 0m 35.67s
sys 0m 0.02s

real 0m 35.78s
user 0m 35.69s
sys 0m 0.02s