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

Je copie N octets de pSrcvers pDest. Cela peut être fait en une seule boucle:

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

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

Comme memcpy utilise des pointeurs de mots au lieu de pointeurs d'octets, les implémentations de memcpy sont souvent écrites avec des instructions SIMD , ce 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 dans un vecteur d'une longueur maximale de 16 octets. Cela comprend les instructions de chargement et de stockage.

Les routines de copie de mémoire peuvent être beaucoup plus compliquées et plus rapides qu'une simple copie de mémoire via des pointeurs tels que:

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 faire est d'aligner l'un des pointeurs sur une limite de mot (par mot, je veux dire une taille entière native, généralement 32 bits / 4 octets, mais peut être de 64 bits / 8 octets sur les architectures plus récentes) et utiliser un mouvement de taille de mot / copier les instructions. Cela nécessite d'utiliser une copie d'octet en 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 fonctionneront différemment selon que la source ou le pointeur de 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, un certain déroulement de boucle peut être effectué, de sorte que davantage de registres du processeur soient chargés de données et cela signifie que les instructions de chargement / stockage peuvent être entrelacées et avoir leur latence masquée par des instructions supplémentaires (telles que le comptage de boucles, etc.). L'avantage que cela apporte varie un peu 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 Assembly plutôt qu'en C (ou C ++), car vous devez placer manuellement les instructions de chargement et de stockage pour tirer le meilleur parti du masquage de la latence et du débit.

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

Ce qui m'amène à la prochaine amélioration, l'ajout de la pré-extraction. Ce sont des 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. Puisqu'il y a un délai entre l'émission de l'instruction et le remplissage de la ligne d'antémémoire, les instructions doivent être placées de telle manière que les données soient disponibles au moment où elles doivent être copiées, et pas plus tôt / plus tard.

Cela signifie mettre des instructions de prélecture au début de la fonction ainsi qu'à l'intérieur de la boucle de copie principale. Avec les instructions de prélecture au milieu de la boucle de copie, des données qui seront copiées en plusieurs itérations.

Je ne me souviens pas, mais il peut également être avantageux de pré-extraire les adresses de destination ainsi que celles de la source.

Les facteurs

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

• 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.).

Donc, si vous voulez écrire une routine de gestion de la mémoire efficace et rapide, vous devrez en savoir beaucoup sur le processeur et l'architecture pour lesquels vous écrivez. Qu'il suffise de dire qu'à moins que vous n'écriviez sur une plate-forme intégrée, il serait beaucoup plus facile d'utiliser simplement les routines de copie mémoire intégrées.

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

À partir d' un exemple d'implémentation :

    00026 * Pour une copie rapide, optimisez le cas courant où les deux pointeurs
    00027 * et la longueur sont alignées sur les mots, et copiez mot à la fois à la place
    00028 * d'octet à la fois. Sinon, copiez par octets.

Vous pouvez implémenter en memcpy()utilisant l'une des techniques suivantes, certaines dépendant de votre architecture pour les gains de performances, et elles seront toutes beaucoup plus rapides que votre code:

1. Utilisez des unités plus grandes, telles que des mots de 32 bits au lieu d'octets. Vous pouvez également (ou devrez peut-être) traiter l'alignement ici aussi. Vous ne pouvez pas lire / écrire un mot de 32 bits dans un emplacement de mémoire étrange, par exemple sur certaines plates-formes, et sur d'autres plates-formes, vous payez une pénalité de performance énorme. Pour résoudre ce problème, l'adresse doit être une unité divisible par 4. Vous pouvez prendre cela jusqu'à 64 bits pour les processeurs 64 bits, ou même plus en utilisant les instructions SIMD (instruction unique, données multiples) ( MMX , SSE , etc.)

2. Vous pouvez utiliser des instructions CPU spéciales que votre compilateur ne pourra peut-être pas optimiser à partir de C. Par exemple, sur un 80386, vous pouvez utiliser l'instruction de préfixe "rep" + l'instruction "movsb" pour déplacer N octets dictés en plaçant N dans le décompte S'inscrire. Les bons compilateurs le feront juste pour vous, mais vous êtes peut-être sur une plate-forme qui manque d'un bon compilateur. Notez que cet exemple a tendance à être une mauvaise démonstration de vitesse, mais combiné à un alignement + des instructions d'unité plus grandes, il peut être plus rapide que presque tout le reste sur certains processeurs.

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

