Small optimization idea for alter[F]

[sjakobi]

alter and alterF rely on lookupRecordCollision to gather information about the location of a key in the map. This info is stored in a LookupRes:

unordered-containers/Data/HashMap/Internal.hs

Lines 654 to 656 in 8bb958e

	-- The result of a lookup, keeping track of if a hash collision occured.
	-- If a collision did not occur then it will have the Int value (-1).
	data LookupRes a = Absent | Present a !Int

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%?!

unordered-containers/Data/HashMap/Internal.hs

Lines 1385 to 1422 in 8bb958e

	-- | This is the default version of alterF that we use in most non-trivial
	-- cases. It's called "eager" because it looks up the given key in the map
	-- eagerly, whether or not the given function requires that information.
	alterFEager :: (Functor f, Eq k, Hashable k)
	=> (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
	alterFEager f !k m = (<$> f mv) $ \case
	------------------------------
	-- Delete the key from the map.
	Nothing -> case lookupRes of
	-- Key did not exist in the map to begin with, no-op
	Absent -> m
	-- Key did exist
	Present _ collPos -> deleteKeyExists collPos h k m
	------------------------------
	-- Update value
	Just v' -> case lookupRes of
	-- Key did not exist before, insert v' under a new key
	Absent -> insertNewKey h k v' m
	-- Key existed before
	Present v collPos ->
	if v `ptrEq` v'
	-- If the value is identical, no-op
	then m
	-- If the value changed, update the value.
	else insertKeyExists collPos h k v' m
	where !h = hash k
	!lookupRes = lookupRecordCollision h k m
	!mv = case lookupRes of
	Absent -> Nothing
	Present v _ -> Just v
	{-# INLINABLE alterFEager #-}