[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?

[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?

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à, 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]

Originariamente inviato da Teo@Unix

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! Non capisco, forse dipende anche dal compilatore e dai flags di ottimizzazione. Appena ho tempo faccio altre prove con gcc.

[Unrue]

Originariamente inviato da gugoXX

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]

Originariamente inviato da gugoXX

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]

Originariamente inviato da gugoXX

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

double matrice[1000][1000];

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

[gugoXX]

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

[Teo@Unix]

Originariamente inviato da Unrue

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]

Originariamente inviato da Teo@Unix

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