pourquoi éviter une puissance de 2 du dim tableau pour optimisation
12 réponses
poulacou
Sur quelques documents qui relatent les bons usages du codage par
soucis d'optimisation d'execution,
il est mentionn=E9 :
- d'=E9viter d'avoir une dimension de tableau =E9gal =E0 une puissance de 2
Je comprend pas trop cette recommandation ... m=EAme au contraire, dans
mon esprit je l'aurai encourag=E9 ! essayer au maximum des tailles de
tableau multiple du cache de donn=E9es L1 et L2
En esperant que vous ayez compris mon int=E9rrogation,
Merci pour vos eclaircissements
En news:fhm765$tdk$, Patrick 'Zener' Brunet va escriure:
...alors allouer 4 octets de moins qu'un multiple de cette puissance est une optimisation,
... qui ne marche QUE si l'implémentation de malloc() réserve 4 octets ou moins pour sa gestion interne.
Si par contre cette dite implémentation utilise une taille sur 6 ou 8 octets pour la taille, ou si elle stocke en plus un détrompeur (cookie) pour repérer les allocations-désallocations mal faites, ou deux pointeurs 32 bits sur les blocs suivant et précédent, l'optimisation est prise gravement en défaut.
Par ailleurs, si la taille du bloc alloué est stockée en dehors du bloc (par exemple, dans le malloc() rapide, où les blocs ont toujours des tailles multiples de 2, et où l'adresse du bloc indique de quel tas il provient donc de quel taille il s'agit; ou si on utilise une mémoire segmentée, et où chaque bloc est un segment à lui tout seul), tu punis inutilement le programme.
Antoine
En news:fhm765$tdk$1@shakotay.alphanet.ch, Patrick 'Zener' Brunet va
escriure:
...alors allouer 4 octets de moins qu'un multiple
de cette puissance est une optimisation,
... qui ne marche QUE si l'implémentation de malloc() réserve 4 octets ou
moins pour sa gestion interne.
Si par contre cette dite implémentation utilise une taille sur 6 ou 8 octets
pour la taille, ou si elle stocke en plus un détrompeur (cookie) pour
repérer les allocations-désallocations mal faites, ou deux pointeurs 32 bits
sur les blocs suivant et précédent, l'optimisation est prise gravement en
défaut.
Par ailleurs, si la taille du bloc alloué est stockée en dehors du bloc (par
exemple, dans le malloc() rapide, où les blocs ont toujours des tailles
multiples de 2, et où l'adresse du bloc indique de quel tas il provient donc
de quel taille il s'agit; ou si on utilise une mémoire segmentée, et où
chaque bloc est un segment à lui tout seul), tu punis inutilement le
programme.
En news:fhm765$tdk$, Patrick 'Zener' Brunet va escriure:
...alors allouer 4 octets de moins qu'un multiple de cette puissance est une optimisation,
... qui ne marche QUE si l'implémentation de malloc() réserve 4 octets ou moins pour sa gestion interne.
Si par contre cette dite implémentation utilise une taille sur 6 ou 8 octets pour la taille, ou si elle stocke en plus un détrompeur (cookie) pour repérer les allocations-désallocations mal faites, ou deux pointeurs 32 bits sur les blocs suivant et précédent, l'optimisation est prise gravement en défaut.
Par ailleurs, si la taille du bloc alloué est stockée en dehors du bloc (par exemple, dans le malloc() rapide, où les blocs ont toujours des tailles multiples de 2, et où l'adresse du bloc indique de quel tas il provient donc de quel taille il s'agit; ou si on utilise une mémoire segmentée, et où chaque bloc est un segment à lui tout seul), tu punis inutilement le programme.
Antoine
Patrick 'Zener' Brunet
Bonsoir.
"Antoine Leca" a écrit dans le message de news: fhs426$nvl$
En news:fhm765$tdk$, Patrick 'Zener' Brunet va escriure:
...alors allouer 4 octets de moins qu'un multiple de cette puissance est une optimisation,
... qui ne marche QUE si l'implémentation de malloc() réserve 4 octets ou moins pour sa gestion interne.
Si par contre cette dite implémentation utilise une taille sur 6 ou 8 octets
pour la taille, ou si elle stocke en plus un détrompeur (cookie) pour repérer les allocations-désallocations mal faites, ou deux pointeurs 32 bits
sur les blocs suivant et précédent, l'optimisation est prise gravement en défaut.
Par ailleurs, si la taille du bloc alloué est stockée en dehors du bloc (par
exemple, dans le malloc() rapide, où les blocs ont toujours des tailles multiples de 2, et où l'adresse du bloc indique de quel tas il provient donc
de quel taille il s'agit; ou si on utilise une mémoire segmentée, et où chaque bloc est un segment à lui tout seul), tu punis inutilement le programme.
Je suis innocent Antoine :-)
J'ai bien écrit: "Evidemment tout dépend de l'algorithme et de ses réglages".
En effet, en plus du header caché (de taille variable c'est vrai, mais formellement il contient l'information de taille et un bit indiquant l'état libre/alloué, sauf bien sûr en mode debug ou ça peut être plus bavard) indispensable pour les algorithmes à tailles libres, on prévoit souvent une sentinelle en fin de bloc... Il y en a même qui y conservent les pointeurs de chaînage pour les bocs alloués... J'avais voulu faire simple dans ma démo.
Concernant les algorithmes à ségrégation, en effet on n'a pas forcément besoin de header, par contre la taille de bloc n'est pas forcément binaire: il y a des algos en 1/4 + 3/4 et j'en ai écrit un qui utilise 4 classes par niveau d'échelle.
Bref ce que je voulais dire c'est qu'il n'y a pas de recette magique, la recommandation sur laquelle s'interrogeait "poucalou" *peut être justifiée* dans un contexte particulier, je donnais donc *un exemple* concret, mais il n'est pas correct d'en faire une règle générale.
Bref si on veut optimiser, il faut en savoir plus sur les outils sous-jacents.
-- Cordialement. -- /************************************************** * Patrick BRUNET * E-mail: lien sur http://zener131.free.fr/ContactMe **************************************************/
Bonsoir.
"Antoine Leca" <root@localhost.invalid> a écrit dans le message de news:
fhs426$nvl$1@shakotay.alphanet.ch...
En news:fhm765$tdk$1@shakotay.alphanet.ch, Patrick 'Zener' Brunet va
escriure:
...alors allouer 4 octets de moins qu'un multiple
de cette puissance est une optimisation,
... qui ne marche QUE si l'implémentation de malloc() réserve 4 octets ou
moins pour sa gestion interne.
Si par contre cette dite implémentation utilise une taille sur 6 ou 8
octets
pour la taille, ou si elle stocke en plus un détrompeur (cookie) pour
repérer les allocations-désallocations mal faites, ou deux pointeurs 32
bits
sur les blocs suivant et précédent, l'optimisation est prise gravement en
défaut.
Par ailleurs, si la taille du bloc alloué est stockée en dehors du bloc
(par
exemple, dans le malloc() rapide, où les blocs ont toujours des tailles
multiples de 2, et où l'adresse du bloc indique de quel tas il provient
donc
de quel taille il s'agit; ou si on utilise une mémoire segmentée, et où
chaque bloc est un segment à lui tout seul), tu punis inutilement le
programme.
Je suis innocent Antoine :-)
J'ai bien écrit:
"Evidemment tout dépend de l'algorithme et de ses réglages".
En effet, en plus du header caché (de taille variable c'est vrai, mais
formellement il contient l'information de taille et un bit indiquant l'état
libre/alloué, sauf bien sûr en mode debug ou ça peut être plus bavard)
indispensable pour les algorithmes à tailles libres, on prévoit souvent une
sentinelle en fin de bloc... Il y en a même qui y conservent les pointeurs
de chaînage pour les bocs alloués...
J'avais voulu faire simple dans ma démo.
Concernant les algorithmes à ségrégation, en effet on n'a pas forcément
besoin de header, par contre la taille de bloc n'est pas forcément binaire:
il y a des algos en 1/4 + 3/4 et j'en ai écrit un qui utilise 4 classes par
niveau d'échelle.
Bref ce que je voulais dire c'est qu'il n'y a pas de recette magique, la
recommandation sur laquelle s'interrogeait "poucalou" *peut être justifiée*
dans un contexte particulier, je donnais donc *un exemple* concret, mais il
n'est pas correct d'en faire une règle générale.
Bref si on veut optimiser, il faut en savoir plus sur les outils
sous-jacents.
--
Cordialement.
--
/**************************************************
* Patrick BRUNET
* E-mail: lien sur http://zener131.free.fr/ContactMe
**************************************************/
"Antoine Leca" a écrit dans le message de news: fhs426$nvl$
En news:fhm765$tdk$, Patrick 'Zener' Brunet va escriure:
...alors allouer 4 octets de moins qu'un multiple de cette puissance est une optimisation,
... qui ne marche QUE si l'implémentation de malloc() réserve 4 octets ou moins pour sa gestion interne.
Si par contre cette dite implémentation utilise une taille sur 6 ou 8 octets
pour la taille, ou si elle stocke en plus un détrompeur (cookie) pour repérer les allocations-désallocations mal faites, ou deux pointeurs 32 bits
sur les blocs suivant et précédent, l'optimisation est prise gravement en défaut.
Par ailleurs, si la taille du bloc alloué est stockée en dehors du bloc (par
exemple, dans le malloc() rapide, où les blocs ont toujours des tailles multiples de 2, et où l'adresse du bloc indique de quel tas il provient donc
de quel taille il s'agit; ou si on utilise une mémoire segmentée, et où chaque bloc est un segment à lui tout seul), tu punis inutilement le programme.
Je suis innocent Antoine :-)
J'ai bien écrit: "Evidemment tout dépend de l'algorithme et de ses réglages".
En effet, en plus du header caché (de taille variable c'est vrai, mais formellement il contient l'information de taille et un bit indiquant l'état libre/alloué, sauf bien sûr en mode debug ou ça peut être plus bavard) indispensable pour les algorithmes à tailles libres, on prévoit souvent une sentinelle en fin de bloc... Il y en a même qui y conservent les pointeurs de chaînage pour les bocs alloués... J'avais voulu faire simple dans ma démo.
Concernant les algorithmes à ségrégation, en effet on n'a pas forcément besoin de header, par contre la taille de bloc n'est pas forcément binaire: il y a des algos en 1/4 + 3/4 et j'en ai écrit un qui utilise 4 classes par niveau d'échelle.
Bref ce que je voulais dire c'est qu'il n'y a pas de recette magique, la recommandation sur laquelle s'interrogeait "poucalou" *peut être justifiée* dans un contexte particulier, je donnais donc *un exemple* concret, mais il n'est pas correct d'en faire une règle générale.
Bref si on veut optimiser, il faut en savoir plus sur les outils sous-jacents.
-- Cordialement. -- /************************************************** * Patrick BRUNET * E-mail: lien sur http://zener131.free.fr/ContactMe **************************************************/
