I think we could slightly reduce the work that a subsequent insertKeyExists or deleteKeyExists has to perform by enhancing this location information with the sequence of array indices that lead to the relevant Leaf or Collision node:
type IndexPath = Word
data LookupRes a = Absent | Present a !IndexPath !Int
This IndexPath is basically a Hash with the difference that even for BitmapIndexed nodes, the array index can be computed with the simple index function instead of the more involved sparseIndex. We won't even need index and the Shift it requires, though, if we simply right-shift the IndexPath at each step.
I don't expect a large speedup from this, but maybe something like 2, 3%?!
alterandalterFrely onlookupRecordCollisionto gather information about the location of a key in the map. This info is stored in aLookupRes:https://github.com/haskell-unordered-containers/unordered-containers/blob/8bb958e53cb21cf20894fbfd8fbfa37672879173/Data/HashMap/Internal.hs#L654-L656
I think we could slightly reduce the work that a subsequent
insertKeyExistsordeleteKeyExistshas to perform by enhancing this location information with the sequence of array indices that lead to the relevantLeaforCollisionnode:This
IndexPathis basically aHashwith the difference that even forBitmapIndexednodes, the array index can be computed with the simpleindexfunction instead of the more involvedsparseIndex. We won't even needindexand theShiftit requires, though, if we simply right-shift theIndexPathat each step.I don't expect a large speedup from this, but maybe something like 2, 3%?!
https://github.com/haskell-unordered-containers/unordered-containers/blob/8bb958e53cb21cf20894fbfd8fbfa37672879173/Data/HashMap/Internal.hs#L1385-L1422