Improve Int{Set,Map}.fold*.
authorMilan Straka <fox@ucw.cz>
Sun, 4 Mar 2012 15:26:38 +0000 (16:26 +0100)
committerMilan Straka <fox@ucw.cz>
Sun, 4 Mar 2012 15:38:12 +0000 (16:38 +0100)
In the fold definitions, do not call go if the Bin constructor was
matched during the test for negative numbers. Instead, manually inline
that branch of go.

Otherwise GHC optimizer does this for us -- it creates local definition
of that branch of go and calls it. On my machine, it causes >200B growth
of object file, for every fold.

Data/IntMap/Base.hs
Data/IntSet.hs

index 2cda65f..0fd9eac 100644 (file)
@@ -1385,7 +1385,8 @@ splitLookup k t =
 foldr :: (a -> b -> b) -> b -> IntMap a -> b
 foldr f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
   case t of Bin _ m l r | m < 0 -> go (go z l) r -- put negative numbers before
-            _                   -> go z t
+                        | otherwise -> go (go z r) l
+            _ -> go z t
   where
     go z' Nil           = z'
     go z' (Tip _ x)     = f x z'
@@ -1398,7 +1399,8 @@ foldr f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
 foldr' :: (a -> b -> b) -> b -> IntMap a -> b
 foldr' f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
   case t of Bin _ m l r | m < 0 -> go (go z l) r -- put negative numbers before
-            _                   -> go z t
+                        | otherwise -> go (go z r) l
+            _ -> go z t
   where
     STRICT_1_OF_2(go)
     go z' Nil           = z'
@@ -1418,7 +1420,8 @@ foldr' f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
 foldl :: (a -> b -> a) -> a -> IntMap b -> a
 foldl f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
   case t of Bin _ m l r | m < 0 -> go (go z r) l -- put negative numbers before
-            _                   -> go z t
+                        | otherwise -> go (go z l) r
+            _ -> go z t
   where
     go z' Nil           = z'
     go z' (Tip _ x)     = f z' x
@@ -1431,7 +1434,8 @@ foldl f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
 foldl' :: (a -> b -> a) -> a -> IntMap b -> a
 foldl' f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
   case t of Bin _ m l r | m < 0 -> go (go z r) l -- put negative numbers before
-            _                   -> go z t
+                        | otherwise -> go (go z l) r
+            _ -> go z t
   where
     STRICT_1_OF_2(go)
     go z' Nil           = z'
@@ -1452,7 +1456,8 @@ foldl' f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
 foldrWithKey :: (Int -> a -> b -> b) -> b -> IntMap a -> b
 foldrWithKey f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
   case t of Bin _ m l r | m < 0 -> go (go z l) r -- put negative numbers before
-            _                   -> go z t
+                        | otherwise -> go (go z r) l
+            _ -> go z t
   where
     go z' Nil           = z'
     go z' (Tip kx x)    = f kx x z'
@@ -1465,7 +1470,8 @@ foldrWithKey f z = \t ->      -- Use lambda t to be inlinable with two arguments
 foldrWithKey' :: (Int -> a -> b -> b) -> b -> IntMap a -> b
 foldrWithKey' f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
   case t of Bin _ m l r | m < 0 -> go (go z l) r -- put negative numbers before
-            _                   -> go z t
+                        | otherwise -> go (go z r) l
+            _ -> go z t
   where
     STRICT_1_OF_2(go)
     go z' Nil           = z'
@@ -1486,7 +1492,8 @@ foldrWithKey' f z = \t ->      -- Use lambda t to be inlinable with two argument
 foldlWithKey :: (a -> Int -> b -> a) -> a -> IntMap b -> a
 foldlWithKey f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
   case t of Bin _ m l r | m < 0 -> go (go z r) l -- put negative numbers before
-            _                   -> go z t
+                        | otherwise -> go (go z l) r
+            _ -> go z t
   where
     go z' Nil           = z'
     go z' (Tip kx x)    = f z' kx x
@@ -1499,7 +1506,8 @@ foldlWithKey f z = \t ->      -- Use lambda t to be inlinable with two arguments
 foldlWithKey' :: (a -> Int -> b -> a) -> a -> IntMap b -> a
 foldlWithKey' f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
   case t of Bin _ m l r | m < 0 -> go (go z r) l -- put negative numbers before
-            _                   -> go z t
+                        | otherwise -> go (go z l) r
+            _ -> go z t
   where
     STRICT_1_OF_2(go)
     go z' Nil           = z'
index c22dbb4..f2ca853 100644 (file)
@@ -716,7 +716,8 @@ fold = foldr
 foldr :: (Int -> b -> b) -> b -> IntSet -> b
 foldr f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
   case t of Bin _ m l r | m < 0 -> go (go z l) r -- put negative numbers before
-            _                   -> go z t
+                        | otherwise -> go (go z r) l
+            _ -> go z t
   where
     go z' Nil           = z'
     go z' (Tip kx bm)   = foldrBits kx f z' bm
@@ -729,7 +730,8 @@ foldr f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
 foldr' :: (Int -> b -> b) -> b -> IntSet -> b
 foldr' f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
   case t of Bin _ m l r | m < 0 -> go (go z l) r -- put negative numbers before
-            _                   -> go z t
+                        | otherwise -> go (go z r) l
+            _ -> go z t
   where
     STRICT_1_OF_2(go)
     go z' Nil           = z'
@@ -746,7 +748,8 @@ foldr' f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
 foldl :: (a -> Int -> a) -> a -> IntSet -> a
 foldl f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
   case t of Bin _ m l r | m < 0 -> go (go z r) l -- put negative numbers before
-            _                   -> go z t
+                        | otherwise -> go (go z l) r
+            _ -> go z t
   where
     STRICT_1_OF_2(go)
     go z' Nil           = z'
@@ -760,7 +763,8 @@ foldl f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
 foldl' :: (a -> Int -> a) -> a -> IntSet -> a
 foldl' f z = \t ->      -- Use lambda t to be inlinable with two arguments only.
   case t of Bin _ m l r | m < 0 -> go (go z r) l -- put negative numbers before
-            _                   -> go z t
+                        | otherwise -> go (go z l) r
+            _ -> go z t
   where
     STRICT_1_OF_2(go)
     go z' Nil           = z'