le plus rapide

Version imprimable

le plus rapide

Bonjour,
je me demandai si entre ces deux ecriture il y aura une differance de performance et pourquoi?
Code:

1 2 3 4 5 6 7 8 9 10 11 12 int h ; int w; std::vector<char> buffer; chargerBuffer(buffer,h,w); std::vector<float> bufferout(buffer.size()); for(int i=0;i<h;++i) for (int j =1;j<w;++j) { bufferout[i*w+j] = buffer[i*w+j]-buffer[i*w+j-1]; }
et
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int h ; int w; std::vector<char> buffer; chargerBuffer(buffer,h,w); std::vector<float> bufferout(buffer.size()); for(int i=0;i<h;++i) { std::vector<char>::iterator itIn =buffer.begin() + i*w; std::vector<float>::iterator itout =bufferout.begin()+i*w; for (int j =1;j<w;++j) { *(itout +j) = *(itIn +j)-(itIn +j-1); } }
A mon avis les multiplication en moins ne change rien.
Je me demande si il y aurait pas une différence au niveau du chargement de la memoire pour le CPU, et que l'écriture 2 est meilleur.

Une autre question, est il vrai que le parcoure d'un tableau est plus rapide quand on va de la fin au debut?

merci

Théoriquement, tu peux faire beaucoup plus lisible et peut-être même plus optimal si tu ne fait pas des somme entre itérateur et valeurs à chaque fois. Genre :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int h ;
int w;
std::vector<char> buffer;
chargerBuffer(buffer,h,w);
 
std::vector<float> bufferout(buffer.size());
 
std::vector<char>::const_iterator itIn = buffer.begin();
std::vector<float>::iterator itOut =bufferout.begin();
 
for(int i=0;i<h;++i)
{
  std::vector<char>::const_iterator itInDecal = itIn;
  std::advance(itIn, 1);
  std::advance(itOut, 1);
 
  for (int j =1;j<w;++j)
  {
    *(itout +j) = *(itIn +j)-(itIn +j-1);
    ++itOut;
    ++itIn;
    ++itInDecal;
  }
 }

23/11/2007, 17h20
Sylvain Togni
Citation:
Envoyé par Mongaulois

Code:

1 2 3 4 5 for(int i=0;i<h;++i) for (int j =1;j<w;++j) { bufferout[i*w+j] = buffer[i*w+j]-buffer[i*w+j-1]; }
Les compilateurs savent assez bien identifier les invariants d'une boucle simple et optimiser comme il faut le code ci-dessus.

Il n'y a, à mon avis, rien a gagner en performance à réécrire ce code différemment.

Citation:

Une autre question, est il vrai que le parcoure d'un tableau est plus rapide quand on va de la fin au debut?

Non, il n'y a pas de raison pour que cela soit plus rapide.

Seule exception : si on parcours deux fois de suite une zone mémoire de taille légèrement supérieur à la taille du cache mémoire du processeur.

Si les deux parcours se font dans le même sens, 0% des données seront dans le cache lors du deuxième parcours.

S'ils se font dans des sens opposés, près de 100% des données seront dans le cache.
25/11/2007, 12h12
yan
EN faite c'etait la partie chargement de memoire que j'ai du mal a comprendre.
Ce que je semble comprendre( mais je sait qu'il y as un tru cqui cloche :aie:) est dans le cas :

Code:

- buffer[i*w+j]

il va charger dans le cash la zone ou se trouve l'element (si il n'y est pas deja) ce qu'il fait que lorsquel'on fait buffer[i*w+j] - buffer[(i-1)*w+j],il va charger une zone memoire pui une autre puis recharge l'encienne puis .... ce qu'il fazit une perte de temps.
Code:

1 2 std::vector<char>::iterator itIn =buffer.begin() + i*w; std::vector<float>::iterator itout =bufferout.begin()+(i+1)*w;
Il va charger deux zone memoire car deux "pointeur". Et donc moins de rechargement pendant une operation.

Si quelqu'un pourrai me donner un tuto ou autre expliquant cela...
Merci pour vos reponse
26/11/2007, 09h44
yan

Dite moi si vous n'avez rien compris.... :cry:
26/11/2007, 14h10
yan

Bon je croit que je me suis pas fait comprendre. Je vais poser la question différemment...
As un instant t, je doit accéder à deux éléments contenue dans un grand trés buffer. Et cela successivement suivant une boucle. Maintenant, quel est le plus rapide pour le CPU :
1-avoir un seul pointeur sur le début du buffer et de calculer à l'id de chaque l'élément un a prés l'autre. Ce qui pourrait représenter au pire , comme un chargement et un dechargement à chaque fois que l'on veut accéder a un element eloigné l'un de l'autre (car même pointeur et deux zone mémoire éloigné)

2- avoir deux pointeurs, l'un pour le premier élément et l'autre pour le second. Ainsi le CPU charge une zone memoire pour chaque pointeur et les rechargent uniquement quand on en as besoin.

3- C'est pareil
26/11/2007, 14h13
Matthieu Brucher

Dans les deux cas, tes données seront en cache si tu accèdes à des données proches. Si tu n'as que deux pointeurs, ça sera plus rapide a priori car dans l'autre cas, tu as un calcul pour obtenir l'offset dans le tableau (multiplication + addition).
26/11/2007, 14h23
yan

Citation:

Envoyé par Miles

Dans les deux cas, tes données seront en cache si tu accèdes à des données proches. Si tu n'as que deux pointeurs, ça sera plus rapide a priori car dans l'autre cas, tu as un calcul pour obtenir l'offset dans le tableau (multiplication + addition).

Ok. Donc il n'y as toujours qu'une zone de la mémoire chargé par le CPU. Il faut donc optimiser les accés au elements les plus proche avant d'accéder au élément les plus éloigné. Comme lors d'un filtrage 2D sur une image. C'est bien cela?
26/11/2007, 14h28
Matthieu Brucher

Il peut y en avoir plusieurs, le cache est constitué de plusieurs pages qui sont mises à jour en fonction de ce qui est accédé. De préférence, il faut effectivement utiliser les données proches de celles déjà utilisées.
26/11/2007, 14h34
yan

Citation:

Envoyé par Miles

Il peut y en avoir plusieurs, le cache est constitué de plusieurs pages qui sont mises à jour en fonction de ce qui est accédé. De préférence, il faut effectivement utiliser les données proches de celles déjà utilisées.

Donc juste pour conclure,
utiliser plusieur pointeur pourrai permettre d'avoir plusieurs morceau du même buffer en cache. Contrairement à un pointeur. Ou alors c'est indépendant...
27/11/2007, 09h43
yan

Dit d'une autre manier,
dans le cas ou on accède à des elements, utiliser un ou plusieurs pointeur va t'il influencer les pages mise en cache?
27/11/2007, 22h54
yan

personne ne sait?
27/11/2007, 22h56
Matthieu Brucher

C'est l'adresse mémoire qui compte, pas le nombre de références à cet espace mémoire ;)
27/11/2007, 22h59
yan

merci. :king:
j'arrêterai de réfléchir dessus comme ca.
Ca me paraissait bizzare. Mais bon, sait on jamais...:aie: