Worldlex Wiki Codage CDR
( Apprenez comment et quand supprimer ce message ) En informatique, le codage CDR est une représentation compressée des données pour les listes chaînées Lisp . Il a été développ...
En informatique, le codage CDR est une représentation compressée des données pour les listes chaînées Lisp . Il a été développé et breveté par le Laboratoire d'intelligence artificielle du MIT , et implémenté dans le matériel informatique de plusieurs machines Lisp dérivées du MIT CADR .
Le codage CDR est en réalité un concept assez général : lorsqu'un objet de données A se termine par une référence à une autre structure de données B , on peut y insérer directement la structure B , qui chevauche A et s'étend jusqu'à son extrémité . Ce faisant, on libère l'espace occupé par la référence, ce qui peut s'avérer important si l'opération est répétée, et on améliore la localité des références , optimisant ainsi les performances sur les machines modernes. Cette transformation est particulièrement efficace pour les listes basées sur les blocs `cons` pour lesquelles elle a été conçue ; elle permet de libérer environ la moitié de l'espace pour chaque nœud sur lequel elle est appliquée.
Il n'est pas toujours possible d'effectuer cette substitution, car l'espace libre au-delà de la fin de A peut être insuffisant. Ainsi, certains objets se termineront par une référence réelle, d'autres par l'objet référencé, et la machine doit pouvoir déterminer, en lisant la dernière cellule, de quel objet il s'agit. Ceci peut être réalisé, avec une certaine inefficacité, par logiciel à l'aide de pointeurs marqués , qui permettent d'étiqueter spécifiquement un pointeur en position finale, mais la solution optimale est d'effectuer le traitement matériel.
En présence d' objets mutables , le codage CDR se complexifie. Si une référence est mise à jour pour pointer vers un autre objet, mais qu'un objet est déjà stocké dans ce champ, cet objet doit être déplacé, ainsi que tous les autres pointeurs qui y font référence. Non seulement ces déplacements sont généralement coûteux, voire impossibles, mais ils entraînent à terme une fragmentation du stockage. Ce problème est généralement évité en utilisant le codage CDR uniquement sur des structures de données immuables .