Par exemple, http://www.agner.org/optimize/#asmlib a une memcpyimplémentation qui bat le plus là-bas (par une très petite quantité). Si vous lisez le code source, il sera plein de tonnes de code d'assemblage intégré qui tire parti de toutes les trois techniques ci-dessus, en choisissant laquelle de ces techniques en fonction du processeur sur lequel vous utilisez.

Notez que des optimisations similaires peuvent également être effectuées pour rechercher des octets dans un tampon. strchr()et les amis seront souvent plus rapides que votre équivalent roulé à la main. Cela 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 une recherche de chaîne Boyer – Moore , car elle utilise les techniques d'optimisation ci-dessus.

Réponse courte:

• remplissage du cache
• les transferts de mots au lieu d'octets lorsque cela est possible
• Magie SIMD

Je ne sais pas s'il est réellement utilisé dans des implémentations réelles de memcpy, mais je pense que Duff's Device mérite une mention ici.

De Wikipedia :

send(to, from, count)
register short *to, *from;
register count;
{
        register n = (count + 7) / 8;
        switch(count % 8) {
        case 0:      do {     *to = *from++;
        case 7:              *to = *from++;
        case 6:              *to = *from++;
        case 5:              *to = *from++;
        case 4:              *to = *from++;
        case 3:              *to = *from++;
        case 2:              *to = *from++;
        case 1:              *to = *from++;
                } while(--n > 0);
        }
}

Notez que ce qui précède n'est pas un memcpycar il n'incrémente pas délibérément le topointeur. Il implémente une opération légèrement différente: l'écriture dans un registre mappé en mémoire. Voir l'article Wikipedia pour plus de détails.

Comme d'autres disent que memcpy copie des morceaux de plus de 1 octet. La copie en blocs de la taille d'un mot est beaucoup plus rapide. Cependant, la plupart des implémentations vont plus loin et exécutent plusieurs instructions MOV (mot) avant de boucler. L'avantage de copier par exemple 8 blocs de mots par boucle est que la boucle elle-même est coûteuse. Cette technique réduit le nombre de branches conditionnelles d'un facteur 8, optimisant la copie pour les blocs géants.

Les réponses sont très bien, mais si vous voulez toujours mettre en œuvre un jeûne memcpyvous, il y a un blog intéressant memcpy rapide, memcpy rapide en C .

void *memcpy(void* dest, const void* src, size_t count)
{
    char* dst8 = (char*)dest;
    char* src8 = (char*)src;

    if (count & 1) {
        dst8[0] = src8[0];
        dst8 += 1;
        src8 += 1;
    }

    count /= 2;
    while (count--) {
        dst8[0] = src8[0];
        dst8[1] = src8[1];

        dst8 += 2;
        src8 += 2;
    }
    return dest;
}

Même, cela peut être mieux avec l'optimisation des accès mémoire.

Parce que, comme de nombreuses routines de bibliothèque, il a été optimisé pour l'architecture sur laquelle vous exécutez. D'autres ont publié diverses techniques qui peuvent être utilisées.

Si vous avez le choix, utilisez les routines de la bibliothèque plutôt que les vôtres. C'est une variante de DRY que j'appelle DRO (Don't Repeat Others). En outre, les routines de bibliothèque sont moins susceptibles d'être erronées que votre propre implémentation.

J'ai vu des vérificateurs d'accès à la mémoire se plaindre de lectures hors limites sur la mémoire ou des tampons de chaîne qui n'étaient pas un multiple de la taille du mot. Ceci est le résultat de l'optimisation utilisée.

Vous pouvez regarder l'implémentation MacOS de memset, memcpy et memmove.

Au moment du démarrage, le système d'exploitation détermine sur quel processeur il s'exécute. Il a intégré un code spécifiquement optimisé pour chaque processeur pris en charge et, au moment du démarrage, stocke une instruction jmp dans le bon code dans un emplacement fixe en lecture / seule.

Les implémentations C memset, memcpy et memmove ne sont qu'un saut vers cet emplacement fixe.

Les implémentations utilisent un code différent en fonction de l'alignement de la source et de la destination pour memcpy et memmove. Ils utilisent évidemment toutes les capacités vectorielles disponibles. Ils utilisent également des variantes sans mise en cache lorsque vous copiez de grandes quantités de données et ont des instructions pour minimiser les temps d'attente pour les tables de pages. Ce n'est pas seulement du code assembleur, c'est du code assembleur écrit par quelqu'un avec une très bonne connaissance de chaque architecture de processeur.

Intel a également ajouté des instructions d'assemblage qui peuvent accélérer les opérations de chaîne. Par exemple, avec une instruction pour prendre en charge strstr qui effectue une comparaison de 256 octets en un cycle.