IntMap.delete allocates even for absent keys

[sjakobi]

containers/containers/src/Data/IntMap/Internal.hs

Lines 966 to 974 in 78da761

	delete :: Key -> IntMap a -> IntMap a
	delete !k t@(Bin p l r)
	| nomatch k p = t
	| left k p = binCheckL p (delete k l) r
	| otherwise = binCheckR p l (delete k r)
	delete k t@(Tip ky _)
	| k == ky = Nil
	| otherwise = t
	delete _k Nil = Nil

I noticed some code in GHC that performs a bunch of deletions (on the very similar Word64Map) with keys that are most likely absent from the map. So now I'm wondering whether to introduce pointer-checks in Word64Map.delete or to split off a delete_possiblyAbsent version or…

But since Word64Map is derived from IntMap, my first question is: why doesn't IntMap.delete perform these pointer-checks already, even though Map.delete does?

containers/containers/src/Data/Map/Internal.hs

Lines 941 to 955 in 78da761

	delete :: Ord k => k -> Map k a -> Map k a
	delete = go
	where
	go :: Ord k => k -> Map k a -> Map k a
	go !_ Tip = Tip
	go k t@(Bin _ kx x l r) =
	case compare k kx of
	LT | l' `ptrEq` l -> t
	| otherwise -> balanceR kx x l' r
	where !l' = go k l
	GT | r' `ptrEq` r -> t
	| otherwise -> balanceL kx x l r'
	where !r' = go k r
	EQ -> glue l r
	{-# INLINABLE delete #-}

[sjakobi]

I just noticed that I posed a more general version of this question before: #835

[meooow25]

This is a good point, I think currently the library is not very consistent. Some functions on some structures try to avoid these allocations, and the rest don't.

In theory such checks would have a small runtime cost affecting both cases, absent and present, but it is likely worth it. We can benchmark and see how much it matters in practice.

Also, it doesn't have to be through pointer-equality (which feels hacky to me). Returning a StrictPair Bool (Map k a) with the Bool indicating whether we need to allocate should be equally efficient on GHC.

[sjakobi]

For keys, that are likely to be absent, I think it may also be a good pattern to simply run a member check before performing the deletion. This ought to be even faster than enhancing delete to avoid allocations, because unlike delete, member doesn't have to walk back up the tree.