weak hash table in sbcl and allegro

[Jim Newton]

I'm trying to figure out which allegro-specific arguments to pass to make-hash-table so that
hash entries are preserved if either the key or the value is referenced elsewhere.
But the documentation is a bit confusing.

https://franz.com/support/documentation/10.1/doc/implementation.htm#cl-make-hash-table-2

In sbcl I can give the arguments :weakness :key-or-value to make-hash-table. This tells the GC
not to preserve this hash entry if either the key or value is referenced.

When I look at the allegroCL documentation, it is not clear how to get the same functionality.
Since allegro uses a generational GC, the make-hash-table arguments allow lots of flexibility,
and it is not clear how to get the most conservative behavior. Can someone help?

[Pascal J. Bourguignon]

| :values | nil | t | :weak |
| :weak-key | | | |
|------------+-----------------------------------+-------------------+------------------------------|
| nil | no value stored | normal hash-table | weak-value: it becomes nil |
| t | weak key, no value stored | weak key | weak key, weak value |
| :tenurable | tenured weak key, no value stored | tenured weak key | tenured weak key, weak value |



| sbcl | allegro |
|--------------------------+-----------------------------|
| :weakness nil | :weak-key nil :values :t |
| :weakness :key | :weak-key t :values t |
| :weakness :value | :weak-key nil :values :weak |
| :weakness :key-and-value | :weak-key t :values :weak |
| :weakness :key-or-value | |


So, it looks like :key-or-value is not implemented directly by Allegro
hash-tables.

This is indeed unfortunate, since weak-or is a primitive that is
difficult to implement properly. cf.
https://github.com/informatimago/lisp/blob/master/clext/closer-weak.lisp

One way to get the effect when it's not available, is to make circular
references between the key and the value, if that's possible (if they
are compound objects). In that case, if either a hard reference to the
key, or to the value exist, the circular references will hold both.


--
__Pascal J. Bourguignon__
http://www.informatimago.com

[Jim Newton]

On Tuesday, January 29, 2019 at 12:56:56 PM UTC+1, informatimago wrote:

> This is indeed unfortunate, since weak-or is a primitive that is
> difficult to implement properly. cf.
> https://github.com/informatimago/lisp/blob/master/clext/closer-weak.lisp
>
> One way to get the effect when it's not available, is to make circular
> references between the key and the value, if that's possible (if they
> are compound objects). In that case, if either a hard reference to the
> key, or to the value exist, the circular references will hold both.
>
>

Hi Pascal, thanks for the analysis. Are you suggesting that I could simply make the values be a cons of key.value ? Would that work?

[Pascal J. Bourguignon]

That would work if the external references you make, are only to those
cons cells, and not to the individual key or value!

More precisely, if you need a WEAK-OR, I would do:

(defstruct wrapper
object
other)

(defun wrap-association (key value)
(let ((key-wrapper (make-wrapper :object key))
(val-wrapper (make-wrapper :object value)))
(setf (wrapper-other key-wrapper) val-wrapper
(wrapper-other val-wrapper) key-wrapper)
(values key-wrapper
val-wrapper)))


(defparameter *table* (make-hash-table #+allegro :weak-key t :values t))

(multiple-value-bind (kw vw) (wrap-association key value)
(setf (gethash kw *table*) vw)

(setf vw nil) ; lost reference to the value wrapper, but we still have a
;; reference to kw -> key -> vw -> value, so nothing's lost.

(setf kw nil) ; lost reference to the key wrapper, we don't have
;; a reference to the value, so kw AND vw can be GC'ed,
;; and the entry can be removed from the HT.

)


We can also use: (setf (gethash (wrapper-object kw) *table*) vw)
as long as we keep a reference to the key wrappers kw.

Note: if multiple such tables are used with keys in common, we have to
use one key wrapper/value wrapper circular list per table, so we need to
keep a list of key wrapper to retain the entries in all the tables.
Everywhere we would have used the key or the value, we would have to use
the wrapper instead.