Reduce insert code size

[tibbe]

Currently the insert function generated ~600 lines of Cmm with GHC HEAD. The breakdown for each constructor is roughly:

• Empty: 16 (2.7%)
• BitmapIndexed: 213 (35.5%)
• Leaf: 133 (22.2%)
• Full: 65 (10.8%)
• Collision: 63 (10.5%)

plus 33 (5.5%) shared lines. There are also 67 non-code lines.

Code related to collisions could probably be pulled out-of-line without a performance hit. We might also be able to avoid inlining larger function, such as Array.insert, without a performance penalty.

[treeowl]

In an informal experiment, I saw quite a performance improvement by just refraining from inlining two. Specifically, I renamed the current function twoBase and then wrote monadic and pure versions calling it, each of which were NOINLINE. I bet you're right about those larger functions as well— pretty much any thaw-modify-unsafeFreeze would be a good candidate, especially if it doesn't have to call a user function or use a class instance in the process. And I know you're wary of INLINABLE, but I have the feeling we could probably afford to use it a bit more.

[treeowl]

As I've mentioned before, I also want to experiment with getting rid of the Full constructor.

[treeowl]

Hrmph.... Simply removing Full gives horrible performance. Oh well.

[sjakobi]

In an informal experiment, I saw quite a performance improvement by just refraining from inlining two. Specifically, I renamed the current function twoBase and then wrote monadic and pure versions calling it, each of which were NOINLINE.

This still seems worth implementing. Although I don't currently understand why both a monadic and a pure version are required.

---

unordered-containers/Data/HashMap/Internal.hs

Lines 969 to 987 in 8c20f7a

	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 (nextShift s) 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
	{-# INLINE two #-}

The code size of two itself could be substantially reduced by tweaking the computation of idx2. Currently it involves a branch where the two alternatives differ only by the array index of the write:

          case <#
                 (word2Int# (and# (uncheckedShiftRL# ww1 ww) 31##))
                 (word2Int# (and# (uncheckedShiftRL# ww2 ww) 31##))
          of {
            __DEFAULT ->
              case writeSmallArray# @s @(HashMap k v) ipv1 0# w2 ipv of s'
              { __DEFAULT ->
              case unsafeFreezeSmallArray# @s @(HashMap k v) ipv1 s' of
              { (# ipv2, ipv3 #) ->
              (# ipv2, BitmapIndexed @k @v (or# x y) ipv3 #)
              }
              };
            1# ->
              case writeSmallArray# @s @(HashMap k v) ipv1 1# w2 ipv of s'
              { __DEFAULT ->
              case unsafeFreezeSmallArray# @s @(HashMap k v) ipv1 s' of
              { (# ipv2, ipv3 #) ->
              (# ipv2, BitmapIndexed @k @v (or# x y) ipv3 #)
              }
              }

This branch could probably be entirely avoided if we'd re-use the comparison result as the index, maybe with something like

idx2 = fromEnum (index h1 s < index h2 s)

(The comparison itself could probably be optimized a tiny bit too: We don't actually need the index – just clearing the higher bits should be sufficient.)