Pourquoi std :: fill (0) est-il plus lent que std :: fill (1)?

Question

J'ai observé sur un système qui std::fill sur un grand std::vector<int> était significativement et toujours plus lente lors de la définition d'une valeur constante 0 par rapport à une valeur constante 1 ou une valeur dynamique:

5,8 Gio/s vs 7,5 Gio/s

Cependant, les résultats sont différents pour les petites tailles de données, où fill(0) est plus rapide:

avec plus d'un fil, à 4 la taille des données GiB, fill(1) montre une pente plus élevée, mais atteint une beaucoup plus faible pic de fill(0) (51 GiB/s vs 90 GiB/s):

Cette soulève la question secondaire, pourquoi la bande passante maximale de fill(1) est tellement inférieure.

Le système de test pour cela était un CPU Intel Xeon double socket E5-2680 v3 réglé à 2,5 GHz (via /sys/cpufreq) avec 8x16 GiB DDR4-2133. J'ai testé avec GCC 6.1.0 (-O3) et le compilateur Intel 17.0.1 (-fast), les deux obtiennent des résultats identiques. GOMP_CPU_AFFINITY=0,12,1,13,2,14,3,15,4,16,5,17,6,18,7,19,8,20,9,21,10,22,11,23 a été défini. Strem/add/24 threads obtient 85 GiB/s sur le système.

J'ai été capable de reproduire cet effet sur un autre système de serveur Haswell à double socket, mais pas sur n'importe quelle autre architecture. Par exemple sur Sandy Bridge EP, les performances de la mémoire sont identiques, tandis que dans le cache fill(0) est beaucoup plus rapide.

Voici le code à reproduire:

#include <algorithm> 
#include <cstdlib> 
#include <iostream> 
#include <omp.h> 
#include <vector> 

using value = int; 
using vector = std::vector<value>; 

constexpr size_t write_size = 8ll * 1024 * 1024 * 1024; 
constexpr size_t max_data_size = 4ll * 1024 * 1024 * 1024; 

void __attribute__((noinline)) fill0(vector& v) { 
    std::fill(v.begin(), v.end(), 0); 
} 

void __attribute__((noinline)) fill1(vector& v) { 
    std::fill(v.begin(), v.end(), 1); 
} 

void bench(size_t data_size, int nthreads) { 
#pragma omp parallel num_threads(nthreads) 
    { 
     vector v(data_size/(sizeof(value) * nthreads)); 
     auto repeat = write_size/data_size; 
#pragma omp barrier 
     auto t0 = omp_get_wtime(); 
     for (auto r = 0; r < repeat; r++) 
      fill0(v); 
#pragma omp barrier 
     auto t1 = omp_get_wtime(); 
     for (auto r = 0; r < repeat; r++) 
      fill1(v); 
#pragma omp barrier 
     auto t2 = omp_get_wtime(); 
#pragma omp master 
     std::cout << data_size << ", " << nthreads << ", " << write_size/(t1 - t0) << ", " 
        << write_size/(t2 - t1) << "\n"; 
    } 
} 

int main(int argc, const char* argv[]) { 
    std::cout << "size,nthreads,fill0,fill1\n"; 
    for (size_t bytes = 1024; bytes <= max_data_size; bytes *= 2) { 
     bench(bytes, 1); 
    } 
    for (size_t bytes = 1024; bytes <= max_data_size; bytes *= 2) { 
     bench(bytes, omp_get_max_threads()); 
    } 
    for (int nthreads = 1; nthreads <= omp_get_max_threads(); nthreads++) { 
     bench(max_data_size, nthreads); 
    } 
} 

Les résultats présentés compilé avec g++ fillbench.cpp -O3 -o fillbench_gcc -fopenmp.

Answer 1

De votre question + le compilateur généré asm de votre réponse:

• fill(0) est un ERMSB rep stosb qui utilisera 256B stocke dans une boucle microcodée optimisée. (Fonctionne mieux si le tampon est aligné, probablement à au moins 32B ou peut-être 64B).

• fill(1) est une simple boucle de stockage de vecteur de 128 bits movaps. Un seul magasin peut exécuter par cycle d'horloge de base indépendamment de la largeur, jusqu'à 256b AVX. Ainsi, les magasins 128b ne peuvent remplir que la moitié de la bande passante d'écriture du cache L1D de Haswell. C'est pourquoi fill(0) est environ 2x plus rapide pour les tampons jusqu'à ~ 32kiB. Compiler avec -march=haswell ou -march=native pour corriger cela.

  Haswell peut à peine faire face à la surcharge de la boucle, mais il peut toujours fonctionner 1 magasin par horloge, même si elle n'est pas déroulée du tout.Mais avec 4 Uops de domaine fusionné par horloge, c'est beaucoup de remplissage prenant de l'espace dans la fenêtre hors service. Certains déroulements permettraient peut-être à TLB de commencer à se résoudre plus loin devant les magasins, car il y a plus de débit pour les adresses de magasin que pour les données de magasin. Le désassemblage pourrait aider à combler le reste de la différence entre ERMSB et cette boucle vectorielle pour les tampons qui s'inscrivent dans L1D. (Un commentaire sur la question dit que -march=native seulement aidé fill(1) pour L1.)

