CDR coding

CDR coding

In computer science CDR coding is a compressed data representation for Lisp linked lists. It was developed and patented by the MIT Artificial Intelligence Laboratory, and implemented in computer hardware in a number of Lisp machines 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 of 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 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 lists 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.

External links

* [http://www.faqs.org/faqs/lisp-faq/part2/section-9.html "(2-9) What is CDR-coding?"]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • High-Efficiency Advanced Audio Coding — MIME audio/aacp, audio/3gpp, audio/3gpp2 Разработан ISO Тип формата Формат сжатия звука Содержится в 3GP, MP4, .dvb Расширен из AAC Стандарт(ы) ISO/IEC 14496 3 …   Википедия

  • Advanced Audio Coding — (AAC) собственнический (патентованный) формат аудиофайла с меньшей потерей качества при кодировании, чем MP3 при одинаковых размерах.[1] Также AAC это широкополосный алгоритм кодирования аудио, который использует два основных принципа кодирования …   Википедия

  • Развёрнутый связный список — список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что …   Википедия

  • 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 (in other words, a link) to the next node in the… …   Wikipedia

  • Lisp machine — Lisp machines were general purpose computers designed (usually through hardware support) to efficiently run Lisp as their main software language. In a sense, they were the first commercial single user workstations. Despite being modest in number… …   Wikipedia

  • 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… …   Wikipedia

  • Composite Health Care System — The Composite Health Care System (CHCS) is a VMS based medical informatics system designed by Science Applications International Corporation (SAIC) and used by all United States and OCONUS military health care centers. In 1988, SAIC won a… …   Wikipedia

  • JPEG — For other uses, see JPEG (disambiguation). Joint Photographic Experts Group A photo of a cat compressed with successively more lossy compression ratios from right to left Filename extension .jpg …   Wikipedia

  • Comparison of vector graphics editors — A number of vector graphics editors for various platforms exist. Potential users of these editors will make a decision based on factors such as the availability for the user s platform, the feature set, usability of the user interface (UI) and… …   Wikipedia

  • MPEG-1 Audio Layer I — MPEG 1 Audio Layer 1 Расширение .mp1 MIME audio/mpeg,[1] audio/MPA[2] Разработан ISO, IEC Тип формата audio Стандарт(ы) …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”