En informática, la codificación CDR es una representación de datos comprimidos para listas enlazadas Lisp . Fue desarrollado y patentado por el Laboratorio de Inteligencia Artificial del MIT e implementado en hardware de computadora en una serie de máquinas Lisp derivadas del CADR del MIT .
La codificación CDR es de hecho una idea bastante general; cada vez que un objeto de datos A fines en una referencia a otra estructura de datos B , que en lugar pueden colocar la estructura B en sí no, la superposición y se salga de la final de A . Al hacer esto, liberamos el espacio requerido por la referencia, que puede sumarse si se hace muchas veces, y también mejoramos la localidad de referencia , mejorando el rendimiento en las máquinas modernas. La transformación es especialmente efectiva para las listas basadas en contras para las que fue creada; liberamos aproximadamente la mitad del espacio para cada nodo en el que realizamos esta transformación.
No siempre es posible realizar esta sustitución, porque puede que no haya una porción suficientemente grande de espacio libre más allá del final de A. Por lo tanto, algunos objetos terminarán en una referencia real y otros con el objeto referenciado, y la máquina debe podrá saber al leer la celda final cuál es. Esto se puede lograr con cierta ineficiencia en el software mediante el uso de punteros etiquetados , que permiten que un puntero en una posición final se etiquete específicamente como tal, pero se hace mejor en hardware.
En presencia de objetos mutables , la codificación de CDR se vuelve más compleja. Si una referencia se actualiza para apuntar a otro objeto, pero actualmente tiene un objeto almacenado en ese campo, el objeto debe reubicarse, junto con cualquier otro puntero hacia él. Estos movimientos no solo son típicamente costosos o imposibles, sino que con el tiempo provocan la fragmentación de la tienda. Este problema se evita típicamente utilizando codificación CDR solo en estructuras de datos inmutables .
enlaces externos
- Mark Kantrowitz; Barry Margolin (eds.). "(2-9) ¿Qué es la codificación CDR?" . FAQ: Preguntas frecuentes sobre Lisp . Advameg, Inc . Consultado el 9 de octubre de 2011 .
- Allen, John (1978). La anatomía de Lisp . McGraw-Hill.