Notez que rep movsd (qui pourrait être utilisé pour mettre en œuvre fill(1) pour int éléments) effectuerez probablement les mêmes que rep stosb sur Haswell. Bien que seule la documentation officielle garantit seulement que ERMSB donne rep stosb rapide (mais pas rep stosd), actual CPUs that support ERMSB use similarly efficient microcode for rep stosd. Il y a un doute sur IvyBridge, où peut-être seulement b est rapide. Voir l'excellent ERMSB answer @ BeeOnRope pour les mises à jour à ce sujet.

gcc a quelques options de réglage x86 pour ops (chaîne like -mstringop-strategy=alg and -mmemset-strategy=strategy), mais IDK si l'un d'entre eux obtenir émette effectivement rep movsd pour fill(1). Probablement pas, puisque je suppose que le code commence comme une boucle, plutôt qu'un memset.

---

avec plus d'un fil, à 4 la taille des données GiB, remplissage (1) présente une pente plus élevée, mais atteint un pic beaucoup plus faible que remplissage (0) (51 GiB/s vs 90 GiB/s):

un magasin movaps normal à une ligne de cache froid déclenche une Read For Ownership (RFO). Une grande partie de la bande passante DRAM réelle est utilisée pour lire les lignes de cache de la mémoire lorsque movaps écrit les 16 premiers octets. Les magasins ERMSB utilisent un protocole no-RFO pour ses magasins, de sorte que les contrôleurs de mémoire écrivent uniquement. (Excepté pour les lectures diverses, comme les tables de pages si des pages manquent même dans le cache L3, et peut-être un manque de chargement dans les gestionnaires d'interruption ou autre). Que la différence entre les mémoires RFO normales et le protocole RFO-évitement utilisé par ERMSB a des inconvénients pour certaines plages de tailles de tampon sur les CPU serveur où il y a une latence élevée dans le cache uncore/L3. Voir aussi la réponse ERMSB liée pour plus d'informations sur RFO et non-RFO, et la latence élevée de l'uncore (L3/mémoire) dans les processeurs Intel à plusieurs cœurs étant un problème pour la bande passante à un seul cœur.

---

movntps (_mm_stream_ps()) stocke sont faiblement commandés, de sorte qu'ils peuvent contourner le cache et aller directement à la mémoire cache une ligne entière à la fois, sans jamais lire la ligne de cache en L1D. movntps évite les RFO, comme rep stos fait. (rep stos les magasins peuvent réorganiser les uns avec les autres, mais pas en dehors des limites de l'instruction.)

Vos résultats movntps dans votre réponse mise à jour sont surprenants.
Pour un seul thread avec des tampons volumineux, les résultats sont movnt >> RFO standard> ERMSB. Donc, c'est vraiment bizarre que les deux méthodes non-RFO soient sur les côtés opposés des anciens magasins, et que ERMSB est loin d'être optimale. Je n'ai pas d'explication pour le moment. (Les modifications sont les bienvenues avec une explication + une bonne preuve).

