> vs> = dans le sorting à bulles provoque une différence de performance significative

Je suis juste tombé sur quelque chose. Au début, je pensais que cela pourrait être une erreur de prédiction de la twig, comme c’est le cas dans ce cas , mais je ne peux pas expliquer pourquoi la mauvaise prononciation des twigs devrait provoquer ce phénomène.

J’ai implémenté deux versions de Bubble Sort en Java et réalisé des tests de performance:

import java.util.Random; public class BubbleSortAnnomaly { public static void main(Ssortingng... args) { final int ARRAY_SIZE = Integer.parseInt(args[0]); final int LIMIT = Integer.parseInt(args[1]); final int RUNS = Integer.parseInt(args[2]); int[] a = new int[ARRAY_SIZE]; int[] b = new int[ARRAY_SIZE]; Random r = new Random(); for (int run = 0; RUNS > run; ++run) { for (int i = 0; i = 0; --i) { for (int j = 0; j  a[j + 1]) { swap(a, j, j + 1); ++counter; } } } return (counter); } public static int bubbleSortB(int[] a) { int counter = 0; for (int i = a.length - 1; i >= 0; --i) { for (int j = 0; j = a[j + 1]) { swap(a, j, j + 1); ++counter; } } } return (counter); } private static void swap(int[] a, int j, int i) { int h = a[i]; a[i] = a[j]; a[j] = h; } } 

Comme vous pouvez le voir, la seule différence entre ces deux méthodes de sorting est le > vs >= . Lorsque vous exécutez le programme avec java BubbleSortAnnomaly 50000 10 10 , vous pouvez vous attendre à ce que sortB soit plus lent que sortA car il doit exécuter plus de swap(...) . Mais j’ai obtenu la sortie suivante (ou similaire) sur trois machines différentes:

 Sorting with sortA: 4.214 seconds. It used 564960211 swaps. Sorting with sortB: 2.278 seconds. It used 1249750569 swaps. Sorting with sortA: 4.199 seconds. It used 563355818 swaps. Sorting with sortB: 2.254 seconds. It used 1249750348 swaps. Sorting with sortA: 4.189 seconds. It used 560825110 swaps. Sorting with sortB: 2.264 seconds. It used 1249749572 swaps. Sorting with sortA: 4.17 seconds. It used 561924561 swaps. Sorting with sortB: 2.256 seconds. It used 1249749766 swaps. Sorting with sortA: 4.198 seconds. It used 562613693 swaps. Sorting with sortB: 2.266 seconds. It used 1249749880 swaps. Sorting with sortA: 4.19 seconds. It used 561658723 swaps. Sorting with sortB: 2.281 seconds. It used 1249751070 swaps. Sorting with sortA: 4.193 seconds. It used 564986461 swaps. Sorting with sortB: 2.266 seconds. It used 1249749681 swaps. Sorting with sortA: 4.203 seconds. It used 562526980 swaps. Sorting with sortB: 2.27 seconds. It used 1249749609 swaps. Sorting with sortA: 4.176 seconds. It used 561070571 swaps. Sorting with sortB: 2.241 seconds. It used 1249749831 swaps. Sorting with sortA: 4.191 seconds. It used 559883210 swaps. Sorting with sortB: 2.257 seconds. It used 1249749371 swaps. 

Lorsque vous définissez le paramètre de LIMIT sur, par exemple, 50000 ( java BubbleSortAnnomaly 50000 50000 10 ), vous obtenez les résultats attendus:

 Sorting with sortA: 3.983 seconds. It used 625941897 swaps. Sorting with sortB: 4.658 seconds. It used 789391382 swaps. 

