Compte à rebours en boucle

Question

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

J'ai actuellement ceci:

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

mon 'i' est un resgister non signé, aussi 'domaine' est unsigned int

dans la boucle for i est utilisé pour parcourir un tableau, par exemple

array[i] = do stuff

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

Je peux imaginer que la réponse est assez triviale, 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 a du sens).

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

S'il vous plaît, aidez-nous.

Answer 1

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

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

Dans ce cas, étant donné que i est unsigned , 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 signer i , soit de changer la condition dans la boucle for comme suit:

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

Ou compter de domaine à 1 plutôt que de domaine - 1 à 0 :

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

Answer 2

Il existe une seule méthode correcte pour effectuer une boucle arrière en utilisant 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 parce que 1 > 0, alors i = 0 dans le corps de la boucle. À la prochaine itération, je-- > 0 échoue car i == 0, le décrément postfixel n'a donc pas d'importance.

Je sais que ce n'est pas évident.

Answer 3

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

Ce type d’optimisation n’est absolument pas pertinent et devrait être laissé au compilateur (le cas échéant).

Avez-vous profilé votre programme pour vérifier que votre boucle for est un goulot d'étranglement? Si non, alors vous n'avez pas besoin de passer du temps à vous inquiéter à ce sujet. Encore plus, avoir " i " en tant que "registre" int, comme vous écrivez, n’a aucun sens réel du point de vue de la performance.

Même si je ne connais pas votre domaine de problème, je peux vous garantir que la technique de la boucle inverse et le "registre" int counter aura un impact négligeable sur les performances de votre programme. N'oubliez pas que "l'optimisation prématurée est la racine de tous les maux".

Cela dit, il serait préférable de consacrer plus de temps à l'optimisation en réfléchissant à la structure globale du programme, aux structures de données et aux algorithmes utilisés, à l'utilisation des ressources, etc.

Answer 4

Vérifier si un nombre est égal à zéro peut être plus rapide ou plus efficace qu'une comparaison. Mais c’est là le type de micro-optimisation dont vous ne devriez vraiment pas vous inquiéter - quelques cycles d’horloge seront considérablement minimisés par à peu près tout autre problème de performance.

Sur x86:

dec eax
jnz Foo

Au lieu de:

inc eax
cmp eax, 15
jl Foo

Answer 5

Si vous avez un compilateur correct, il optimisera le "décompte". de manière aussi efficace que "compte à rebours". Essayez juste quelques repères et vous verrez.

Answer 6

Vous avez donc "lu". ce 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.

Answer 7

Lorsque vous parcourez des structures de données de toutes sortes, les erreurs de cache ont un impact beaucoup plus important que la direction dans laquelle vous vous dirigez. Concentrez-vous sur l’ensemble de la structure de la mémoire et de la structure des algorithmes plutôt que sur des micro-optimisations triviales.

Answer 8

Cela n'a rien à voir avec le comptage up ou down . Ce qui peut être plus rapide, c'est compter vers zéro . La réponse de Michael montre pourquoi & # 8212; x86 vous donne une comparaison avec zéro comme effet secondaire implicite de nombreuses instructions. Ainsi, une fois que vous avez ajusté votre compteur, vous devez simplement créer une branche 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 ceci:

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 à la place, ce qui provoque une confusion et une panique sans précédent pour les programmeurs qui pensent que leurs boucles tournent en arrière.)

L’idée est que même avec l’instruction supplémentaire Inc ou Dec , le gain en termes de temps d’exécution reste supérieur à celui de la comparaison explicite. Si vous pouvez réellement remarquer que cette différence est à débattre.

Cependant, notez que la conversion est une opération que le compilateur ferait automatiquement , selon que la transformation est jugée rentable ou non. Le compilateur optimise généralement mieux le code que vous-même. Ne vous efforcez donc pas trop de le concurrencer.

Quoi qu'il en soit, vous avez posé des questions sur C ++, pas sur Pascal. C ++ "pour" Les boucles ne sont pas aussi faciles à appliquer à cette optimisation que Pascal "pour" les boucles sont dues au fait que 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 du contenu de la boucle. Les compilateurs C ++ doivent effectuer un certain nombre d'analyses 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'analyse, il pourrait effectuer une transformation similaire.

Rien ne vous empêche d'écrire vos boucles de cette façon par vous-même:

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

