Is unions "little" wrong ?

[ashishnegi]

Looking at unions and union

union says that first argument should be smaller set.
foldl' used in unions would give bigger sets in each iteration's accumulator,
which becomes first argument to union ; leading to slower performance.

Should not we use flip union in unions ?
Or i am missing something.

[sjakobi]

Thanks for the report, @ashishnegi. Indeed it does seem like we're missing out on some easy wins!

union says that first argument should be smaller set.

This is the relevant code section:

unordered-containers/Data/HashSet/Base.hs

Lines 267 to 278 in f1a53e2

	-- | /O(n+m)/ Construct a set containing all elements from both sets.
	--
	-- To obtain good performance, the smaller set must be presented as
	-- the first argument.
	--
	-- ==== __Examples__
	--
	-- >>> union (fromList [1,2]) (fromList [2,3])
	-- fromList [1,2,3]
	union :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
	union s1 s2 = HashSet $ H.union (asMap s1) (asMap s2)
	{-# INLINE union #-}

Since HashSet.union is just such a tiny wrapper around HashMap.union, which in turn wraps HashMap.unionWithKey via HashMap.unionWith, I think it's a bit curious that the latter two don't have a similar note!

unordered-containers/Data/HashMap/Base.hs

Lines 1368 to 1384 in f1a53e2

	union :: (Eq k, Hashable k) => HashMap k v -> HashMap k v -> HashMap k v
	union = unionWith const
	{-# INLINABLE union #-}
	-- | /O(n+m)/ The union of two maps. If a key occurs in both maps,
	-- the provided function (first argument) will be used to compute the
	-- result.
	unionWith :: (Eq k, Hashable k) => (v -> v -> v) -> HashMap k v -> HashMap k v
	-> HashMap k v
	unionWith f = unionWithKey (const f)
	{-# INLINE unionWith #-}
	-- | /O(n+m)/ The union of two maps. If a key occurs in both maps,
	-- the provided function (first argument) will be used to compute the
	-- result.
	unionWithKey :: (Eq k, Hashable k) => (k -> v -> v -> v) -> HashMap k v -> HashMap k v
	-> HashMap k v

I think we should first check whether this advice is still true. @tibbe, do you have any insight here?

[tibbe]

I don't remember the details here but likely HashMap should have the same note as HashSet.

[sjakobi]

Thanks, @tibbe! :)

It would be good to investigate the issue a bit! :)

I think the first thing to do would be some simple benchmarks in order to confirm that this "performance bias" exists.

It would also be interesting to know where the bias comes from – somewhere in unionWithKey, I assume! Although a fix wouldn't necessarily have to wait for that.

@ashishnegi Are you still interested in this issue?

[ashishnegi]

it has been some time since i used this repo.. and haskell :(
but i think their should be many customers of this repo.. who will benefit from perf improvements.

[sjakobi]

Thanks for the fast response, @ashishnegi! :)

I understand that you're currently not interested in working on this. No wonder – it's been 3 and a half years!

[treeowl]

If we flip the union, I believe that'll change semantics. We might want to write an opposite-biased version for this purpose.

[sjakobi]

If this performance bias actually exists, improving unions might be as simple changing

-unions = L.foldl' union empty
+unions = L.foldl' (flip (unionWith (flip const))) empty

(just check that the flips are optimized away)

In fact, if this implementation gives significantly better benchmark results, I'd take that as sufficient evidence that the claimed performance bias exists.

[treeowl]

Good point!