Skip to content

Instantly share code, notes, and snippets.

@viercc
Last active November 30, 2022 06:00
Show Gist options
  • Save viercc/bb860aa4d8409ba5f00efb183c3e7576 to your computer and use it in GitHub Desktop.
Save viercc/bb860aa4d8409ba5f00efb183c3e7576 to your computer and use it in GitHub Desktop.
Performance of manually implemented foldl' on GHCi
module Foldl(foldl', foldl'Copied, foldl'CopiedMono, foldl'Recursion, foldl'Recursion2) where
import Data.List (foldl')
import GHC.Exts (oneShot)
foldl'Copied :: Foldable t => (b -> a -> b) -> b -> t a -> b
{-# INLINE foldl'Copied #-}
foldl'Copied f z0 = \ xs -> foldr (\ (x::a) (k::b->b) -> oneShot (\ (z::b) -> z `seq` k (f z x))) (id::b->b) xs z0
foldl'CopiedMono :: (b -> a -> b) -> b -> [a] -> b
{-# INLINE foldl'CopiedMono #-}
foldl'CopiedMono f z0 = \ xs -> foldr (\ (x::a) (k::b->b) -> oneShot (\ (z::b) -> z `seq` k (f z x))) (id::b->b) xs z0
foldl'Recursion :: (b -> a -> b) -> b -> [a] -> b
{-# INLINE foldl'Recursion #-}
foldl'Recursion f !z [] = z
foldl'Recursion f !z (x:xs) = foldl'Recursion f (f z x) xs
foldl'Recursion2 :: (b -> a -> b) -> b -> [a] -> b
{-# INLINE foldl'Recursion2 #-}
foldl'Recursion2 f = loop
where
loop !z [] = z
loop !z (x:xs) = loop (f z x) xs
$ ghci -fobject-code -O2 -ddump-rule-firings -XGHC2021 Foldl.hs
GHCi, version 9.4.2: https://www.haskell.org/ghc/ :? for help
Ok, one module loaded.
ghci> :set +s
ghci> foldl' (+) 0 [0..100000000]
Rule fired: Class op foldl' (BUILTIN)
Rule fired: unsafeEqualityProof (BUILTIN)
5000000050000000
(2.02 secs, 8,800,114,176 bytes)
ghci> foldl' (+) 0 [0..100000000]
Rule fired: Class op foldl' (BUILTIN)
Rule fired: unsafeEqualityProof (BUILTIN)
5000000050000000
(1.98 secs, 8,800,111,152 bytes)
ghci> foldl' (+) 0 [0..100000000]
Rule fired: Class op foldl' (BUILTIN)
Rule fired: unsafeEqualityProof (BUILTIN)
5000000050000000
(2.00 secs, 8,800,111,152 bytes)
ghci> foldl'Copied (+) 0 [0..100000000]
Rule fired: unsafeEqualityProof (BUILTIN)
5000000050000000
(5.37 secs, 20,000,111,392 bytes)
ghci> foldl'Copied (+) 0 [0..100000000]
Rule fired: unsafeEqualityProof (BUILTIN)
5000000050000000
(5.32 secs, 20,000,111,392 bytes)
ghci> foldl'Copied (+) 0 [0..100000000]
Rule fired: unsafeEqualityProof (BUILTIN)
5000000050000000
(5.21 secs, 20,000,111,392 bytes)
ghci> foldl'Recursion (+) 0 [0..100000000]
Rule fired: unsafeEqualityProof (BUILTIN)
5000000050000000
(2.74 secs, 8,800,111,152 bytes)
ghci> foldl'Recursion (+) 0 [0..100000000]
Rule fired: unsafeEqualityProof (BUILTIN)
5000000050000000
(2.61 secs, 8,800,111,152 bytes)
ghci> foldl'Recursion (+) 0 [0..100000000]
Rule fired: unsafeEqualityProof (BUILTIN)
5000000050000000
(2.77 secs, 8,800,111,152 bytes)
ghci> foldl'Recursion2 (+) 0 [0..100000000]
Rule fired: unsafeEqualityProof (BUILTIN)
5000000050000000
(2.04 secs, 8,800,111,152 bytes)
ghci> foldl'Recursion2 (+) 0 [0..100000000]
Rule fired: unsafeEqualityProof (BUILTIN)
5000000050000000
(2.06 secs, 8,800,111,152 bytes)
ghci> foldl'Recursion2 (+) 0 [0..100000000]
Rule fired: unsafeEqualityProof (BUILTIN)
5000000050000000
(2.03 secs, 8,800,111,152 bytes)
$ # Additional run for foldl'CopiedMono
$ ghci -fobject-code -O2 -ddump-stg-final -ddump-to-file -XGHC2021 Foldl.hs
GHCi, version 9.4.2: https://www.haskell.org/ghc/ :? for help
[1 of 1] Compiling Foldl ( Foldl.hs, Foldl.o ) [Missing object file]
Ok, one module loaded.
ghci> :set +s
ghci> foldl' (+) 0 [0..100000000]
5000000050000000
(2.13 secs, 8,800,121,168 bytes)
ghci> foldl' (+) 0 [0..100000000]
5000000050000000
(2.15 secs, 8,800,118,128 bytes)
ghci> foldl' (+) 0 [0..100000000]
5000000050000000
(2.20 secs, 8,800,118,136 bytes)
ghci> foldl'CopiedMono (+) 0 [0..100000000]
5000000050000000
(2.22 secs, 8,800,118,136 bytes)
ghci> foldl'CopiedMono (+) 0 [0..100000000]
5000000050000000
(2.15 secs, 8,800,118,136 bytes)
ghci> foldl'CopiedMono (+) 0 [0..100000000]
5000000050000000
(2.16 secs, 8,800,118,136 bytes)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment