Make use of shrinkSmallMutableArray# primop

[sjakobi]

Since GHC 8.10 there is a shrinkSmallMutableArray# primop that may be useful for functions like filter and mapMaybe. It would allow us to perform deletions in-place instead of creating a new array.

[treeowl]

Ooh, good thinking!

[sjakobi]

We may be able to use it wherever we're currently using trim:

unordered-containers/Data/HashMap/Internal/Array.hs

Lines 295 to 298 in d4e31f6

	-- | Create a new array of the @n@ first elements of @mary@.
	trim :: MArray s a -> Int -> ST s (Array a)
	trim mary n = cloneM mary 0 n >>= unsafeFreeze
	{-# INLINE trim #-}

[sjakobi]

#406 has introduced shrink:

unordered-containers/Data/HashMap/Internal/Array.hs

Lines 210 to 222 in d24cc1f

	-- | When 'Exts.shrinkSmallMutableArray#' is available, the returned array is the same as the array given, as it is shrunk in place.
	-- Otherwise a copy is made.
	shrink :: MArray s a -> Int -> ST s (MArray s a)
	#if __GLASGOW_HASKELL__ >= 810
	shrink mary _n@(I# n#) =
	CHECK_GT("shrink", _n, (0 :: Int))
	CHECK_LE("shrink", _n, (lengthM mary))
	ST $ \s -> case Exts.shrinkSmallMutableArray# (unMArray mary) n# s of
	s' -> (# s', mary #)
	#else
	shrink mary n = cloneM mary 0 n
	#endif
	{-# INLINE shrink #-}

So far it's only used in intersection[With[Key]] though.

[sjakobi]

With #433 we're using shrink in filter and mapMaybe now. #435 refactors updateOrConcatWithKey to use shrink. I can't find any obvious other spots where shrink would be useful.

[sjakobi]

For reference: some performance aspects of shrinkSmallMutableArray# are still unclear: #441