Введение

В информатике CDR-кодирование — это сжатое представление данных для связанных списков Lisp. Оно было разработано и запатентовано Лабораторией искусственного интеллекта MIT и реализовано в компьютерном оборудовании в ряде машин Lisp, основанных на MIT CADR. CDR-кодирование, по сути, является довольно общей идеей: когда объект данных A заканчивается ссылкой на другую структуру данных B, вместо ссылки можно поместить непосредственно саму структуру B, перекрывая конец A. Это освобождает место, необходимое для ссылки, что может быть значительным при многократном применении, а также улучшает локальность данных, повышая производительность на современных машинах. Преобразование особенно эффективно для списков, созданных на основе cons; оно позволяет освободить около половины пространства для каждого узла, к которому применяется. Выполнить такую замену не всегда возможно, так как за концом A может не быть достаточного количества свободного места. Таким образом, некоторые объекты заканчиваются реальной ссылкой, а другие — непосредственно ссылаемым объектом, и аппаратное обеспечение должно определять, какой из вариантов используется, считывая последнюю ячейку. Это можно реализовать в программном обеспечении с некоторой потерей эффективности, используя тегированные указатели, которые позволяют пометить указатель в конечной позиции как таковой, но оптимально это делать на аппаратном уровне. При наличии изменяемых объектов CDR-кодирование становится сложнее. Если ссылка обновляется для указания на другой объект, а в текущем поле хранится объект, этот объект необходимо переместить вместе со всеми другими указателями на него. Такие перемещения не только обычно дороги или невозможны, но и со временем приводят к фрагментации памяти. Обычно этой проблемы избегают, используя CDR-кодирование только для неизменяемых структур данных.