Pourquoi est-il plus rapide de traiter un tableau trié qu'un tableau non trié?

Voici un morceau de code C ++ qui semble très particulier. Pour une raison étrange, trier les données miraculeusement rend le code presque six fois plus rapide.

 import java.util.Arrays; import java.util.Random; public class Main { public static void main(String[] args) { // Generate data int arraySize = 32768; int data[] = new int[arraySize]; Random rnd = new Random(0); for (int c = 0; c < arraySize; ++c) data[c] = rnd.nextInt() % 256; // !!! With this, the next loop runs faster Arrays.sort(data); // Test long start = System.nanoTime(); long sum = 0; for (int i = 0; i < 100000; ++i) { // Primary loop for (int c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } } System.out.println((System.nanoTime() - start) / 1000000000.0); System.out.println("sum = " + sum); } } 

Avec un résultat un peu similaire, mais moins extrême.


Ma première pensée a été que le tri amène les données dans le cache, mais je me suis dit à quel point c'était stupide, car le tableau venait d'être généré.

  • Ce qui se passe
  • Pourquoi le tableau trié est-il traité plus rapidement que le tableau non trié?
  • Le code résume certains termes indépendants et l'ordre n'a pas d'importance.
22512
27 июня '12 в 16:51 2012-06-27 16:51 GManNickG est programmé pour le 27 juin '12 à 4:51 2012-06-27 16:51
@ 26 réponses

Vous êtes victime d'une déviation par rapport aux branches .


Qu'est-ce que la prédiction de branche?

Considérez le carrefour ferroviaire:

2019

Prédiction de branches.

Avec un tableau trié, la condition data[c] >= 128 est la première valeur false pour la chaîne de valeur, puis devient true pour toutes les valeurs suivantes. C'est facile à prédire. Avec un tableau non trié, vous payez les coûts de branchement.

3815
27 июня '12 в 16:54 2012-06-27 16:54 la réponse est donnée par Daniel Fischer le 27 juin 12 à 16:54 . 2012-06-27 16:54

Si les performances s’améliorent considérablement lors du tri des données, c’est que la pénalité pour la prédiction de branche est éliminée, comme l’ a parfaitement expliqué Mysticial .

Maintenant, si on regarde le code

 if (data[c] >= 128) sum += data[c]; 

nous pouvons trouver que la signification de cette particularité if... else... branche consiste à ajouter quelque chose lorsque la condition est remplie. Ce type de branche peut être facilement converti en un opérateur conditionnel , qui sera compilé en une instruction de mouvement conditionnel: cmovl , dans le système x86 . La branche et, par conséquent, la pénalité potentielle pour prédire la branche sont supprimés.

En C , donc, C++ , l'opérateur qui sera directement (sans aucune optimisation) compilé dans une instruction de mouvement conditionnel en x86 est un opérateur ternaire ...?... :... ...?... :... Par conséquent, nous réécrivons l'instruction ci-dessus pour qu'elle soit équivalente:

 sum += data[c] >=128 ? data[c] : 0; 

En maintenant la lisibilité, nous pouvons vérifier le facteur d'accélération.

Pour le test de référence du mode de version du processeur Intel Core i7 - 2600K à 3,4 GHz et Visual Studio 2010 (format copié à partir de Mysticial):

x86

 // Branch - Random seconds = 8.885 // Branch - Sorted seconds = 1.528 // Branchless - Random seconds = 3.716 // Branchless - Sorted seconds = 3.71 

x64

 // Branch - Random seconds = 11.302 // Branch - Sorted seconds = 1.830 // Branchless - Random seconds = 2.736 // Branchless - Sorted seconds = 2.737 

Le résultat est fiable dans plusieurs tests. Nous obtenons une accélération significative lorsque le résultat d’une ramification est imprévisible, mais nous souffrons un peu lorsque cela est prévisible. En fait, lorsque vous utilisez un déplacement conditionnel, les performances restent les mêmes quel que soit le modèle de données.

Voyons maintenant de plus près en explorant la construction x86 générée. Pour simplifier, nous utilisons deux fonctions max1 et max2 .

max1 utilise la branche conditionnelle, if... else... :

 int max1(int a, int b) { if (a > b) return a; else return b; } 

max2 utilise l'opérateur ternaire ...?... :... ...?... :... : ...?... :... :

 int max2(int a, int b) { return a > b ? a : b; } 

Sur l'ordinateur x86-64, le GCC -S construit un assemblage ci-dessous.

 :max1 movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl -4(%rbp), %eax cmpl -8(%rbp), %eax jle .L2 movl -4(%rbp), %eax movl %eax, -12(%rbp) jmp .L4 .L2: movl -8(%rbp), %eax movl %eax, -12(%rbp) .L4: movl -12(%rbp), %eax leave ret :max2 movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl -4(%rbp), %eax cmpl %eax, -8(%rbp) cmovge -8(%rbp), %eax leave ret 

max2 utilise beaucoup moins de code en raison de l'utilisation de l'instruction cmovge . Mais le gain réel est que max2 n'inclut pas les transitions sur max2 , jmp , ce qui peut conduire à des performances max2 significatives si le résultat prévu est max2 .

Alors, pourquoi le déménagement conditionnel fonctionne-t-il mieux?

Dans un processeur x86 typique, l'exécution des x86 est divisée en plusieurs étapes. Grosso modo, nous avons différents matériels pour différentes étapes. Par conséquent, il n'est pas nécessaire d'attendre la fin d'une instruction pour en commencer une nouvelle. Ceci s'appelle pipelining .

Dans le cas de la création de branches, l'instruction suivante est déterminée par la précédente, nous ne pouvons donc pas effectuer de traitement en pipeline. Nous devons attendre ou prédire.

Dans le cas d'un déplacement conditionnel, l'exécution de la commande de déplacement conditionnel est divisée en plusieurs étapes, mais les étapes précédentes, telles que Fetch et Decode , ne dépendent pas du résultat de l'instruction précédente. seules les étapes finales nécessitent un résultat. Nous attendons donc une partie du temps d'exécution d'une instruction. C'est pourquoi la version avec déplacement conditionnel est plus lente que la branche lorsque la prédiction est facile.

Le livre Computer Systems: Une perspective pour un programmeur, deuxième édition, explique cela en détail. Vous pouvez consulter la section 3.6.6 pour les instructions de mouvement conditionnel, l'intégralité du chapitre 4 pour l'architecture du processeur et la section 5.11.2 pour le traitement spécial des pénalités de prévision et des prédictions erronées.

Parfois, certains compilateurs modernes peuvent optimiser notre code pour générer de meilleures performances, parfois non (ce code utilise son propre compilateur Visual Studio). Connaître la différence de performance entre ramification et mouvement conditionnel, lorsque cela est imprévisible, peut nous aider à écrire du code avec de meilleures performances lorsque le script devient si complexe que le compilateur ne peut pas les optimiser automatiquement.

3064
28 июня '12 в 5:14 2012-06-28 05:14 la réponse est donnée par WiSaGaN le 28 juin 2012 à 5 h 14 du matin. 2012-06-28 05:14

Si vous souhaitez encore plus d'optimisations avec ce code, tenez compte des points suivants:

A partir du cycle initial:

 for (unsigned i = 0; i < 100000; ++i) { for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) sum += data[j]; } } 

