Commits

Robert Smith  committed 729fbb6

Initial implementation of hash consing. Slow.

  • Participants

Comments (0)

Files changed (4)

+An implementation of hash consing for Common Lisp.

File hash-cons.asd

+;;;; hash-cons.asd
+
+(asdf:defsystem #:hash-cons
+  :serial t
+  :description "An implementation of hash consing."
+  :author "Robert Smith <quad@symbo1ics.com>"
+  :license "Public Domain"
+  :components ((:file "package")
+               (:file "hash-cons")))
+

File hash-cons.lisp

+;;;; hash-cons.lisp
+
+(in-package #:hash-cons)
+
+(defvar *hash-cons-table*
+  #+sbcl
+  (make-hash-table :test 'equal
+                   :weakness :key-and-value)
+  #-sbcl
+  (error "Implementation of weak hash tables needed."))
+
+(let ((temp (cons nil nil)))
+  (defun hcons (a b)
+    (setf (car temp) a
+          (cdr temp) b)
+    (or (gethash temp *hash-cons-table*)
+        (prog1 (setf (gethash temp *hash-cons-table*) (cons a b))
+          (setf (car temp) nil
+                (cdr temp) nil)))))
+
+
+(defun random-symbol ()
+  (aref #(:a :b :c :d :e :f :g :h)
+        (random 8)))
+
+(defun test (&optional (trials 1000))
+  (format t "=== CONS~%")
+  (time (loop :repeat trials
+              :collect (cons (random-symbol)
+                             (random-symbol))))
+  (sb-ext:gc :full t)
+  (format t "=== HASH CONS~%")
+  (time (loop :repeat trials
+              :collect (hcons (random-symbol)
+                              (random-symbol))))
+  (sb-ext:gc :full t)
+  t)

File package.lisp

+;;;; package.lisp
+
+(defpackage #:hash-cons
+  (:use #:cl)
+  (:export #:hcons))
+