UniqSet: Implement unionManyUniqSets in terms of foldl' instead of foldr
authorBen Gamari <bgamari.foss@gmail.com>
Tue, 24 Jan 2017 17:50:00 +0000 (12:50 -0500)
committerBen Gamari <ben@smart-cactus.org>
Tue, 24 Jan 2017 21:07:34 +0000 (16:07 -0500)
foldr generally isn't a good choice for folds where the result can't be
consumed incrementally. This gives a very modest improvement in
compiler allocations,
```
        -1 s.d.                -----          -0.182%
        +1 s.d.                -----          -0.050%
        Average                -----          -0.116%
```
This is clearly semantics-preserving since we are constructing a set.

Test Plan: Validate

Reviewers: austin

Subscribers: dfeuer, thomie

Differential Revision: https://phabricator.haskell.org/D2965

compiler/utils/UniqSet.hs

index f08fa86..6f58652 100644 (file)
@@ -34,6 +34,7 @@ module UniqSet (
 
 import UniqFM
 import Unique
+import Data.Foldable (foldl')
 
 {-
 ************************************************************************
@@ -90,19 +91,18 @@ type UniqSet a = UniqFM a
 
 emptyUniqSet = emptyUFM
 unitUniqSet x = unitUFM x x
-mkUniqSet = foldl addOneToUniqSet emptyUniqSet
+mkUniqSet = foldl' addOneToUniqSet emptyUniqSet
 
 addOneToUniqSet set x = addToUFM set x x
 addOneToUniqSet_C f set x = addToUFM_C f set x x
-addListToUniqSet = foldl addOneToUniqSet
+addListToUniqSet = foldl' addOneToUniqSet
 
 delOneFromUniqSet = delFromUFM
 delOneFromUniqSet_Directly = delFromUFM_Directly
 delListFromUniqSet = delListFromUFM
 
 unionUniqSets = plusUFM
-unionManyUniqSets [] = emptyUniqSet
-unionManyUniqSets sets = foldr1 unionUniqSets sets
+unionManyUniqSets = foldl' (flip unionUniqSets) emptyUniqSet
 minusUniqSet = minusUFM
 intersectUniqSets = intersectUFM