alter could be much more efficient

[sjakobi]

unordered-containers/Data/HashMap/Internal.hs

Lines 1241 to 1247 in 26a1c33

	alter :: (Eq k, Hashable k) => (Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v
	-- TODO(m-renaud): Consider using specialized insert and delete for alter.
	alter f k m =
	case f (lookup k m) of
	Nothing -> delete k m
	Just v -> insert k v m
	{-# INLINABLE alter #-}

Currently this code will attempt to delete keys that aren't present in the first place. Inserts could be more efficient too, compare alterFEager:

unordered-containers/Data/HashMap/Internal.hs

Lines 1358 to 1392 in 26a1c33

	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 #-}

The Strict version has the same problems.

[sjakobi]

Even with the optimizations added in #404, we end up walking the tree twice. It would certainly be more efficient to walk the tree once, similarly to insert or delete.

[sjakobi]

It would certainly be more efficient to walk the tree once, similarly to insert or delete.

Re-opening to keep track of this idea.