Alex Shinn <xxxxxx@gmail.com> schrieb am So., 2. Sep. 2018 um 03:05 Uhr:

I forgot to mention the even simpler case which is what I implemented for chibi-scheme.

If you use alists for collision resolution, you can ensure the same cell is preserved even after rehash. Then

(let ((cell (%hash-table-cell table key)))
(set-cdr! cell (update (cdr cell))))

works even if `update' mutates the table, and avoids resolving the cell a second time.

This does not work if `update' removes (and possibly reinserts the key). For example, the following test case fails in Chibi:

(import (chibi) (chibi test) (srfi 125) (srfi 128))

(define ht (make-hash-table (make-default-comparator)))
(hash-table-set! ht 'a 'old)
(hash-table-update! ht 'a (lambda (x)
(hash-table-delete! ht 'a)
'new))
(test 'new (hash-table-ref/default ht 'a 'not-found))

A solution would be to add a flag to each cell that is set when a cell is added to a hash table and cleared when it is removed. `hash-table-update!' would have to check this flag. For example, the flag can be implemented by distinguishing between a valid key and a non-key in the car-field of the cell.

However, this may add a (slight) overhead to every hash-table insertion/deletion (which may not be the intent of the SRFI 125 authors).

-- Marc

--
Alex

On Sat, Sep 1, 2018 at 11:09 PM, Alex Shinn <xxxxxx@gmail.com> wrote:
On Fri, Aug 31, 2018 at 9:11 PM, Marc Nieper-Wißkirchen <xxxxxx@nieper-wisskirchen.de> wrote:
SRFI 125 states that

(hash-table-update! hash-table key updater)

"is semantically equivalent to, but may be more efficient than, the following code":

(hash-table-set! hash-table key (updater (hash-table-ref hash-table key)))

It seems unnecessary difficult for an implementation to provide a more efficient implementation of the latter if the updater procedure is allowed to mutate hash-table arbitrarily.

In its abstract, SRFI 125 says: "Does not guarantee that whole-table operations work in the presence of a concurrent mutation of the whole hash table (values may be safely mutated)."

If this restriction applies to hash-table-update! as well, the problem raised above won't occur. However, with this restriction, hash-table-update! would not be strictly semantically equivalent to the combination of hash-table-set! and hash-table-ref.

What has been the intent of the SRFI authors? It is possibly a good idea to spell out such a restriction/to clarify hash-table-update! in a post-finalization note.

The obvious optimization is if the implementation knows `updater' doesn't mutate the hash-table, e.g. if it is inlined.

Alternately you don't need to detect arbitrary mutations but merely rehashes, which is already tracked in some implementations, a cheap optimistic optimization.

The optimization doesn't always have to be applicable to note that it "may" be more efficient.

Specifying the same restriction as for whole-table operations may have been a good idea in retrospect, but I think this is too much for an errata.

--
Alex

-- Marc

To unsubscribe from this list please go to http://www.simplelists.com/confirm.php?u=HMSJedTgWFrXaSU4l6a5mA0U4NgC8sBK