CDRコーディング

フリー百科事典ウィキペディアより

コンピュータ サイエンス では、CDR コーディングはLispリンク リスト圧縮 データ表現ですこれは、 MIT 人工知能研究所によって開発および特許取得されMIT CADRから派生した多数のLisp マシンのコンピューターハードウェアに実装されています。

実際、CDR コーディングはかなり一般的な考え方です。データオブジェクトA が別のデータ構造Bへの参照で終わるときはいつでも、代わりに構造B自体をそこに配置し、 Aの終わりからオーバーラップして実行することができますこれを行うことで、参照に必要なスペースが解放されます。これは、何度も実行すると加算される可能性があり、参照の局所性も向上し、最新のマシンでのパフォーマンスが向上します。この変換は、それが作成されたconsベースのリストに対して特に効果的です。この変換を実行するノードごとに約半分のスペースを解放します。

A の末尾を超える十分な大きさの空き領域がない可能性があるため、この置換を常に実行できるとは限りません。したがって、一部のオブジェクトは実際の参照で終了し、一部のオブジェクトは参照されたオブジェクトで終了します。最後のセルを読むことで、それがどれであるかを知ることができます。これは、タグ付けされたポインターを使用することにより、ソフトウェアでいくらか非効率に実現できます。これにより、最終位置のポインターをそのように具体的にタグ付けできますが、ハードウェアで行うのが最適です。

可変オブジェクトが存在する場合、CDR コーディングはより複雑になります。参照が別のオブジェクトを指すように更新されたが、現在そのフィールドに格納されているオブジェクトがある場合、そのオブジェクトへの他のポインターと共にオブジェクトを再配置する必要があります。このような移動は通常、費用がかかるか不可能であるだけでなく、時間の経過とともに店舗の断片化を引き起こします。通常、この問題は、不変のデータ構造に対してのみ CDR コーディングを使用することで回避されます。

外部リンク

  • マーク・カントロウィッツ; バリー・マーゴリン(編)。「(2-9)CDRコーディングとは?」. FAQ: Lisp よくある質問. アドバメグ2011 年 10 月 9 日閲覧
  • アレン、ジョン(1978)。Lisp の解剖学マグロウヒル。