CDR coding
 | This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
|
In
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 pointers, which allow a pointer in a final position to be specifically tagged as such, but is best done in hardware.
In the presence of
External links
- Mark Kantrowitz; Barry Margolin (eds.). "(2-9) What is CDR-coding?". FAQ: Lisp Frequently Asked Questions. Advameg, Inc. Retrieved 2011-10-09.
- Allen, John (1978). The Anatomy of Lisp. McGraw-Hill.
 | This computer-programming-related article is a stub. You can help Wikipedia by expanding it. |