Discussion :

[torNAdE]

Salut,

je voudrais savoir,pourquoi dans le cas de deux boucles imbriquées je dois mettre la boucle ayant le nombre maximum d'iterations la plus externe.

Svp j en ai bsoin pour mon PFE.

Merci.

[ol9245]

qu'est-ce qui te fait dire ça ?

[PRomu@ld]

Intuitivement, j'aurai plutôt dit le contraire.

De toute façon le nombre d'itération total sera le même, ça serait juste pour diminuer les calculs si tu dois faire des opérations avec la boucle la plus interne, mais hormis ce cas (somme toute extrêmement rare, et dans ce cas je doute que tu puisses inverser les boucles), je ne vois absolument pas l'intérêt d'échanger les boucles (si tant est que ça soit possible).

[millie]

Je dirais qu'il faut privilégier le sens pour lequel les accès sont le plus proche.

Par exemple, pour une image, qui en mémoire est stocké par ligne :

Code :

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

1
2
3
4
 
1 2 3 
4 5 6
7 8 9

Est stocké en mémoire comme ça :

Code :

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

1 2 3 4 5 6 7 8 9

Il vaut mieux parcourir l'image dans le sens de la ligne plutôt que dans le sens des colonnes.

Pourquoi cela ? Car il est souvent préferable de grouper les accès de zone proche. Car il est possible que des parties alignées soit mis dans le cache du processeur.

Cela dit, je n'ai jamais fait de benckmark sérieux.

Mais le système d'exploitation (ou autres) utilisent souvent le principe de la localité spatiale et temporelle pour optimiser les accès (que ce soit au niveau du disque dur (buffer cache) qu'au niveau de la mémoire (cache sur le processeur))

[PRomu@ld]

Oui, ça permet d'éviter les défauts de page, et de rendre ton programme "cache-friendly", suivant la machine les résultats sont plus ou moins importants. Mais en règle général, le compilateur peut réorganiser les boucles pour traiter ces cas.

En revanche, par rapport à la question originale, ça n'est pas la longueur de la boucle qui importera.

[Zavonen]

Le seul cas où on peut avoir à réfléchir sérieusement à ce problème c'est quand les boucles sont contrôlées par des instructions de sorties extraordinaires, par exemple en C 'continue' et 'break'.
Il faut de plus savoir quand on peut s'attendre à avoir ces sorties. Alors on peut s'attendre à des améliorations notables en imbriquant correctement les boucles, mais c'est au cas par cas.

[pseudocode]

je voudrais savoir,pourquoi dans le cas de deux boucles imbriquées je dois mettre la boucle ayant le nombre maximum d'iterations la plus externe.

??

Oui, moi aussi je voudrais bien savoir pourquoi ??!!!?

[progfou]

Ce n'est pas un devoir de mettre la boucle ayant le plus grand nombre d'itérations en amont, mais c'est souvent mieux, sauf si c'est contraire, comme le disait millie, au sens des données.

Un exemple, qui s'appelle le cache blocking :

Code :

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

1
2
3
4
5
6
7
For (i=0 ; i<10000 ; i++)
 
	for (j=0 ; j<10000 ; j++)
 
		for (k=0 ; k<10000 ; k++)
 
			C[j][k] += A[i][k]*B[j][i];

Dans ce cas précis, il y a un problème quand on est dans les boucles j/k, car A peut très bien ne plus se trouver en cache.
La solution en général, pour améliorer les choses :

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
for (i=0 ; i<10000 ; i++)
 
  for (j1=0 ; j1<100 ; j1++)
 
    for (k1=0 ; k1<100 ; k1++)
 
      for (j2=0 ; j2<100 ; j2++)
 
        for (k2=0 ; k2<100 ; k2++)
 
	{
 
	  j = j1*100 + j2;
 
	  k = k1*100 + k2;
 
 
 
	  C[j][k] += A[i][k]*B[j][i];
 
	}