Fonction de décalage de masortingce conviviale en cache

Je souhaite décaler la première ligne d’une masortingce carrée 2D vers la dernière ligne. Donc, si j’ai une masortingce comme A, je veux obtenir B.

visuel du processus

Je peux le faire en utilisant deux simples boucles for. Par exemple

void shift(int M, int N, int A[M][N]){ int i, j,temp; for (i = 1; i < M; i++){ for (j = 0; j < N; j++){ temp=A[i][j]; A[i][j]=A[i-1][j]; A[i-1][j]=temp; } } } 

Mais je veux obtenir le moins de cache possible. Une astuce sur comment faire cela?

 /* M is the number of rows; N is the number of columns. */ void masortingx_shift(int M, int N, int A[M][N]) { size_t rowbytes = N * sizeof(int); int temprow[N]; memcpy(temprow, A, rowbytes); // store first row memmove(A, A + 1, (M-1) * rowbytes); // shift up memcpy(A + (M-1), temprow, rowbytes); // replace last row } 

Cela rest simple et repose sur des routines qui doivent être hautement optimisées sur toute plate-forme commune. Il y a une ligne supplémentaire copiée, mais il s’agit d’une inefficacité mineure dans le cas déclaré d’une masortingce carrée.

Je viens de voir votre commentaire sur les masortingces 4×4. Un tableau 4×4 d’ int s’intègre dans une seule ligne de cache (sur les processeurs x86 modernes, où une ligne de cache est de 64B). Dans ce cas, vous voulez que le compilateur génère quelque chose comme:

 ## masortingx address in [rdi] movups xmm0, [rdi] movups xmm1, [rdi+16] movups xmm2, [rdi+32] movups xmm3, [rdi+48] movups [rdi], xmm1 ; doing all the stores after all the loads avoids any possible false dependency movups [rdi+16], xmm2 movups [rdi+32], xmm3 movups [rdi+48], xmm0 

Ou peut-être moins de charges / magasins AVX 256b, mais AVX non aligné pourrait faire pire. Si le tableau est aligné sur 64B, aucun des chargements / magasins requirejs ne dépasserait les limites de la ligne de cache. Donc, 2x vmovups ymm charge, et un magasin vmovups ymm , un magasin vmovups xmm (jusqu’à la fin) et un magasin vextractf128 (jusqu’au début).

Si vous avez de la chance, la mémoire de John sera optimisée si la fonction est insérée dans un appelant dont les valeurs constantes de compilation sont 4 .

Pour les baies minuscules, le problème ne réside pas dans les erreurs de cache, mais dans la manière d’obtenir la copie complète avec le moins de temps possible. Mes idées ci-dessous concernant l’introduction d’un niveau d’indirection ne sont pas une bonne idée, car il est très économique de charger toutes les données et de les stocker à nouveau.


Pour les grandes masortingces:

Si vous laissez de la place à la fin de votre masortingce pour une autre ligne, vous pouvez simplement copier la première ligne dans cet espace supplémentaire et faire passer un pointeur sur la deuxième ligne.

Cela vous permet d’avoir temporairement une vue différente d’une masortingce, mais ce n’est pas un processus reproductible.

Si vous avez un grand tampon, vous pouvez continuer à faire pivoter les lignes de la masortingce jusqu’à atteindre la fin de l’espace réservé et à copier le tableau en haut du tampon. Cela minimise les frais de copie, mais signifie que vous touchez une nouvelle mémoire.


Si la surcharge de copie de ligne est un gros problème, l’introduction d’un niveau d’indirection peut être une bonne idée. En fonction du modèle d’access du code qui l’utilise après avoir mélangé les lignes, la situation pourrait être pire. Au lieu d’un tableau 2D normal, il peut s’agir d’un cas d’utilisation d’un tableau de pointeurs vers des lignes.

Vous pouvez et devez allouer le stockage de la masortingce avec une grande allocation au lieu d’allouer chaque ligne séparément. Un std::vector de vecteurs n’est pas idéal. Initialiser vos int *rows[M] prend juste une boucle de &A[i][0] , donc ce ne sont que des calculs, pas des charges ou des affectations multiples.

L’access au tableau via cette table d’indirection remplace i*N + j math avec pointer-Chasse: charge les rows[i] , puis indexe-le avec j .

Lorsque vous n’avez pas besoin de la vue aléatoire de la masortingce, vous pouvez y accéder directement, mais si vous voulez pouvoir effectuer une réorganisation permanente de la masortingce, tous les utilisateurs doivent toujours passer par la couche indirection.