C : vitesse de memcpy sur les tableaux alloués dynamiquement

Question

J'ai besoin d'aide concernant les performances du code suivant. Il effectue un memcpy sur deux tableaux alloués dynamiquement de taille arbitraire :

int main()
{
  double *a, *b;
  unsigned n = 10000000, i;
  a = malloc(n*sizeof(double));
  b = malloc(n*sizeof(double));
  for(i=0; i<n; i++) {
    a[i] = 1.0;
    /* b[i] = 0.0; */
  }

  tic();
  bzero(b, n*sizeof(double));
  toc("bzero1");

  tic();
  bzero(b, n*sizeof(double));
  toc("bzero2");

  tic();
  memcpy(b, a, n*sizeof(double));
  toc("memcpy");
}

tic/toc mesurent le temps d'exécution.

Sur mon ordinateur, il faut 0,035s pour faire un memcpy (Linux, gcc version 4.4.6). Si je décommente maintenant la ligne qui initialise le tableau de destination b, le code est trois fois plus rapide ( !) - 0.011s.

J'ai observé un comportement similaire en utilisant une boucle au lieu de memcpy. En général, je ne m'en soucie pas, car il suffit d'initialiser la mémoire avant de l'utiliser. Cependant, j'ai maintenant besoin d'effectuer une simple copie de mémoire, et de le faire aussi vite que possible. L'initialisation des données nécessite d'écrire, par exemple, 0 dans la mémoire, ce qui n'est pas nécessaire et prend du temps. Et je voudrais effectuer une copie de mémoire en utilisant toute la bande passante disponible.

Existe-t-il une solution à ce problème ? Ou est-il lié à la façon dont Linux gère la mémoire dynamique (une sorte d'allocation de page paresseuse ?) et ne peut être contourné ? Comment cela se passe-t-il sur d'autres systèmes ?

Editar: Les mêmes résultats sont obtenus avec gcc 4.6. J'ai utilisé -O3 pour compiler.

Editar: Merci à tous pour vos commentaires. Je comprends que la cartographie de la mémoire prend du temps. Je suppose que j'ai juste du mal à accepter que cela prenne autant de temps, beaucoup plus que l'accès réel à la mémoire. Le code a été modifié pour inclure un benchmark de l'initialisation du tableau b en utilisant deux appels bzero successifs. Les temps sont maintenant les suivants

bzero1 0.273981
bzero2 0.056803
memcpy 0.117934

Clairement, le premier appel à bzero fait mucho plus qu'un simple flux de zéros en mémoire - c'est un mappage de la mémoire et une mise à zéro de la mémoire. Le deuxième appel bzero, quant à lui, prend la moitié du temps nécessaire pour faire un memcpy, ce qui est exactement ce à quoi on s'attendait - temps d'écriture seulement contre temps de lecture et d'écriture. Je comprends que l'overhead du second appel bzero doit être présent pour des raisons de sécurité du système d'exploitation. Mais qu'en est-il du reste ? Ne puis-je pas le réduire d'une manière ou d'une autre, par exemple en utilisant des pages de mémoire plus grandes ? Différents paramètres du noyau ?

Je dois mentionner que je l'exécute sur Ubuntu wheeze.

Answer 1

C'est probablement une allocation de page paresseuse, Linux ne mappant les pages qu'au premier accès. IIRC chaque page dans un nouveau bloc sous Linux est une copie sur l'écriture d'une page blanche, et vos allocations sont assez grandes pour demander de nouveaux blocs.

Si vous voulez le contourner, vous pouvez écrire un octet ou un mot, à intervalles de 4k. Cela pourrait permettre de mapper les adresses virtuelles en RAM un peu plus rapidement qu'en écrivant la totalité de chaque page.

Je ne m'attendrais pas à ce que (solution de contournement la plus efficace pour forcer le mappage paresseux de la mémoire) plus (copie) soient significativement plus rapides que (copie) sans l'initialisation de b mais Donc, à moins qu'il n'y ait une raison spécifique pour laquelle vous vous souciez uniquement des performances de la copie, et non de l'ensemble de l'opération, c'est plutôt futile. C'est "payez maintenant ou payez plus tard", Linux paye plus tard, et vous ne mesurez le temps que pour plus tard.

Answer 2

Si vous comparez la vitesse de l'initialisation et de la copie à celle de la copie seule, l'initialisation devrait être incluse dans la section chronométrée. Il me semble que vous devriez en fait comparer cela :

// Version 1
for(i=0; i<n; i++)
    a[i] = 1.0;

tic();

memcpy(b, a, n*sizeof(double));

toc();

A ceci :

// Version 2
for(i=0; i<n; i++)
    a[i] = 1.0;

tic();

for(i=0; i<n; i++)
    b[i] = 0.0;
memcpy(b, a, n*sizeof(double));

toc();

Je m'attends à ce que l'amélioration de votre vitesse de 3x diminue fortement.

EDIT : Comme le suggère Steve Jessop, vous pouvez également tester une troisième stratégie consistant à ne toucher qu'une entrée par page :

// Version 3
for(i=0; i<n; i++)
    a[i] = 1.0;

tic();

for(i=0; i<n; i+=DOUBLES_PER_PAGE)
    b[i] = 0.0;
memcpy(b, a, n*sizeof(double));

toc();

Answer 3

Le premier bzero s'exécute plus longtemps à cause (1) de l'allocation paresseuse des pages et (2) de l'initialisation paresseuse de la page zéro par le noyau. Alors que la deuxième raison est inévitable pour des raisons de sécurité, l'allocation paresseuse de pages peut être optimisée en utilisant des pages plus grandes ("énormes").

Il y a au moins deux façons d'utiliser des pages énormes sous Linux. La manière dure est hugetlbfs . Le moyen le plus simple est Des pages énormes et transparentes .

Recherche khugepaged dans la liste des processus de votre système. Si un tel processus existe, les pages transparentes énormes sont prises en charge, vous pouvez les utiliser dans votre application si vous modifiez les éléments suivants malloc à ça :

posix_memalign((void **)&b, 2*1024*1024, n*sizeof(double));
madvise((void *)b, n*sizeof(double), MADV_HUGEPAGE);