Pourquoi memcpy() et memmove() sont-ils plus rapides que les incréments de pointeur ?

Question

Je copie N octets de pSrc à pDest . Ceci peut être fait dans une seule boucle :

for (int i = 0; i < N; i++)
    *pDest++ = *pSrc++

Pourquoi est-ce plus lent que memcpy ou memmove ? Quelles astuces utilisent-ils pour l'accélérer ?

Answer 1

Parce que memcpy utilise des pointeurs de mot au lieu de pointeurs d'octet, les implémentations de memcpy sont souvent écrites avec SIMD qui permet de mélanger 128 bits à la fois.

Les instructions SIMD sont des instructions d'assemblage qui peuvent effectuer la même opération sur chaque élément d'un vecteur d'une longueur maximale de 16 octets. Cela inclut les instructions de chargement et de stockage.

Answer 2

Les routines de copie de mémoire peuvent être bien plus compliquées et plus rapides qu'une simple copie de mémoire via des pointeurs, par exemple :

void simple_memory_copy(void* dst, void* src, unsigned int bytes)
{
  unsigned char* b_dst = (unsigned char*)dst;
  unsigned char* b_src = (unsigned char*)src;
  for (int i = 0; i < bytes; ++i)
    *b_dst++ = *b_src++;
}

Améliorations

La première amélioration que l'on peut apporter est d'aligner l'un des pointeurs sur une frontière de mot (par mot, j'entends la taille native d'un entier, généralement 32 bits/4 octets, mais qui peut être 64 bits/8 octets sur les architectures plus récentes) et d'utiliser des instructions de déplacement/copie de taille mot. Cela nécessite l'utilisation d'une copie octet par octet jusqu'à ce qu'un pointeur soit aligné.

void aligned_memory_copy(void* dst, void* src, unsigned int bytes)
{
  unsigned char* b_dst = (unsigned char*)dst;
  unsigned char* b_src = (unsigned char*)src;

  // Copy bytes to align source pointer
  while ((b_src & 0x3) != 0)
  {
    *b_dst++ = *b_src++;
    bytes--;
  }

  unsigned int* w_dst = (unsigned int*)b_dst;
  unsigned int* w_src = (unsigned int*)b_src;
  while (bytes >= 4)
  {
    *w_dst++ = *w_src++;
    bytes -= 4;
  }

  // Copy trailing bytes
  if (bytes > 0)
  {
    b_dst = (unsigned char*)w_dst;
    b_src = (unsigned char*)w_src;
    while (bytes > 0)
    {
      *b_dst++ = *b_src++;
      bytes--;
    }
  }
}

Différentes architectures auront des performances différentes selon que le pointeur source ou le pointeur destination est correctement aligné. Par exemple, sur un processeur XScale, j'ai obtenu de meilleures performances en alignant le pointeur de destination plutôt que le pointeur source.

Pour améliorer encore les performances, il est possible de dérouler certaines boucles, de sorte qu'une plus grande partie des registres du processeur soit chargée de données, ce qui signifie que les instructions de chargement/stockage peuvent être entrelacées et que leur latence est masquée par des instructions supplémentaires (comme le comptage de boucles, etc.). L'avantage que cela apporte varie beaucoup selon le processeur, car les latences des instructions de chargement/stockage peuvent être très différentes.

À ce stade, le code finit par être écrit en assembleur plutôt qu'en C (ou C++), car il faut placer manuellement les instructions de chargement et de stockage pour tirer le meilleur parti de la dissimulation de la latence et du débit.

En général, une ligne entière de données du cache doit être copiée en une seule itération de la boucle déroulée.

Ce qui m'amène à l'amélioration suivante, l'ajout de la recherche préalable. Il s'agit d'instructions spéciales qui indiquent au système de cache du processeur de charger des parties spécifiques de la mémoire dans son cache. Comme il y a un délai entre l'émission de l'instruction et le remplissage de la ligne de cache, les instructions doivent être placées de manière à ce que les données soient disponibles au moment où elles doivent être copiées, et pas avant/après.

Cela signifie qu'il faut placer les instructions de préextraction au début de la fonction ainsi qu'à l'intérieur de la boucle de copie principale. Les instructions de préextraction au milieu de la boucle de copie récupèrent les données qui seront copiées dans plusieurs itérations.