Faire cela pourrait faire fonctionner votre code plus rapidement. 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 parfaitement "& ordinaire; pour". boucle, mais il ne ressemble plus à un & # 8212; il 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 & # 8212; de sorte que toute personne lisant votre code (y compris vous, une semaine, un mois ou une année à compter de maintenant, lorsque vous aurez 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 en effet une boucle déguisée ordinaire.

(Avez-vous remarqué que mon code ci-dessus utilisait des variables non signées sans danger de virer à 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. Faites en sorte qu'un code ordinaire ait l'air ordinaire afin qu'il ne soit pas concurrencé par un code spécial pour attirer l'attention des utilisateurs 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é.

Answer 9

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))

Vous pouvez maintenant 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 

Answer 10

Difficile à dire avec les informations données mais ... inversez votre tableau et décomptez?

Answer 11

Jeremy Ruten a souligné à 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’avais 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 ...)
}

Ce formulaire tire parti de l'indicateur de condition défini sur les certains processeurs après des opérations arithmétiques. Sur certaines architectures, les décrémentations et les tests relatifs à la condition de branche peuvent être combinés en une seule instruction. Notez que l’utilisation de prédécrément ( - i ) est la clé: l’utilisation de postdécrément ( i - ) n’aurait pas aussi bien fonctionné.

Sinon,

// 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 pointeur (adresse). Je vois rarement la forme (pointeur - int) de nos jours (pour une bonne raison), mais le langage garantit que lorsque vous soustrayez un int à un pointeur, le pointeur est décrémenté par (int * sizeof (* pointeur)) .

Je soulignerai à nouveau 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.

Answer 12

Dans certains noyaux 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 les boucles à incrémentation.

Je ne sais pas pourquoi il n'y a pas d'instruction d'incrément de comparaison aussi.

Je suis surpris que ce message ait été voté -1 lorsqu'il s'agit d'un véritable problème.

Answer 13

Tout le monde ici se concentre sur la performance. Il existe en fait une raison logique pour itérer vers zéro qui peut générer 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 savons 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 les éléments défectueux en les échangeant avec une extrémité du tableau et en modifiant les limites du tableau pour les exclure.

Alors évidemment:

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

Cela implique donc:

3. Si nous nous éloignons de la variable liée, les éléments entre la variable liée et le pointeur d'itération actuel se sont révélés 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:

4. 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.

Answer 14

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'accès à 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 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

d'exécuter ce programme:

#include <chrono>
#include <iostream>
#include <random>
#include <vector>

template<class Iterator, typename T>
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_distribution<T> dist(a, b);
  for (auto it = start; it != one_past_end; it++)
    *it = dist(generator);
  return ;
}

template<class Iterator>
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_distribution<double> dist(a, b);
  for (auto it = start; it != one_past_end; it++)
    *it = dist(generator);
  return ;
}

template<class RAI, class T>
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<class RAI, class T>
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<class T> std::chrono::nanoseconds TimeDown(
                      std::vector<T> &vec, const std::vector<T> &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<class T> std::chrono::nanoseconds TimeUp(
                      std::vector<T> &vec, const std::vector<T> &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<ValueType>::min();
  auto upper = std::numeric_limits<ValueType>::max();
  std::vector<ValueType> 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<ValueType>::min();
  auto upper = std::numeric_limits<ValueType>::max();
  std::vector<ValueType> 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 monte en mémoire alors que < code> sum_abs_down réduit la mémoire. Je passe même vec par référence afin 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 . Lancez-vous vous-même (je l'ai compilé avec g ++ -O3).

FYI vec_original est disponible à des fins d’expérimentation; il m’est plus facile de changer sum_abs_up et sum_abs_down de manière à les modifier < code> vec tout en empêchant ces modifications d’affecter les timings futurs.

Il est important de noter à quel point la boucle que je chronomètre est serrée. Si le corps d'une boucle est volumineux, peu importe que son itérateur monte ou descende en mémoire, le temps qu'il faudra pour exécuter le corps de la boucle n'aura probablement aucune importance. 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 l'augmenter. Mais même avec de telles boucles, il est rarement le cas que la montée soit toujours plus lente que la descente (contrairement aux 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, le corps de la boucle est petit et s'il y a peu de différence entre le fait que votre boucle augmente la mémoire au lieu de la baisser, vous devez le faire.