Refactor unionWithKey

[treeowl]

Most unpleasantly, it has a separate case for taking the union of a Leaf with each type of (non-empty) node. Perhaps we should pull the go function out of insertModifying and make it provide the old key to the function as well as the old value. Then we can just have one case in unionWithKey for a leaf as the left argument and a leaf as the right argument.

[sjakobi]

It's these sections that you want to improve, right?

unordered-containers/Data/HashMap/Base.hs

Lines 1433 to 1447 in 7485f5c

	-- leaf vs. leaf
	go s t1@(Leaf h1 l1@(L k1 v1)) t2@(Leaf h2 l2@(L k2 v2))
	| h1 == h2 = if k1 == k2
	then Leaf h1 (L k1 (f k1 v1 v2))
	else collision h1 l1 l2
	| otherwise = goDifferentHash s h1 h2 t1 t2
	go s t1@(Leaf h1 (L k1 v1)) t2@(Collision h2 ls2)
	| h1 == h2 = Collision h1 (updateOrSnocWithKey (\k a b -> (# f k a b #)) k1 v1 ls2)
	| otherwise = goDifferentHash s h1 h2 t1 t2
	go s t1@(Collision h1 ls1) t2@(Leaf h2 (L k2 v2))
	| h1 == h2 = Collision h1 (updateOrSnocWithKey (\k a b -> (# f k b a #)) k2 v2 ls1)
	| otherwise = goDifferentHash s h1 h2 t1 t2
	go s t1@(Collision h1 ls1) t2@(Collision h2 ls2)
	| h1 == h2 = Collision h1 (updateOrConcatWithKey f ls1 ls2)
	| otherwise = goDifferentHash s h1 h2 t1 t2

unordered-containers/Data/HashMap/Base.hs

Lines 1463 to 1495 in 7485f5c

	-- leaf vs. branch
	go s (BitmapIndexed b1 ary1) t2
	| b1 .&. m2 == 0 = let ary' = A.insert ary1 i t2
	b' = b1 .|. m2
	in bitmapIndexedOrFull b' ary'
	| otherwise = let ary' = A.updateWith' ary1 i $ \st1 ->
	go (s+bitsPerSubkey) st1 t2
	in BitmapIndexed b1 ary'
	where
	h2 = leafHashCode t2
	m2 = mask h2 s
	i = sparseIndex b1 m2
	go s t1 (BitmapIndexed b2 ary2)
	| b2 .&. m1 == 0 = let ary' = A.insert ary2 i $! t1
	b' = b2 .|. m1
	in bitmapIndexedOrFull b' ary'
	| otherwise = let ary' = A.updateWith' ary2 i $ \st2 ->
	go (s+bitsPerSubkey) t1 st2
	in BitmapIndexed b2 ary'
	where
	h1 = leafHashCode t1
	m1 = mask h1 s
	i = sparseIndex b2 m1
	go s (Full ary1) t2 =
	let h2 = leafHashCode t2
	i = index h2 s
	ary' = update16With' ary1 i $ \st1 -> go (s+bitsPerSubkey) st1 t2
	in Full ary'
	go s t1 (Full ary2) =
	let h1 = leafHashCode t1
	i = index h1 s
	ary' = update16With' ary2 i $ \st2 -> go (s+bitsPerSubkey) t1 st2
	in Full ary'

Is the repetitiveness the main problem or are you suspecting a performance issue, too?

[treeowl]

Just repetitiveness and especially unnecessary complication.

[sjakobi]

I noticed that this issue is basically the same as #227. @treeowl, could you please consolidate these two?

[sjakobi]

Copying @treeowl's comment from #227:

Hrm.... It's trickier than that. If m doesn't contain k, and we're combining t@(Leaf h l@(L k v)) with m, we can usually reuse t and the rest of the time we can reuse l. Using insertModifying, we'd end up allocating a lot of new Leaf and L constructors, to the tune of something like six words per entry. That's a bit too steep. But I think it may still make sense to try to tease these things apart a bit.