Accelerating keyword lookups

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')))

Start by locating the map lookup and keyword call-site implementations, then trace how hash maps represent keys, nodes, bitmaps, and transients. Done means a shape-based optimized accessor is designed and implemented with collision-safe key and bitmap validation, but the issue does not identify specific files or tests to run.