haskell - 为什么 Prelude.drop 比普通的快？

Question

我做了一些运行:

main = print $ head . drop (2^30) $ [1..]

— 两者兼具 Prelude.drop和一个微不足道的 drop . Prelude 变体始终快约 45%，我不知道为什么。我什至提取了 GHC.List.drop 的定义来自 base-4.11.1.0但它的性能比我的琐碎代码还差!到底是怎么回事？

这就是我正在做的:

% stack ghc -- --version           
The Glorious Glasgow Haskell Compilation System, version 8.2.2

Prelude.drop :

% git checkout drop-prelude
% git clean --force
% cat ListTest.hs
module Main where

main = print $ head . drop (2^30) $ [1..]
% stack ghc -- ListTest.hs
[1 of 1] Compiling Main             ( ListTest.hs, ListTest.o )
Linking ListTest ...
% time ./ListTest
1073741825
./ListTest  18.76s user 0.09s system 99% cpu 18.906 total

一件小事 drop :

% git checkout drop-naive 
% git clean --force
% cat ListTest.hs
module Main where

dropNaive :: Int -> [a] -> [a]
dropNaive 0 xs = xs
dropNaive n [ ] = [ ]
dropNaive n (x: xs) = dropNaive (pred n) xs

main = print $ head . dropNaive (2^30) $ [1..]
% stack ghc -- ListTest.hs
[1 of 1] Compiling Main             ( ListTest.hs, ListTest.o )
Linking ListTest ...
% time ./ListTest
1073741825      
./ListTest  31.56s user 0.12s system 99% cpu 31.774 total

drop来自 GHC.List :

% git checkout drop-ghc 
% git clean --force
% cat ListTest.hs 
{-# LANGUAGE BangPatterns #-}

module ListTest where

dropGhc :: Int -> [a] -> [a]
{-# INLINE dropGhc #-}
dropGhc n xs
  | n <= 0     = xs
  | otherwise  = unsafeDrop n xs
  where
    unsafeDrop :: Int -> [a] -> [a]
    unsafeDrop !_ []     = []
    unsafeDrop 1  (_:xs) = xs
    unsafeDrop m  (_:xs) = unsafeDrop (m - 1) xs
% cat ListTestRunner.hs 
import ListTest

main = print $ head . dropGhc (2^30) $ [1..]
% stack ghc -- ListTestRunner.hs
[1 of 2] Compiling ListTest         ( ListTest.hs, ListTest.o )
[2 of 2] Compiling Main             ( ListTestRunner.hs, ListTestRunner.o )
Linking ListTestRunner ...
% time ./ListTestRunner
1073741825            
./ListTestRunner  35.35s user 0.14s system 99% cpu 35.591 total

Answer 1

我以前犯过这个错误，所以我有一个怀疑......

看起来您只是没有在启用优化的情况下进行编译。 Prelude 是使用优化编译并链接的，因此当您使用 prelude 的 drop 时，您隐式地使用了优化代码。 .本地复制(在将常量从 2^30 减少到 2^25 之后——没有理由让自己等这么久)，启用优化导致 dropGhc和序曲drop具有相同的时间，和 dropNaive并没有显着恶化。 dropGhc之间的措辞略有不同和 dropNaive这可能会对生成的代码产生微妙的影响；我对为什么一个会比另一个更好没有很好的直觉。

另请注意 base是一个特殊的包，因为它是作为 ghc 的一部分构建的。的构建过程，使用自己的构建系统，而不是像普通包那样由 Cabal 构建。正如@sjakobi 在评论中指出的那样，there is a setting in ghc 's build configuration设置 base 的优化级别在 O2 .