Le moyen le plus rapide de lire/stocker beaucoup de données multidimensionnelles? (Java)
J'ai trois questions sur trois boucles imbriquées:
for (int x=0; x<400; x++)
{
for (int y=0; y<300; y++)
{
for (int z=0; z<400; z++)
{
// compute and store value
}
}
}
Et j'ai besoin de stocker toutes les valeurs calculées. Mon approche standard serait d'utiliser un tableau 3D:
values[x][y][z] = 1; // test value
Mais cela s'avère lent: il faut 192 ms pour terminer cette boucle, où une seule affectation int
int value = 1; // test value
Ne prend que 66 ms.
1) Pourquoi un tableau est-il si lent?
2) Et pourquoi devient-il encore plus lent quand je mets cela dans la boucle intérieure:
values[z][y][x] = 1; // (notice x and z switched)
Cela prend plus de 4 secondes!
3) Plus important encore: Puis-je utiliser une structure de données aussi rapide que l'affectation d'un seul entier, mais pouvant stocker autant de données que le tableau 3D?
5 answers
1) Pourquoi un tableau est-il si lent?
Comme d'autres l'ont souligné, vous comparez des pommes à des oranges. Le tableau triple est lent car il doit déréférencer (en interne au moins - oui, "il n'y a pas de pointeurs en Java") trois fois; mais là encore, vous ne pouvez pas référencer une seule variable entière...
2) Et pourquoi devient-il encore plus lent quand je mets cela dans la boucle intérieure:
values[z][y][x] = 1; // (notice x and z switched)
Parce que vous avez diminué la cohérence du cache. Le les indices qui changent le plus rapidement devraient être les derniers, de sorte que la plupart des accès à la mémoire se produisent les uns à côté des autres, dans les mêmes blocs de cache, au lieu de forcer votre processeur à attendre que les blocs soient lus à partir de la RAM principale.
3) Plus important encore: Puis-je utiliser une structure de données aussi rapide que l'affectation d'un seul entier, mais pouvant stocker autant de données que le tableau 3D?
Non. Il n'existe pas de telle structure, car la variable entière s'inscrit dans un registre machine (plus rapide même que le cache mémoire du processeur), et peut toujours être consulté plus rapidement que tout ce que vous souhaitez mentionner. Les vitesses du processeur sont beaucoup, beaucoup plus rapides que les vitesses de la mémoire principale. Si votre "ensemble de travail" (les données sur lesquelles vous devez opérer) ne rentre pas dans les registres ou le cache, vous devrez payer une pénalité pour le récupérer à partir de la RAM (ou pire encore, du disque).
Cela étant dit, Java vérifie les limites de chaque accès au tableau et ne semble pas trop intelligent pour optimiser le limite vérifie l'écart. La comparaison suivante peut être intéressante:
public static long test1(int[][][] array) {
long start = System.currentTimeMillis();
for ( int x = 0; x < 400; x++ ) {
for ( int y = 0; y < 300; y++ ) {
for ( int z = 0; z < 400; z++ ) {
array[x][y][z] = x + y + z;
}
}
}
return System.currentTimeMillis() - start;
}
public static long test2(int [] array) {
long start = System.currentTimeMillis();
for ( int x = 0; x < 400; x++ ) {
for ( int y = 0; y < 300; y++ ) {
for ( int z = 0; z < 400; z++ ) {
array[z + y*400 + x*400*300] = x + y + z;
}
}
}
return System.currentTimeMillis() - start;
}
public static void main(String[] args) {
int[][][] a1 = new int[400][300][400];
int[] a2 = new int[400*300*400];
int n = 20;
System.err.println("test1");
for (int i=0; i<n; i++) {
System.err.print(test1(a1) + "ms ");
}
System.err.println();
System.err.println("test2");
for (int i=0; i<n; i++) {
System.err.print(test2(a2) + "ms ");
}
System.err.println();
}
La sortie, sur mon système, est -
test1
164ms 177ms 148ms 149ms 148ms 147ms 150ms 151ms 152ms 154ms 151ms 150ms 148ms 148ms 150ms 148ms 150ms 148ms 148ms 149ms
test2
141ms 153ms 130ms 130ms 130ms 133ms 130ms 130ms 130ms 132ms 129ms 131ms 130ms 131ms 131ms 130ms 131ms 130ms 130ms 130ms
Il y a donc matière à amélioration... mais je ne pense vraiment pas qu'il est utile de votre temps.
public static void main( String[] args ) {
int[][][] storage = new int[ 400 ][ 300 ][ 400 ];
long start = System.currentTimeMillis();
for ( int x = 0; x < 400; x++ ) {
for ( int y = 0; y < 300; y++ ) {
for ( int z = 0; z < 400; z++ ) {
storage[x][y][z] = 5;
}
}
}
long end = System.currentTimeMillis();
System.out.println( "Time was: " + ( end - start ) / 1000.0 + " seconds." );
}
Exécuté avec-Xmx1g
Le Temps était: 0.188 secondes.
Cela semble sacrément rapide.. vous regardez 48 MILLIONS d'éléments dans la boucle la plus interne.
Homerolling une petite structure de données stupide..
public static void main( String[] args ) {
StorerGuy[] storerGuys = new StorerGuy[ 400 ];
long start = System.currentTimeMillis();
for ( int x = 0; x < 400; x++ ) {
for ( int y = 0; y < 300; y++ ) {
for ( int z = 0; z < 400; z++ ) {
storerGuys[x] = new StorerGuy( x, y, z, 5 );
}
}
}
long end = System.currentTimeMillis();
System.out.println( "Time was: " + ( end - start ) / 1000.0 + " seconds." );
}
public static class StorerGuy {
public int x;
public int y;
public int z;
public int value;
StorerGuy( int x, int y, int z, int value ) {
this.x = x;
this.y = y;
this.z = z;
this.value = value;
}
}
Le Temps était: 0.925 secondes.
Qui est plus rapide que 4 secondes que vous aviez dans votre exemple d'ordre mélangé.
Je pense que les tableaux multiples sont trop pour le problème. Vous êtes mieux avec une structure de données plus complexe, comme il le fera gardez le tout dans 1 emplacement de mémoire (x,y,z, valeur).
Java est un langage OO. Dans la plupart des cas, vous devez utiliser des objets et non des structures de données étranges comme int [] [] []
Avez-vous essayé ceci:
Object[][][] store = new Object[ 400 ][300][400];
for (int x=0; x<400; x++)
{
Object[][] matrix = store[x];
for (int y=0; y<300; y++)
{
Object[] line = matrix[y];
for (int z=0; z<400; z++)
{
// compute and store value
line[z] = // result;
}
}
}
Cela pourrait améliorer votre cache.
Je suppose que cela a beaucoup à voir avec la mise en cache et les registres et le principe de la localité de la mémoire.
Java doit accéder à des milliers d'octets de mémoire supplémentaires lors du stockage dans un tableau. Avec la variable unique, il peut simplement garder cette valeur dans le cache et continuer à la mettre à jour.
Le cache n'est pas assez grand pour contenir tout le tableau multidimensionnel, donc Java doit continuer à mettre à jour le cache vers et depuis la mémoire. Les temps d'accès au cache sont beaucoup plus rapides que l'accès à la mémoire temps.
Je ne vois même pas pourquoi vous feriez ce test cependant. Si vous avez besoin de stocker beaucoup de données dans un tableau multidimensionnel, à l'aide d'une seule variable n'est pas utile, même si elle est plus rapide.
De plus, la raison pour laquelle lorsque les paramètres sont changés lors de l'accès au tableau est que vous sautez beaucoup plus en mémoire (beaucoup plus de manques de cache) que lorsque vous itérez simplement dans l'autre sens.
Considérant que le tableau est énorme, la quantité de mémoire utilisée, les indirections nécessaires (un tableau multidimensionnel est un tableau de référence aux tableaux...), cela ne me semble pas du tout lent. Lorsque vous changez x et z, vous saccagez probablement le cache.
À titre de comparaison, vous pouvez tout stocker dans un tableau plat.... Cela améliorerait la vitesse de stockage... mais alors la récupération serait plus complexe et beaucoup plus lent.
int k = 0;
for (int x=0; x<400; x++)
{
for (int y=0; y<300; y++)
{
for (int z=0; z<400; z++)
{
// compute and store value
arr[k++] = val;
}
}
}