J’ai porté le programme en C ++ pour déterminer si ce problème est spécifique à Java. Voici le code C ++.

 #include  #include  #include  #ifndef ARRAY_SIZE #define ARRAY_SIZE 50000 #endif #ifndef LIMIT #define LIMIT 10 #endif #ifndef RUNS #define RUNS 10 #endif void swap(int * a, int i, int j) { int h = a[i]; a[i] = a[j]; a[j] = h; } int bubbleSortA(int * a) { const int LAST = ARRAY_SIZE - 1; int counter = 0; for (int i = LAST; 0 < i; --i) { for (int j = 0; j  a[next]) { swap(a, j, next); ++counter; } } } return (counter); } int bubbleSortB(int * a) { const int LAST = ARRAY_SIZE - 1; int counter = 0; for (int i = LAST; 0 < i; --i) { for (int j = 0; j = a[next]) { swap(a, j, next); ++counter; } } } return (counter); } int main() { int * a = (int *) malloc(ARRAY_SIZE * sizeof(int)); int * b = (int *) malloc(ARRAY_SIZE * sizeof(int)); for (int run = 0; RUNS > run; ++run) { for (int idx = 0; ARRAY_SIZE > idx; ++idx) { a[idx] = std::rand() % LIMIT; b[idx] = a[idx]; } std::cout << "Sorting with sortA: "; double start = omp_get_wtime(); int swaps = bubbleSortA(a); std::cout << (omp_get_wtime() - start) << " seconds. It used " << swaps << " swaps." << std::endl; std::cout << "Sorting with sortB: "; start = omp_get_wtime(); swaps = bubbleSortB(b); std::cout << (omp_get_wtime() - start) << " seconds. It used " << swaps << " swaps." << std::endl; } free(a); free(b); return (0); } 

Ce programme montre le même comportement. Quelqu’un peut-il expliquer, que se passe-t-il exactement ici?

L’exécution sortB sortA puis de sortA ne modifie pas les résultats.

Je pense que cela peut être dû à la prédiction de twig. Si vous comptez le nombre de swaps par rapport au nombre d’itérations de sorting internes, vous trouvez:

Limite = 10

  • A = 560M swaps / 1250M boucles
  • B = 1250 M swaps / 1250 M de boucles (0,02% moins de swaps que de boucles)

Limite = 50000

  • A = 627M swaps / 1250M boucles
  • B = 850M swaps / 1250M boucles

Donc, dans le cas Limit == 10 , le swap est effectué à 99,98% du temps dans le type B, ce qui est évidemment favorable au prédicteur de twig. Dans le cas Limit == 50000 , le swap n’est frappé que 68% au hasard, donc le prédicteur de twig est moins avantageux.

Je pense que cela peut en effet s’expliquer par une mauvaise interprétation des agences.

Considérez, par exemple, LIMIT = 11, et sortB . Lors de la première itération de la boucle externe, il se heurtera très rapidement à l’un des éléments égal à 10. Il aura donc a[j]=10 , et donc certainement a[j] sera >=a[next] , comme il y a ne sont pas des éléments supérieurs à 10. Par conséquent, il effectuera un échange, puis effectuera une étape en j uniquement pour trouver qu’un a[j]=10 une fois de plus (la même valeur échangée). Donc, encore une fois, ce sera a[j]>=a[next] , et ainsi de suite. Toutes les comparaisons, sauf plusieurs au tout début, seront vraies. De même, il sera exécuté sur les prochaines itérations de la boucle externe.

Pas la même chose pour sortA . Cela commencera à peu près de la même manière, trébucher sur a[j]=10 , faire des swaps de manière similaire, mais seulement à un point où il trouve a[next]=10 aussi. La condition sera alors fausse et aucun échange ne sera effectué. Et ainsi de suite: à chaque fois qu’il tombe sur a[next]=10 , la condition est fausse et aucun échange n’est effectué. Par conséquent, cette condition est vraie 10 fois sur 11 (valeurs de a[next] de 0 à 9) et false dans 1 cas sur 11. Rien d’étrange que la prédiction de twig échoue.

En utilisant le code C ++ fourni (suppression du temps) avec la commande perf stat j’ai obtenu des résultats qui confirment la théorie du “brach-miss”.

Avec Limit = 10 , BubbleSortB profite fortement de la prédiction de twig (0.01% manqués) mais avec Limit = 50000 , la prédiction de la twig échoue encore plus (avec 15.65% manquants) que dans BubbleSortA (12.69% et 12.76% respectivement).

BubbleSortA Limit = 10:

 Performance counter stats for './bubbleA.out': 46670.947364 task-clock # 0.998 CPUs utilized 73 context-switches # 0.000 M/sec 28 CPU-migrations # 0.000 M/sec 379 page-faults # 0.000 M/sec 117,298,787,242 cycles # 2.513 GHz 117,471,719,598 instructions # 1.00 insns per cycle 25,104,504,912 twigs # 537.904 M/sec 3,185,376,029 branch-misses # 12.69% of all twigs 46.779031563 seconds time elapsed 