Comme nous nous y attendions, movnt permet à plusieurs threads d'atteindre une bande passante de stockage agrégée élevée, comme ERMSB. movnt va toujours directement dans les tampons de remplissage de ligne et ensuite dans la mémoire, donc c'est beaucoup plus lent pour les tailles de tampon qui tiennent dans le cache. Un vecteur 128b par horloge est suffisant pour saturer facilement la bande passante sans RFO d'un seul cœur en DRAM. Probablement vmovntps ymm (256b) est seulement un avantage mesurable sur vmovntps xmm (128b) lors de la mémorisation des résultats d'un calcul vectoriel AVX 256b lié au CPU (c'est-à-dire seulement quand il évite le déballage à 128b).

movnti bande passante est faible parce que le stockage en 4B morceaux goulots d'étranglement sur 1 magasin uop par horloge ajout de données dans les tampons de remplissage de ligne, et non pas sur l'envoi de ces tampons de ligne pleine vers la mémoire DRAM (jusqu'à ce que vous avez fils suffisantes pour saturer la bande passante de la mémoire).

---

@osgx affiché some interesting links in comments:

• Agner Guide d'optimisation de asm brouillard, tables d'instruction et guide microarch: http://agner.org/optimize/

• Guide d'optimisation Intel: http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf.

• NUMA Espionne: http://frankdenneman.nl/2016/07/11/numa-deep-dive-part-3-cache-coherency/

• https://software.intel.com/en-us/articles/intelr-memory-latency-checker
• Cache Coherence Protocol and Memory Performance of the Intel Haswell-EP Architecture

Voir aussi d'autres choses dans le wiki tag x86.

Answer 2

Je vais partager mes résultats préliminaires , dans l'espoir de encourager des réponses plus détaillées. J'ai juste senti que ce serait trop dans le cadre de la question elle-même.

Le compilateur optimisefill(0) à un interne memset. Il ne peut pas faire la même chose pour fill(1), puisque memset ne fonctionne que sur des octets.

Plus précisément, les deux glibcs ​​__memset_avx2 et __intel_avx_rep_memset sont mis en œuvre avec une seule instruction chaude:

rep stos %al,%es:(%rdi) 

Wheres la boucle manuelle compile jusqu'à une instruction 128 bits réelle:

add $0x1,%rax                          
add $0x10,%rdx                          
movaps %xmm0,-0x10(%rdx)                        
cmp %rax,%r8                           
ja  400f41 

Il est intéressant alors qu'il est une optimisation de modèle/en-tête pour implémenter std::fill via memset pour les types d'octets, mais dans ce cas c'est une optimisation du compilateur pour transformer la boucle réelle. Etrangement, pour un std::vector<char>, gcc commence à optimiser également fill(1).Le compilateur Intel ne le fait pas, malgré la spécification du modèle memset. Comme cela se produit uniquement lorsque le code fonctionne réellement en mémoire plutôt qu'en mémoire cache, il semble que l'architecture Haswell-EP ne parvienne pas à consolider efficacement les écritures à un seul octet.

Je voudrais apprécier toute autre information dans le problème et les détails de la micro-architecture connexes. En particulier, il n'est pas clair pour moi pourquoi cela se comporte si différemment pour quatre threads ou plus et pourquoi memset est tellement plus rapide dans le cache.

Mise à jour:

est ici un résultat en comparaison avec

• remplissage (1) qui utilise -march=native (AVX2 vmovdq %ymm0) - il fonctionne mieux en L1, mais similaire à la version movaps %xmm0 pour une autre mémoire les niveaux.
• Variantes de mémoires non temporelles de 32, 128 et 256 bits. Ils fonctionnent de manière cohérente avec la même performance indépendamment de la taille des données. Tous surpassent les autres variantes en mémoire, en particulier pour un petit nombre de threads. 128 bits et 256 bits fonctionnent exactement de la même manière, pour un faible nombre de threads, 32 bits sont nettement moins performants.

Pour < = 6 fils, vmovnt a un avantage de plus de 2x rep stos lors du fonctionnement dans la mémoire.

bande passante filetée simple:

bande passante totale en mémoire:

Voici le code utilisé pour les tests supplémentaires avec leurs chaudes boucles respectives:

void __attribute__ ((noinline)) fill1(vector& v) { 
    std::fill(v.begin(), v.end(), 1); 
} 
┌─→add $0x1,%rax 
│ vmovdq %ymm0,(%rdx) 
│ add $0x20,%rdx 
│ cmp %rdi,%rax 
└──jb  e0 


void __attribute__ ((noinline)) fill1_nt_si32(vector& v) { 
    for (auto& elem : v) { 
     _mm_stream_si32(&elem, 1); 
    } 
} 
┌─→movnti %ecx,(%rax) 
│ add $0x4,%rax 
│ cmp %rdx,%rax 
└──jne 18 


void __attribute__ ((noinline)) fill1_nt_si128(vector& v) { 
    assert((long)v.data() % 32 == 0); // alignment 
    const __m128i buf = _mm_set1_epi32(1); 
    size_t i; 
    int* data; 
    int* end4 = &v[v.size() - (v.size() % 4)]; 
    int* end = &v[v.size()]; 
    for (data = v.data(); data < end4; data += 4) { 
     _mm_stream_si128((__m128i*)data, buf); 
    } 
    for (; data < end; data++) { 
     *data = 1; 
    } 
} 
┌─→vmovnt %xmm0,(%rdx) 
│ add $0x10,%rdx 
│ cmp %rcx,%rdx 
└──jb  40 


void __attribute__ ((noinline)) fill1_nt_si256(vector& v) { 
    assert((long)v.data() % 32 == 0); // alignment 
    const __m256i buf = _mm256_set1_epi32(1); 
    size_t i; 
    int* data; 
    int* end8 = &v[v.size() - (v.size() % 8)]; 
    int* end = &v[v.size()]; 
    for (data = v.data(); data < end8; data += 8) { 
     _mm256_stream_si256((__m256i*)data, buf); 
    } 
    for (; data < end; data++) { 
     *data = 1; 
    } 
} 
┌─→vmovnt %ymm0,(%rdx) 
│ add $0x20,%rdx 
│ cmp %rcx,%rdx 
└──jb  40 

Note: J'ai dû faire un calcul manuel du pointeur afin de rendre les boucles si compactes. Sinon, il ferait l'indexation vectorielle dans la boucle, probablement en raison de la confusion intrinsèque de l'optimiseur.