Clojure/JVM has accelerated keyword lookups for records. At keyword call site a kind of polymorphic inline cache is created to hold an optimized accessor function.
We could apply something equivalent but more broadly: since our maps internal shapes are deterministic we can have optimized accessors for maps of same shape.
To recognize the shape we could store in each map a hash value depending on its keys.
Then the optimized accessor would run only when the "shape hash" is the same, following a path into the map encoded as an integer, ignoring all bitmaps.
In case of "shape hash" collision two things can happen:
exception during the traversal
pointing to a different key.
🤔worrying: there's the elusive possibility of the path pointing to a value which happens to be the keyword, and we shouldn't mistake this for an actual successful lookup
Thus even when fast lookup succeeds it must be checked to be correct. Checking key equality is cheap enough. However checking we didn't end on a value slot would require bit twiddling again.
Except if we compare bitmaps as a proxy: we are expecting the same shape, so bitmaps should be equals (except for the transient "spin"). Either we ignore transients and accept that fast lookup may fail when alternating between maps of same shape but built differently (transient or not) or we spend a few extra ops.
For hash maps the proper test should be:
; (bit-and hi lo) ; 1 for each kv
; (bit-xor hi lo) ; 1 for each node
; this is 0 when equivalent bitmaps
(bit-or (bit-xor (bit-xor hi lo) (bit-xor hi' lo'))
(bit-xor (bit-and hi lo) (bit-and hi' lo')))
Clojure/JVM has accelerated keyword lookups for records. At keyword call site a kind of polymorphic inline cache is created to hold an optimized accessor function.
We could apply something equivalent but more broadly: since our maps internal shapes are deterministic we can have optimized accessors for maps of same shape.
To recognize the shape we could store in each map a hash value depending on its keys.
Then the optimized accessor would run only when the "shape hash" is the same, following a path into the map encoded as an integer, ignoring all bitmaps.
In case of "shape hash" collision two things can happen:
Thus even when fast lookup succeeds it must be checked to be correct. Checking key equality is cheap enough. However checking we didn't end on a value slot would require bit twiddling again.
Except if we compare bitmaps as a proxy: we are expecting the same shape, so bitmaps should be equals (except for the transient "spin"). Either we ignore transients and accept that fast lookup may fail when alternating between maps of same shape but built differently (transient or not) or we spend a few extra ops.
For hash maps the proper test should be: