pourquoi éviter une puissance de 2 du dim tableau pour optimisation

Le
poulacou
Sur quelques documents qui relatent les bons usages du codage par
soucis d'optimisation d'execution,
il est mentionné :
- d'éviter d'avoir une dimension de tableau égal à une puissance de 2

Je comprend pas trop cette recommandation même au contraire, dans
mon esprit je l'aurai encouragé ! essayer au maximum des tailles de
tableau multiple du cache de données L1 et L2

En esperant que vous ayez compris mon intérrogation,
Merci pour vos eclaircissements

Bien amicalement
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Pierre Maurette
Le #999260
Sur quelques documents qui relatent les bons usages du codage par
soucis d'optimisation d'execution,
il est mentionné :
- d'éviter d'avoir une dimension de tableau égal à une puissance de 2

Je comprend pas trop cette recommandation ... même au contraire, dans
mon esprit je l'aurai encouragé ! essayer au maximum des tailles de
tableau multiple du cache de données L1 et L2


Je ne vois pas immédiatement la relation avec l'optimisation. Mais à
mon avis le fait que choisir une puissance de 2 et à fortiori la taille
d'une segment - par exemple - peut être une fausse bonne idée est en
rapport avec la règle "one past the last element". En gros, l'adresse
qui /pointerait/ vers le premier élément suivant un tableau doit être
évaluable, sans bien entendu être déréférençable. En gros on a le droit
d'écrire:
if(ptr < ptrlastelement + 1) {/* */}

Je vais maintenant attendre les Leca's éclaircissements ;-)

--
Pierre Maurette

Antoine Leca
Le #999259
En news:,
poulacou va escriure:
Sur quelques documents qui relatent les bons usages du codage par
soucis d'optimisation d'execution,
il est mentionné :
- d'éviter d'avoir une dimension de tableau égal à une puissance de 2


L'original est-il en français ou en anglais ?

Pris à la lettre, c'est une idiotie : cela prohibe les tableaux à une
dimension (2°) et les matrices à deux dimensions (2¹), qui sont de loin les
plus communs.
Donc soit c'est mal écrit, soit beaucoup plus probable, c'est mal traduit ;
et si c'est mal traduit, en cherchant la version originale peut-être que tu
vas trouver des pistes d'explication.

Et accessoirement, le rapport avec le langage C.


Antoine

Jean-Marc Bourguet
Le #999257
"Antoine Leca"
En news:,
poulacou va escriure:
Sur quelques documents qui relatent les bons usages du codage par
soucis d'optimisation d'execution,
il est mentionné :
- d'éviter d'avoir une dimension de tableau égal à une puissance de 2


L'original est-il en français ou en anglais ?

Pris à la lettre, c'est une idiotie : cela prohibe les tableaux à une
dimension (2°) et les matrices à deux dimensions (2¹), qui sont de loin les
plus communs.


Il me semble que tu confondes les dimensions et le nombre de dimension.

A+

--
Jean-Marc
FAQ de fclc: http://www.isty-info.uvsq.fr/~rumeau/fclc
Site de usenet-fr: http://www.usenet-fr.news.eu.org


Jean-Marc Bourguet
Le #999256
poulacou
Sur quelques documents qui relatent les bons usages du codage par
soucis d'optimisation d'execution,
il est mentionné :
- d'éviter d'avoir une dimension de tableau égal à une puissance de 2

Je comprend pas trop cette recommandation ... même au contraire, dans
mon esprit je l'aurai encouragé ! essayer au maximum des tailles de
tableau multiple du cache de données L1 et L2


J'ai l'impression que le probleme que ce conseil cherche a eviter est celui
de la resonnance dans les caches. Les caches sont rares parfaitement
associatif, donc le contenu d'une adresse ne peut etre stocke qu'a un
(direct-mapped), deux (two-way associative), quatre (four-way associative
-- on va rarement plus loin sans aller jusqu'au fully-associative) endroits
qui sont determine par les bits de poids "moyen" de l'adresse (les bits de
poids faible indiquant la position dans la ligne de cache). Si on accede a
des elements qui sont regulierement espace avec un espacement qui est un
sous-multiple ou un multiple de la taille du cache, ca diminue le nombre
d'endroit ou les donnees sont stockees, ce qui peut etre problematique si
des informations inutiles sont stockees dans le reste du cache. Ca pose
donc un probleme pour les tableaux de struct dont on accede regulierement
qu'a certains membres ou pour des tableaux multidimentionnels quand on les
parcours suivant d'autres directions que celle qui varie le plus
rapidement.

--
Jean-Marc
FAQ de fclc: http://www.isty-info.uvsq.fr/~rumeau/fclc
Site de usenet-fr: http://www.usenet-fr.news.eu.org

poulacou
Le #999120
On 12 nov, 12:26, "Antoine Leca"
Ennews:,
poulacou va escriure:

Sur quelques documents qui relatent les bons usages du codage par
soucis d'optimisation d'execution,
il est mentionné :




- d'éviter d'avoir une dimension de tableau égal à une puissance de 2


L'original est-il en français ou en anglais ?

Pris à la lettre, c'est une idiotie : cela prohibe les tableaux à une
dimension (2°) et les matrices à deux dimensions (2¹), qui sont de loin les
plus communs.
Donc soit c'est mal écrit, soit beaucoup plus probable, c'est mal tradu it ;
et si c'est mal traduit, en cherchant la version originale peut-être qu e tu
vas trouver des pistes d'explication.

Et accessoirement, le rapport avec le langage C.

Antoine



L'original est en anglais ...
"avoid leading array dimensions equal to a power of two"
http://www.ualberta.ca/CNS/RESEARCH/Courses/2007/Workshop/_07_CodeOpt/may20 07-opt.pdf
-> page 9
Il se peut que je confonde "dimensions" and "sizes"


poulacou
Le #999119
On 12 nov, 12:26, "Antoine Leca"
Ennews:,
poulacou va escriure:

Sur quelques documents qui relatent les bons usages du codage par
soucis d'optimisation d'execution,
il est mentionné :




- d'éviter d'avoir une dimension de tableau égal à une puissance de 2


L'original est-il en français ou en anglais ?

Pris à la lettre, c'est une idiotie : cela prohibe les tableaux à une
dimension (2°) et les matrices à deux dimensions (2¹), qui sont de loin les
plus communs.
Donc soit c'est mal écrit, soit beaucoup plus probable, c'est mal tradu it ;
et si c'est mal traduit, en cherchant la version originale peut-être qu e tu
vas trouver des pistes d'explication.

Et accessoirement, le rapport avec le langage C.

Antoine



L'original est en anglais ...
"avoid leading array dimensions equal to a power of two"
http://www.ualberta.ca/CNS/RESEARCH/Courses/2007/Workshop/_07_CodeOpt/may20 07-opt.pdf
-> page 9
Il se peut que je confonde "dimensions" and "sizes"


Vincent Lefevre
Le #999118
Dans l'article poulacou
L'original est en anglais ...
"avoid leading array dimensions equal to a power of two"
^^^^^^^


Effectivement, je pense que le point important est "leading".
Sinon, avec un parcours de certaines rangées, tu vas avoir des
problèmes de cache, car les accès consécutifs se feront à une
même adresse modulo une puissance de 2.

--
Vincent Lefèvre 100% accessible validated (X)HTML - Blog: Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)

Antoine Leca
Le #999117
En news:, Jean-Marc Bourguet va escriure:
Antoine Leca writes:
éviter d'avoir une dimension de tableau égal à une puissance de 2


Pris à la lettre, c'est une idiotie : cela prohibe les tableaux à une
dimension (2°) et les matrices à deux dimensions (2¹), qui sont de
loin les plus communs.


Il me semble que tu confondes les dimensions et le nombre de
dimension.


On m'avais appris (en français) qu'il y avait d'une part la dimension et
d'autre part le cardinal.


Antoine



Jean-Marc Bourguet
Le #999116
"Antoine Leca"
En news:, Jean-Marc Bourguet va escriure:
Antoine Leca writes:
éviter d'avoir une dimension de tableau égal à une puissance de 2


Pris à la lettre, c'est une idiotie : cela prohibe les tableaux à une
dimension (2°) et les matrices à deux dimensions (2¹), qui sont de
loin les plus communs.


Il me semble que tu confondes les dimensions et le nombre de
dimension.


On m'avais appris (en français) qu'il y avait d'une part la dimension et
d'autre part le cardinal.


Je ne me souviens pas avoir vu/entendu/lu quelqu'un utiliser cardinal pour
ça.

--
Jean-Marc
FAQ de fclc: http://www.isty-info.uvsq.fr/~rumeau/fclc
Site de usenet-fr: http://www.usenet-fr.news.eu.org




Patrick 'Zener' Brunet
Le #998658
Bonjour.

"poulacou"
Sur quelques documents qui relatent les bons usages du codage par
soucis d'optimisation d'execution,
il est mentionné :
d'éviter d'avoir une dimension de tableau égal à une puissance de 2

Je comprend pas trop cette recommandation ... même au contraire,
dans mon esprit je l'aurai encouragé ! essayer au maximum des tailles
de tableau multiple du cache de données L1 et L2


Hors contexte, je ne suis pas sûr que cela ait un rapport direct avec le
cache ou même les tableaux, mais...

Dans le cas d'une allocation de mémoire en général, comme l'algorithme
d'allocation doit conserver au minimum un tag de l'ordre de 4 octets caché
sous l'adresse de base du bloc (donc en p[-4] en général), et comme beaucoup
de tels algorithmes arrondissent la taille du bloc à un multiple d'une
certaine puissance de 2 (genre granularité de 16, 32 ou 64 octets),
...alors allouer 4 octets de moins qu'un multiple de cette puissance est une
optimisation, alors qu'allouer juste cette taille force l'algo à rajouter un
grain, donc à gaspiller de la mémoire.

Evidemment tout dépend de l'algorithme et de ses réglages, et l'importance
du phénomène dépend du nombre de blocs alloués (genre les algos en C++
plutôt, qui allouent des tonnes de petits noeuds avec 3 pointeurs et un
entier... qui vont occuper 32 ou 64 octets chacun).
Ensuite la "propagation générale des bonnes pratiques" peut avoir conduit à
préconiser ça dans vos documents...

Simple hypothèse...

--
Cordialement.
--
/**************************************************
* Patrick BRUNET
* E-mail: lien sur http://zener131.free.fr/ContactMe
**************************************************/

Publicité
Poster une réponse
Anonyme