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

Comme memcpy utilise des pointeurs de mots au lieu de pointeurs d’octets, les implémentations 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 d’un vecteur d’une longueur maximale de 16 octets. Cela inclut 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 puisse faire consiste à aligner l'un des pointeurs sur une limite de mot (mot signifie taille entière native, généralement 32 bits / 4 octets, mais peut être 64 bits / 8 octets sur des architectures plus récentes) et utiliser un déplacement de la taille d'un mot / copier les instructions. Cela nécessite l'utilisation d'un octet à octet copie 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 le pointeur source ou 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, le déroulement des boucles peut être effectué de sorte que davantage de registres du processeur soient chargés de données, ce qui signifie que les instructions de chargement / stockage peuvent être entrelacées et leur latence masquée par des instructions supplémentaires (comptage de boucles, etc.). L'avantage que cela apporte varie beaucoup par le processeur, puisque les latences des instructions de chargement / stockage peuvent être très différentes.

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

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

Ce qui m'amène à la prochaine amélioration, en ajoutant 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. 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 même où elles doivent être copiées et à tout moment.

Cela signifie qu'il faut placer les instructions de prélecture au début de la fonction, ainsi que dans la boucle de copie principale. Avec les instructions prefetch au milieu de la boucle de copie, vous récupérez les données qui seront copiées dans plusieurs itérations.

Je ne me souviens pas, mais il peut également être utile de pré-télécharger les adresses de destination ainsi que celles d'origine.

Facteurs

Les principaux facteurs influant sur la rapidité 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.).

Donc, si vous voulez écrire une routine de mémoire efficace et rapide, vous devez en savoir beaucoup sur le processeur et l'architecture pour lesquels vous écrivez. Inutile de dire que, à moins d’écrire sur une plate-forme embarquée, il serait beaucoup plus simple d’utiliser les routines de copie de mémoire intégrées.

memcpy peut copier plus d’un octet à la fois en fonction de l’architecture de l’ordinateur. La plupart des ordinateurs modernes peuvent fonctionner avec 32 bits ou plus dans une seule instruction de processeur.

A partir d’ un exemple d’implémentation :

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

Vous pouvez implémenter memcpy() utilisant l’une des techniques suivantes, certaines dépendant de votre architecture pour des 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 peut-être) avoir à gérer l’alignement ici aussi. Vous ne pouvez pas lire / écrire un mot de 32 bits dans un emplacement de mémoire impair, par exemple sur certaines plates-formes, et sur d’autres plates-formes, vous payez une pénalité de performance considérable. Pour corriger cela, 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 spéciales de processeur que votre compilateur ne peut pas optimiser depuis 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 registre. Les bons compilateurs le feront simplement pour vous, mais vous êtes peut-être sur une plate-forme dépourvue de bon compilateur. Notez que cet exemple a tendance à être une mauvaise démonstration de la vitesse, mais combiné à l’alignement et aux instructions plus larges de l’unité, il peut être plus rapide que la plupart des autres CPU.

3. Le déroulement des boucles – les twigs peuvent être assez onéreuses sur certains processeurs, donc le déroulement des boucles peut réduire le nombre de twigs. C’est aussi 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 implémentation memcpy qui bat le plus fort (d’un tout petit nombre). Si vous lisez le code source, il sera rempli de tonnes de code d’assemblage qui extrait toutes les trois techniques ci-dessus, en choisissant laquelle de ces techniques est basée sur le processeur sur lequel vous travaillez.

Notez que des optimisations similaires peuvent également être effectuées pour trouver des octets dans un tampon. strchr() et ses amis seront souvent plus rapides que vos équivalents roulés à la main. Cela est particulièrement vrai pour .NET et Java . Par exemple, dans .NET, le Ssortingng.IndexOf() est beaucoup plus rapide que même une recherche de chaîne de Boyer – Moore , car il utilise les techniques d’optimisation ci-dessus.

Réponse courte:

• remplissage du cache
• des transferts de mots plutôt que des octets
• Magie SIMD

Comme d’autres disent des copies plus grandes que des morceaux d’un octet. La copie en morceaux au format Word est beaucoup plus rapide. Cependant, la plupart des implémentations vont plus loin et exécutent plusieurs instructions MOV (word) avant de boucler. L’avantage de copier 8 blocs de mots par boucle est que la boucle elle-même est coûteuse. Cette technique réduit le nombre de twigments conditionnels d’un facteur 8, optimisant la copie pour les blocs géants.

Je ne sais pas si elle est utilisée dans des implémentations memcpy 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 memcpy car il n’inclut pas délibérément le pointeur to . Il implémente une opération légèrement différente: l’écriture dans un registre mappé en mémoire. Voir l’article de Wikipedia pour plus de détails.

Les réponses sont géniales, mais si vous souhaitez toujours vous implémenter rapidement, il existe un article de blog intéressant sur fast memcpy, Fast memcpy in 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, il peut être préférable d’optimiser les access mémoire.

Parce que, comme de nombreuses routines de bibliothèque, il a été optimisé pour l’architecture sur laquelle vous travaillez. D’autres ont posté diverses techniques pouvant être utilisées.

Étant donné le choix, utilisez les routines de la bibliothèque plutôt que de rouler les vôtres. C’est une variation de DRY que j’appelle DRO (Don’t Repeat Others). De plus, les routines de bibliothèque sont moins susceptibles d’être erronées que votre propre implémentation.

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