Compte à rebours en boucle

Je crois (d’après certaines lectures de recherche) que le décompte dans les boucles for-loop est en réalité plus efficace et plus rapide dans l’exécution Mon code logiciel complet est C ++

J’ai actuellement ceci:

for (i=0; i<domain; ++i) { 

mon ‘i’ est unsigned resgister int, ainsi que ‘domain’ est non signé int

dans la boucle for i, on utilise pour parcourir un tableau, p.ex.

 array[i] = do stuff 

convertir cela en compte à rebours gâche la sortie attendue / correcte de ma routine.

J’imagine que la réponse est assez sortingviale, mais je n’arrive pas à comprendre.

UPDATE: ‘do stuff’ ne dépend pas de l’itération précédente ou ultérieure. Les calculs dans la boucle for sont indépendants pour cette itération de i. (J’espère que cela à du sens).

UPDATE: Pour obtenir une accélération de l’exécution avec ma boucle For, dois-je compter à rebours et si tel est le cas, supprimer la partie non signée lors de la création de mon int, ou quelle autre méthode?

S’il vous plaît aider.

Je suppose que votre boucle arrière en arrière ressemble à ceci:

 for (i = domain - 1; i >= 0; --i) { 

Dans ce cas, i étant non signé , il sera toujours supérieur ou égal à zéro. Lorsque vous décrémentez une variable non signée égale à zéro, elle se réduit à un très grand nombre. La solution est soit de faire en sorte que i signe, soit de changer la condition dans la boucle for comme ceci:

 for (i = domain - 1; i >= 0 && i < domain; --i) { 

Ou comptez de domain à 1 plutôt que de domain - 1 à 0 :

 for (i = domain; i >= 1; --i) { array[i - 1] = ...; // notice you have to subtract 1 from i inside the loop now } 

Il existe une seule méthode correcte pour effectuer une boucle en arrière à l’aide d’un compteur non signé:

 for( i = n; i-- > 0; ) { // Use i as normal here } 

Il y a un truc ici: pour la dernière itération de la boucle, vous aurez i = 1 en haut de la boucle, i–> 0 passe car 1> 0, puis i = 0 dans le corps de la boucle. Lors de la prochaine itération, i–> 0 échoue car i == 0; le décrément postfix n’a donc pas d’importance.

Très non évidente je sais.

Ce n’est pas une réponse à votre problème, car vous ne semblez pas avoir de problème.

Ce type d’optimisation n’a absolument aucune pertinence et devrait être laissé au compilateur (si cela est fait).

Avez-vous profilé votre programme pour vérifier que votre boucle est un goulot d’étranglement? Si non, alors vous n’avez pas besoin de passer du temps à vous inquiéter à ce sujet. Plus encore, avoir “i” comme “registre” int, au fur et à mesure que vous écrivez, n’a aucun sens du sharepoint vue des performances.

Même sans connaître votre domaine de problème, je peux vous garantir que la technique de la boucle inverse et le compteur “register” int auront un impact négligeable sur les performances de votre programme. Rappelez-vous, “l’optimisation prématurée est la racine de tout le mal”.

Cela dit, il serait préférable d’optimiser le temps consacré à l’optimisation de la structure globale du programme, des structures de données et des algorithmes utilisés, de l’utilisation des ressources, etc.

Vérifier si un nombre est égal à zéro peut être plus rapide ou plus efficace qu’une comparaison. Mais c’est le genre de micro-optimisation dont vous ne devriez vraiment pas vous inquiéter – quelques cycles d’horloge seront considérablement réduits à néant par tout autre problème de performances.

Sur x86:

 dec eax jnz Foo 

Au lieu de:

 inc eax cmp eax, 15 jl Foo 

Si vous avez un compilateur décent, il optimisera le “décompte” tout aussi efficacement que le “décompte”. Essayez juste quelques repères et vous verrez.

Donc, vous “lisez” que le dénigrement est plus efficace? Je trouve cela très difficile à croire si vous ne me montrez pas les résultats du profileur et le code. Je peux l’acheter dans certaines circonstances, mais dans le cas général, non. Il me semble que ceci est un cas classique d’optimisation prématurée.

Votre commentaire sur “register int i” est également très révélateur. De nos jours, le compilateur sait toujours mieux que vous comment allouer des registres. Ne vous embêtez pas avec le mot-clé register, à moins que vous n’ayez profilé votre code.

Lorsque vous parcourez des structures de données de toute sorte, les erreurs de cache ont un impact beaucoup plus important que la direction dans laquelle vous vous dirigez. Concentrez-vous sur la vue d’ensemble de la structure de la mémoire et de la structure de l’algorithme au lieu de micro-optimisations sortingviales.

Cela n’a rien à voir avec le comptage. Ce qui peut être plus rapide, c’est compter vers zéro . La réponse de Michael montre pourquoi – x86 vous donne une comparaison avec zéro comme effet secondaire implicite de nombreuses instructions. Ainsi, après avoir ajusté votre compteur, vous twigz simplement en fonction du résultat plutôt que de faire une comparaison explicite. (Peut-être que d’autres architectures le font aussi; je ne sais pas.)

Les compilateurs Pascal de Borland sont connus pour effectuer cette optimisation. Le compilateur transforme ce code:

 for i := x to y do foo(i); 

dans une représentation interne plus proche de celle-ci:

 tmp := Succ(y - x); i := x; while tmp > 0 do begin foo(i); Inc(i); Dec(tmp); end; 

(Je dis notoire non pas parce que l’optimisation affecte le résultat de la boucle, mais parce que le débogueur n’affiche pas correctement la variable compteur. Lorsque le programmeur inspecte i , le débogueur peut afficher la valeur de tmp place, causant une confusion sans fin et une panique pour les programmeurs. qui pensent que leurs boucles sont en recul.)

L’idée est que même avec l’instruction extra Inc ou Dec , c’est toujours un gain net, en termes de temps d’exécution, de faire une comparaison explicite. Vous pouvez débattre de la question de savoir si vous pouvez réellement remarquer cette différence.

Mais notez que la conversion est une opération que le compilateur ferait automatiquement , selon que la transformation l’intéresse ou non. Le compilateur est généralement plus doué pour l’optimisation de code que vous ne l’êtes, aussi ne perdez pas trop d’efforts pour le concurrencer.

Quoi qu’il en soit, vous avez posé des questions sur le C ++, pas sur Pascal. Les boucles “pour” C ++ ne sont pas aussi faciles à appliquer à l’optimisation que les boucles “pour” de Pascal car les limites des boucles de Pascal sont toujours entièrement calculées avant que la boucle ne s’exécute, alors que les boucles C ++ dépendent parfois de la condition d’arrêt et de la boucle. Contenu. Les compilateurs C ++ doivent effectuer un certain nombre d’parsings statiques pour déterminer si une boucle donnée peut répondre aux exigences du type de transformation auquel les boucles Pascal peuvent prétendre sans condition. Si le compilateur C ++ effectue l’parsing, il pourrait effectuer une transformation similaire.

Rien ne vous empêche d’écrire vos boucles de cette façon:

 for (unsigned i = 0, tmp = domain; tmp > 0; ++i, --tmp) array[i] = do stuff 

Faire cela pourrait rendre votre code courir plus vite. Comme je l’ai déjà dit, vous ne le remarquerez probablement pas. Le coût plus élevé que vous payez en organisant manuellement vos boucles est que votre code ne suit plus les idiomes établis. Votre boucle est une boucle “pour” parfaitement ordinaire, mais elle ne ressemble plus à une – elle a deux variables, elles comptent dans des directions opposées et l’une d’elles n’est même pas utilisée dans le corps de la boucle – le code (y compris vous-même, une semaine, un mois ou une année à partir de maintenant où vous avez oublié l’optimisation que vous espériez réaliser) devra déployer des efforts supplémentaires pour prouver à lui-même que la boucle est bien une boucle ordinaire déguisé.

(Avez-vous remarqué que mon code ci-dessus utilisait des variables non signées sans aucun danger d’enrouler à zéro? L’utilisation de deux variables distinctes le permet.)

Trois choses à retenir de tout cela:

  1. Laissez l’optimiseur faire son travail; dans l’ensemble, c’est mieux que vous.
  2. Rendez le code ordinaire ordinaire afin qu’il n’ait pas à entrer en concurrence avec un code spécial pour attirer l’attention de personnes qui le révisent, le déboguent ou le mettent à jour.
  3. Ne faites rien de fantaisiste au nom de la performance avant que les tests et le profilage n’en montrent la nécessité.

Difficile à dire avec les informations données mais … inversez votre tableau et compte à rebours?

Jeremy Ruten a fait remarquer à juste titre que l’utilisation d’un compteur de boucles non signé est dangereuse. C’est aussi inutile, autant que je sache.

D’autres ont également souligné les dangers d’une optimisation prématurée. Ils ont absolument raison.

Cela dit, voici un style que j’ai utilisé lors de la programmation de systèmes embarqués il y a de nombreuses années, lorsque chaque octet et chaque cycle comptait pour quelque chose. Ces formulaires m’ont été utiles pour les processeurs et les compilateurs que j’utilisais, mais votre kilométrage peut varier.

 // Start out pointing to the last elem in array pointer_to_array_elem_type p = array + (domain - 1); for (int i = domain - 1; --i >= 0 ; ) { *p-- = (... whatever ...) } 

Cette forme tire parti de l’indicateur de condition défini sur certains processeurs après des opérations arithmétiques. Sur certaines architectures, le décrément et le test de la condition de twig peuvent être combinés en une seule instruction. Notez que l’utilisation de predecrement ( --i ) est la clé – l’utilisation de postdecrement ( i-- ) n’aurait pas fonctionné aussi bien.

Alternativement

 // Start out pointing *beyond* the last elem in array pointer_to_array_elem_type p = array + domain; for (pointer_to_array_type p = array + domain; p - domain > 0 ; ) { *(--p) = (... whatever ...) } 

Cette seconde forme tire parti de l’arithmétique de pointeur (adresse). Je vois rarement la forme (pointer - int) nos jours (pour une bonne raison), mais le langage garantit que lorsque vous soustrayez un int à un pointeur, celui-ci est décrémenté de (int * sizeof (*pointer)) .

Je soulignerai encore une fois que le fait de savoir si ces formes sont gagnantes dépend du processeur et du compilateur que vous utilisez. Ils m’ont bien servi sur les architectures Motorola 6809 et 68000.

Dans certains kernelx d’armement ultérieurs, décrémenter et comparer ne prend qu’une seule instruction. Cela rend les boucles de décrémentation plus efficaces que celles incrémentées.

Je ne sais pas pourquoi il n’y a pas non plus d’instruction de comparaison incrémentale.

Je suis surpris que ce message ait été voté -1 alors que c’est un vrai problème.

Vous pouvez essayer ce qui suit, quel compilateur optimisera très efficacement:

 #define for_range(_type, _param, _A1, _B1) \ for (_type _param = _A1, _finish = _B1,\ _step = static_cast<_type>(2*(((int)_finish)>(int)_param)-1),\ _stop = static_cast<_type>(((int)_finish)+(int)_step); _param != _stop; \ _param = static_cast<_type>(((int)_param)+(int)_step)) 

Maintenant, vous pouvez l’utiliser:

 for_range (unsigned, i, 10,0) { cout << "backwards i: " << i << endl; } for_range (char, c, 'z','a') { cout << c << endl; } enum Count { zero, one, two, three }; for_range (Count, c, three, zero) { cout << "backwards: " << c << endl; } 

Vous pouvez parcourir n'importe quelle direction:

 for_range (Count, c, zero, three) { cout << "forward: " << c << endl; } 

La boucle

 for_range (unsigned,i,b,a) { // body of the loop } 

produira le code suivant:

  mov esi,b L1: ; body of the loop dec esi cmp esi,a-1 jne L1 

Tout le monde ici se concentre sur la performance. Il y a en fait une raison logique pour itérer vers zéro qui peut résulter en un code plus propre.

Itérer sur le dernier élément en premier est pratique lorsque vous supprimez des éléments non valides en permutant avec la fin du tableau. Pour les mauvais éléments non adjacents à la fin, nous pouvons basculer vers la position de fin, diminuer la limite de fin du tableau et continuer à itérer. Si vous deviez itérer vers la fin, alors permuter avec la fin pourrait avoir pour résultat un échange mauvais pour mauvais. En itérant bout à 0, nous soaps que l’élément à la fin du tableau a déjà fait ses preuves pour cette itération.

Pour plus d’explications …

Si:

  1. Vous supprimez des éléments défectueux en permutant avec une extrémité du tableau et en modifiant les limites du tableau pour exclure les éléments défectueux.

Alors évidemment:

  1. Vous devriez échanger un bon élément, c’est-à-dire un élément qui a déjà été testé dans cette itération.

Donc, cela implique:

  1. Si nous nous éloignons de la variable liée, les éléments entre la variable liée et le pointeur d’itération actuel s’avèrent bons. Que le pointeur d’itération obtienne ++ ou – importe peu. Ce qui compte, c’est que nous nous éloignons de la variable liée pour savoir que les éléments adjacents sont bons.

Alors finalement:

  1. Itérer vers 0 nous permet d’utiliser une seule variable pour représenter les limites du tableau. Que cela compte ou non est une décision personnelle entre vous et votre compilateur.

Ce qui compte beaucoup plus que d’augmenter ou de diminuer votre compteur, c’est de savoir si vous augmentez ou diminuez la mémoire. La plupart des caches sont optimisés pour augmenter la mémoire, pas pour la réduire. Le temps d’access à la mémoire étant le goulot d’étranglement auquel sont confrontés la plupart des programmes actuels, cela signifie que le fait de modifier votre programme afin d’augmenter la mémoire peut entraîner une amélioration des performances, même si cela nécessite de comparer votre compteur à une valeur non nulle. Dans certains de mes programmes, j’ai constaté une amélioration significative des performances en modifiant le code pour augmenter la mémoire au lieu de le réduire.

Sceptique? Voici le résultat que j’ai obtenu:

 sum up = 705046256 sum down = 705046256 Ave. Up Memory = 4839 mus Ave. Down Memory = 5552 mus sum up = inf sum down = inf Ave. Up Memory = 18638 mus Ave. Down Memory = 19053 mus 

de l’exécution de ce programme:

 #include  #include  #include  #include  template void FillWithRandomNumbers(Iterator start, Iterator one_past_end, T a, T b) { std::random_device rnd_device; std::mt19937 generator(rnd_device()); std::uniform_int_dissortingbution dist(a, b); for (auto it = start; it != one_past_end; it++) *it = dist(generator); return ; } template void FillWithRandomNumbers(Iterator start, Iterator one_past_end, double a, double b) { std::random_device rnd_device; std::mt19937_64 generator(rnd_device()); std::uniform_real_dissortingbution dist(a, b); for (auto it = start; it != one_past_end; it++) *it = dist(generator); return ; } template inline void sum_abs_up(RAI first, RAI one_past_last, T &total) { T sum = 0; auto it = first; do { sum += *it; it++; } while (it != one_past_last); total += sum; } template inline void sum_abs_down(RAI first, RAI one_past_last, T &total) { T sum = 0; auto it = one_past_last; do { it--; sum += *it; } while (it != first); total += sum; } template std::chrono::nanoseconds TimeDown( std::vector &vec, const std::vector &vec_original, std::size_t num_repititions, T &running_sum) { std::chrono::nanoseconds total{0}; for (std::size_t i = 0; i < num_repititions; i++) { auto start_time = std::chrono::high_resolution_clock::now(); sum_abs_down(vec.begin(), vec.end(), running_sum); total += std::chrono::high_resolution_clock::now() - start_time; vec = vec_original; } return total; } template std::chrono::nanoseconds TimeUp( std::vector &vec, const std::vector &vec_original, std::size_t num_repititions, T &running_sum) { std::chrono::nanoseconds total{0}; for (std::size_t i = 0; i < num_repititions; i++) { auto start_time = std::chrono::high_resolution_clock::now(); sum_abs_up(vec.begin(), vec.end(), running_sum); total += std::chrono::high_resolution_clock::now() - start_time; vec = vec_original; } return total; } int main() { std::size_t num_repititions = 1 << 10; { typedef int ValueType; auto lower = std::numeric_limits::min(); auto upper = std::numeric_limits::max(); std::vector vec(1 << 24); FillWithRandomNumbers(vec.begin(), vec.end(), lower, upper); const auto vec_original = vec; ValueType sum_up = 0, sum_down = 0; auto time_up = TimeUp(vec, vec_original, num_repititions, sum_up).count(); auto time_down = TimeDown(vec, vec_original, num_repititions, sum_down).count(); std::cout << "sum up = " << sum_up << '\n'; std::cout << "sum down = " << sum_down << '\n'; std::cout << "Ave. Up Memory = " << time_up/(num_repititions * 1000) << " mus\n"; std::cout << "Ave. Down Memory = "<< time_down/(num_repititions * 1000) << " mus" << std::endl; } { typedef double ValueType; auto lower = std::numeric_limits::min(); auto upper = std::numeric_limits::max(); std::vector vec(1 << 24); FillWithRandomNumbers(vec.begin(), vec.end(), lower, upper); const auto vec_original = vec; ValueType sum_up = 0, sum_down = 0; auto time_up = TimeUp(vec, vec_original, num_repititions, sum_up).count(); auto time_down = TimeDown(vec, vec_original, num_repititions, sum_down).count(); std::cout << "sum up = " << sum_up << '\n'; std::cout << "sum down = " << sum_down << '\n'; std::cout << "Ave. Up Memory = " << time_up/(num_repititions * 1000) << " mus\n"; std::cout << "Ave. Down Memory = "<< time_down/(num_repititions * 1000) << " mus" << std::endl; } return 0; } 

sum_abs_up et sum_abs_down font la même chose et sont chronométrés de la même manière, la seule différence étant que sum_abs_up augmente la mémoire, tandis que sum_abs_down diminue la mémoire. Je passe même vec par référence pour que les deux fonctions accèdent aux mêmes emplacements mémoire. Néanmoins, sum_abs_up est toujours plus rapide que sum_abs_down . Donnez-vous une course (je l'ai compilé avec g ++ -O3).

FYI vec_original est disponible à des fins d’expérimentation afin de faciliter la modification de sum_abs_up et sum_abs_down de manière à les rendre vec tout en ne permettant pas à ces modifications d’affecter les timings futurs.

Il est important de noter à quel point la boucle est serrée. Si le corps d'une boucle est volumineux, peu importe si son iterator monte ou descend de la mémoire, car le temps qu'il faudra pour exécuter le corps de la boucle dominera probablement complètement. En outre, il est important de mentionner qu'avec certaines boucles rares, il est parfois plus rapide de perdre de la mémoire que de la remonter. Mais même avec de telles boucles, il est rarement le cas que la montée soit toujours plus lente que la descente (à la différence des boucles qui remontent la mémoire, qui sont souvent toujours plus rapides que les boucles équivalentes à la mémoire; 40 fois +% plus vite).

En règle générale, si vous avez l'option, si le corps de la boucle est petit et qu'il y a peu de différence entre le fait que votre boucle augmente la mémoire au lieu de la baisser, vous devez augmenter la mémoire.