Wikilivres

« Les opérations bit à bit/Les subtilités du XOR » : différence entre les versions

Navigation interactive dans l’historique
← Modification précédenteModification suivante →
Contenu supprimé Contenu ajouté
VisuelWikicode
Ligne 19 :
Pour résumer : MOV Ra -> Rb <=> Ra XOR 0 -> Rb
 
==ListesLes listes chainées XOR==
 
La propriété <math>a \oplus a = 0</math> est aussi utilisée pour créer des listes doublement chainées plus économes en mémoire que la normale, appelées '''listes liées par ou exclusif''', ou encore ''listes à chaînage XOR''.
 
Une liste doublement chainée normale stocke deux pointeurs : un vers le nœud suivant, et un vers le nœud précédent.
 
[[File:XorLinked1.png|centre|vignette|upright=2.0|Liste doublement chainée normale.]]
 
Les listes liées par ou exclusif (''XOR linked lists'') permettentremplacent deles stockerdeux unepointeurs valeurpar auun lieuseul deentier, deux pointeurs. Cette valeurqui contient le XOR entre leces pointeurdeux vers le prochain nœud, et le pointeur vers le nœud précédent. Son type doit donc être capable de stocker une adresse complète (64 bits sur les architectures 64 bits)pointeurs. Ainsi, on gagne un petit peu de mémoire : au lieu de stocker deux adresses, on n'en stocke plus qu'une. La consommation mémoire est identique à celle d'une liste simplement chainée.
 
[[File:XORlinked2.png|centre|vignette|upright=2.0|Liste chainée XOR.]]
 
Le: Dans ce qui suit, le pointeur sur le nœud précédent sera noté P (pour Précédent), le pointeur contenu dans le nœud actuellement visité est appelé Ptr et le pointeur vers le nœud suivant sera noté S (pour Suivant). Pour rappel, le pointeur stocké dans le nœud est égal au XOR entre P et S : <math>Ptr = P \oplus S</math>.
 
===Parcourir une liste liée par ou exclusif===
Ligne 75 :
Le premier inconvénient est le fait que l'on doive parcourir la liste à chaînage XOR du début à la fin. Impossible de revenir en arrière pendant le parcours de la liste chaînée, à moins d'utiliser une variable supplémentaire. Certes, revenir en arrière de cette manière est assez rare, mais cela peut avoir son utilité.
 
D'autresEnsuite, avantagesles desinsertions listeset doublementsretraits chaînéesdemandent normalesde neparcourir sonttoute pasla possiblesliste, sauf dans quelques cas assez rares, contrairement à ce qu'on a avec les listes à chaînagedoublement XORchainées. Par exemple, il est impossible de retirer un élément de la liste si on ne connaît que son adresse. Il est aussi impossible d'insérer un élément avant/après un élément repère si on ne connaît que l'adresse du dit repère. Pour simplifier, les insertions et retraits demandent de parcourir toute la liste, sauf dans quelques cas assez rares. Ce n'est pas le cas sur les listes sans chaînage XOR. Les 2 inconvénients sur le parcours en sens inverse et la modification à partir d'un pointeur sont résolus en utilisant deux pointeurs : un sur l'élément et un autre sur le suivant ou le précédent de l'élément pointé.
 
Enfin, de telles listes marchent assez mal avec les algorithmes de ramasse-miettes (''garbage collection''). Avec l'usage d'un ramasse-miette, la libération de la mémoire inutilisée est automatique. Les algorithmes de libération de la mémoire inutilisée se basent cependant sur l'usage de pointeurs. Pour être précis, ils analysent les données accessibles via les pointeurs d'un programmes pour déterminer la mémoire utile de la mémoire libre. Si les pointeurs sont cachées, comme dans les listes à chaînage XOR, les algorithmes ne peuvent pas les reconnaître et donnent un résultat sous-optimal. La libération de la mémoire se fait moins bien, ce qui peut poser quelques problèmes. Ironiquement, cela peut augmenter la consommation mémoire alors que le but du chaînage XOR est justement de la réduire. Cependant les langages à ramasse-miette n'autorisent pas les pointeurs, car le langage les gère. Il n'est donc pas possible d'implémenter de telles listes dans ces langages. Par contre, le problème peut se poser si un ramasse-miette est utilisé dans un langage qui n'en utilise pas nativement. En effet, il existe des librairies qui permettent d'ajouter un ramasse-miette dans des programmes codés en C ou en C++, un bon exemple étant le ''Boehm garbage collector''. L'usage d'une liste à chaînage XOR avec de telles librairies peut éventuellement poser quelques problèmes.
 
Ces inconvénients sont à comparer avec les avantages promis pour cette structure de données. L'avantage principal d'une liste à chaînage XOR est évidemment la consommation de mémoire, sa consommation mémoire étant équivalente à celle d'une liste chaînée simple. L'économie en mémoire est d'un pointeur par élément de la liste. Le gain et surtout sensible sur les longues listes chaînées, sur les machines où les pointeurs sont longs, et où chaque élément a une petite taille. Plus les éléments de la liste sont gros, moins l'économie est importante, rapportée au poids total de la liste chaînée. De plus, il existe d'autres solutions pour économiser de la mémoire avec les listes chaînées, comme les listes chaînées déroulées (''unrolled linked lists''). Tout cela expliquer que le chaînage XOR est actuellement peu , voire pas du tout, utilisé sur les machines modernes. Il peut éventuellement être utile sur quelques machines embarquées très peu puissantes, et encore !
 
{{NavChapitre | book=Les opérations bit à bit
Récupérée de « https://fr.wikibooks.org/wiki/Les_opérations_bit_à_bit/Les_subtilités_du_XOR »