Discussion:
Proposal: Strict variant of foldMap
(too old to reply)
Andrew Martin
2018-06-08 13:20:11 UTC
Permalink
I propose adding another method to the Foldable typeclass: foldMap'

This has the same behavior as foldMap except that it is strict in the
accumulator. This can lead to considerable performance gains when the user
knows that monoidal append is strict both arguments. Consider the following
example (available as a gist at
https://gist.github.com/andrewthad/f79b7022725532baf709514cf08c3955):

{-# LANGUAGE BangPatterns #-}
{-# OPTIONS_GHC -O2 #-}
import Gauge
import Data.Foldable
import qualified Data.Set as S

foldMap' :: (Monoid m, Foldable f) => (a -> m) -> f a -> m
foldMap' f = foldl' (\ !acc a -> acc <> f a) mempty

numbers :: [Int]
numbers = [1..4000]

intToSet :: Int -> S.Set Int
intToSet i = S.singleton (mod i 10)

main :: IO ()
main = defaultMain
[ bench "lazy" $ whnf (foldMap intToSet) numbers
, bench "strict" $ whnf (foldMap' intToSet) numbers
]

Here are the results we get from running this:

benchmarked lazy
time 178.8 ÎŒs (176.1 ÎŒs .. 183.1 ÎŒs)
0.996 R² (0.993 R² .. 0.998 R²)
mean 180.8 ÎŒs (179.1 ÎŒs .. 183.3 ÎŒs)
std dev 7.242 ÎŒs (5.856 ÎŒs .. 9.304 ÎŒs)
variance introduced by outliers: 20% (moderately inflated)

benchmarked strict
time 108.4 ÎŒs (106.1 ÎŒs .. 111.0 ÎŒs)
0.997 R² (0.996 R² .. 0.999 R²)
mean 107.9 ÎŒs (107.0 ÎŒs .. 109.3 ÎŒs)
std dev 3.672 ÎŒs (2.451 ÎŒs .. 6.220 ÎŒs)
variance introduced by outliers: 15% (moderately inflated)

These performance gains are considerable. It needs to be a method of
Foldable and not just a function written using foldl' for the same reason
that the lazy foldMap needs to be a method of Foldable. There are types for
which the default implementation can be improved upon. This is a
non-breaking change since there is a sensible default implementation.
--
-Andrew Thaddeus Martin
Michael Snoyman
2018-06-08 14:11:23 UTC
Permalink
+1

On Fri, Jun 8, 2018, 7:10 AM Simon Jakobi via Libraries <
I'm in favor of adding this to Foldable.
Post by Andrew Martin
I propose adding another method to the Foldable typeclass: foldMap'
This has the same behavior as foldMap except that it is strict in the
accumulator. This can lead to considerable performance gains when the
user
Post by Andrew Martin
knows that monoidal append is strict both arguments. Consider the
following
Post by Andrew Martin
example (available as a gist at
{-# LANGUAGE BangPatterns #-}
{-# OPTIONS_GHC -O2 #-}
import Gauge
import Data.Foldable
import qualified Data.Set as S
foldMap' :: (Monoid m, Foldable f) => (a -> m) -> f a -> m
foldMap' f = foldl' (\ !acc a -> acc <> f a) mempty
numbers :: [Int]
numbers = [1..4000]
intToSet :: Int -> S.Set Int
intToSet i = S.singleton (mod i 10)
main :: IO ()
main = defaultMain
[ bench "lazy" $ whnf (foldMap intToSet) numbers
, bench "strict" $ whnf (foldMap' intToSet) numbers
]
benchmarked lazy
time 178.8 ÎŒs (176.1 ÎŒs .. 183.1 ÎŒs)
0.996 R² (0.993 R² .. 0.998 R²)
mean 180.8 ÎŒs (179.1 ÎŒs .. 183.3 ÎŒs)
std dev 7.242 ÎŒs (5.856 ÎŒs .. 9.304 ÎŒs)
variance introduced by outliers: 20% (moderately inflated)
benchmarked strict
time 108.4 ÎŒs (106.1 ÎŒs .. 111.0 ÎŒs)
0.997 R² (0.996 R² .. 0.999 R²)
mean 107.9 ÎŒs (107.0 ÎŒs .. 109.3 ÎŒs)
std dev 3.672 ÎŒs (2.451 ÎŒs .. 6.220 ÎŒs)
variance introduced by outliers: 15% (moderately inflated)
These performance gains are considerable. It needs to be a method of
Foldable and not just a function written using foldl' for the same reason
that the lazy foldMap needs to be a method of Foldable. There are types
for
Post by Andrew Martin
which the default implementation can be improved upon. This is a
non-breaking change since there is a sensible default implementation.
--
-Andrew Thaddeus Martin
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Daniel Cartwright
2018-06-08 17:10:48 UTC
Permalink
+1
Post by Andrew Martin
I propose adding another method to the Foldable typeclass: foldMap'
This has the same behavior as foldMap except that it is strict in the
accumulator. This can lead to considerable performance gains when the user
knows that monoidal append is strict both arguments. Consider the following
example (available as a gist at
{-# LANGUAGE BangPatterns #-}
{-# OPTIONS_GHC -O2 #-}
import Gauge
import Data.Foldable
import qualified Data.Set as S
foldMap' :: (Monoid m, Foldable f) => (a -> m) -> f a -> m
foldMap' f = foldl' (\ !acc a -> acc <> f a) mempty
numbers :: [Int]
numbers = [1..4000]
intToSet :: Int -> S.Set Int
intToSet i = S.singleton (mod i 10)
main :: IO ()
main = defaultMain
[ bench "lazy" $ whnf (foldMap intToSet) numbers
, bench "strict" $ whnf (foldMap' intToSet) numbers
]
benchmarked lazy
time 178.8 ÎŒs (176.1 ÎŒs .. 183.1 ÎŒs)
0.996 R² (0.993 R² .. 0.998 R²)
mean 180.8 ÎŒs (179.1 ÎŒs .. 183.3 ÎŒs)
std dev 7.242 ÎŒs (5.856 ÎŒs .. 9.304 ÎŒs)
variance introduced by outliers: 20% (moderately inflated)
benchmarked strict
time 108.4 ÎŒs (106.1 ÎŒs .. 111.0 ÎŒs)
0.997 R² (0.996 R² .. 0.999 R²)
mean 107.9 ÎŒs (107.0 ÎŒs .. 109.3 ÎŒs)
std dev 3.672 ÎŒs (2.451 ÎŒs .. 6.220 ÎŒs)
variance introduced by outliers: 15% (moderately inflated)
These performance gains are considerable. It needs to be a method of
Foldable and not just a function written using foldl' for the same reason
that the lazy foldMap needs to be a method of Foldable. There are types for
which the default implementation can be improved upon. This is a
non-breaking change since there is a sensible default implementation.
--
-Andrew Thaddeus Martin
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
evan@evan-borden.com
2018-06-08 19:11:17 UTC
Permalink
+1 We utilize a foldMap' in the freckle codebase.
Post by Andrew Martin
+1
Post by Andrew Martin
I propose adding another method to the Foldable typeclass: foldMap'
This has the same behavior as foldMap except that it is strict in the
accumulator. This can lead to considerable performance gains when the user
knows that monoidal append is strict both arguments. Consider the following
example (available as a gist at https://gist.github.com/andrewthad/
{-# LANGUAGE BangPatterns #-}
{-# OPTIONS_GHC -O2 #-}
import Gauge
import Data.Foldable
import qualified Data.Set as S
foldMap' :: (Monoid m, Foldable f) => (a -> m) -> f a -> m
foldMap' f = foldl' (\ !acc a -> acc <> f a) mempty
numbers :: [Int]
numbers = [1..4000]
intToSet :: Int -> S.Set Int
intToSet i = S.singleton (mod i 10)
main :: IO ()
main = defaultMain
[ bench "lazy" $ whnf (foldMap intToSet) numbers
, bench "strict" $ whnf (foldMap' intToSet) numbers
]
benchmarked lazy
time 178.8 ÎŒs (176.1 ÎŒs .. 183.1 ÎŒs)
0.996 R² (0.993 R² .. 0.998 R²)
mean 180.8 ÎŒs (179.1 ÎŒs .. 183.3 ÎŒs)
std dev 7.242 ÎŒs (5.856 ÎŒs .. 9.304 ÎŒs)
variance introduced by outliers: 20% (moderately inflated)
benchmarked strict
time 108.4 ÎŒs (106.1 ÎŒs .. 111.0 ÎŒs)
0.997 R² (0.996 R² .. 0.999 R²)
mean 107.9 ÎŒs (107.0 ÎŒs .. 109.3 ÎŒs)
std dev 3.672 ÎŒs (2.451 ÎŒs .. 6.220 ÎŒs)
variance introduced by outliers: 15% (moderately inflated)
These performance gains are considerable. It needs to be a method of
Foldable and not just a function written using foldl' for the same reason
that the lazy foldMap needs to be a method of Foldable. There are types for
which the default implementation can be improved upon. This is a
non-breaking change since there is a sensible default implementation.
--
-Andrew Thaddeus Martin
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
--
--
Evan Borden
Edward Kmett
2018-06-09 08:23:26 UTC
Permalink
+1 from me.

-Edward
Post by ***@evan-borden.com
+1 We utilize a foldMap' in the freckle codebase.
Post by Andrew Martin
+1
Post by Andrew Martin
I propose adding another method to the Foldable typeclass: foldMap'
{-# LANGUAGE BangPatterns #-}
{-# OPTIONS_GHC -O2 #-}
import Gauge
import Data.Foldable
import qualified Data.Set as S
foldMap' :: (Monoid m, Foldable f) => (a -> m) -> f a -> m
foldMap' f = foldl' (\ !acc a -> acc <> f a) mempty
numbers :: [Int]
numbers = [1..4000]
intToSet :: Int -> S.Set Int
intToSet i = S.singleton (mod i 10)
main :: IO ()
main = defaultMain
[ bench "lazy" $ whnf (foldMap intToSet) numbers
, bench "strict" $ whnf (foldMap' intToSet) numbers
]
benchmarked lazy
time 178.8 ÎŒs (176.1 ÎŒs .. 183.1 ÎŒs)
0.996 R² (0.993 R² .. 0.998 R²)
mean 180.8 ÎŒs (179.1 ÎŒs .. 183.3 ÎŒs)
std dev 7.242 ÎŒs (5.856 ÎŒs .. 9.304 ÎŒs)
variance introduced by outliers: 20% (moderately inflated)
benchmarked strict
time 108.4 ÎŒs (106.1 ÎŒs .. 111.0 ÎŒs)
0.997 R² (0.996 R² .. 0.999 R²)
mean 107.9 ÎŒs (107.0 ÎŒs .. 109.3 ÎŒs)
std dev 3.672 ÎŒs (2.451 ÎŒs .. 6.220 ÎŒs)
variance introduced by outliers: 15% (moderately inflated)
These performance gains are considerable. It needs to be a method of Foldable and not just a function written using foldl' for the same reason that the lazy foldMap needs to be a method of Foldable. There are types for which the default implementation can be improved upon. This is a non-breaking change since there is a sensible default implementation.
--
-Andrew Thaddeus Martin
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
--
--
Evan Borden
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Andrew Martin
2018-06-29 00:11:30 UTC
Permalink
I don't see any reason to not do this. Someone just needs to put a
differential on phabricator, adding foldMap, a default implementation, and
documentation of it. It would be maybe 6 lines total. The default
implementation of foldMap' would use foldl' and that would be optimal for
everything in base.

On Thu, Jun 28, 2018 at 6:38 PM, Simon Jakobi via Libraries <
Is there any chance that foldMap' might still make it into base-4.12?
Post by Edward Kmett
+1 from me.
-Edward
+1 We utilize a foldMap' in the freckle codebase.
Post by Andrew Martin
+1
Post by Andrew Martin
I propose adding another method to the Foldable typeclass: foldMap'
This has the same behavior as foldMap except that it is strict in the
accumulator. This can lead to considerable performance gains when the user
knows that monoidal append is strict both arguments. Consider the following
example (available as a gist at https://gist.github.com/andrewthad/
Post by Edward Kmett
Post by Andrew Martin
Post by Andrew Martin
{-# LANGUAGE BangPatterns #-}
{-# OPTIONS_GHC -O2 #-}
import Gauge
import Data.Foldable
import qualified Data.Set as S
foldMap' :: (Monoid m, Foldable f) => (a -> m) -> f a -> m
foldMap' f = foldl' (\ !acc a -> acc <> f a) mempty
numbers :: [Int]
numbers = [1..4000]
intToSet :: Int -> S.Set Int
intToSet i = S.singleton (mod i 10)
main :: IO ()
main = defaultMain
[ bench "lazy" $ whnf (foldMap intToSet) numbers
, bench "strict" $ whnf (foldMap' intToSet) numbers
]
benchmarked lazy
time 178.8 ÎŒs (176.1 ÎŒs .. 183.1 ÎŒs)
0.996 R² (0.993 R² .. 0.998 R²)
mean 180.8 ÎŒs (179.1 ÎŒs .. 183.3 ÎŒs)
std dev 7.242 ÎŒs (5.856 ÎŒs .. 9.304 ÎŒs)
variance introduced by outliers: 20% (moderately inflated)
benchmarked strict
time 108.4 ÎŒs (106.1 ÎŒs .. 111.0 ÎŒs)
0.997 R² (0.996 R² .. 0.999 R²)
mean 107.9 ÎŒs (107.0 ÎŒs .. 109.3 ÎŒs)
std dev 3.672 ÎŒs (2.451 ÎŒs .. 6.220 ÎŒs)
variance introduced by outliers: 15% (moderately inflated)
These performance gains are considerable. It needs to be a method of
Foldable and not just a function written using foldl' for the same reason
that the lazy foldMap needs to be a method of Foldable. There are types for
which the default implementation can be improved upon. This is a
non-breaking change since there is a sensible default implementation.
Post by Edward Kmett
Post by Andrew Martin
Post by Andrew Martin
--
-Andrew Thaddeus Martin
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
--
--
Evan Borden
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
--
-Andrew Thaddeus Martin
Loading...