CDR coding
Encyclopedia
In computer science
CDR coding is a compressed
data representation
for Lisp
linked list
s. It was developed and patented by the MIT Artificial Intelligence Laboratory, and implemented in computer
hardware in a number of Lisp machine
s derived from the MIT CADR.
CDR coding is in fact a fairly general idea; whenever a data object A ends in a reference
to another data structure B, we can instead place the structure B itself there, overlapping and running off the end of A. By doing this we free the space required by the reference, which can add up if done many times, and also improve locality of reference
, enhancing performance on modern machines. The transformation is especially effective for the cons
-based lists it was created for; we free about half of the space for each node we perform this transformation on.
It is not always possible to perform this substitution, because there might not be a large enough chunk of free space beyond the end of A. Thus, some objects will end in a real reference, and some with the referenced object, and the machine must be able to tell by reading the final cell which one it is. This can be accomplished with some inefficiency in software by the use of tagged pointer
s, which allow a pointer in a final position to be specifically tagged as such, but is best done in hardware.
In the presence of mutable objects, CDR coding becomes more complex. If a reference is updated to point to another object, but currently has an object stored in that field, the object must be relocated, along with any other pointers to it. Not only are such moves typically expensive or impossible, but over time they cause fragmentation
of the store. This problem is typically avoided by using CDR coding only on immutable
data structures.
Unrolled linked list
s are simpler and often higher-performance than CDR coding (no "tagged pointers"; typically less fragmentation). For short lists, CDR coding uses the least amount of space.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
CDR coding is a compressed
Data compression
In computer science and information theory, data compression, source coding or bit-rate reduction is the process of encoding information using fewer bits than the original representation would use....
data representation
Data (computing)
In computer science, data is information in a form suitable for use with a computer. Data is often distinguished from programs. A program is a sequence of instructions that detail a task for the computer to perform...
for Lisp
Lisp programming language
Lisp is a family of computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older...
linked list
Linked list
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
s. It was developed and patented by the MIT Artificial Intelligence Laboratory, and implemented in computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
hardware in a number of Lisp machine
Lisp machine
Lisp machines were general-purpose computers designed to efficiently run Lisp as their main software language. In a sense, they were the first commercial single-user workstations...
s derived from the MIT CADR.
CDR coding is in fact a fairly general idea; whenever a data object A ends in a reference
Reference
Reference is derived from Middle English referren, from Middle French rèférer, from Latin referre, "to carry back", formed from the prefix re- and ferre, "to bear"...
to another data structure B, we can instead place the structure B itself there, overlapping and running off the end of A. By doing this we free the space required by the reference, which can add up if done many times, and also improve locality of reference
Locality of reference
In computer science, locality of reference, also known as the principle of locality, is the phenomenon of the same value or related storage locations being frequently accessed. There are two basic types of reference locality. Temporal locality refers to the reuse of specific data and/or resources...
, enhancing performance on modern machines. The transformation is especially effective for the cons
Cons
In computer programming, cons is a fundamental function in most dialects of the Lisp programming language. cons constructs memory objects which hold two values or pointers to values. These objects are referred to as cells, conses, non-atomic s-expressions , or pairs...
-based lists it was created for; we free about half of the space for each node we perform this transformation on.
It is not always possible to perform this substitution, because there might not be a large enough chunk of free space beyond the end of A. Thus, some objects will end in a real reference, and some with the referenced object, and the machine must be able to tell by reading the final cell which one it is. This can be accomplished with some inefficiency in software by the use of tagged pointer
Tagged pointer
In computer science, a tagged pointer is a common example of a tagged union, where the primary type of data to be stored in the union is a pointer...
s, which allow a pointer in a final position to be specifically tagged as such, but is best done in hardware.
In the presence of mutable objects, CDR coding becomes more complex. If a reference is updated to point to another object, but currently has an object stored in that field, the object must be relocated, along with any other pointers to it. Not only are such moves typically expensive or impossible, but over time they cause fragmentation
Fragmentation (computer)
In computer storage, fragmentation is a phenomenon in which storage space is used inefficiently, reducing storage capacity and in most cases reducing the performance. The term is also used to denote the wasted space itself....
of the store. This problem is typically avoided by using CDR coding only on immutable
Immutable object
In object-oriented and functional programming, an immutable object is an object whose state cannot be modified after it is created. This is in contrast to a mutable object, which can be modified after it is created...
data structures.
Unrolled linked list
Unrolled linked list
In computer programming, an unrolled linked list is a variation on the linked list which stores multiple elements in each node. It can drastically increase cache performance, while decreasing the memory overhead associated with storing list metadata such as references...
s are simpler and often higher-performance than CDR coding (no "tagged pointers"; typically less fragmentation). For short lists, CDR coding uses the least amount of space.