Discussion :

[yan]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Matthieu Brucher]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
  }
 }

[Sylvain Togni]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

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.

[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 ) est dans le cas :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Sélectionner tout - Visualiser dans une fenêtre à part

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

[yan]

Dite moi si vous n'avez rien compris....

[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

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

[yan]

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?

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

[yan]

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

[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?

[yan]

personne ne sait?

[Matthieu Brucher]

C'est l'adresse mémoire qui compte, pas le nombre de références à cet espace mémoire

[yan]

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