预定义函数的Haskell速度与复制源代码

Question

为什么当我使用预定义的filter时，它的工作速度比我使用Hackage源文件的精确副本的函数要快得多？

因此，将预定义filter与

filter1 :: (a -> Bool) -> [a] -> [a]
filter1 _pred []    = []
filter1 pred (x:xs)
  | pred x         = x : filter1 pred xs
  | otherwise      = filter1 pred xs

当我们在它的时候

filter2 ::  (a -> Bool) -> [a] -> [a]
filter2 pred  xs = [x | x <- xs, pred x]

和

filter3 :: (a -> Bool) -> [a] -> [a]
filter3 pred = foldr (x ys -> if pred x then x : ys else ys) []

面向所有人的运行last $ filter odd [1..20000000]提供：

*Main> :set +s
*Main> last $ filter odd [1..20000000]
19999999
(**2.42 secs**, 4,716,736,640 bytes)
*Main> last $ filter1 odd [1..20000000]
19999999
(**15.72 secs**, 6,883,675,064 bytes)
*Main> last $ filter2 odd [1..20000000]
19999999
(**13.17 secs**, 5,839,140,920 bytes)
*Main> last $ filter3 odd [1..20000000]
19999999
(**11.09 secs**, 6,486,331,496 bytes)

为什么filter1与filter不同（考虑到源代码filter1），为什么源代码比其他 2 个实现慢？（使用列表推导式或foldr）

注意没有目的的最终功能。我只是在测试不同的速度...

Answer 1

区别在于，当您将MyFilter.hs直接加载到 GHCi 中时，它会被解释而不是编译。

也就是说，以下是我的机器上使用 GHC 7.8.3 将所有内容加载到 GHCi 中的计时：

$ ghci-7.8.3 MyFilter.hs
GHCi, version 7.8.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling MyFilter     ( MyFilter.hs, interpreted )
Ok, modules loaded: MyFilter.
*MyFilter> let xs = [1..20000000] :: [Int]
*MyFilter> :set +s
*MyFilter> last xs  -- Just to remove any effect of evaluating `xs` itself
20000000
(3.00 secs, 627134572 bytes)
*MyFilter> last $ filter odd xs
19999999
(2.00 secs, 1451220660 bytes)
*MyFilter> last $ filter1 odd xs
19999999
(17.55 secs, 2627102272 bytes)
*MyFilter> last $ filter2 odd xs
19999999
(13.54 secs, 1877989348 bytes)
*MyFilter> last $ filter3 odd xs
19999999
(15.44 secs, 2256212504 bytes)

尤其要注意MyFilter.hs, interpreted行。

现在，如果我们在将其加载到 GHCi 之前对其进行编译，则 filter 和 filter1/filter2/filter3 之间的时序数字会突然排列：

$ ghc-7.8.3 --make MyFilter.hs
[1 of 1] Compiling MyFilter     ( MyFilter.hs, MyFilter.o )
$ ghci-7.8.3 MyFilter.hs
GHCi, version 7.8.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Ok, modules loaded: MyFilter.
Prelude MyFilter> let xs = [1..20000000] :: [Int]
Prelude MyFilter> :set +s
Prelude MyFilter> last xs
20000000
(2.84 secs, 710745024 bytes)
Prelude MyFilter> last $ filter odd xs
19999999
(2.07 secs, 1374513668 bytes)
Prelude MyFilter> last $ filter1 odd xs
19999999
(2.07 secs, 1499566524 bytes)
Prelude MyFilter> last $ filter2 odd xs
19999999
(2.12 secs, 1499505652 bytes)
Prelude MyFilter> last $ filter3 odd xs
19999999
(2.26 secs, 1500830732 bytes)