Test prestazionale degli allocatori standard in Java e C per blocchi di dimensione fissa
Obiettivi
Studiare il tempo totale richiesto per effettuare una sequenza casuale di allocazioni/deallocazioni di array di 1024 int (blocchi di 4KB) con un massimo di n blocchi contemporaneamente allocati. I test sono stati effettuati in C e Java assumendo diversi limiti superiori alla dimensione dell'heap della JVM e senza nessun limite in C.Piattaforma
Sistema operativo: Mac OS X vs. 10.4.10Processore: 2.16 GHz Intel Core Duo
Memoria: 2 GB 667 MHz DDR2 SDRAM
L2 Cache (per processor): 2 MB
Java version "1.5.0_07"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_07-164)
Java HotSpot(TM) Client VM (build 1.5.0_07-87, mixed mode, sharing)
gcc-4.0.1
Programmi di test
Il programma seguente crea per ciascun n compreso tra minN e maxN con passo stepN un array v di n riferimenti ad array, ed effettua rep*n operazioni di allocazione/deallocazione casuale. Ogni operazione consiste nel prendere una cella a caso di v di indice k e: se la cella è null, viene fatta puntare a un nuovo array di blockSize int, altrimenti viene messa a null (forzando quindi il garbage collector a deallocare l'array puntato). Il programma fornisce come output una riga per ogni valore considerato di n nel seguente formato:
n tempo_in_msec bytes_usati max_bytes_usati
dove tempo_in_msec è il tempo totale in millisecondi per effettuare le rep*n operazioni, bytes_usati è il numero di byte allocati alla fine della sequenza, e max_bytes_usati è il massimo numero di byte allocati durante la sequenza.
public class TestAllocFixedLin {
private static final int minN=1000, maxN=200000, stepN=1000, rep=30, blockSize=1024;
public static void main(String[] x) {
for (int n=minN; n<=maxN; n+=stepN) {
int bytes = n*4, max=0;
long start = System.nanoTime();
int[][] v = new int[n][];
for (int i=0; i<rep*n; i++) {
int k = (int)(Math.random()*n);
int q = blockSize;
if (v[k] == null) {
v[k] = new int[q];
bytes += 4*v[k].length;
if (bytes>max) max = bytes;
}
else {
bytes -= 4*v[k].length;
v[k] = null;
}
}
long end = System.nanoTime();
System.out.println(n+", "+(end-start)/1000000+", "+bytes+", "+max);
}
}
}
private static final int minN=1000, maxN=200000, stepN=1000, rep=30, blockSize=1024;
public static void main(String[] x) {
for (int n=minN; n<=maxN; n+=stepN) {
int bytes = n*4, max=0;
long start = System.nanoTime();
int[][] v = new int[n][];
for (int i=0; i<rep*n; i++) {
int k = (int)(Math.random()*n);
int q = blockSize;
if (v[k] == null) {
v[k] = new int[q];
bytes += 4*v[k].length;
if (bytes>max) max = bytes;
}
else {
bytes -= 4*v[k].length;
v[k] = null;
}
}
long end = System.nanoTime();
System.out.println(n+", "+(end-start)/1000000+", "+bytes+", "+max);
}
}
}
Si noti che modificando la riga q = blockSize si può ottenere l'allocazione di blocchi di dimensioni diverse per effettuare ulteriori test. Il corrispondente programma in C è il seguente:
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
static int minN=1000, maxN=200000, stepN=1000, rep=30, blockSize=1024;
int main() {
int n, i, k, q;
for (n=minN; n<=maxN; n+=stepN) {
int bytes = n*4, max=0;
long start = clock(), end;
int** v = (int**)calloc(n,sizeof(int*));
int* size = (int*)malloc(n*sizeof(int));
for (i=0; i<rep*n; i++) {
k = (int)(((double)rand()/RAND_MAX)*n);
q = blockSize;
if (v[k] == NULL) {
v[k] = (int*)malloc(q*sizeof(int));
bytes += 4*q;
size[k] = q;
if (bytes > max) max = bytes;
}
else {
bytes -= 4*size[k];
free(v[k]);
v[k] = NULL;
}
}
for (i=0; i<n; i++) if (v[i] != NULL) free(v[i]);
free(size);
free(v);
end = clock();
printf("%ld, %d, %d, %d\n", n,
1000*(end-start)/CLOCKS_PER_SEC, bytes, max);
}
return 0;
}
#include <stdio.h>
#include <time.h>
static int minN=1000, maxN=200000, stepN=1000, rep=30, blockSize=1024;
int main() {
int n, i, k, q;
for (n=minN; n<=maxN; n+=stepN) {
int bytes = n*4, max=0;
long start = clock(), end;
int** v = (int**)calloc(n,sizeof(int*));
int* size = (int*)malloc(n*sizeof(int));
for (i=0; i<rep*n; i++) {
k = (int)(((double)rand()/RAND_MAX)*n);
q = blockSize;
if (v[k] == NULL) {
v[k] = (int*)malloc(q*sizeof(int));
bytes += 4*q;
size[k] = q;
if (bytes > max) max = bytes;
}
else {
bytes -= 4*size[k];
free(v[k]);
v[k] = NULL;
}
}
for (i=0; i<n; i++) if (v[i] != NULL) free(v[i]);
free(size);
free(v);
end = clock();
printf("%ld, %d, %d, %d\n", n,
1000*(end-start)/CLOCKS_PER_SEC, bytes, max);
}
return 0;
}
Anche in questo caso, modificando la riga q = blockSize si può ottenere l'allocazione di blocchi di dimensioni diverse per effettuare ulteriori test.
Risultati sperimentali
Il seguente grafico mostra il tempo di esecuzione di una sequenza casuale di 30n allocazioni/deallocazioni di array di 1024 int (blocchi di 4KB) in Java (con limiti di 16, 32 e 64 MB sulla dimensione massima di heap) e in C, per n crescente. Si noti il netto deterioramento delle prestazioni in Java nel caso in cui la memoria utilizzata superi circa i 2/3 della memoria massima utilizzabile.
Il seguente grafico mostra lo spazio massimo effettivamente utilizzato dal programma.
Si noti ad esempio che, per n=32000, si ha un valore atteso di 16000 array allocati, ciascuno dei quali richiede 4KB, per un totale di circa 64MB come riportato dal grafico.
Conclusioni
Data la specificità dei test effettuati non è possibile trarre alcuna considerazione sulle prestazioni generali dei gestori di memoria considerati. Essi evidenziano tuttavia la possibilità di incontrare situazioni di estrema inefficienza del gestore di memoria della JVM quando la memoria usata si avvicina a quella massima disponibile.