Avec la permutation de cycle, nous pouvons changer ce cycle en toute sécurité pour:

 for (unsigned j = 0; j < arraySize; ++j) { for (unsigned i = 0; i < 100000; ++i) { if (data[j] >= 128) sum += data[j]; } } 

Ensuite, vous pouvez voir que la condition if est constante pendant l'exécution de la boucle i , vous pouvez donc retirer if :

 for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) { for (unsigned i = 0; i < 100000; ++i) { sum += data[j]; } } } 

Ensuite, vous verrez que la boucle interne peut être réduite en une seule expression, en supposant que le modèle à virgule flottante le permette (par exemple, / fp: fast)

 for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) { sum += data[j] * 100000; } } 

C'est 100 000 fois plus rapide qu'avant.

2105
03 июля '12 в 5:25 2012-07-03 05:25 la réponse est donnée au vulcan raven le 3 juillet 2012 à 05h25. 2012-07-03 05:25

Certains d’entre nous s’intéresseront sans aucun doute aux moyens d’identifier le code problématique pour un processeur prédicteur de CPU. L'outil Valgrind cachegrind a une syntaxe de branche de prédicteur de branche qui est activée à l'aide de l' --branch-sim=yes . En utilisant les exemples de cette question, le nombre de boucles externes, réduit à 10 000 et compilé avec g++ , donne les résultats suivants:

Trier par:

 ==32551== Branches: 656,645,130 ( 656,609,208 cond + 35,922 ind) ==32551== Mispredicts: 169,556 ( 169,095 cond + 461 ind) ==32551== Mispred rate: 0.0% ( 0.0% + 1.2% ) 

Non trié:

 ==32555== Branches: 655,996,082 ( 655,960,160 cond + 35,922 ind) ==32555== Mispredicts: 164,073,152 ( 164,072,692 cond + 460 ind) ==32555== Mispred rate: 25.0% ( 25.0% + 1.2% ) 

En ce qui concerne la sortie linéaire créée par cg_annotate , nous voyons pour le cycle en question:

