Why is this function much slower when named?

user_17360986 0
Viewed 104

I have a function that computes the number of divisors of an integer:

numDivisor = ( \n -> length $ filter (\x -> n `mod` x == 0) [1..n] )

When I run this function in GHCI with or without giving it a name, there is a constant ~1.4 times performance hit. Example copyable to ghci:

:set +s
x = 20000000
( \n -> length $ filter (\x -> n `mod` x == 0) [1..n] ) x
numDivisor = ( \n -> length $ filter (\x -> n `mod` x == 0) [1..n] )
numDivisor x

and the results:

Prelude> ( \n -> length $ filter (\x -> n `mod` x == 0) [1..n] ) x
72
(8.67 secs, 3,040,063,784 bytes)
Prelude> numDivisor x
72
(12.68 secs, 4,000,064,048 bytes)

It doesn't matter if x is 20000000, 200000 or is below 10000, the hit is ~1.4, also it happens when I name my function in a "where" something. In the next example I calculate the divisors for all the numbers from 1 to x, then drop them:

:set +s
x = 10000
divisorListAnon = map ( \n -> length $ filter (\x -> n `mod` x == 0) [1..n] ) [1..] 
filter odd $ filter even $ take x divisorListAnon
:{
divisorListNamed  = map numDivisor [1..]
    where numDivisor = ( \n -> length $ filter (\x -> n `mod` x == 0) [1..n] )
:}
filter odd $ filter even $ take x divisorListNamed

the results:

Prelude> filter odd $ filter even $ take x divisorListAnon
[]
(21.17 secs, 7,613,246,464 bytes)
Prelude> filter odd $ filter even $ take x divisorListNamed
[]
(29.84 secs, 9,213,726,504 bytes)

Anyone can give some pointers what's going on? Also how can I use and name this subroutine without this performance hit? I'd prefer to give it a name, and don't use it anonymous.

Thank you,

edit:

ubuntu 20.04, ghc 8.6.5 from the ubuntu distributed ghc package, not stack

haskell
1 Answers

( \n -> length $ filter (\x -> n `mod` x == 0) [1..n] ) x has the type Num a => Int. The "hidden" type variable a (the type of x) is defaulted to Integer. This happens, I suppose, before GHCi generates its bytecode, and it's smart enough to use operations from the Integer specialization instead of the generic Num methods when the numeric type is known to be Integer.

let-binding the function generalizes it to forall a. Num a => a -> Int. In the Core intermediate language, the function takes a Num a dictionary as an argument, and all operations on the numeric values go through the dictionary. GHCi compiles the function to bytecode without knowing what the type a will be.

You can work around this in GHCi by giving numDivisor the explicit type Integer -> Int. GHC (the compiler) will most likely automatically specialize it at Integer, so there will be no performance difference.

You could also work around this by enabling the monomorphism restriction in GHCi, which will cause x and numDivisor to immediately be defaulted to Integer and Integer -> Int.

user_56707730
Related