CDR 부호화
CDR coding |
컴퓨터 공학에서 CDR 코딩은 Lisp 링크된 목록을 위한 압축된 데이터 표현이다. MIT인공지능연구소가 개발하고 특허를 냈으며, MIT CADR에서 파생된 다수의 리스프 머신의 컴퓨터 하드웨어에 구현했다.
CDR 부호화는 사실 꽤 일반적인 생각이다. 데이터 객체 A가 다른 데이터 구조 B에 대한 참조로 끝날 때마다 우리는 구조 B 자체를 그곳에 배치하여 A의 끝부분을 겹치고 실행할 수 있다. 이를 통해 참조에 필요한 공간을 확보할 수 있으며, 이는 여러 번 수행하면 추가될 수 있으며 참조의 위치도 개선하여 현대적인 기계에 대한 성능을 향상시킨다. 변환은 특히 생성된 cons 기반 목록에 효과적이다. 이 변환을 수행하는 각 노드에 대해 절반의 공간을 확보한다.
A의 끝을 넘어서면 충분한 여유 공간의 덩어리가 없을 수 있기 때문에 이 대체 작업을 항상 수행할 수 있는 것은 아니다. 따라서 어떤 물체는 실제 참조로 끝나고, 어떤 물체는 참조된 물체와 함께 끝나게 되며, 기계는 그것이 어떤 물체인지 최종 셀을 읽음으로써 알 수 있어야 한다. 이는 최종 위치에 있는 포인터를 특별히 이와 같이 태그가 붙을 수 있도록 하는 태그가 붙은 포인터를 사용함으로써 소프트웨어의 일부 비효율성으로 이루어질 수 있지만, 하드웨어에서 가장 잘 수행된다.
변이 가능한 물체가 있으면 CDR 코딩은 더욱 복잡해진다. 참조가 다른 객체를 가리키도록 업데이트되었지만 현재 해당 필드에 저장된 객체를 가지고 있는 경우 객체를 다른 포인터와 함께 재배치해야 한다. 그러한 움직임은 전형적으로 비싸거나 불가능할 뿐만 아니라, 시간이 지남에 따라 가게의 단편화를 야기한다. 이 문제는 일반적으로 불변의 데이터 구조에만 CDR 코딩을 사용함으로써 방지된다.
외부 링크
- 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.
