Linear Lisp -- Reconstituting Trees from Fresh Frozen Concentrate
Reconstituting Trees from Fresh Frozen Concentrate
新鮮な凍った濃縮物から木を再構成 (どういう意味？)
We will now show how to implement a linear machine with the instructions CONS, CAR, CDR, COPY, EQUAL, RPLACA, RPLACD, NULL, ATOM and EQ in such a way that all of these instructions operate in O(1) average time.
私達は平均O(1)時間で操作するこれらの命令、CONS, CAR, CDR, COPY, EQUAL, RPLACA, RPLACD, NULL, ATOM, EQ命令を備えた線形マシンをどのように実装するかを示します。
In other words, our machine will be as fast as a machine based on "hash consing" [Goto74], except that our machine can also execute RPLACX.
言い替えると、私達のマシンは「ハッシュコンシング」に基づいたマシンと同じくらい速いでしょう、私達のマシンがRPLACXも実行できることを除いて。
Our machine will operate on a "virtual heap", and the real heap will be separated from the CPU by a "read barrier" [Moon84].
私達のマシンは「仮想ヒープ」で操作され、そして実ヒープは「リードバリア」によってCPUから分離されるでしょう。
More precisely, the cons cells pointed at directly by the machine registers will operate in the fashion described above, but any cons cells which are not directly pointed at by machine registers may be represented differently.
さらに正確には、マシンレジスタによって直接刺されるコンスセルは上で述べられたやり方で操作されるでしょう、しかしマシンレジスタによって直接指されることのないいくつかのコンスセルは異なった表現をされるでしょう。
In particular, any cons cells which are not directly pointed at by machine registers are represented in a hidden hash table which is built in such a way that list structures which are EQUAL will be represented by exactly the same cell in this hash table.
特に、マシンレジスタによって直接指されないいくつかのコンスセルはEQUALがこのハッシュテーブルで厳密に同じセルによって表現されるようなリスト構造の方法で構築された隠れたハッシュテーブルで表現されます。
This "hash cons" table is built inductively from cells having atomic CAR's and CDR's by hashing the addresses of non-atomic CAR's and CDR's; this scheme is called "hash consing" and under the appropriate circumstances the cost of a "hash cons" operation averages O(1).
この「ハッシュコンス」テーブルは非アトミックなCARとCDRのアドレスをハッシュすることによってアトミックなCARとCDRを持つセルから帰納的に構築されます:この仕組は「ハッシュコンシング」と呼ばれ、適当な環境の下で「ハッシュコンス」操作のコストは平均O(1)です。
Furthermore, these cells can be dereferenced for CAR or CDR in O(1) time.
さらに、これらのセルはO(1)時間で逆参照することもできます。
These cells cannot be side-effected, however, so that RPLACX cannot be used directly on these hash-consed cells.
これらのセルは副作用を起こせません、一方、RPLACXはハッシュコンスされたセルで直接使用することが出来ません。
We will manage this hash table using reference counts, since we intend that cells stored in this table are capable of being shared.
私達はこのハッシュテーブルを参照カウントを使用することで管理します、このテーブルに格納されるセルは共有することを意図しているので。
We now analyze the operation of the read barrier.
私達は今リードバリアーの操作を解析します。
If the CPU attempts to read the CAR or CDR of a cell referenced directly by a machine register, then the read barrier causes the cell in the hash table to be copied ("unshared") into a normal cell, and the reference count of the cell in the hash table is decremented.
もしCPUがマシンレジスタによって直接参照されたセルのCARかCDRの読み込みを試みたとき、リードバリアはハッシュテーブルのセルを通常のセルへコピー(「非共有」)させます、そしてハッシュテーブルの参照カウントはデクリメントされます。
Similarly, if the CPU attempts to write the CAR or CDR of a cell referenced directly by a machine register, then the cell is copied into the hash table by "hash consing" (including incrementing the reference counter) and the copied pointer is stored into the CAR/CDR instead.
同様に、もしCPUがマシンレジスタによって直接参照されたセルのCARやCDRに書き込みを試みたとき、セルは「ハッシュコンシング」(参照カウンタのインクリメントを含む)によってハッシュテーブルへコピーされ、コピーされたポインタはCAR/CDRの代わりに格納されます。
Since there are never more than n "normal" cells which can be seen by the CPU, because there are only n registers, and because none of these normal cells can be shared, we can eliminate the expense of allocating and deallocating these cells, and associate one of these normal cells with each machine register.
CPUによって見ることのできる「通常の」セルは決してnを越えないから、そしてこれらの標準のセルは共有することができません、私達はこれらのセルの割り当てと開放のコストを無視することが出来ます、そして各マシンレジスタにこれらの標準セルの1つを結びつけます。
Thus, all storage management effort is concentrated in the hash cons table.
このように、全てのストレージ管理の試みはハッシュコンステーブルに集中されます。
Another optimization is that of keeping a "hidden" pointer in each normal cell to the entry in the hash table from which it was copied; if it is newly consed, then this pointer is empty.
別の最適化はコピーされたそれからハッシュテーブルのエントリに「隠れた」ポインタを各標準セルに保持することです:もしそれが新しくコンスされたら、そのときこのポインタは空です。
This pointer is used as a "hint" when hash consing, so that no searching will be necessary to share the cell in the hash consed heap.
このポインタはハッシュコンシングの時に「手掛かり」として使われます、そのため検索はハッシュコンスされたヒープでセルを共有するのに必要ではありません。
Of course, any side-effects to this normal cell will cause its "hint" pointer to be cleared, since we will now require a hash lookup in order to share the cell in the hash consed heap.
もちろん、この標準セルへのいくつかの副作用はその「手掛かり」ポインタをクリアさせるでしょう、私達は今ハッシュコンスされたヒープでセルを共有するためにハッシュルックアップを必要とします。
Since the free list seen by the CPU is an infinite list of NIL's, we can represent it as a special circular list of one cell in the hash table whose reference count is not modified.
CPUによって見られるフリーリストはNILの無限リストなので、私達は参照カウントが修正されないハッシュテーブルの1つのセルの特別な循環リストとしてそれを表現することが出来ます。
In this case, the free list register is identical in nature to the other registers in the CPU; the only difference is in the hash table pointer stored in the CDR of the first cell on the list.
この場合、フリーリストレジスタはCPUでは他のレジスタに自然に同一です:唯一の違いはリストの最初のセルのCDRに格納されるハッシュテーブルのポインタです。
Of course, there is a real "free list" which is hidden from the CPU which is used to provide cells for the hash table when a never-before-hashed
もちろん、ハッシュされなかった
This "free list" is refreshed whenever the reference count of a table entry drops to zero.
この「フリーリスト」はテーブルエントリの参照カウントがゼロに落ちたときはいつも刷新されます。
Depending upon our time/space tradeoff, we can either recycle hash table cells aggressively or lazily.
私達の時間/空間のトレードオフによって、私達は積極的または消極的のどちらかでハッシュテーブルのセルを再利用することができます。
If we recycle aggressively, then we may have to recycle an unbounded number of nodes at one time, which can create an unbounded delay.
もし私達が積極的に再利用したならば、そのとき私達は一度に際限ない沢山のノードを再利用しなければならないかもしれません。そしてそれは、際限なく遅延を引き起こすことができます。
Alternatively, we can recycle lazily, in which case the CAR and CDR of a recycled cell are only marked as deleted, but not actually reclaimed, at the time that the reference count for the cell drops to zero.
代わりに、私達は消極的にリサイクルすることができます、その場合、再利用されたセルのCARとCDRは削除されたとしてマークだけされます、しかし実際に再利用されません、その時点でそのセルの参照カウントはゼロに落とされます。
Notice, though, that any sublists of this "garbage" list are still hashable by the hash table and can become non-garbage at any time.
この「ゴミ」リストのどんなサブリストもそれでもハッシュテーブルによってハッシュできていつでもゴミでなくなることができます。
Thus, the garbage is not really garbage, although it can only be used for a very special purpose until recycled for general use.
このように、それは一般的利用のために再利用されるまできわめて特別な目的のためだけに使用されることができるだけで、ゴミは本当のゴミではありません。
We can now describe the operation of our "fast" machine.
私達は今私達の「速い」マシンの操作を述べることができます。
All primitive operations, with the exception of FREE, COPY and EQUAL, operate exactly as if the CPU were operating on a "real heap" rather than a "virtual heap".
全てのプリミティブな操作、FREE, COPY, EQUALを除いて、ちょうどCPUが「仮想ヒープ」よりむしろ「実ヒープ」を操作しているように操作します。
COPY copies only the top-level cons cell, and "copies" the sublists by simply incrementing the reference counts of the CAR and CDR cells in the hash table.
COPYはトップレベルのコンスセルだけをコピーします、そして単にハッシュテーブルでCARとCDRセルの参照カウントのインクリメントによってサブリストを「コピー」します。
EQUAL compares only the top-level cons cell, and simply compares the addresses of the CAR's and CDR's for their locations in the hash table.
EQUALはトップレベルのコンスセルだけを比較します、そして単にハッシュテーブルでそれらの場所のためにCARとCDRのアドレスを比較します。
Thus, COPY and EQUAL are both O(1) operations.
このようにCOPYとEQUALはともにO(1)操作です。
If we utilize lazy recycling for hash table entries, then FREE is also an O(1) operation.
もし私達がハッシュテーブルエントリの遅延再利用を使用したら、FREEもまたO(1)操作です。
>> Lively Linear Lisp
>> Abstract
>> Introduction
>> A Linear Lisp Machine
>> A Linear Lisp Machine with FREE, COPY, EQUAL and Assignment
>> Dataflow-like Producer/Consumer EVAL
>> Reconstituting Trees from Fresh Frozen Concentrate
>> Linear Lisp EVAL
>> Implications for Real Multiprocessors
>> Conclusions and Previous Work
0 件のコメント:
コメントを投稿