Je ne m'en souviens pas, mais il peut également être utile de préempter les adresses de destination ainsi que les adresses d'origine.

Facteurs

Les principaux facteurs qui affectent la vitesse de copie de la mémoire sont les suivants :

• La latence entre le processeur, ses caches et la mémoire principale.
• La taille et la structure des lignes de cache du processeur.
• Les instructions de déplacement/copie de la mémoire du processeur (latence, débit, taille du registre, etc.).

Ainsi, si vous souhaitez écrire une routine de traitement de la mémoire efficace et rapide, vous devrez en savoir beaucoup sur le processeur et l'architecture pour lesquels vous écrivez. Il suffit de dire que, à moins que vous n'écriviez sur une plate-forme embarquée, il serait beaucoup plus facile d'utiliser les routines de copie de mémoire intégrées.

Answer 3

memcpy peut copier plus d'un octet à la fois, selon l'architecture de l'ordinateur. La plupart des ordinateurs modernes peuvent travailler avec 32 bits ou plus dans une seule instruction du processeur.

De un exemple de mise en œuvre :

    00026          \* For speedy copying, optimize the common case where both pointers
    00027          \* and the length are word-aligned, and copy word-at-a-time instead
    00028          \* of byte-at-a-time. Otherwise, copy by bytes.

Answer 4

Vous pouvez mettre en œuvre memcpy() en utilisant l'une des techniques suivantes, dont certaines dépendent de votre architecture pour les gains de performance, et elles seront toutes beaucoup plus rapides que votre code :

1. Utilisez des unités plus grandes, comme des mots de 32 bits au lieu d'octets. Vous pouvez également (ou devrez peut-être) traiter l'alignement ici aussi. Sur certaines plates-formes, vous ne pouvez pas lire/écrire un mot de 32 bits dans un emplacement mémoire impair, par exemple. Sur d'autres plates-formes, vous payez un lourd tribut en termes de performances. Pour résoudre ce problème, l'adresse doit être une unité divisible par 4. Vous pouvez aller jusqu'à 64 bits pour les processeurs 64 bits, ou même plus en utilisant les méthodes suivantes SIMD (Instruction unique, données multiples) instructions ( MMX , SSE etc.)

2. Vous pouvez utiliser des instructions spéciales du CPU que votre compilateur ne pourra peut-être pas optimiser à partir du C. Par exemple, sur un 80386, vous pouvez utiliser l'instruction préfixe "rep" + l'instruction "movsb" pour déplacer N octets dictés par le placement de N dans le registre de comptage. Les bons compilateurs le feront pour vous, mais il se peut que vous soyez sur une plate-forme qui ne dispose pas d'un bon compilateur. Notez que cet exemple tend à être une mauvaise démonstration de la vitesse, mais combiné avec l'alignement + des instructions unitaires plus grandes, il peut être plus rapide que presque tout le reste sur certains CPU.

3. Déroulement de la boucle -- les branches peuvent être assez coûteuses sur certains processeurs, donc dérouler les boucles peut réduire le nombre de branches. C'est également une bonne technique à combiner avec les instructions SIMD et les unités de très grande taille.

Par exemple, http://www.agner.org/optimize/#asmlib a un memcpy qui bat la plupart des autres (de très peu). Si vous lisez le code source, vous verrez qu'il est rempli de tonnes de code assembleur intégré qui met en œuvre les trois techniques ci-dessus, en choisissant laquelle de ces techniques en fonction du processeur sur lequel vous travaillez.

Notez que des optimisations similaires peuvent être réalisées pour trouver des octets dans un tampon. strchr() et amis seront souvent plus rapides que leur équivalent roulé à la main. C'est particulièrement vrai pour .NET et Java . Par exemple, dans .NET, la fonction intégrée String.IndexOf() est beaucoup plus rapide que même un Recherche de chaînes Boyer-Moore car il utilise les techniques d'optimisation ci-dessus.

Answer 5

Réponse courte :

• remplissage du cache
• les transferts de mots au lieu d'octets lorsque c'est possible
• La magie SIMD