HASH-CONSING

Linear Lispの論文を訳したけど
「hash consing(ハッシュコンシング)」
の意味がいまいちよく分からんかった。
他の記述を探したらBoyer benchmarkについて書かれた文書の中に
「HASH-CONSING」
の文字を発見、訳してみる。


HASH-CONSING

Memoizing rewrite produces the largest performance improvement, but performance can be further improved by using hash consing. Hash consing was invented by Ershov in 1958 [Ershov58] to speed up the recognition of common subexpressions, and popularized by Goto [Goto74] for use in a symbolic algebra system.

メモ化は生産物の最も大きいパフォーマンスの改良を書き換えます、しかしパフォーマンスはハッシュコンシングを使用してさらに改良することが可能です。ハッシュコンシングは1958年に一般的な部分式の構築のスピードアップのためにErshovによって提案されました、そして記号代数システムで使用するためにGotoによって広められました。

Hash consing builds up an expression recursively from atoms by use of the hcons function, which is a true mathematical function in the sense that given the same pair of arguments, the result is always eq. Hash consing can be simulated in Common Lisp by using an equal hash table, but such an implementation is at least an order of magnitude less efficient than a direct implementation, because the hash table never needs to recurse beyond the car and cdr in order to determine equality, and the value is always the key itself. As a result, the effectiveness of the hash consing optimization of the Boyer benchmark is dependent upon the efficiency of the hcons function.

ハッシュコンシングはhcons関数の使用によってアトムから式を再帰的に作り上げます、それ(hcons)は同じ引数のペアが与えられる真の数学的関数です、結果は常に同じです。ハッシュコンシングはイコールハッシュテーブルの使用によってCommon Lispでシミュレーションすることが出来ます、しかしそのような実装は少なくとも直接実装より桁違いに効果ではありません、なぜならハッシュテーブルは等価性を決定するためにcarとcdrを越えて決して再帰を必要としません、そして値は常にキーそれ自身です。結果として、Boyerベンチマークのハッシュコンシングの最適化の効果はhcons関数の効率に依存します。

(defparameter *cons-table* (make-hash-table :test #'equal))

(defparameter *a-cons-cell* (list nil)) ;holding area for spare cons.

(defun hcons (x y) ;not very fast; only for illustration.
(setf (car *a-cons-cell*) x (cdr *a-cons-cell*) y) ;don't cons yet.
(let ((z (gethash *a-cons-cell* *cons-table*)))
(or z (prog1 (setf (gethash *a-cons-cell* *cons-table*) *a-cons-cell*)
(setq *a-cons-cell* (list nil)))))) ;do next cons here.

Notice that hash consing saves both space and time. Space is saved, because a subtree is never duplicated in memory. Time is saved, because any equal tests reduce to eq tests, and the original Boyer benchmark performs 1,403 equal tests. More importantly, however, the memo hash table itself can now use the more efficient eq test instead of an equal test.

ハッシュコンシングは両方の空間と時間を節約することに注意してください。空間は節約されます、なぜならサブツリーは決してメモリで複製されません。時間は節約されます、なぜならどんなequalテストもeqテストに簡約できるからです、そしてオリジナルBoyerベンチマークは1403のequqlテストを実行します。さらに重要なことは、しかし、memoハッシュテーブルそれ自身は現在equalテストの代わりにさらに効果的なeqテストを使用することができます。

(defparameter *memo-table* (make-hash-table :test #'eq))

The effectiveness of hash consing for the Boyer benchmark can be seen by considering the result of rewrite. In the original Boyer benchmark, the answer consumes 48,139 cons cells, but if one copies the answer using hcons, the answer consumes only 146 distinct cons cells (!), for a ratio of 1:330. With hash consing in effect for both setup and test in the Boyer benchmark, the total number of cons cells consumed is 2,216, for a ratio of 1:102.

Boyerベンチマークのためのハッシュコンシングの効果は書き直しの結果を考慮することによって見ることが出来ます。オリジナルBoyerベンチマークでは、解答は48139のコンスセルを消費します、しかし、もし一回のコピーhconsを使用した解答ならば、解答はたった146の異なったコンスセルを消費します!、1:330の比です。Boyerベンチマークでのセットアップとテストの両方への効果でハッシュコンシングで、消費されたコンスセルの総数は2216です、1:102の比です。


あんまり訳した意味はなさそう。
でもこのCommon Lispのソースは参考になるな。