Trier par:

  Bc Bcm Bi Bim 10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i) . . . . { . . . . // primary loop 327,690,000 10,016 0 0 for (unsigned c = 0; c < arraySize; ++c) . . . . { 327,680,000 10,006 0 0 if (data[c] >= 128) 0 0 0 0 sum += data[c]; . . . . } . . . . } 

Non trié:

  Bc Bcm Bi Bim 10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i) . . . . { . . . . // primary loop 327,690,000 10,038 0 0 for (unsigned c = 0; c < arraySize; ++c) . . . . { 327,680,000 164,050,007 0 0 if (data[c] >= 128) 0 0 0 0 sum += data[c]; . . . . } . . . . } 

Cela vous permet d'identifier facilement la ligne Bcm problème - dans une version non triée, la ligne if (data[c] >= 128) entraîne Bcm branches conditionnelles prédites de façon incorrecte ( Bcm ) dans le modèle de prédicteur de branche Cachegrind, alors qu'elle ne génère que 10 006 entrées triées. version.


Sous Linux, vous pouvez également utiliser un sous-système de compteur de performance pour effectuer la même tâche, mais avec ses propres performances en utilisant des compteurs de CPU.

 perf stat ./sumtest_sorted 

Trier par:

  Performance counter stats for './sumtest_sorted': 11808.095776 task-clock # 0.998 CPUs utilized 1,062 context-switches # 0.090 K/sec 14 CPU-migrations # 0.001 K/sec 337 page-faults # 0.029 K/sec 26,487,882,764 cycles # 2.243 GHz 41,025,654,322 instructions # 1.55 insns per cycle 6,558,871,379 branches # 555.455 M/sec 567,204 branch-misses # 0.01% of all branches 11.827228330 seconds time elapsed 

Non trié:

  Performance counter stats for './sumtest_unsorted': 28877.954344 task-clock # 0.998 CPUs utilized 2,584 context-switches # 0.089 K/sec 18 CPU-migrations # 0.001 K/sec 335 page-faults # 0.012 K/sec 65,076,127,595 cycles # 2.253 GHz 41,032,528,741 instructions # 0.63 insns per cycle 6,560,579,013 branches # 227.183 M/sec 1,646,394,749 branch-misses # 25.10% of all branches 28.935500947 seconds time elapsed 

Il peut également créer des annotations de code source avec désassemblage.

 perf record -e branch-misses ./sumtest_unsorted perf annotate -d sumtest_unsorted 
  Percent | Source code  Disassembly of sumtest_unsorted ------------------------------------------------ ... : sum += data[c]; 0.00 : 400a1a: mov -0x14(%rbp),%eax 39.97 : 400a1d: mov %eax,%eax 5.31 : 400a1f: mov -0x20040(%rbp,%rax,4),%eax 4.60 : 400a26: cltq 0.00 : 400a28: add %rax,-0x30(%rbp) ... 

Pour plus de détails, voir le manuel de performance .

1758
12 окт. réponse donnée caf 12 oct. 2012-10-12 08:53 '12 à 8:53 2012-10-12 08:53

Je viens de lire cette question et ses réponses, et j’ai le sentiment que la réponse manque.

Le moyen habituel pour éliminer la prédiction de branche, qui me semblait fonctionner particulièrement bien dans les >

Cette approche fonctionne en général si:

  1. c'est une petite table et sera probablement mis en cache dans le processeur, et
  2. Vous travaillez dans une boucle plutôt étroite et / ou le processeur peut précharger les données.

Contexte et pourquoi

Du point de vue du processeur, votre mémoire est lente. Pour compenser la différence de vitesse, deux caches (cache L1 / L2) sont intégrés à votre processeur. Alors, imaginez que vous faites de bons calculs et découvrez que vous avez besoin d’un morceau de mémoire. Le processeur effectue l'opération de chargement et charge une partie de la mémoire dans le cache, puis utilise le cache pour effectuer les calculs restants. Puisque la mémoire est relativement lente, cette «charge» ralentira votre programme.

Comme la prédiction de branche, elle a été optimisée dans les processeurs Pentium: le processeur prédit qu'il doit charger certaines données et tente de les charger dans le cache avant que l'opération ne soit réellement mise en cache. Comme nous l’avons déjà vu, la prédiction de branche est parfois terriblement fausse - dans le pire des cas, vous devez revenir en arrière et attendre réellement une charge de mémoire qui durera à jamais (en d’ autres termes: une prédiction infructueuse est mauvaise, la charge de mémoire après un échec de prédiction de branche est terrible! ).

Heureusement pour nous, si le schéma d'accès à la mémoire est prévisible, le processeur le chargera dans son cache rapide, et tout va bien.

La première chose que nous devons savoir, c'est qu'il y a peu? Bien qu'une taille plus petite soit généralement préférable, la règle empirique consiste à s'en tenir aux tables de recherche <= 4096 octets. En tant que limite supérieure: si votre table de référence est supérieure à 64 Ko, elle devrait probablement être révisée.

Construire la table

Nous avons donc découvert que nous pouvions créer une petite table. La prochaine chose à faire est de remplacer la fonction de recherche. Les fonctions de recherche sont généralement de petites fonctions qui utilisent plusieurs opérations entières de base (et, ou, xor, shift, ajouter, supprimer et éventuellement une multiplication). Vous voulez que votre saisie soit traduite en recherchant une sorte de "clé unique" dans votre tableau, qui vous donne simplement la réponse à tout le travail que vous vouliez qu'elle fasse.

Dans ce cas:> = 128 signifie que nous pouvons enregistrer la valeur, <128 signifie que nous nous en débarrasserons. La façon la plus simple de faire est d'utiliser 'AND': si nous le sauvegardons, nous le faisons avec 7FFFFFFF; если мы хотим избавиться от него, мы И это с 0. Отметим также, что 128 - это степень 2 - так что мы можем пойти дальше и составить таблицу из 32768/128 целых чисел и заполнить ее одним нулем и большим количеством 7FFFFFFFF годов.

Управляемые языки