CODEWITHSUNDEEP
haskellprofiling
Dave0504
Dave0504

Reputation: 1107

Haskell Profiling

I'm going through LYAH and have been looking at the use of list comprehension vs map/filters when processing lists. I've profiled the following two functions and included the prof outputs as well. If I am reading the prof correctly id say the FiltB is running a lot slower than FiltA (although its only by thousandths of seconds).

Would be right in saying this is because FiltB has to evaluate x^2 twice?

FiltA.hs (filter odd)

-- FiltA.hs

module Main
    where

main = do
    let x = sum (takeWhile (<10000) (filter odd (map (^2) [1..])))
    print x

    Sat Jul 26 18:26 2014 Time and Allocation Profiling Report  (Final)

       Filta.exe +RTS -p -RTS

    total time  =        0.00 secs   (0 ticks @ 1000 us, 1 processor)
    total alloc =      92,752 bytes  (excludes profiling overheads)

COST CENTRE MODULE           %time %alloc

main        Main               0.0   10.1
main.x      Main               0.0   53.0
CAF         GHC.IO.Handle.FD   0.0   36.3


                                                         individual     inherited
COST CENTRE MODULE                     no.     entries  %time %alloc   %time %alloc

MAIN        MAIN                        37           0    0.0    0.2     0.0  100.0
 CAF        GHC.IO.Encoding.CodePage    61           0    0.0    0.1     0.0    0.1
 CAF        GHC.IO.Encoding             58           0    0.0    0.1     0.0    0.1
 CAF        GHC.IO.Handle.FD            52           0    0.0   36.3     0.0   36.3
 CAF        Main                        44           0    0.0    0.2     0.0   63.3
  main      Main                        74           1    0.0   10.1     0.0   63.1
   main.x   Main                        75           1    0.0   53.0     0.0   53.0

FiltB (list comprehensions)

-- FiltB.hs

module Main
    where

main = do
    let x = sum (takeWhile (<10000) [n^2 | n <- [1..], odd (n^2)])
    print x

    Sat Jul 26 18:30 2014 Time and Allocation Profiling Report  (Final)

       FiltB.exe +RTS -p -RTS

    total time  =        0.00 secs   (2 ticks @ 1000 us, 1 processor)
    total alloc =     107,236 bytes  (excludes profiling overheads)

COST CENTRE MODULE           %time %alloc

main        Main              50.0    8.8
CAF         Main              50.0    0.1
main.x      Main               0.0   59.4
CAF         GHC.IO.Handle.FD   0.0   31.4


                                                         individual     inherited
COST CENTRE MODULE                     no.     entries  %time %alloc   %time %alloc

MAIN        MAIN                        37           0    0.0    0.2   100.0  100.0
 CAF        GHC.IO.Encoding.CodePage    61           0    0.0    0.1     0.0    0.1
 CAF        GHC.IO.Encoding             58           0    0.0    0.0     0.0    0.0
 CAF        GHC.IO.Handle.FD            52           0    0.0   31.4     0.0   31.4
 CAF        Main                        44           0   50.0    0.1   100.0   68.3
  main      Main                        74           1   50.0    8.8    50.0   68.1
   main.x   Main                        75           1    0.0   59.4     0.0   59.4

Upvotes: 3

Views: 268

Answers (1)

djfoote
djfoote

Reputation: 141

Yes. In this particular case, since n^2 will be odd if and only if n is odd, you can speed up FiltB to the same speed as FiltA by replacing odd (n^2) with odd n.

Like you said, the problem is that for each element n it's squaring it, checking if that's odd, and if it is, then squaring n and adding that to the list.

More generally though, the difference is that in a list comprehension, the filtering happens before you map, whereas with map and filter, you can choose the order. So if what you actually want to filter based on is the values in the list after mapping, using map and filter is probably a better choice. You still could do something like this to filter based on whether the squared values are odd:

sum (takeWhile (<10000) [ x | x <- [ n^2 | n <- [1..] ], odd x ])

But that's getting to be pretty hard to read. Map and filter or filtering over the list comprehension explicitly (i.e. filter odd [ n^2 | n <- [1..] ]) are much better options.

Upvotes: 3

Related Questions