Pourquoi le traitement d'un tableau trié plus rapide que le traitement d'un tableau non-trié?
Voici un morceau de code C++ qui montre une partie très particulière de comportement. Pour une raison étrange, le tri des données miraculeusement rend le code près de six fois plus rapide:
#include <algorithm>
#include <ctime>
#include <iostream>
int main()
{
//Generate data
const unsigned arraySize = 32768;
int data[arraySize];
for (unsigned c = 0; c < arraySize; ++c)
data[c] = std::rand() % 256;
//!!! With this, the next loop runs faster.
std::sort(data, data + arraySize);
//Test
clock_t start = clock();
long long sum = 0;
for (unsigned i = 0; i < 100000; ++i)
{
//Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}
double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << std::endl;
std::cout << "sum = " << sum << std::endl;
}- Sans
std::sort(data, data + arraySize);, le code s'exécute dans 11.54 secondes. - Avec les données triées, le code s'exécute dans 1.93 secondes.
Au départ, j'ai pensé que cela pourrait être juste une langue ou le compilateur anomalie, j'ai donc essayé de Java:
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 semblable, mais moins extrême résultat.
Ma première pensée a été que le tri regroupe les données dans le cache, mais ensuite j'ai pensé comment stupide que c'était parce que le tableau a été qui vient d'être généré.
- Ce qui se passe?
- Pourquoi le traitement d'un tableau trié plus rapide que le traitement d'un tableau non-trié? Le code est en résumant certains indépendants termes, l'ordre n'a plus d'importance.
- Juste pour le record. Sur Windows / VS2017 / i7-6700K 4GHz il n'y a PAS de différence entre les deux versions. Il prend 0,6 s pour les deux cas. Si le nombre d'itérations de la boucle externe est augmenté de 10 fois le temps d'exécution augmente de 10 fois trop à 6s dans les deux cas.
- un compilateur qui utilise un
cmovou d'autres dépourvu de branches de mise en œuvre (comme auto-vectorisation avecpcmpgtd) auront des performances pas de données dépend de la CPU. Mais si c'est le branchu, il sera tri-dépendant à un CPU avec de l'exécution spéculative. (Même à haute performance dans l'ordre Cpu usage de la branche de prédiction pour éviter d'extraction/décoder des bulles sur les prises de branches; la miss peine est plus petite). - Oups... re: Effondrement et le Spectre
- a-t-elle quelque chose à voir avec les deux? Je n'ai pas lu beaucoup sur les deux
- deux de ces failles de sécurité de rentrer dans une large catégorie de vulnérabilités classés comme “direction de la cible d'injection” attaques
- Il a essayé avec 200M de tableau sur la JVM hotspot 1.8. Pas de différence pour triés et non triés. Toutes les explications?
- Sur le dessus de ma tête: 1) La JVM peut-être finalement assez intelligent pour utiliser conditionnelle se déplace. 2) Le code est liés à la mémoire. 200 m est trop grand pour tenir dans le cache du PROCESSEUR. Donc, la performance peut être un goulot d'étranglement par la bande passante de la mémoire au lieu de ramification.
- 2). Je pensais que la prédiction de la table assure le suivi des patrons(indépendamment des variables réelles qui ont été vérifiés pour ce motif) et de changer la prédiction de la sortie en fonction de l'histoire. Pourriez-vous me donner une raison, pourquoi un super grand tableau ne serait pas bénéficier de direction de la prévision?
- Il le fait, mais quand le tableau est très grande, d'autant plus un facteur probable entre dans le jeu - la bande passante mémoire. La mémoire est ce n'est pas plat. Accès à la mémoire est très lent, et il ya une quantité limitée de la bande passante. De sur-simplifier les choses, il y a une limite au nombre d'octets qui peuvent être transférés entre la CPU et de la mémoire en un montant fixe de temps. Code Simple comme celui de cette question sera probablement frappé de cette limite, même si elle est ralentie par mispredictions. Ce n'est pas le cas avec un tableau de 32768 (128 KO) car il s'inscrit dans le cache L2 du PROCESSEUR.
- Il y a une nouvelle faille de sécurité a appelé BranchScope: cs.ucr.edu/~nael/pubs/asplos18.pdf
- Pour l'enregistrement de vos données n'ont pas besoin d'être triés, seulement partitionné qui est beaucoup plus rapide pour l'opération.
- Une autre observation est que vous n'avez pas besoin de trier le tableau, mais vous avez juste besoin de la partition avec la valeur 128. Le tri est n*log(n), alors que le partitionnement est seulement linéaire. Fondamentalement, c'est juste une exécution du tri rapide étape de partitionnement avec le pivot choisi à 128. Malheureusement, en C++ il y a juste nth_element fonction de partition en position, et non par valeur.
- Qu'en est std::partition()?
- En effet, std::la partition est la réponse correcte. Merci
- Est-il une explication pour pourquoi il faut le même temps, en dépit de la direction de la prévision encore utilisé?
- FWIW: Le développeur moyen ne jamais avoir d'expérience avec de très uniques matériel de questions de ce genre. Direction de la prévision n'est pas encore connu pour le développeur moyen.
- Sur Linux avec un processeur Intel i3-7020U (4) @ 2.3 GHz, le speed-up est tout le contraire quand il s'agit de la langue. Le temps d'exécution pour le C++ permet de réduire de 29.7285 à 10.3184 (près de 3 fois). Mais quand j'utilise Java, il va de 13.3513 à 3.2957 (près de 4 fois).
- Pouvez-vous en fournir des preuves? Ce banc de marque, montre une très grande différence.
Vous devez vous connecter pour publier un commentaire.
Vous êtes une victime de la direction de la prévision fail.
Ce qui est de la Branche de Prédiction?
Envisager un chemin de fer de jonction:
Image par Mecanismo, via Wikimedia Commons. Utilisé sous la CC-By-SA 3.0 la licence.
Maintenant, pour les besoins de la discussion, supposons que c'est dans les années 1800 - avant de longue distance ou de communication radio.
Vous êtes l'exploitant d'un carrefour et que vous entendiez un train qui s'en vient. Vous n'avez aucune idée de la façon dont il est censé aller. Vous arrêter le train à demander au conducteur quelle direction ils veulent. Et puis vous réglez le commutateur de manière appropriée.
Trains sont lourds et ont beaucoup d'inertie. Donc, ils prennent une éternité à démarrer et à ralentir.
Est-il un meilleur moyen? - Vous deviner quelle direction le train va aller!
Si vous devinez juste à chaque fois, le train n'aurez jamais à vous arrêter.
Si vous devinez mal trop souvent, le train va passer beaucoup de temps à l'arrêt, de la sauvegarde et de redémarrer.
Envisager un if: Au niveau du processeur, c'est une branche de l'instruction:
Vous êtes un processeur et vous voyez une branche. Vous n'avez aucune idée de la façon dont il va. Que faites-vous? Vous suspendre l'exécution et attendre jusqu'à ce que les instructions précédentes sont complètes. Puis vous continuez sur le chemin d'accès correct.
Les processeurs modernes sont complexes et ont de longs pipelines. Donc, ils prennent une éternité à se "réchauffer" et de "slow down".
Est-il un meilleur moyen? - Vous deviner quelle direction la direction va aller!
Si vous devinez juste à chaque fois, l'exécution n'aura jamais à s'arrêter.
Si vous devinez mal trop souvent, vous passez beaucoup de temps de blocage, la restauration et la remise en marche.
C'est la direction de la prévision. J'avoue que c'est pas la meilleure analogie depuis le train pourrait juste le signal de la direction avec un drapeau. Mais dans les ordinateurs, le processeur ne sais pas de quelle direction une branche ira jusqu'au dernier moment.
Alors, comment voulez-vous stratégiquement deviner à minimiser le nombre de fois que le train doit sauvegarder et aller vers le bas un autre chemin? Vous regardez l'histoire du passé! Si le train va de gauche à 99% du temps, alors vous devinez gauche. Si elle alterne, alors vous alternez vos suppositions. Si il va dans un sens chaque fois, trois fois, vous devinez la même...
En d'autres termes, vous essayez d'identifier un modèle et de le suivre. C'est plus ou moins comment branche prédicteurs de travail.
La plupart des applications ont bien comportés branches. À la pointe de la branche prédicteurs généralement atteindre >90% de taux de réussite. Mais lorsqu'ils sont confrontés à des branches avec aucun des modèles reconnaissables, de la direction générale, les indicateurs sont pratiquement inutile.
Pour en savoir plus: Branche"prédicteur" de l'article sur Wikipédia.
Comme évoqué à partir de ci-dessus, le coupable est-ce si-déclaration:
Avis que les données sont réparties uniformément entre 0 et 255. Lorsque les données sont triées, environ la première moitié de la itérations n'entrerez pas dans le if. Après cela, ils seront tous d'entrer dans le if.
C'est très sympathique à la direction générale prédicteur depuis la branche consécutivement va dans la même direction à plusieurs reprises. Même un simple effet de saturer compteur de prédire correctement la branche, sauf pour les quelques itérations après il passe en direction.
Rapide de visualisation:
Toutefois, lorsque les données sont complètement aléatoires, la direction générale prédicteur est rendue inutile, car il ne peut pas prédire des données aléatoires. Ainsi, il sera probablement autour de 50% les erreurs de prédiction (pas mieux que l'estimation aléatoire).
Donc ce qui peut être fait?
Si le compilateur n'est pas capable d'optimiser la branche dans un conditionnelle déplacer, vous pouvez essayer certains des hacks si vous êtes prêt à sacrifier la lisibilité de la performance.
Remplacer:
avec:
Ceci élimine la direction générale et le remplace par certaines opérations bit à bit.
(à Noter que ce hack n'est pas strictement équivalent à l'original si l'instruction. Mais dans ce cas, c'est valable pour toutes les valeurs d'entrée de
data[].)De référence: Core i7 920 @ 3.5 GHz
De C++ de Visual Studio 2010 - x64 Version
Java NetBeans 7.1.1 JDK 7 - x64
Observations:
Une règle générale est d'éviter de données dépendant de la ramification de la critique, des boucles (comme dans cet exemple).
Mise à jour:
GCC 4.6.1 avec
-O3ou-ftree-vectorizesur x64 est capable de générer un conditionnel déplacer. Donc, il n'y a pas de différence entre l'triés et non triés de données - les deux sont rapides.VC++ 2010 est incapable de générer conditionnelle se déplace pour cette branche, même sous
/Ox.Le Compilateur Intel C++ (CPI) 11 est-ce que quelque chose de miraculeux. Il échangeurs les deux boucles, et ainsi de levage à l'imprévisible de la branche de la boucle externe. Ainsi, non seulement est immunisé contre la mispredictions, il est aussi deux fois plus rapide que ce que VC++ et GCC peut générer! En d'autres termes, la CPI a pris avantage de l'essai en boucle à la défaite de l'indice de référence...
Si vous donnez le compilateur Intel le sans branches code, il les a tout simplement droit vectorizes... et est tout aussi rapide comme la branche (avec la boucle de l'échangeur).
Cela montre que, même à maturité les compilateurs modernes peuvent varier énormément dans leur capacité à optimiser le code...
1dans ou hors de le bit de signe d'un entier signé n'est plus autorisée.private int sumIfGreaterThan128(int curSum, int value). Le compilateur JIT sera inline lors de l'exécution de toute façon. Je suppose que dans d'autres langues, il y a l'égalité des optimisations disponibles.int t = (data[c] - 128) >> 31; sum += ~t & data[c];pour remplacer l'original, si la condition ci-dessus?-ftree-loop-distributionet-ftree-loop-distribute-patterns), déplacer des sections invariantes (par défaut), déplacer des conditions d'invariant de la boucle (avec-funswitch-loops, mais entraîne la duplication des efforts), de convertir conditionnelle sauts conditionnels magasins ou les supprimer (-ftree-loop-if-convertet-ftree-loop-if-convert-stores). Malheureusement, beaucoup de ces options sont dangereux effets secondaires, et seulement faire une bonne amélioration très naïvement code écrit.cdqetmovlpdqui sont normalement utilisés pour les opérations à virgule flottante.sum += data[i] > 128 ? data[i] : 0for (register unsigned i = 0; i < 100000; ++i) { // Primary loop for (register unsigned c = 0; c < arraySize; ++c) { register int t=(data[c]<<25)>>31; sum += ~t & data[c]; } }identify a pattern and follow itcela semble plus de l'intelligence artificielle. Donc, il est sûr de dire que les compilateurs modernes sont équipées avec des algorithmes d'IA pour la direction de la prévision?halt execution and wait until the previous instructions are completequi me semble de plusieurs threads. N'PROCESSEUR interne des sauts de blocs de code dans les threads? (D'un ton commentaire mentionne égalementprocessor is executing many instructions at the same time). Si oui, quel est le rôle de compilateur jouer?if( rand.nextInt(100) < 50 )et correctement prédit quelque chose comme 99% du temps.sum += ~((data[c] - 128) >> 31) & data[c];?int t = (data[c] - 128) >> 31; sum += ~t & data[c];estchar t = data[c] >> 7 ; /* Truncating the 7 bits (equivalent to data[c] >=128 ) */ sum += -t & data[c]; /* -t will be equivalent to -1 if data[c] >= 128*/.int t = (data[c] - 128) >> 31;a mise en œuvre, les comportements définis:data[c]ainttype, de sortedata[c] - 128sera négatif pour les valeurs inférieures à 128. Droit de transfert d'une valeur négative est mise en œuvre, les comportements définis. Vous pouvez corriger cela pour 2 en complément des architectures avec une expression simple:sum += -(data[c] >= 128) & data[c];pour laquelle de nombreux compilateurs produire du code sans sauts. Sinon, compte tenu de la gamme dedata[c]:sum += -(data[c] >> 7) & data[c];int. Ça fait un moment, mais j'ai probablement ne pas utiliser une solution avec une comparaison car j'ai eu des expériences avec des compilateurs de générer des branches pourbool -> intconversions. Vous aussi vous ne pouvez pas le faire en Java. De toute façon, c'était il y a 5 ans. Je fais rarement ces hacks plus depuis que je préfère le SIMD intrinsèque de la route.sum += data[c] * (data[c] >= 128);. Il est mieux que le posté réponse, même dans les unoptimized construit (dans optimisé construit, même la version naïve est plus rapide que le posté réponse en fait, un bon rappel que les micro-optimisation est mauvais). Une comparaison ne signifie pas une branche. Compilateur clang 9.0.Direction de la prévision.
Avec un tableau trié, la condition
data[c] >= 128est d'abordfalsepour une série de valeurs, puis devienttruepour tous plus tard des valeurs. C'est facile à prévoir. Avec un tableau non-trié, vous devez payer le coût de branchement.La raison pour laquelle les performances s'améliorent considérablement lorsque les données sont triées, c'est que la direction de la prévision pénalité est supprimé, comme l'explique magnifiquement dans Mysticial réponse.
Maintenant, si on regarde le code
nous pouvons constater que le sens de cette
if... else...direction est d'ajouter quelque chose lorsqu'une condition est satisfaite. Ce type de branche peut être facilement transformé en un conditionnelle déplacer déclaration, qui seraient rassemblés dans un conditionnelle déplacer instruction:cmovl, dans unx86système. La direction générale et donc le potentiel de la branche de prédiction de la pénalité est supprimé.Dans
C, ainsiC++, la déclaration, ce qui permettrait de compiler directement (sans optimisation) dans la condition de déplacer l'instruction dansx86, est l'opérateur ternaire... ? ... : .... Nous avons donc réécrire la déclaration ci-dessus dans un type équivalent:Tout en conservant la lisibilité, nous pouvons vérifier le facteur d'accélération.
Sur un processeur Intel Core i7-2600K @ 3.4 GHz et Visual Studio 2010 Mode de Libération, le point de référence (format copié à partir de Mysticial):
x86
x64
Le résultat est robuste à de nombreux tests. Nous obtenons une grande accélération lorsque la branche résultat est imprévisible, mais il souffre un peu quand elle est prévisible. En fait, lors de l'utilisation d'un conditionnel déplacer, la performance est la même quel que soit le modèle de données.
Maintenant, regardons de plus près par l'enquête sur le
x86assemblée qu'ils génèrent. Pour des raisons de simplicité, nous utilisons deux fonctionsmax1etmax2.max1utilise la branche conditionnelleif... else ...:max2utilise l'opérateur ternaire... ? ... : ...:Sur un x86-64-linge,
GCC -Sgénère l'assemblée ci-dessous.max2utilise beaucoup moins de code en raison de l'utilisation de l'instructioncmovge. Mais le véritable gain est quemax2ne pas impliquer la direction générale des sauts, desjmp, ce qui aurait considérablement les performances de pénalité si le résultat prévu est pas droit.Alors pourquoi ne conditionnelle déplacer mieux performer?
Dans un typique
x86processeur, l'exécution d'une instruction est divisée en plusieurs étapes. En gros, nous avons un matériel différent pour aborder les différentes étapes. Donc nous n'avons pas à attendre pour une instruction à terminer pour en commencer une nouvelle. Ceci est appelé le pipelining.Dans une branche cas, l'instruction suivante est déterminée par la précédente, de sorte que nous ne pouvons pas faire le pipelining. Nous n'avons ni à attendre ou prévoir.
Dans un conditionnelle déplacer cas, l'exécution conditionnelle de déplacer l'instruction est divisée en plusieurs étapes, mais les étapes antérieures comme
FetchetDecodene dépend pas du résultat de l'instruction précédente; seuls les derniers stades besoin de la suite. Ainsi, nous attendons une fraction de l'une des instructions temps d'exécution. C'est pourquoi le conditionnel déplacer version est plus lente que la branche lorsque la prédiction est facile.Le livre Systèmes informatiques: Un point de vue du Programmeur, deuxième édition explique cela en détail. Vous pouvez consulter la Section 3.6.6 pour Conditionnelle Déplacer Instructions, tout le Chapitre 4 pour Architecture de Processeur, et de l'Article 5.11.2 un traitement spécial pour Direction de la Prévision et des erreurs de prédiction de Sanctions.
Parfois, certains les compilateurs modernes peuvent optimiser notre code pour l'assemblage avec une meilleure performance, parfois, certains compilateurs ne peut pas (le code en question est à l'aide de Visual Studio compilateur natif). Sachant que la différence de performances entre la direction générale et à la condition que déplacer lorsque imprévisibles peuvent nous aider à écrire du code avec de meilleures performances lorsque le scénario est tellement complexe que le compilateur ne peut pas optimiser automatiquement.
-O0l'exemple et de montrer la différence de optimisé asm sur votre deux cas de tests.Si vous êtes curieux de connaître encore plus d'optimisations qui peut être fait à ce code, pensez à ceci:
De départ avec la boucle d'origine:
Avec boucle d'échange, nous pouvons changer cette boucle:
Ensuite, vous pouvez voir que le
ifconditionnelle est constante tout au long de l'exécution de laiboucle, de sorte que vous pouvez hisser leifout:Alors, vous voyez que la boucle interne peuvent être regroupées en une seule expression, en supposant que la virgule flottante modèle permet (
/fp:fastest jeté, par exemple)Que l'on est 100 000 fois plus rapide qu'avant.
id'une unité =1e5. Il ne fait aucune différence pour le résultat final, mais je voulais juste mettre les choses puisque c'est un fréquentés de la page.ifà ce point pourrait être converti à:sum += (data[j] >= 128) ? data[j] * 100000 : 0;qui le compilateur peut être en mesure de réduire àcmovgeou l'équivalent.Sans doute certains d'entre nous seraient intéressés par les moyens d'un code d'identification qui est problématique pour le CPU de la branche prédicteur. L'outil Valgrind
cachegrinda une branche de prédiction-simulateur, activé à l'aide de la--branch-sim=yesdrapeau. À travers les exemples de cette question, avec le nombre de boucles externes réduit à 10000 et compilé avecg++, donne ces résultats:Triés:
Non triés:
De forage vers le bas dans la, ligne par ligne, la sortie produite par
cg_annotatenous voir pour la boucle en question:Triés:
Non triés:
Cela vous permet de facilement identifier la problématique de ligne dans le non triés version la
if (data[c] >= 128)ligne est à l'origine de 164,050,007 mispredicted branches conditionnelles (Bcm) sous cachegrind de la direction générale de prédiction-modèle, alors qu'il est seulement de causer 10,006 dans la version triée.Sinon, sur Linux, vous pouvez utiliser les compteurs de performance du sous-système pour accomplir la même tâche, mais avec des performances natives CPU à l'aide de compteurs.
Triés:
Non triés:
Il peut également faire le code source d'annotation avec dissassembly.
Voir la performance tutoriel pour plus de détails.
data[c] >= 128(qui a 50% de miss taux comme vous le suggérez) et un pour la condition de la bouclec < arraySizequi a ~0% miss taux.Je viens de lire sur cette question et ses réponses, et je sens que la réponse est manquant.
Un bon moyen d'éliminer les branchements que j'ai trouvé pour un travail particulièrement bon dans la gestion des langues est une table de recherche au lieu d'utiliser une branche (bien que je ne l'ai pas testé dans ce cas).
Cette approche fonctionne en général si:
De fond et pourquoi
À partir d'un processeur point de vue, votre mémoire est lente. Pour compenser la différence de vitesse, un couple de caches sont intégrées dans votre processeur (L1/L2 cache). Alors, imaginez que vous êtes en train de faire votre belle calculs et de comprendre que vous avez besoin d'un morceau de la mémoire. Le processeur va obtenir sa "charge" de fonctionnement et charges de l'élément de mémoire dans le cache, et ensuite utilise le cache pour faire le reste des calculs. Parce que la mémoire est relativement lente, cette "charge" va ralentir votre programme.
Comme la direction de la prévision, cela a été optimisé pour les processeurs Pentium: le processeur prédit qu'il doit charger un morceau de données et tente de charger dans le cache avant l'opération de frappe réellement le cache. Comme nous l'avons déjà vu, direction de la prévision, parfois, va terriblement mal-dans le pire des cas, vous devez revenir en arrière et fait attendre pour un mémoire de charge, qui va prendre une éternité (en d'autres termes: à défaut de direction de la prévision est mauvaise, un mémoire de charge après une branche de prédiction de l'échec est juste horrible!!!).
Heureusement pour nous, si l'accès à la mémoire de modèle est prévisible, le processeur va le charger dans son cache rapide et tout est bien.
La première chose que nous devons savoir, c'est ce qui est petit? Bien que plus petit, mieux c'est, une règle du pouce est de s'en tenir à des tables de consultation qui sont <= 4096 octets la taille. Comme une limite supérieure: si votre table de recherche est supérieure à 64 ko c'est probablement la peine de reconsidérer.
La construction d'un tableau
Donc, nous avons compris que nous pouvons créer une petite table. La prochaine chose à faire est d'obtenir une fonction de recherche en place. Fonctions de recherche sont généralement de petites fonctions qui utilisent un couple de base opérations sur entiers (et, ou, xor, maj, ajouter, supprimer et peut-être se multiplient). Vous souhaitez avoir votre avis traduit par la fonction de recherche pour une sorte de "clé unique" dans votre table, puis simplement vous donne la réponse de tout le travail que vous voulez qu'il fasse.
Dans ce cas: >= 128 signifie que nous pouvons conserver la valeur, < 128, cela signifie pour nous en débarrasser. La façon la plus simple de le faire est d'utiliser un "ET": si nous continuons, nous ET avec 7FFFFFFF; si nous voulons nous débarrasser de lui, nous ET avec 0. Notez également que les 128 est une puissance de 2 -- pour que nous puissions aller de l'avant et faire un tableau de 32768/128 entiers et de le remplir avec un zéro et un lot de 7FFFFFFFF de l'.
Géré langues
Vous pourriez vous demander pourquoi cela fonctionne bien dans la gestion des langues. Après tout, géré langues vérifier les limites des tableaux avec une branche pour vous assurer de ne pas gâcher...
Eh bien, pas exactement... 🙂
Il y a eu très peu de travail sur l'élimination de cette branche à la gestion des langues. Par exemple:
Dans ce cas, il est évident pour le compilateur que la condition à la limite ne sera jamais frappé. Au moins Microsoft compilateur JIT (mais j'attends de Java n'des choses similaires) remarquerez que cette et décochez la case tout à fait. WOW, ce qui signifie pas de la branche. De même, il va faire face à d'autres raisons évidentes.
Si vous rencontrez un problème avec les recherches en gestion des langues-la clé est d'ajouter un
& 0x[something]FFFà votre fonction de recherche pour faire la vérification de limites prévisibles -- et regarder ce que ça va plus vite.La suite de cette affaire
sum += lookup[data[j]]oùlookupest un tableau de 256 entrées, la première étant le zéro et le dernier étant égal à l'index?lookup[data[j]]comme vous le suggérez, à la place.sum += lookup[data[j]];. Cependant, ce qui va aider, c'est que la recherche ne sera jamais sortir des limites d'un bug programme libre, de sorte que la direction de la prédicteur peut prédire la direction générale de la perfection. Et cela signifie que la vitesse!byte[] data); ce qui permettrait d'éliminer la branche complètement, ce qui signifie plus de vitesse. 🙂 En fait, j'ai toujours supposer que si (1) vous êtes dans une boucle serrée, avec une quantité limitée de code (comme ici) et (2) si vous pouviez prédire les branches avec 'l'analyse statique de code', puis le processeur / JIT'ter va faire leur travail correctement.for (int c = 0; c < 256; ++c) lookup[c] = (c >= 128) ? c : 0;peut être remplacé parfor (int c = 128; c < 256; ++c) lookup[c] = c;parce que la matrice déjà initialisé à zéros dans la gestion de la langue lors de l'initialisation.Que les données sont réparties entre 0 et 255 lorsque le tableau est trié, autour de la première moitié de la itérations ne pas entrer dans le
if-déclaration (laifdéclaration est partagée ci-dessous).La question est: Que fait la déclaration ci-dessus de ne pas exécuter, dans certains cas, comme dans le cas de données triées? Voici la branche "prédicteur". Une branche predictor est un circuit numérique qui tente de deviner la façon dont une branche (par exemple un
if-then-elsestructure) ira de l'avant c'est certain. Le but de la branche prédicteur est d'améliorer le flux dans le pipeline d'instruction. Direction des prédicteurs jouent un rôle essentiel dans la réalisation de haute performance efficace!Nous allons faire quelques bench-marking pour mieux la comprendre
La performance d'un
if-déclaration dépend de son état de santé a un schéma prévisible. Si la condition est toujours vraie ou toujours fausse, la direction de la prévision logique dans le processeur va chercher le motif. D'autre part, si le motif est imprévisible, laif-déclaration sera beaucoup plus cher.Nous allons mesurer la performance de cette boucle avec des conditions différentes:
Voici les horaires de la boucle avec différents vrai-faux motifs:
Un “mauvais” vrai-faux motif peut faire un
if-déclaration jusqu'à six fois plus lent qu'un “bonne” patron de! Bien sûr, dont le motif est bon et qui est mauvais en fonction sur les instructions exactes généré par le compilateur et sur le processeur spécifique.Donc il n'y a aucun doute sur l'impact de la direction de la prévision sur la performance!
Une façon d'éviter de branche erreurs de prédiction est de construire une table de recherche et d'index en utilisant les données. Stefan de Bruijn discuté que dans sa réponse.
Mais dans ce cas, nous savons que les valeurs sont dans l'intervalle [0, 255] et nous ne se soucient valeurs >= 128. Cela signifie que l'on peut facilement extraire un bit unique qui nous permettra de savoir si nous voulons une valeur ou pas: en transférant les données à droite 7 bits, ce qui nous laisse avec un bit à 0 ou 1 bit, et nous ne voulons ajouter de la valeur lorsque nous avons un bit à 1. Appelons ce bit la décision "bits".
À l'aide de la 0/1 valeur de la décision peu comme un index dans un tableau, on peut faire du code qui sera tout aussi rapide si les données sont triées ou non triées. Notre code sera toujours ajouter une valeur, mais lorsque la décision du bit est 0, nous allons ajouter de la valeur, quelque part, nous ne nous soucions pas. Voici le code:
Ce code déchets de la moitié de l'ajoute mais ne l'a jamais une branche de prédiction de l'échec. C'est énormément plus rapide sur des données aléatoires que la version avec un effectif si l'instruction.
Mais dans mes tests, explicite d'une table de recherche a été légèrement plus rapide que ce, probablement en raison de l'indexation dans une table de recherche a été légèrement plus rapide que le décalage de bits. Cela montre combien mon code met en place et utilise la table de recherche (imagination appelé
lutpour "LookUp Table" dans le code). Voici le code C++:Dans ce cas, la table de recherche a été seulement 256 octets, de sorte qu'il s'intègre parfaitement dans un cache et tout a été rapide. Cette technique ne fonctionnerait pas bien si les données ont été 24-bit valeurs et nous voulions seulement la moitié d'entre eux... la table de recherche serait beaucoup trop grande pour être pratique. D'autre part, on peut combiner les deux techniques présentées ci-dessus: d'abord décale les bits de plus, alors l'index d'une table de recherche. Pour un 24-bits de la valeur que nous voulons seulement la moitié supérieure de la valeur, nous pourrions éventuellement modifier les données de 12 bits, et d'être de gauche avec 12 bits de la valeur de l'index d'une table. Un 12-bit index de la table implique une table de 4096 valeurs, ce qui peut être pratique.
La technique de l'indexation dans un tableau, au lieu d'utiliser un
ifdéclaration, peuvent être utilisés pour décider du pointeur à utiliser. J'ai vu une bibliothèque mise en œuvre d'arbres binaires, et au lieu d'avoir deux pointeurs (pLeftetpRightou autre) a une longueur-2 tableau de pointeurs et utilisé la décision "peu" technique pour décider de ce qui doit suivre. Par exemple, au lieu de:cette bibliothèque devrait faire quelque chose comme:
Voici un lien vers ce code: Rouge Noir Des Arbres, Éternellement Confuzzled
data[c]>>7- ce qui est discuté quelque part ici); j'ai volontairement laissé cette solution, mais bien sûr, vous avez raison. Juste une petite remarque: La règle de base pour les tables de recherche, c'est que si elle s'inscrit dans 4KO (en raison de la mise en cache), il va travailler de préférence, la table la plus petite possible. Pour les langues je l'avais poussée à 64 ko, à faible niveau de langages tels que le C++ et le C, je serais probablement revoir (c'est juste mon expérience). Depuistypeof(int) = 4, j'avais essayer de s'en tenir à un maximum de 10 bits.sizeof(int) == 4? Ce serait vrai pour la version 32 bits. Mes deux-année-vieux téléphone cellulaire a 32 ko de cache L1, de sorte que même un 4K table de recherche peuvent fonctionner, surtout si les valeurs de recherche ont été un octet au lieu d'un int.jest égal à 0 ou 1 méthode pourquoi ne pas simplement multiplier votre valeur parjavant d'ajouter plutôt que d'utiliser le tableau d'indexation (éventuellement devrait être multiplié par1-jplutôt quej)int c = data[j]; sum += c & -(c >> 7);qui ne nécessite pas de multiplications à tous.i = (x < node->value); node = node->link[i];n'a pas explicitement la branche, mais elle contient tout de même une comparaison; il dépend beaucoup de l'architecture cible pour savoir si cela peut être résolu sans une succursale ou pas. Depuis, il peut être fait sur x86 (à l'aide de CMOV ou LAHF) et le BRAS (conditionnel ajouter ou déplacer), qui sont les seules architectures que j'utilise, c'est peut-être pas important!(x < node->value)nécessitent une branche à évaluer? Toutes les architectures avec lequel je suis familier ont un "drapeaux" s'inscrire, et il est simple d'extraire les valeur de l'indicateur. Je suppose que sur le Pentium 4 le bit indicateur de l'extraction peut être lent comme autant que je me souvienne que la puce n'a pas consacré déplacement de matériel pour les adresses, mais emprunte de l'ALU de décalage de bits. Mais je ne sais pas d'où une succursale serait nécessaire. Hmm, vos exemples sont conditionnelles... l'idée est qu'une fois que vous extrayez le peu de drapeaux, vous pouvez simplement utiliser l'indexation avec aucune branche.Dans la triés cas, vous pouvez faire mieux que de s'appuyer sur le succès de la direction de la prévision ou de tout dépourvu de branches comparaison astuce: supprimer complètement la branche.
En effet, le tableau est divisé en une zone contiguë avec
data < 128et un autre avecdata >= 128. Il faut donc trouver la partition de point avec un recherche dichotomique (à l'aide deLg(arraySize) = 15comparaisons), puis faire un tout droit d'accumulation à partir de ce point.Quelque chose comme (case non cochée)
ou, un peu plus d'obfuscation
Un encore plus rapide approche, qui donne un approximative solution pour les deux triés ou non triée est:
sum= 3137536;(en supposant une véritable distribution uniforme, 16384 échantillons avec valeur attendue 191.5) 🙂sum= 3137536- intelligent. C'est un peu évidemment pas le point de la question. La question est clairement expliquer surprenant caractéristiques de performance. Je suis enclin à dire que l'addition de fairestd::partitionau lieu destd::sortest précieux. Mais la question s'étend de plus que le synthétique de référence donné.Ce comportement se produit en raison de la Direction de la prévision.
À comprendre la direction de la prévision, on doit d'abord comprendre Instruction Pipeline:
Toute instruction est décomposé en une séquence d'étapes, de sorte que les différentes étapes peuvent être exécutées simultanément en parallèle. Cette technique est connue comme instruction de pipeline et ce est utilisé pour augmenter le débit dans les processeurs modernes. Pour mieux comprendre ce processus, veuillez consulter cette exemple sur Wikipédia.
Généralement, les processeurs modernes ont assez longue pipelines, mais pour faciliter la considérons ces 4 étapes seulement.
4 étages de pipeline en général de 2 des instructions.
De revenir à la question ci-dessus considérons les instructions suivantes:
Sans direction de la prévision, ce qui suit se produit:
Pour exécuter l'instruction B ou d'une instruction C le processeur devra attendre jusqu'à ce que l'instruction A n'est pas d'atteindre jusqu'EX étape dans le pipeline, comme la décision de passer à l'instruction B ou d'une instruction C dépend du résultat de l'instruction A. de Sorte que le pipeline doit ressembler à cela.
quand si la condition renvoie true:
Quand si la condition retourne false:
Comme un résultat de l'attente du résultat d'Une instruction, le nombre total de cycles CPU passé dans le cas ci-dessus (sans direction de la prévision, pour à la fois vrai et faux) est de 7.
Alors, quelle est la direction de la prévision?
Branche prédicteur essayer de deviner la façon dont une branche (if-then-else structure) ira de l'avant c'est certain. Il ne sera pas attendre pour l'instruction A pour accéder à l'EX-stade de la préparation, mais il va deviner la décision et aller à l'instruction (B ou C dans le cas de notre exemple).
En cas de bonne réponse, le pipeline ressemble à quelque chose comme ceci:
Si elle est détectée plus tard que l'estimation était mauvaise, l'partiellement exécuté les instructions sont ignorées et le pipeline commence avec la bonne direction, entraînant un retard.
Le temps qui est perdu dans le cas d'une succursale, les erreurs de prédiction est égal au nombre d'étapes dans le pipeline à partir de l'extraction de l'étape de l'exécution de la scène. Des microprocesseurs modernes ont tendance à avoir assez longue pipelines, de sorte que les erreurs de prédiction de retard est compris entre 10 et 20 cycles d'horloge. Plus le pipeline le plus grand est le besoin pour une bonne direction de la prédicteur.
Dans le cas des OP code, la première fois où le conditionnel, la direction générale prédicteur n'avons pas toutes les informations à la base de la prédiction, de sorte que la première fois, elle va choisir au hasard la prochaine instruction. Plus tard dans la boucle for, il peut de la base de la prédiction sur l'histoire.
Pour un tableau trié dans l'ordre croissant, il y a trois possibilités:
Supposons que le prédicteur sera supposons toujours que le véritable branche sur la première manche.
Ainsi, dans le premier cas, il prend toujours la vraie direction puisque, jusqu'ici, toutes ses prédictions sont correctes.
Dans le 2e cas, d'abord, il prédit que de mal, mais après quelques itérations, il va prédire correctement.
Dans le 3ème cas, il va d'abord prédire correctement jusqu'les éléments sont de moins de 128. Après quoi ce sera un échec pour un certain temps et le corriger lui-même lorsqu'il voit branche de prédiction de défaillance dans l'histoire.
Dans tous ces cas, l'échec sera trop moins en nombre et en conséquence, seulement quelques fois il sera nécessaire de jeter l'partiellement exécuté les instructions et commencez la bonne direction, ce qui entraîne moins de cycles de PROCESSEUR.
Mais dans le cas d'un hasard non triés tableau, la prédiction sera nécessaire de jeter l'partiellement exécuté les instructions et recommencer avec la branche correcte la plupart du temps, et donc le nombre de cycles CPU par rapport au tableau trié.
Une réponse officielle serait de
Vous pouvez le voir sur cette belle diagramme pourquoi la direction de la prédicteur devient confus.
Chaque élément dans le code d'origine est une valeur aléatoire
de sorte que le prédicteur va changer sur les côtés, comme le
std::rand()coup.D'autre part, une fois triés, les prédicteur sera la première à se déplacer vers un état de fortement de ne pas prendre et lors du changement des valeurs de la forte valeur prédictive sera dans trois courses à travers le changement de tout le chemin d'fortement de ne pas prendre fortement pris.
Dans la même ligne (je pense que cela n'a pas été mis en évidence par une réponse) il est bon de mentionner que parfois (spécialement dans les logiciels d'où la question de performance—comme dans le noyau Linux), vous pouvez trouver quelques si les déclarations comme suit:
ou de même:
Les deux
likely()etunlikely()sont en fait des macros qui sont définis en utilisant quelque chose comme la GCC est__builtin_expectpour aider le compilateur insérer la prédiction de code en faveur de la condition de prendre en compte les informations fournies par l'utilisateur. GCC supporte d'autres objets internes qui pourraient modifier le comportement du programme en cours d'exécution ou émettent de faibles niveau des instructions comme l'effacement de la mémoire cache, etc. Voir cette documentation qui va par le biais de la disposition du CCG les builtins.Normalement, ce genre d'optimisations sont principalement utilisés dans les applications en temps réel ou les systèmes embarqués où le temps d'exécution de questions et il est essentiel. Par exemple, si vous êtes à la vérification de certaines condition d'erreur qui n'arrive qu'1/10000000 fois, alors pourquoi ne pas informer le compilateur à ce sujet? De cette façon, par défaut, la direction de la prévision suppose que la condition est fausse.
Fréquemment utilisés opérations Booléennes en C++ produire de nombreuses filiales dans le programme compilé. Si ces branches sont à l'intérieur des boucles et sont difficiles à prévoir, ils peuvent ralentir l'exécution de manière significative. Les variables booléennes sont stockés en tant que 8 bits entiers avec la valeur
0pourfalseet1pourtrue.Variables booléennes sont fermement déterminés dans le sens que tous les opérateurs qui ont des variables Booléennes comme entrée de vérifier si les entrées ont une valeur autre que
0ou1, mais les opérateurs Booléens comme sortie peut produire aucune autre valeur que0ou1. Cela rend les opérations avec des variables Booléennes comme entrée moins efficace que le nécessaire.Examiner exemple:
C'est généralement mis en œuvre par le compilateur de la manière suivante:
Ce code est loin d'être optimale. Les branches peuvent prendre un certain temps en cas de mispredictions. Les opérations Booléennes peuvent être beaucoup plus efficace si elle est connue avec certitude que les opérandes ont pas d'autres valeurs que la
0et1. La raison pourquoi le compilateur ne pas faire une telle hypothèse est que les variables peuvent avoir d'autres valeurs que si elles ne sont pas initialisées ou provenir de sources inconnues. Le code ci-dessus peut être optimisé siaetba été initialisé aux valeurs valides ou si ils viennent de la part des opérateurs qui produisent Booléenne sortie. L'optimisation de code ressemble à ceci:charest utilisé à la place deboolafin de rendre possible l'usage des opérateurs au niveau du bit (&et|) à la place des opérateurs Booléens (&&et||). Les opérateurs au niveau du bit sont de simples instructions ne prendre qu'un seul cycle d'horloge. L'opérateur OU (|) fonctionne même siaetbont d'autres valeurs que la0ou1. L'opérateur and (&) et le OU EXCLUSIF logique (^) peuvent donner des résultats incohérents si les opérandes ont d'autres valeurs que la0et1.~ne peut pas être utilisé pour ne PAS. Au lieu de cela, vous pouvez faire un Booléen PAS sur une variable qui est connu pour être0ou1par utilise XOR avec1:peut être optimisé pour:
a && bne peut pas être remplacé para & bsibest une expression qui ne doit pas être évaluée siaestfalse(&&n'évaluera pasb,&va). De même,a || bne peut pas être remplacé para | bsibest une expression qui ne doit pas être évaluée siaesttrue.L'aide d'opérateurs au niveau du bit est plus avantageux si les opérandes sont des variables que si les opérandes sont des comparaisons:
est optimale dans la plupart des cas (sauf si vous attendez la
&&expression pour générer un grand nombre de branche mispredictions).C'est sûr!...
Direction de la prévision fait de la logique de l'exécution plus lente, en raison de la commutation de ce qui se passe dans votre code! C'est comme si vous allez a droite de la rue ou d'une rue avec beaucoup de détours, pour assurer la droite que l'on va faire plus rapide!...
Si le tableau est trié, votre condition est fausse, à la première étape:
data[c] >= 128, puis devient une véritable valeur pour l'ensemble de la voie à la fin de la rue. C'est la façon dont vous obtenez à la fin de la logique plus rapide. D'autre part, à l'aide d'un tableau non trié, vous avez besoin d'un lot de tournage et de transformation, ce qui rend votre code plus lent pour vous...Regarde l'image que j'ai créée pour vous ci-dessous. La rue qui va être fini au plus vite?
Donc par programme, direction de la prévision fait que le processus d'être plus lent...
Aussi à la fin, il est bon de savoir que nous avons deux types de direction des prédictions que chacun va affecter votre code différemment:
1. Statique
2. Dynamique
Cette question a déjà été répondu parfaitement à plusieurs reprises. Cependant, je voudrais attirer l'attention du groupe à encore une autre analyse intéressante.
Récemment cet exemple (modifié très légèrement) a également été utilisé comme un moyen de démontrer comment un morceau de code peuvent être présentés dans le programme lui-même sur Windows. Le long du chemin, l'auteur montre également comment utiliser les résultats pour déterminer si le code est de passer la plupart de son temps dans les deux triés & non triés cas. Enfin, la pièce montre également comment utiliser un peu connu de HAL (Couche d'Abstraction du Matériel) pour déterminer combien de branche les erreurs de prédiction qui se passe dans le non triés cas.
Le lien est ici:
http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm
When the input is unsorted, all the rest of the loop takes substantial time. But with sorted input, the processor is somehow able to spend not just less time in the body of the loop, meaning the buckets at offsets 0x18 and 0x1C, but vanishingly little time on the mechanism of looping.Auteur tente de discuter de profilage dans le contexte de code posté ici et dans le processus d'essayer d'expliquer pourquoi l'triés cas est donc beaucoup plus rapide.Que ce qui a déjà été mentionné par d'autres, que derrière le mystère, c'est Direction De La Prédicteur.
Je ne suis pas d'essayer d'ajouter quelque chose, mais d'expliquer le concept d'une autre manière.
Il y a une introduction concise sur le wiki qui contient du texte et diagramme.
J'aime bien l'explication ci-dessous qui utilise un schéma d'élaborer la Branche Prédicteur de manière intuitive.
Basé sur le scénario décrit, j'ai écrit une animation de démonstration pour montrer comment les instructions sont exécutées dans un pipeline dans différentes situations.
L'exemple contient trois instructions et la première est une instruction de saut conditionnel. Les deux dernières instructions peut aller dans le pipeline jusqu'à ce que le saut conditionnel instruction est exécutée.
Il faudra 9 cycles d'horloge pour 3 instructions pour être achevé.
Il faudra 7 cycles d'horloge pour 3 instructions pour être achevé.
Il faudra 9 cycles d'horloge pour 3 instructions pour être achevé.
Comme vous pouvez le voir, il semble que nous n'avons pas de raison de ne pas utiliser la Branche Prédicteur.
C'est assez simple, une démo qui précise les principes de base de la partie de la Branche Prédicteur. Si ces gifs sont ennuyeux, n'hésitez pas à les retirer de la réponse et les visiteurs peuvent également obtenir la démo de BranchPredictorDemo
Direction de la prévision du gain!
Il est important de comprendre que les erreurs de prédiction de branche ne ralentit pas les programmes. Le coût de l'absence de prédiction est juste que si la branche de prédiction n'existait pas et vous avez attendu pour l'évaluation de l'expression de décider quel est le code à exécuter (plus d'explications dans le paragraphe suivant).
Dès qu'il y a un
if-else\switchdéclaration, l'expression doit être évaluée afin de déterminer le bloc doit être exécutée. Dans le code assembleur généré par le compilateur, à condition branche instructions sont insérés.Une branche d'instruction peut causer un ordinateur pour commencer l'exécution d'une autre séquence d'instruction et donc de s'écarter de son comportement par défaut de l'exécution des instructions dans l'ordre (c'est à dire si l'expression est fausse, le programme ignore le code de la
ifbloc) selon une condition, qui est l'évaluation de l'expression dans notre cas.Cela étant dit, le compilateur essaie de prédire le résultat avant qu'il soit réellement évalué. Il va chercher les instructions de la
ifbloc, et si l'expression s'avère être vrai, alors merveilleux! Nous avons gagné du temps qu'il a fallu pour l'évaluer, et fait des progrès dans le code; si non, alors nous courons le mauvais code, le pipeline est vidé, et que le bloc est exécuté.De visualisation:
Disons que vous avez besoin de choisir la voie 1 ou voie 2. En attente de votre partenaire pour vérifier la carte, vous vous êtes arrêté à ## et attendit, ou vous pouvez simplement choisir route1 et si vous avez de la chance (route 1 est la bonne route), puis une grande vous n'avez pas à attendre que votre partenaire, vérifiez la carte (vous avez enregistré le temps qu'il lui a fallu pour vérifier la carte), autrement, il vous suffira de tourner le dos.
Tandis que le rinçage des canalisations est super rapide, aujourd'hui, de prendre ce pari en vaut la peine. La prédiction de trier les données ou les données qui changent lentement est toujours plus facile et mieux que la prévision des changements rapides.
C'est à propos de la branche de prédiction. Quel est-il?
Une branche prédicteur est l'une des plus anciennes de la performance à améliorer les techniques qui trouve encore de la pertinence dans les architectures modernes. Alors que la simple prédiction techniques de recherche rapide et l'efficacité de la puissance, ils présentent un haut taux d'erreurs de prédiction de.
D'autre part, complexe, direction générale des prévisions –soit de neurones ou des variantes de deux niveau de la direction de la prévision –fournir une meilleure précision de la prédiction, mais ils consomment plus de puissance et de complexité augmente de façon exponentielle.
En plus de cela, dans le complexe des techniques de prévision du temps pris pour prédire les branches est lui-même très élevé allant de 2 à 5 cycles –ce qui est comparable à la durée d'exécution réelle des branches.
Direction de la prévision est essentiellement une optimisation (minimisation) problème où l'accent est mis sur pour atteindre le plus bas possible manquer taux, faible consommation d'énergie, et de faible complexité, avec un minimum de ressources.
Vraiment il y a trois différents types de branches:
Avant branches conditionnelles sur la base d'un run-time condition, le PC (program counter) est modifié pour pointer vers une adresse de l'avant dans le volet enseignement.
Arrière branches conditionnelles - le PC est modifié pour pointer vers l'arrière dans le volet enseignement. La direction générale est basée sur une condition, telle que la ramification vers l'arrière pour le début d'une boucle de programme lorsqu'un test à la fin de la boucle membres de la boucle doit être exécutée de nouveau.
Inconditionnel branches - ce qui inclut les sauts, la procédure d'appels et retours qui n'ont pas de condition spécifique. Par exemple, une instruction de saut inconditionnel peut être codé en langage d'assemblage comme simplement "jmp", et le volet enseignement doit être immédiatement dirigé vers la cible à l'emplacement indiqué par l'instruction de saut, alors qu'un saut conditionnel qui peut être codé comme "jmpne" redirige le volet enseignement que si le résultat d'une comparaison de deux valeurs dans une précédente "comparer" instructions indique les valeurs à ne pas être égal. (Segmenté schéma d'adressage utilisé par l'architecture x86 ajoute de la complexité, depuis les sauts peuvent être soit "proche" (à l'intérieur d'un segment) ou "loin" (en dehors du segment). Chaque type a des effets différents sur la branche des algorithmes de prédiction.)
Statique/dynamique de la Direction de la Prévision: Statique de la direction de la prévision est utilisé par le microprocesseur de la première fois qu'une branche conditionnelle est rencontrés, et les dynamiques de la branche de prédiction est utilisée pour les exécutions de la branche conditionnelle code.
Références:
Direction de la prédicteur
Une Démonstration de l'Auto-Profilage
Direction De La Prévision De L'Examen
Direction De La Prévision
Outre le fait que la direction de la prévision peut vous ralentir, un tableau trié a un autre avantage:
Vous pouvez avoir une condition d'arrêt au lieu de la simple vérification de la valeur, de cette façon, vous n'en boucle sur les données pertinentes, et d'ignorer le reste.
La direction de la prévision manquera qu'une seule fois.
Sur les BRAS, il n'y a pas de direction nécessaire, parce que chaque instruction a 4 bits champ de condition, qui est testé à coût zéro. Ceci élimine le besoin pour de courtes branches, et il n'y aurait pas de succursale de prédiction de succès. Par conséquent, la version triée irait plus lent que la version non triés sur le BRAS, à cause de la surcharge de tri. La boucle intérieure devrait ressembler à quelque chose comme ce qui suit:
GEsuffixe peut être effectuée de manière séquentielle, sans modification de la valeur deR3entre les deux?Triés tableaux sont traitées plus rapidement que un tableau non-trié, en raison d'un phénomène appelé la direction de la prévision.
La branche predictor est un circuit numérique (dans l'architecture de l'ordinateur) en essayant de prédire quelle direction aller, l'amélioration de la circulation dans l'instruction de pipeline. Le circuit/ordinateur prédit la prochaine étape et l'exécute.
Faire une mauvaise prédiction conduit à revenir à l'étape précédente, et de l'exécution avec une autre prédiction. En supposant que la prédiction est correcte, le code de continuer à l'étape suivante. Une mauvaise prédiction des résultats en répétant la même étape, jusqu'à ce qu'une bonne prédiction se produit.
La réponse à votre question est très simple.
Dans un tableau non trié, l'ordinateur fait plusieurs prédictions, ce qui augmente le risque d'erreurs.
Alors que, dans un tableau trié, l'ordinateur fait moins de prédictions, de réduire le risque d'erreurs.
Faire plus de prédictions nécessite plus de temps.
Tableau Trié: Droit De La Route
____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
Des Ménagères De Tableau: Courbes De La Route
Direction de la prévision: Deviner/prédire où la route est droite et le suivre sans vérification de
Bien que les deux routes atteindre la même destination, la route droite est plus courte, et l'autre est plus longue. Si vous choisissez l'autre par erreur, il n'y a pas de retour en arrière, et donc vous perdrez un peu de temps supplémentaire si vous choisissez le long de la route. Ceci est similaire à ce qui se passe dans l'ordinateur, et j'espère que cela vous a aidé à mieux comprendre.
Aussi je veux citer @Simon_Weaver de commentaires:
La prise en charge par d'autres réponses que l'on doit trier les données ne sont pas correctes.
Le code suivant ne permet pas de trier le tableau d'ensemble, mais seulement 200-élément segments de celle-ci, et ainsi fonctionne le plus rapide.
Tri k-élément sections complète le pré-traitement dans le temps linéaire,
O(n), plutôt que de laO(n.log(n))temps nécessaire pour trier le tableau d'ensemble.Cela aussi "prouve" qu'il n'a rien à voir avec un quelconque problème algorithmique comme ordre de tri, et c'est en effet la direction de la prévision.