Que manque-t-il / sous-optimal dans cette implémentation memcpy?

Je me suis intéressé à l’écriture de memcpy() tant qu’exercice éducatif. Je n’écrirai pas tout ce que j’ai fait et auquel je n’ai pas pensé, mais voici la mise en œuvre d’un type :

 __forceinline //因为通常Size已知,内联后编译器可以优化掉大部分无用代码void* myMemcpy(char* Dst, const char* Src, size_t Size) { void* start = Dst; for ( ; Size >= sizeof(__m256i); Size -= sizeof(__m256i) ) { __m256i ymm = _mm256_loadu_si256(((const __m256i* &)Src)++); _mm256_storeu_si256(((__m256i* &)Dst)++, ymm); } #define CPY_1B *((uint8_t * &)Dst)++ = *((const uint8_t * &)Src)++ #define CPY_2B *((uint16_t* &)Dst)++ = *((const uint16_t* &)Src)++ #define CPY_4B *((uint32_t* &)Dst)++ = *((const uint32_t* &)Src)++ #if defined _M_X64 || defined _M_IA64 || defined __amd64 #define CPY_8B *((uint64_t* &)Dst)++ = *((const uint64_t* &)Src)++ #else #define CPY_8B _mm_storel_epi64((__m128i *)Dst, _mm_loadu_si128((const __m128i *)Src)), ++(const uint64_t* &)Src, ++(uint64_t* &)Dst #endif #define CPY16B _mm_storeu_si128((__m128i *)Dst, _mm_loadu_si128((const __m128i *)Src)), ++(const __m128i* &)Src, ++(__m128i* &)Dst switch (Size) { case 0x00: break; case 0x01: CPY_1B; break; case 0x02: CPY_2B; break; case 0x03: CPY_1B; CPY_2B; break; case 0x04: CPY_4B; break; case 0x05: CPY_1B; CPY_4B; break; case 0x06: CPY_2B; CPY_4B; break; case 0x07: CPY_1B; CPY_2B; CPY_4B; break; case 0x08: CPY_8B; break; case 0x09: CPY_1B; CPY_8B; break; case 0x0A: CPY_2B; CPY_8B; break; case 0x0B: CPY_1B; CPY_2B; CPY_8B; break; case 0x0C: CPY_4B; CPY_8B; break; case 0x0D: CPY_1B; CPY_4B; CPY_8B; break; case 0x0E: CPY_2B; CPY_4B; CPY_8B; break; case 0x0F: CPY_1B; CPY_2B; CPY_4B; CPY_8B; break; case 0x10: CPY16B; break; case 0x11: CPY_1B; CPY16B; break; case 0x12: CPY_2B; CPY16B; break; case 0x13: CPY_1B; CPY_2B; CPY16B; break; case 0x14: CPY_4B; CPY16B; break; case 0x15: CPY_1B; CPY_4B; CPY16B; break; case 0x16: CPY_2B; CPY_4B; CPY16B; break; case 0x17: CPY_1B; CPY_2B; CPY_4B; CPY16B; break; case 0x18: CPY_8B; CPY16B; break; case 0x19: CPY_1B; CPY_8B; CPY16B; break; case 0x1A: CPY_2B; CPY_8B; CPY16B; break; case 0x1B: CPY_1B; CPY_2B; CPY_8B; CPY16B; break; case 0x1C: CPY_4B; CPY_8B; CPY16B; break; case 0x1D: CPY_1B; CPY_4B; CPY_8B; CPY16B; break; case 0x1E: CPY_2B; CPY_4B; CPY_8B; CPY16B; break; case 0x1F: CPY_1B; CPY_2B; CPY_4B; CPY_8B; CPY16B; break; } #undef CPY_1B #undef CPY_2B #undef CPY_4B #undef CPY_8B #undef CPY16B return start; } 

Le commentaire se traduit par “La taille est généralement connue comme le compilateur peut optimiser le code inline out le plus inutile”.

Je voudrais améliorer, si possible, sur cette mise en œuvre – mais peut-être qu’il n’y a pas grand chose à améliorer. Je vois qu’il utilise SSE / AVX pour les gros morceaux de mémoire, puis qu’une boucle sur les derniers <32 octets fait l’équivalent du déroulement manuel, avec quelques ajustements. Donc, voici mes questions:

  • Pourquoi dérouler la boucle pour les derniers octets sans pour autant dérouler partiellement la première (et maintenant la seule)?
  • Qu’en est-il des problèmes d’alignement? Ne sont-ils pas importants? Devrais-je gérer les premiers octets jusqu’à un quantum d’alignement différemment, puis exécuter les opérations 256 bits sur des séquences d’octets alignées? Et si oui, comment puis-je déterminer le quantum d’alignement approprié?
  • Quelle est la caractéristique manquante la plus importante dans cette implémentation (le cas échéant)?

Caractéristiques / Principes mentionnés dans les réponses jusqu’à présent

  • Vous devriez __ressortingct__ vos parameters. (@chux)
  • La bande passante mémoire est un facteur limitant; mesurez votre implémentation par rapport à elle. (@ Zboson)
  • Pour les petits tableaux, vous pouvez vous attendre à approcher la bande passante de la mémoire; pour les plus grands tableaux – pas autant. (@Zboson)
  • Plusieurs threads (peuvent être nécessaires) pour saturer la bande passante mémoire. (@Zboson)
  • Il est probablement sage d’optimiser différemment pour les grands et les petits formats. (@Zboson)
  • (L’alignement est important? Pas explicitement abordé!)
  • Le compilateur devrait être plus explicitement conscient des “faits évidents” qu’il peut utiliser pour l’optimisation (comme le fait que Size <32 après la première boucle). (@chux)
  • Il existe des arguments pour le déroulement de vos appels SSE / AVX (@BenJackson, ici ) et des arguments contre (@PaulR)
  • les transferts non temporels (avec lesquels vous indiquez à la CPU que vous n’en avez pas besoin pour mettre en cache l’emplacement cible) devraient être utiles pour la copie de mémoires tampons plus volumineuses. (@Zboson)

J’ai étudié la bande passante mémoire de mesure pour les processeurs Intel avec diverses opérations et l’un d’entre eux est memcpy . Je l’ai fait sur Core2, Ivy Bridge et Haswell. J’ai effectué la plupart de mes tests en utilisant C / C ++ avec des éléments insortingnsèques (voir le code ci-dessous – mais je suis en train de réécrire mes tests en assembleur).

Pour écrire votre propre fonction de memcpy efficace, il est important de savoir quelle est la meilleure bande passante possible. Cette bande passante est fonction de la taille des tableaux qui seront copiés. Par conséquent, une fonction de memcpy efficace doit être optimisée différemment pour les petits et les grands (et peut-être entre les deux). Pour garder les choses simples, j’ai optimisé pour les petits tableaux de 8192 octets et les grands tableaux de 1 Go.

Pour les petits réseaux, la largeur de bande maximale en lecture et en écriture pour chaque cœur est la suivante:

 Core2-Ivy Bridge 32 bytes/cycle Haswell 64 bytes/cycle 

C’est la référence à viser pour les petits tableaux. Pour mes tests, je suppose que les tableaux sont alignés sur 64 octets et que la taille du tableau est un multiple de 8*sizeof(float)*unroll_factor . Voici mes résultats actuels pour une taille de 8192 octets (Ubuntu 14.04, GCC 4.9, EGLIBC 2.19):

  GB/s efficiency Core2 (p9600@2.66 GHz) builtin 35.2 41.3% eglibc 39.2 46.0% asmlib: 76.0 89.3% copy_unroll1: 39.1 46.0% copy_unroll8: 73.6 86.5% Ivy Bridge (E5-1620@3.6 GHz) builtin 102.2 88.7% eglibc: 107.0 92.9% asmlib: 107.6 93.4% copy_unroll1: 106.9 92.8% copy_unroll8: 111.3 96.6% Haswell (i5-4250U@1.3 GHz) builtin: 68.4 82.2% eglibc: 39.7 47.7% asmlib: 73.2 87.6% copy_unroll1: 39.6 47.6% copy_unroll8: 81.9 98.4% 

L’ asmlib est l’ asmlib Agner Fog . Les fonctions copy_unroll1 et copy_unroll8 sont définies ci-dessous.

