Some inner loops may benefit from (manual) static argument transformation

[sjakobi]

Many inner loops in this package have a lot of static arguments, for example lookupCont:

unordered-containers/Data/HashMap/Internal.hs

Lines 669 to 686 in 2d537c1

	lookupCont absent present !h0 !k0 !s0 !m0 = go h0 k0 s0 m0
	where
	go :: Eq k => Hash -> k -> Int -> HashMap k v -> r
	go !_ !_ !_ Empty = absent (# #)
	go h k _ (Leaf hx (L kx x))
	| h == hx && k == kx = present x (-1)
	| otherwise = absent (# #)
	go h k s (BitmapIndexed b v)
	| b .&. m == 0 = absent (# #)
	| otherwise =
	go h k (s+bitsPerSubkey) (A.index v (sparseIndex b m))
	where m = mask h s
	go h k s (Full v) =
	go h k (s+bitsPerSubkey) (A.index v (index h s))
	go h k _ (Collision hx v)
	| h == hx = lookupInArrayCont absent present k v
	| otherwise = absent (# #)
	{-# INLINE lookupCont #-}

In bytestring we've sped up some functions by removing these arguments from the inner loop. See e.g. haskell/bytestring#273, haskell/bytestring#347. It would be good to check if u-c can benefit from similar transformations.

Note that GHC also has a -fstatic-argument-transformation option, but issues like GHC19285 suggest that it may not be in a usable state.

This GHC wiki page is interesting though: https://gitlab.haskell.org/ghc/ghc/-/wikis/static-argument-transformation

[sjakobi]

two.go might be a good candidate:

unordered-containers/Data/HashMap/Internal.hs

Lines 924 to 941 in f1ea9a4

	two :: Shift -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
	two = go
	where
	go s h1 k1 v1 h2 t2
	| bp1 == bp2 = do
	st <- go (s+bitsPerSubkey) h1 k1 v1 h2 t2
	ary <- A.singletonM st
	return $ BitmapIndexed bp1 ary
	| otherwise = do
	mary <- A.new 2 $! Leaf h1 (L k1 v1)
	A.write mary idx2 t2
	ary <- A.unsafeFreeze mary
	return $ BitmapIndexed (bp1 .|. bp2) ary
	where
	bp1 = mask h1 s
	bp2 = mask h2 s
	idx2 | index h1 s < index h2 s = 1
	| otherwise = 0

All but the s argument are static.

[sjakobi]

Thinking about this issue, I noticed an important difference to bytestring: In this library, most loops are bounded with a fairly small limit:

• Loops over the arrays of BitmapIndexed or Full have at most 32 iterations.
• Loops to the depth of the tree have at most ceiling (64 / 5) = 13 iterations (if I correctly understand the data structure)

For such loops the overhead of the static arguments may be fairly negligible.