efficient combination of foldl' and foldr -> foldl'r
I want to do a foldl' and a foldr in parallel on a list. I assumed it would be no good idea to run foldl' and foldr separately, because then the input list must be stored completely between the calls of foldl' and foldr. I wanted to be clever and implemented a routine which does foldl' and foldr in one go. But surprisingly, at least in GHCi, my clever routine is less efficient than the naive one. Is foldl'rNaive better than I expect, or is foldl'r worse than I hope? module FoldLR where import Data.List (foldl', ) import Control.Arrow (first, second, (***), ) foldl'r, foldl'rNaive :: (b -> a -> b) -> b -> (c -> d -> d) -> d -> [(a,c)] -> (b,d) foldl'r f b0 g d0 = first ($b0) . foldr (\(a,c) ~(k,d) -> (\b -> k $! f b a, g c d)) (id,d0) foldl'rNaive f b g d xs = (foldl' f b *** foldr g d) $ unzip xs test, testNaive :: (Integer, Char) test = second last $ foldl'r (+) 0 (:) "" $ replicate 1000000 (1,'a') {- *FoldLR> test (1000000,'a') (2.65 secs, 237509960 bytes) -} testNaive = second last $ foldl'rNaive (+) 0 (:) "" $ replicate 1000000 (1,'a') {- *FoldLR> testNaive (1000000,'a') (0.50 secs, 141034352 bytes) -}
You're testing the interpreted code, so it's not surprising that the
naive version performs better; the interpretive overhead only applies
to your bit of glue code. So, you've succeeded in showing that
compiled code performs better than interpreted code, congratulations!
:)
A better test would be to write "main" that does the calculation and
compile with -O2. You can then use plain old command line tools to
test the timing.
Alternatively, at least compile the module with optimizations before
running it in ghci:
ryani$ ghc -ddump-simpl -O2 -c foldlr.hs >foldlr.core
(This gives you "functional assembly language" to look at for
examining code generation)
ryani$ ghci foldlr.hs
[...]
Prelude FoldLR> :set +s
Prelude FoldLR> test
(1000000,'a')
(0.39 secs, 70852332 bytes)
Prelude FoldLR> testNaive
(1000000,'a')
(0.42 secs, 105383824 bytes)
-- ryan
On Fri, Dec 5, 2008 at 7:04 AM, Henning Thielemann
I want to do a foldl' and a foldr in parallel on a list. I assumed it would be no good idea to run foldl' and foldr separately, because then the input list must be stored completely between the calls of foldl' and foldr. I wanted to be clever and implemented a routine which does foldl' and foldr in one go. But surprisingly, at least in GHCi, my clever routine is less efficient than the naive one.
Is foldl'rNaive better than I expect, or is foldl'r worse than I hope?
module FoldLR where
import Data.List (foldl', ) import Control.Arrow (first, second, (***), )
foldl'r, foldl'rNaive :: (b -> a -> b) -> b -> (c -> d -> d) -> d -> [(a,c)] -> (b,d)
foldl'r f b0 g d0 = first ($b0) . foldr (\(a,c) ~(k,d) -> (\b -> k $! f b a, g c d)) (id,d0)
foldl'rNaive f b g d xs = (foldl' f b *** foldr g d) $ unzip xs
test, testNaive :: (Integer, Char) test = second last $ foldl'r (+) 0 (:) "" $ replicate 1000000 (1,'a') {- *FoldLR> test (1000000,'a') (2.65 secs, 237509960 bytes) -}
testNaive = second last $ foldl'rNaive (+) 0 (:) "" $ replicate 1000000 (1,'a') {- *FoldLR> testNaive (1000000,'a') (0.50 secs, 141034352 bytes) -}
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Fri, 5 Dec 2008, Ryan Ingram wrote:
You're testing the interpreted code, so it's not surprising that the naive version performs better; the interpretive overhead only applies to your bit of glue code.
I wanted to avoid the optimizer to do clever things itself.
Alternatively, at least compile the module with optimizations before running it in ghci:
ryani$ ghc -ddump-simpl -O2 -c foldlr.hs >foldlr.core (This gives you "functional assembly language" to look at for examining code generation)
ryani$ ghci foldlr.hs [...] Prelude FoldLR> :set +s Prelude FoldLR> test (1000000,'a') (0.39 secs, 70852332 bytes) Prelude FoldLR> testNaive (1000000,'a') (0.42 secs, 105383824 bytes)
There is still no clear advantage of foldl'r compared to foldl'rNaive, is it?
Hi, Am Freitag, den 05.12.2008, 23:43 +0100 schrieb Henning Thielemann:
ryani$ ghci foldlr.hs [...] Prelude FoldLR> :set +s Prelude FoldLR> test (1000000,'a') (0.39 secs, 70852332 bytes) Prelude FoldLR> testNaive (1000000,'a') (0.42 secs, 105383824 bytes)
There is still no clear advantage of foldl'r compared to foldl'rNaive, is it?
Maybe not directly speed-wise, but the memory consumption is reduced by 30% (probably due to laziness, and unless I misreading ghci’s output) Greetings, Joachim -- Joachim "nomeata" Breitner mail: mail@joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C JID: nomeata@joachim-breitner.de | http://www.joachim-breitner.de/ Debian Developer: nomeata@debian.org
participants (3)
-
Henning Thielemann -
Joachim Breitner -
Ryan Ingram