Dans ce tableau, nous pouvons voir que la mémoire memcpy GCC ne fonctionne pas bien sur Core2 et que la memcpy dans EGLIBC ne fonctionne pas bien sur Core2 ou Haswell. J’ai récemment testé une version principale de GLIBC et les performances étaient bien meilleures sur Haswell. Dans tous les cas, le déroulement donne le meilleur résultat.

 void copy_unroll1(const float *x, float *y, const int n) { for(int i=0; i 

}

VECNF().LOAD est _mm_load_ps() pour SSE ou _mm256_load_ps() pour AVX, VECNF().STORE est _mm_store_ps() pour SSE ou _mm256_store_ps() pour AVX et _mm256_load_ps() pour VECNF().STORE est 4 pour SSE ou 8 pour AVX.

Pour la grande taille, le meilleur résultat est obtenu en utilisant des instructions de magasin non temporelles et en utilisant plusieurs threads. Contrairement à ce que beaucoup de gens peuvent croire, un seul thread ne sature généralement pas la bande passante de la mémoire .

 void copy_stream(const float *x, float *y, const int n) { #pragma omp parallel for for(int i=0; i 

stream est _mm_stream_ps() pour SSE ou _mm256_stream_ps() pour AVX

Voici les résultats de la memcpy sur mon E5-1620@3.6 GHz avec quatre threads pour 1 Go avec une largeur de bande de la mémoire principale maximale de 51,2 Go / s .

  GB/s efficiency eglibc: 23.6 46% asmlib: 36.7 72% copy_stream: 36.7 72% 

Encore une fois, EGLIBC fonctionne mal. En effet, il n’utilise pas de magasins non temporels.

J'ai modifié les fonctions eglibc et asmlib memcpy pour s'exécuter en parallèle comme ceci

 void COPY(const float * __ressortingct x, float * __ressortingct y, const int n) { #pragma omp parallel { size_t my_start, my_size; int id = omp_get_thread_num(); int num = omp_get_num_threads(); my_start = (id*n)/num; my_size = ((id+1)*n)/num - my_start; memcpy(y+my_start, x+my_start, sizeof(float)*my_size); } } 

Une fonction de memcpy générale doit prendre en compte les tableaux qui ne sont pas alignés sur 64 octets (ni même sur 32 ou 16 octets) et dont la taille n’est pas un multiple de 32 octets ni le facteur de déroulement. De plus, il faut décider quand utiliser les magasins non temporels. La règle générale consiste à n'utiliser que des magasins non temporels pour des tailles supérieures à la moitié du niveau de cache le plus important (généralement L3). Mais ces thèses sont des détails de «second ordre» qui, à mon avis, devraient être traités après optimisation pour les cas idéaux, grands ou petits. Il est inutile de s’inquiéter de la correction du désalignement ou des multiples de taille non idéale si le cas idéal fonctionne également mal.

Mettre à jour

D'après les commentaires de Stephen Canon, j'ai appris que sur Ivy Bridge et Haswell, il était plus efficace d'utiliser rep movsb que movntdqa (une instruction de magasin non temporelle). Intel appelle cette version améliorée movsb (ERMSB) . Ceci est décrit dans les manuels d’optimisation Intel dans la section 3.7.6 Fonctionnement amélioré des opérations de type REP et MOVSB ​​(ERMSB) .

De plus, dans le chapitre 17.9 , Optimisation des sous-routines du manuel d' assemblage d' Agner Fog, Déplacement de blocs de données (Tous les processeurs), il écrit:

"Il existe plusieurs façons de déplacer de gros blocs de données. Les méthodes les plus courantes sont les suivantes:

  1. Instruction REP MOVS.
  2. Si les données sont alignées: lisez et écrivez en boucle avec la plus grande taille de registre disponible.
  3. Si la taille est constante: instructions de déplacement en ligne.
  4. Si les données sont mal alignées: déplacez d’abord autant d’octets que nécessaire pour aligner la destination. Ensuite, lisez non aligné et écrivez dans une boucle alignée avec la plus grande taille de registre disponible.
  5. Si les données sont mal alignées: alignées en lecture, décalez pour compenser le désalignement et écrivez en alignement.
  6. Si la taille des données est trop importante pour la mise en cache, utilisez des écritures non temporelles pour contourner le cache. Décalez pour compenser le désalignement, si nécessaire. "

Un memcpy général devrait considérer chacun de ces points. De plus, avec Ivy Bridge et Haswell, il semble que le point 1 soit meilleur que le point 6 pour les grands tableaux. Différentes techniques sont nécessaires pour Intel et AMD et pour chaque itération de technologie. Je pense qu'il est clair que l'écriture de votre propre fonction de memcpy efficace peut être assez compliquée. Mais dans les cas particuliers que j'ai examinés, j'ai déjà réussi à faire mieux que la mémoire memcpy GCC ou celle d'EGLIBC, de sorte que l'hypothèse que vous ne pouvez pas faire mieux que les bibliothèques standard est fausse.

Premièrement, la boucle principale utilise des charges / magasins de vecteurs AVX non alignés pour copier 32 octets à la fois, jusqu’à ce qu’il rest <32 octets à copier:

  for ( ; Size >= sizeof(__m256i); Size -= sizeof(__m256i) ) { __m256i ymm = _mm256_loadu_si256(((const __m256i* &)Src)++); _mm256_storeu_si256(((__m256i* &)Dst)++, ymm); } 

Ensuite, la dernière instruction switch gère les octets 0..31 résiduels de la manière la plus efficace possible, en utilisant une combinaison de copies d’octets 8/4/2/1 selon les cas. Notez qu’il ne s’agit pas d’une boucle non déroulée. Il s’agit simplement de 32 chemins de code optimisés différents qui gèrent les octets résiduels en utilisant le nombre minimal de charges et de magasins.

En ce qui concerne la raison pour laquelle la boucle AVX principale sur 32 octets n’est pas déroulée manuellement, il existe plusieurs raisons à cela:

  • la plupart des compilateurs déroulent automatiquement les petites boucles (en fonction de la taille de la boucle et des commutateurs d’optimisation)
  • un déroulage excessif peut provoquer l’écoulement de petites boucles hors du cache LSD (en général, seulement 28 µops décodés)
  • sur les processeurs Core iX actuels, vous ne pouvez émettre que deux charges / magasins simultanés avant de vous bloquer [*]
  • même une boucle AVX non déroulée comme celle-ci peut saturer la bande passante DRAM disponible [*]

[*] notez que les deux derniers commentaires ci-dessus s’appliquent aux cas où la source et / ou la destination ne sont pas dans le cache (c’est-à-dire l’écriture / la lecture dans / à partir de la mémoire DRAM) et, par conséquent, la latence de chargement / stockage est élevée.

Il est impossible de répondre à la question avec précision sans quelques détails supplémentaires tels que:

  • Quelle est la plate-forme cible (la plupart du temps l’architecture du processeur, mais la configuration de la mémoire joue également un rôle)?
  • Quelle est la dissortingbution et la prévisibilité 1 des longueurs de copie (et dans une moindre mesure, la dissortingbution et la prévisibilité des alignements)?
  • La taille de la copie sera-t-elle un jour connue de manière statique au moment de la compilation?

Néanmoins, je peux souligner quelques points susceptibles d’être sous-optimaux pour au moins une combinaison des parameters ci-dessus.

Déclaration de changement de 32 cas

L’instruction de commutation à 32 cas est une manière élégante de gérer les 0 à 31 octets de fin, et constitue probablement un très bon sharepoint repère – mais elle peut mal fonctionner dans le monde réel en raison de deux facteurs.

Taille du code

Cette instruction de commutateur prend à elle seule plusieurs centaines d’octets de code pour le corps, en plus d’une entrée 32. Le coût de cette opération ne sera pas memcpy dans une référence memcpy sur la memcpy d’un processeur à taille réelle, car tout rest dans le niveau de cache le plus rapide: mais dans le monde réel, vous exécutez également un autre code et vous vous disputez. cache et caches de données et d’instructions L1.

Le fait que de nombreuses instructions prennent à peu près 20% de la taille réelle de votre cache uop 3 et que les échecs de cache uop (ainsi que les cycles de transition du codeur correspondant) pourraient facilement effacer le petit avantage procuré par ce commutateur élaboré.

De plus, le commutateur nécessite une table de recherche de 32 entrées et 256 octets pour les cibles de saut 4 . Si vous avez un problème avec la DRAM lors de cette recherche, vous parlez d’une pénalité de plus de 150 cycles: combien de non-oublis faut-il pour que le switch de switch vaille la peine, étant donné qu’il en économise probablement quelques-uns au plus ? Encore une fois, cela n’apparaîtra pas dans un micro-critère.

Pour ce que cela vaut, cette memcpy n’est pas inhabituelle: ce genre de “énumération exhaustive de cas” est répandu même dans les bibliothèques optimisées. Je peux en conclure que leur développement a principalement été motivé par des micro-critères, ou que cela vaut encore la peine pour une large tranche de code à usage général, malgré les inconvénients. Cela dit, il existe certainement des scénarios (pression des instructions et / ou du cache de données) dans lesquels cela est sous-optimal.

Prédiction de twig

L’instruction switch repose sur une seule twig indirecte pour choisir parmi les alternatives. Cela va être efficace dans la mesure où le prédicteur de twig peut prédire cette twig indirecte, ce qui signifie fondamentalement que la séquence des longueurs observées doit être prévisible.

S’agissant d’une twig indirecte, la prévisibilité de la twig est soumise à davantage de limites qu’une twig conditionnelle car le nombre d’entrées en BTB est limité. Les processeurs récents ont fait des progrès dans ce domaine, mais il est prudent de dire que si la série de longueurs introduites dans memcpy ne suit pas un schéma répétitif simple d’une courte période (aussi courte que 1 ou 2 sur les processeurs plus anciens), il y aura une twig imprévisible à chaque appel.

Ce problème est particulièrement insidieux, car il est susceptible de vous faire le plus mal dans le monde réel, exactement dans les situations où un micro-indice indique que le switch est le meilleur: les courtes longueurs. Pour les très longues longueurs, le comportement sur les 31 derniers octets n’est pas très important car il est dominé par la copie en bloc. Pour les petites longueurs, le switch est de la plus haute importance (en effet, pour les copies de 31 octets ou moins, c’est tout ce qui est exécuté)!

Pour ces courtes longueurs, une série de longueurs prévisibles fonctionne très bien pour le switch car le saut indirect est fondamentalement libre. En particulier, un repère typique de memcpy “balaye” sur une série de longueurs, en utilisant la même longueur de manière répétée pour chaque sous-test afin de rapporter les résultats pour faciliter la représentation graphique des graphiques “temps par rapport à la longueur”. Le switch effectue très bien ces tests, signalant souvent des résultats tels que 2 ou 3 cycles pour de petites longueurs de quelques octets.

Dans le monde réel, vos longueurs pourraient être petites mais imprévisibles . Dans ce cas, la twig indirecte prédit fréquemment 5 , avec une pénalité de ~ 20 cycles sur les processeurs modernes. Comparé au meilleur des cas de deux ou trois cycles, il est pire. La mâchoire en verre peut donc être très grave (c’est-à-dire que le comportement de l’ switch dans ce cas typique peut être d’un ordre de grandeur pire que le meilleur, alors que pour les longues longueurs, vous observez généralement une différence de 50% au maximum entre stratégies différentes).

Solutions

Alors, comment pouvez-vous faire mieux que ce qui précède, du moins dans les conditions où le switch tombe en morceaux?

Utiliser le périphérique de Duff

Une solution au problème de la taille du code consiste à combiner les boîtiers de commutateurs, le style de périphérique de duff .

Par exemple, le code assemblé pour les cas de longueur 1, 3 et 7 ressemble à ceci:

Longueur 1

  movzx edx, BYTE PTR [rsi] mov BYTE PTR [rcx], dl ret 

Longueur 3

  movzx edx, BYTE PTR [rsi] mov BYTE PTR [rcx], dl movzx edx, WORD PTR [rsi+1] mov WORD PTR [rcx+1], dx 

Longueur 7

  movzx edx, BYTE PTR [rsi] mov BYTE PTR [rcx], dl movzx edx, WORD PTR [rsi+1] mov WORD PTR [rcx+1], dx mov edx, DWORD PTR [rsi+3] mov DWORD PTR [rcx+3], edx ret 

Cela peut être combiné dans un seul cas, avec différents sauts:

  len7: mov edx, DWORD PTR [rsi-6] mov DWORD PTR [rcx-6], edx len3: movzx edx, WORD PTR [rsi-2] mov WORD PTR [rcx-2], dx len1: movzx edx, BYTE PTR [rsi] mov BYTE PTR [rcx], dl ret 

Les étiquettes ne coûtent rien, combinent les cas et suppriment deux instructions de retrait sur trois. Notez que la base de rsi et rcx a changé ici: ils rcx le dernier octet à copier de / vers, plutôt que le premier. Ce changement est gratuit ou très bon marché en fonction du code avant le saut.

Vous pouvez l’étendre pour des longueurs plus longues (par exemple, vous pouvez attacher les longueurs 15 et 31 à la chaîne ci-dessus) et utiliser d’autres chaînes pour les longueurs manquantes. L’exercice complet est laissé au lecteur. Vous pouvez probablement obtenir une réduction de taille de 50% uniquement avec cette approche, et bien mieux si vous la combinez avec autre chose pour réduire les tailles de 16 à 31.

Cette approche ne sert qu’à la taille du code (et éventuellement à la taille de la table de saut, si vous réduisez la taille comme décrit dans le paragraphe 4 et que vous passez sous 256 octets, ce qui permet une table de correspondance de la taille d’un octet. Elle ne fait rien pour la prévisibilité.

Chevauchement des magasins

Une astuce qui aide à la fois la taille du code et la prévisibilité consiste à utiliser des magasins qui se chevauchent. En d’autres memcpy , une memcpy de 8 à 15 octets peut être accomplie sans emtwigment avec deux magasins de 8 octets, le second magasin recouvrant partiellement le premier. Par exemple, pour copier 11 octets, vous devez effectuer une copie de 8 octets aux positions relatives 0 et 11 - 8 == 3 . Certains des octets du milieu seraient “copiés deux fois”, mais en pratique, c’est très bien, car une copie de 8 octets correspond à la même vitesse qu’une copie de 1, 2 ou 4 octets.

Le code C ressemble à:

  if (Size >= 8) { *((uint64_t*)Dst) = *((const uint64_t*)Src); size_t offset = Size & 0x7; *(uint64_t *)(Dst + offset) = *(const uint64_t *)(Src + offset); } 

… et l’assemblage correspondant n’est pas problématique:

  cmp rdx, 7 jbe .L8 mov rcx, QWORD PTR [rsi] and edx, 7 mov QWORD PTR [rdi], rcx mov rcx, QWORD PTR [rsi+rdx] mov QWORD PTR [rdi+rdx], rcx 

En particulier, notez que vous obtenez exactement deux charges, deux magasins et un and (en plus du cmp et du jmp dont l’existence dépend de la manière dont vous organisez le code environnant). C’est déjà lié ou meilleur que la plupart des approches générées par le compilateur pour 8-15 octets, qui peuvent utiliser jusqu’à 4 paires de chargement / stockage.

Les anciens transformateurs ont été pénalisés pour de tels “magasins superposés”, mais les architectures les plus récentes (au moins la dernière décennie) semblent les gérer sans pénalité 6 . Cela présente deux avantages principaux:

  1. Le comportement est sans twig pour une gamme de tailles. Effectivement, cela quantifie le twigment de sorte que plusieurs valeurs empruntent le même chemin. Toutes les tailles de 8 à 15 (ou de 8 à 16 si vous le souhaitez) suivent le même chemin et ne subissent aucune pression de prédiction erronée.

  2. Au moins 8 ou 9 cas différents du switch sont incorporés dans un seul cas avec une fraction de la taille totale du code.

Cette approche peut être combinée à la méthode du switch , mais en n’utilisant que quelques cas, ou elle peut être étendue à des tailles plus grandes avec des déplacements conditionnels, comme par exemple tous les déplacements de 8 à 31 octets sans twigs.

Ce qui fonctionne le mieux dépend à nouveau de la dissortingbution des twigs, mais dans l’ensemble, cette technique de “chevauchement” fonctionne très bien.

Alignement

Le code existant ne traite pas de l’alignement.

En fait, il n’est généralement pas légal, ni C, ni C ++, car les pointeurs sont simplement convertis en types plus gros et déréférencés, ce qui n’est pas légal – bien qu’en pratique, il génère des codes qui fonctionnent avec les compilateurs x86 actuels (mais en fait, échouerait pour une plate-forme avec des exigences d’alignement plus ssortingctes).

Au-delà, il est souvent préférable de gérer l’alignement de manière spécifique. Il y a trois cas principaux:

  1. La source et la destination sont déjà en alignement. Même l’algorithme original fonctionnera bien ici.
  2. La source et la destination sont relativement alignées, mais absolument mal alignées. C’est-à-dire qu’il existe une valeur A qui peut être ajoutée à la fois à la source et à la destination afin que les deux soient alignées.
  3. La source et la destination sont totalement mal alignées (c’est-à-dire qu’elles ne sont pas réellement alignées et que le cas (2) ne s’applique pas).

L’algorithme existant fonctionnera correctement dans le cas (1). Dans le cas de (2), il manque potentiellement une optimisation importante, car une petite boucle d’introduction pourrait transformer une copie non alignée en une copie alignée.

Il est également probable que la performance soit médiocre dans le cas (3), car dans le cas totalement désaligné, vous pouvez choisir d’aligner la destination ou la source, puis de procéder “semi-alignés”.

Les pénalités d’alignement ont été réduites avec le temps et, sur les dernières puces, les puces sont modestes pour le code à usage général, mais peuvent restr sérieuses pour le code comportant de nombreuses charges et magasins. Pour les copies volumineuses, cela n’a sans doute pas beaucoup d’importance, car la bande passante DRAM sera limitée, mais pour les copies plus petites, un désalignement peut réduire le débit de 50% ou plus.

Si vous utilisez des magasins NT, l’alignement peut également être important, car de nombreuses instructions de magasin NT fonctionnent mal avec des arguments mal alignés.

Pas de dérouler

Le code n’est pas déroulé et les compilateurs sont déroulés par quantités différentes par défaut. Clairement, cela n’est pas optimal, car parmi deux compilateurs ayant des stratégies de déroulement différentes, un au plus sera le meilleur.

La meilleure approche (du moins pour les cibles de plate-forme connues) consiste à déterminer le facteur de déroulement optimal, puis à l’appliquer dans le code.

De plus, le déroulement peut souvent être combiné de manière intelligente avec “l’intro” de notre code “outro”, faisant ainsi un meilleur travail que le compilateur.

Tailles connues

La principale raison pour laquelle il est difficile de battre la routine de mémoire “intégrée” avec les compilateurs modernes est que les compilateurs n’appellent pas simplement une memcpy bibliothèque à memcpy fois que la memcpy apparaît dans la source. Ils connaissent le contrat de memcpy et sont libres de le mettre en œuvre avec une seule instruction en ligne, voire moins 7 , dans le bon scénario.

Ceci est particulièrement évident avec les longueurs connues de memcpy . Dans ce cas, si la longueur est petite, les compilateurs insèrent simplement quelques instructions pour effectuer la copie de manière efficace et en place. Cela évite non seulement la surcharge de l’appel de fonction, mais également toutes les vérifications de taille, etc. – et génère également au moment de la compilation un code efficace pour la copie, un peu comme le gros switch de la mise en œuvre ci-dessus – mais sans les coûts du switch .

De même, le compilateur en sait beaucoup sur l’alignement des structures dans le code appelant et peut créer un code qui gère efficacement l’alignement.

Si vous venez d’implémenter memcpy2 tant que fonction de bibliothèque, il est difficile à reproduire. Vous pouvez obtenir une partie de la manière dont je divise la méthode en une petite et grande partie: la petite partie apparaît dans le fichier d’en-tête, vérifie la taille et appelle simplement la memcpy existante si la taille est petite ou des delegates à la bibliothèque. routine si c’est grand. Grâce à la magie de l’inline, vous pouvez vous rendre au même endroit que la mémoire memcpy .

Enfin, vous pouvez également essayer des astuces avec __builtin_constant_p ou ses équivalents pour gérer efficacement le petit cas connu.


1 Notez que je fais ici une distinction entre la “dissortingbution” des tailles – par exemple, vous pourriez dire _ uniformément répartie entre 8 et 24 octets – et la “prévisibilité” de la séquence réelle de tailles (par exemple, les tailles ont-elles un modèle prévisible)? La question de la prévisibilité est quelque peu subtile, car elle dépend de la mise en œuvre, car comme décrit ci-dessus, certaines implémentations sont insortingnsèquement plus prévisibles.

2 En particulier, environ 750 octets d’instructions dans clang et environ 600 octets dans gcc pour le corps seul, en plus de la table de recherche des sauts de 256 octets pour le corps du commutateur qui comportait 180 à 250 instructions (respectivement gcc et clang ). Lien Godbolt.

3 Fondamentalement, 200 UOP fusionnés sur une taille de cache uop effective de 1000 instructions. Bien que les x86 récents aient des tailles de cache uop d’environ 1 500 uops, vous ne pouvez pas les utiliser tous en dehors du remplissage extrêmement dédié de votre base de code en raison des règles d’atsortingbution de code à cache ressortingctives.

4 Les cas de commutation ont des longueurs compilées différentes, de sorte que le saut ne peut pas être calculé directement. Pour ce que cela vaut, cela aurait pu être fait différemment: ils auraient pu utiliser une valeur de 16 bits dans la table de recherche au prix de ne pas utiliser de source de mémoire pour le jmp , ce qui jmp sa taille de 75%.

5 Contrairement à la prévision conditionnelle de twig, qui a un taux de prédiction typique dans le pire des cas d’environ 50% (pour les twigs totalement aléatoires), une twig indirecte difficile à prévoir peut facilement approcher les 100%, car vous ne lancez pas une pièce de monnaie. choisissant pour un ensemble presque infini de cibles de twig. Cela se produit dans le monde réel: si memcpy est utilisé pour copier de petites chaînes avec des longueurs uniformément réparties entre 0 et 30, le code du switch sera imprévisible ~ 97% du temps.

Bien sûr, des pénalités peuvent être imposées aux magasins mal alignés , mais elles sont généralement aussi petites et ont diminué.

7 Par exemple, une memcpy dans la stack, suivie d’une manipulation et d’une copie ailleurs, peuvent être totalement éliminées, déplaçant directement les données d’origine à leur emplacement final. Même des choses comme malloc suivi de memcpy peuvent être totalement éliminées.

Taking Benefits of The ERMSB

Please also consider using REP MOVSB for larger blocks.

As you know, since first Pentium CPU produced in 1993, Intel began to make simple commands faster and complex commands (like REP MOVSB) slower. So, REP MOVSB became very slow, and there was no more reason to use it. In 2013, Intel decided to revisit REP MOVSB. If the CPU has CPUID ERMSB (Enhanced REP MOVSB) bit, then REP MOVSB commands are executed differently than on older processors, and are supposed to be fast. On practice, it is only fast for large blocks, 256 bytes and larger, and only when certain conditions are met:

  • both the source and destination addresses have to be aligned to a 16-Byte boundary;
  • the source region should not overlap with the destination region;
  • the length has to be a multiple of 64 to produce higher performance;
  • the direction has to be forward (CLD).

See the Intel Manual on Optimization, section 3.7.6 Enhanced REP MOVSB and STOSB operation (ERMSB) http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf

Intel recommends using AVX for blocks smaller than 2048 bytes. For the larger blocks, Intel recommends using REP MOVSB. This is because high initial startup costs of REP MOVSB (about 35 cycles).

I have done speed tests, and for the blocks of than 2048 bytes and higher, the performance of REP MOVSB is unbeatable. However, for blocks smaller than 256 bytes, REP MOVSB is very slow, even slower than plain MOV RAX back and forth in a loop.

Please not that ERMSB only affects MOVSB, not MOVSD (MOVSQ), so MOVSB is little bit faster than MOVSD (MOVSQ).

So, you can use AVX for your memcpy() implementation, and if the block is larger than 2048 bytes and all the conditions are met, then call REP MOVSB – so your memcpy() implementation will be unbeatable.

Taking Benefits of The Out-of-Order Execution Engine

You can also read about The Out-of-Order Execution Engine in the “Intel® 64 and IA-32 Architectures Optimization Reference Manual” http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf section the 2.1.2, and take benefits of it.

For example, in Intel SkyLake processor series (launched in 2015), it has:

  • 4 execution units for the Arithmetic logic unit (ALU) (add, and, cmp, or, test, xor, movzx, movsx, mov, (v)movdqu, (v)movdqa, (v)movap*, (v)movup),
  • 3 execution units for Vector ALU ( (v)pand, (v)por, (v)pxor, (v)movq, (v)movq, (v)movap*, (v)movup*, (v)andp*, (v)orp*, (v)paddb/w/d/q, (v)blendv*, (v)blendp*, (v)pblendd)

So we can occupy above units (3+4) in parallel if we use register-only operations. We cannot use 3+4 instructions in parallel for memory copy. We can use simultaneously maximum of up to two 32-bytes instructions to load from memory and one 32-bytes instructions to store from memory, and even if we are working with Level-1 cache.

Please see the Intel manual again to understand on how to do the fastest memcpy implementation: http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf

Section 2.2.2 (The Out-of-Order Engine of the Haswelll microarchitecture): “The Scheduler controls the dispatch of micro-ops onto the dispatch ports. There are eight dispatch ports to support the out-of-order execution core. Four of the eight ports provided execution resources for computational operations. The other 4 ports support memory operations of up to two 256-bit load and one 256-bit store operation in a cycle.”

Section 2.2.4 (Cache and Memory Subsystem) has the following note: “First level data cache supports two load micro-ops each cycle; each micro-op can fetch up to 32-bytes of data.”

Section 2.2.4.1 (Load and Store Operation Enhancements) has the following information: The L1 data cache can handle two 256-bit (32 bytes) load and one 256-bit (32 bytes) store operations each cycle. The unified L2 can service one cache line (64 bytes) each cycle. Additionally, there are 72 load buffers and 42 store buffers available to support micro-ops execution in-flight.

The other sections (2.3 and so on, dedicated to Sandy Bridge and other microarchitectures) basically reiterate the above information.

The section 2.3.4 (The Execution Core) gives additional details.

The scheduler can dispatch up to six micro-ops every cycle, one on each port. The following table summarizes which operations can be dispatched on which port.

  • Port 0: ALU, Shift, Mul, STTNI, Int-Div, 128b-Mov, Blend, 256b-Mov
  • Port 1: ALU, Fast LEA, Slow LEA, MUL, Shuf, Blend, 128bMov, Add, CVT
  • Port 2 & Port 3: Load_Addr, Store_addr
  • Port 4: Store_data
  • Port 5: ALU, Shift, Branch, Fast LEA, Shuf, Blend, 128b-Mov, 256b-Mov

The section 2.3.5.1 (Load and Store Operation Overview) may also be useful to understand on how to make fast memory copy, as well as the section 2.4.4.1 (Loads and Stores).

For the other processor architectures, it is again – two load units and one store unit. Table 2-4 (Cache Parameters of the Skylake Microarchitecture) has the following information:

Peak Bandwidth (bytes/cyc):

  • First Level Data Cache: 96 bytes (2x32B Load + 1*32B Store)
  • Second Level Cache: 64 bytes
  • Third Level Cache: 32 bytes.

I have also done speed tests on my Intel Core i5 6600 CPU (Skylake, 14nm, released in September 2015) with DDR4 memory, and this has confirmed the teory. For example, my test have shown that using generic 64-bit registers for memory copy, even many registers in parallel, degrades performance. Also, using just 2 XMM registers is enough – adding the 3rd doesn’t add performance.

If your CPU has AVX CPUID bit, you may take benefits of the large, 256-bit (32 byte) YMM registers to copy memory, to occupy two full load units. The AVX support was first introduced by Intel with the Sandy Bridge processors, shipping in Q1 2011 and later on by AMD with the Bulldozer processor shipping in Q3 2011.

 // first cycle vmovdqa ymm0, ymmword ptr [rcx+0] // load 1st 32-byte part using first load unit vmovdqa ymm1, ymmword ptr [rcx+20h] // load 2nd 32-byte part using second load unit // second cycle vmovdqa ymmword ptr [rdx+0], ymm0 // store 1st 32-byte part using the single store unit // third cycle vmovdqa ymmword ptr [rdx+20h], ymm1 ; store 2nd 32-byte part - using the single store unit (this instruction will require a separate cycle since there is only one store unit, and we cannot do two stores in a single cycle) add ecx, 40h // these instructions will be used by a different unit since they don't invoke load or store, so they won't require a new cycle add edx, 40h 

Also, there is speed benefit if you loop-unroll this code at least 8 times. As I wrote before, adding more registers besides ymm0 and ymm1 doesn’t increase performance, because there are just two load units and one store unit. Adding loops like “dec r9 jnz @@again” degrades the performance, but simple “add ecx/edx” does not.

Finally, if your CPU has AVX-512 extension, you can use 512-bit (64-byte) registers to copy memory:

 vmovdqu64 zmm0, [rcx+0] ; load 1st 64-byte part vmovdqu64 zmm1, [rcx+40h] ; load 2nd 64-byte part vmovdqu64 [rdx+0], zmm0 ; store 1st 64-byte part vmovdqu64 [rdx+40h], zmm1 ; store 2nd 64-byte part add rcx, 80h add rdx, 80h 

AVX-512 is supported by the following processors: Xeon Phi x200, released in 2016; Skylake EP/EX Xeon “Purley” (Xeon E5-26xx V5) processors (H2 2017); Cannonlake processors (H2 2017), Skylake-X processors – Core i9-7×××X, i7-7×××X, i5-7×××X – released on June 2017.

Please note that the memory have to be aligned on the size of the registers that you are using. If it is not, please use “unaligned” instructions: vmovdqu and moveups.