BubbleSortA Limit = 50000:

 Performance counter stats for './bubbleA.out': 46023.785539 task-clock # 0.998 CPUs utilized 59 context-switches # 0.000 M/sec 8 CPU-migrations # 0.000 M/sec 379 page-faults # 0.000 M/sec 118,261,821,200 cycles # 2.570 GHz 119,230,362,230 instructions # 1.01 insns per cycle 25,089,204,844 twigs # 545.136 M/sec 3,200,514,556 branch-misses # 12.76% of all twigs 46.126274884 seconds time elapsed 

BubbleSortB Limit = 10:

 Performance counter stats for './bubbleB.out': 26091.323705 task-clock # 0.998 CPUs utilized 28 context-switches # 0.000 M/sec 2 CPU-migrations # 0.000 M/sec 379 page-faults # 0.000 M/sec 64,822,368,062 cycles # 2.484 GHz 137,780,774,165 instructions # 2.13 insns per cycle 25,052,329,633 twigs # 960.179 M/sec 3,019,138 branch-misses # 0.01% of all twigs 26.149447493 seconds time elapsed 

BubbleSortB Limit = 50000:

 Performance counter stats for './bubbleB.out': 51644.210268 task-clock # 0.983 CPUs utilized 2,138 context-switches # 0.000 M/sec 69 CPU-migrations # 0.000 M/sec 378 page-faults # 0.000 M/sec 144,600,738,759 cycles # 2.800 GHz 124,273,104,207 instructions # 0.86 insns per cycle 25,104,320,436 twigs # 486.101 M/sec 3,929,572,460 branch-misses # 15.65% of all twigs 52.511233236 seconds time elapsed 

Edit 2: Cette réponse est probablement erronée dans la plupart des cas, plus faible quand je dis que tout ce qui précède est correct est toujours vrai, mais la partie inférieure n’est pas vraie pour la plupart des architectures de processeurs, voir les commentaires. Cependant, je dirai qu’il est théoriquement possible qu’il existe des JVM sur certains systèmes d’exploitation / architectures qui le font, mais que JVM est probablement mal implémenté ou qu’il s’agit d’une architecture étrange. En outre, cela est théoriquement possible dans la mesure où la plupart des choses imaginables sont théoriquement possibles, alors je prendrais la dernière partie avec un grain de sel.

D’abord, je ne suis pas sûr du C ++, mais je peux parler un peu de Java.

Voici un code,

 public class Example { public static boolean less(final int a, final int b) { return a < b; } public static boolean lessOrEqual(final int a, final int b) { return a <= b; } } 

javap -c dessus javap -c le bytecode

 public class Example { public Example(); Code: 0: aload_0 1: invokespecial #8 // Method java/lang/Object."":()V 4: return public static boolean less(int, int); Code: 0: iload_0 1: iload_1 2: if_icmpge 7 5: iconst_1 6: ireturn 7: iconst_0 8: ireturn public static boolean lessOrEqual(int, int); Code: 0: iload_0 1: iload_1 2: if_icmpgt 7 5: iconst_1 6: ireturn 7: iconst_0 8: ireturn } 

Vous remarquerez que la seule différence est if_icmpge (si comparé plus grand / égal) que if_icmpgt (si comparé plus grand que).

Tout ce qui précède est un fait, le rest est ma meilleure idée de la manière dont if_icmpge et if_icmpgt sont gérés sur la base d'un cours que j'ai suivi en langage assembleur. Pour obtenir une meilleure réponse, vous devez vérifier comment votre JVM les gère. Je suppose que C ++ se comstack également dans une opération similaire.

Edit: La documentation sur if_i est ici

La façon dont les ordinateurs comparent les nombres soustrait les uns des autres et vérifie si ce nombre est 0 ou non. Par conséquent, lorsque vous effectuez a < b si vous soustrayez b de a et voyez si le résultat est inférieur à 0 b - a < 0 ). Pour faire a < = b il faut faire une étape supplémentaire et soustraire 1 ( b - a - 1 < 0 ).

Normalement, cette différence est minuscule, mais ce n’est pas un code, c’est du sorting des bulles! O (n ^ 2) est le nombre moyen de fois que nous effectuons cette comparaison particulière car elle se trouve dans la boucle la plus interne.

Oui, cela peut avoir quelque chose à voir avec la prédiction de twig Je ne suis pas sûr, je ne suis pas un expert à ce sujet, mais je pense que cela peut aussi jouer un rôle non négligeable.