当找到列表的倒数第二个元素时，为什么在这些当中使用`last`最快？

Question

下面提供了3个函数，这些函数可以找到列表中的最后一个但第二个元素。一个使用last . init似乎比其他人快得多。我似乎不知道为什么。

为了进行测试，我使用了输入列表[1..100000000]（一亿）。最后一个几乎立即运行，而其他则需要几秒钟。

-- slow
myButLast :: [a] -> a
myButLast [x, y] = x
myButLast (x : xs) = myButLast xs
myButLast _ = error "List too short"

-- decent
myButLast' :: [a] -> a
myButLast' = (!! 1) . reverse

-- fast
myButLast'' :: [a] -> a
myButLast'' = last . init

Answer 1

在研究速度和优化时，很容易获得完全错误的结果。特别是，如果不提及编译器版本和基准设置的优化模式，就不能说一个变体比另一个变体快。即使这样，现代处理器也是如此复杂，以至于具有基于神经网络的分支预测器，更不用说各种缓存了，因此，即使进行了精心设置，基准测试结果仍将是模糊的。

话虽如此...

基准测试是我们的朋友。

criterion是一个提供高级基准测试工具的软件包。我迅速起草了如下基准：

module Main where

import Criterion
import Criterion.Main

-- slow
myButLast :: [a] -> a
myButLast [x, y] = x
myButLast (x : xs) = myButLast xs
myButLast _ = error "List too short"

-- decent
myButLast' :: [a] -> a
myButLast' = (!! 1) . reverse

-- fast
myButLast'' :: [a] -> a
myButLast'' = last . init

butLast2 :: [a] -> a
butLast2 (x :     _ : [ ] ) = x
butLast2 (_ : xs@(_ : _ ) ) = butLast2 xs
butLast2 _ = error "List too short"

setupEnv = do
  let xs = [1 .. 10^7] :: [Int]
  return xs

benches xs =
  [ bench "slow?"   $ nf myButLast   xs
  , bench "decent?" $ nf myButLast'  xs
  , bench "fast?"   $ nf myButLast'' xs
  , bench "match2"  $ nf butLast2    xs
  ]

main = defaultMain
    [ env setupEnv $ \ xs -> bgroup "main" $ let bs = benches xs in bs ++ reverse bs ]

如您所见，我添加了一次在两个元素上显式匹配的变体，但在其他方面，它是相同的代码。我还以相反的方式运行基准测试，以了解由于缓存造成的偏差。所以，让我们跑步看看！

% ghc --version
The Glorious Glasgow Haskell Compilation System, version 8.6.5


% ghc -O2 -package criterion A.hs && ./A
benchmarking main/slow?
time                 54.83 ms   (54.75 ms .. 54.90 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 54.86 ms   (54.82 ms .. 54.93 ms)
std dev              94.77 ?s   (54.95 ?s .. 146.6 ?s)

benchmarking main/decent?
time                 794.3 ms   (32.56 ms .. 1.293 s)
                     0.907 R²   (0.689 R² .. 1.000 R²)
mean                 617.2 ms   (422.7 ms .. 744.8 ms)
std dev              201.3 ms   (105.5 ms .. 283.3 ms)
variance introduced by outliers: 73% (severely inflated)

benchmarking main/fast?
time                 84.60 ms   (84.37 ms .. 84.95 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 84.46 ms   (84.25 ms .. 84.77 ms)
std dev              435.1 ?s   (239.0 ?s .. 681.4 ?s)

benchmarking main/match2
time                 54.87 ms   (54.81 ms .. 54.95 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 54.85 ms   (54.81 ms .. 54.92 ms)
std dev              104.9 ?s   (57.03 ?s .. 178.7 ?s)

benchmarking main/match2
time                 50.60 ms   (47.17 ms .. 53.01 ms)
                     0.993 R²   (0.981 R² .. 0.999 R²)
mean                 60.74 ms   (56.57 ms .. 67.03 ms)
std dev              9.362 ms   (6.074 ms .. 10.95 ms)
variance introduced by outliers: 56% (severely inflated)

benchmarking main/fast?
time                 69.38 ms   (56.64 ms .. 78.73 ms)
                     0.948 R²   (0.835 R² .. 0.994 R²)
mean                 108.2 ms   (92.40 ms .. 129.5 ms)
std dev              30.75 ms   (19.08 ms .. 37.64 ms)
variance introduced by outliers: 76% (severely inflated)

benchmarking main/decent?
time                 770.8 ms   (345.9 ms .. 1.004 s)
                     0.967 R²   (0.894 R² .. 1.000 R²)
mean                 593.4 ms   (422.8 ms .. 691.4 ms)
std dev              167.0 ms   (50.32 ms .. 226.1 ms)
variance introduced by outliers: 72% (severely inflated)

benchmarking main/slow?
time                 54.87 ms   (54.77 ms .. 55.00 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 54.95 ms   (54.88 ms .. 55.10 ms)
std dev              185.3 ?s   (54.54 ?s .. 251.8 ?s)

看起来我们的“慢速”版本一点也不慢！模式匹配的复杂性不会增加任何内容。（我们发现两次连续运行之间的速度有所提高，match2这归因于缓存的影响。）

有一种获取更多“科学”数据的方法：我们可以-ddump-simpl看看编译器如何看待我们的代码。

检验中间结构是我们的朋友。

“核心”是GHC的内部语言。每个Haskell源文件都将简化为Core，然后再转换为最终功能图以供运行时系统执行。如果我们看这个中间阶段，它将告诉我们myButLast和butLast2相等。它确实需要查找，因为在重命名阶段，我们所有不错的标识符都被随机地篡改了。

% for i in `seq 1 4`; do echo; cat A$i.hs; ghc -O2 -ddump-simpl A$i.hs > A$i.simpl; done

module A1 where

-- slow
myButLast :: [a] -> a
myButLast [x, y] = x
myButLast (x : xs) = myButLast xs
myButLast _ = error "List too short"

module A2 where

-- decent
myButLast' :: [a] -> a
myButLast' = (!! 1) . reverse

module A3 where

-- fast
myButLast'' :: [a] -> a
myButLast'' = last . init

module A4 where

butLast2 :: [a] -> a
butLast2 (x :     _ : [ ] ) = x
butLast2 (_ : xs@(_ : _ ) ) = butLast2 xs
butLast2 _ = error "List too short"

% ./EditDistance.hs *.simpl
(("A1.simpl","A2.simpl"),3866)
(("A1.simpl","A3.simpl"),3794)
(("A2.simpl","A3.simpl"),663)
(("A1.simpl","A4.simpl"),607)
(("A2.simpl","A4.simpl"),4188)
(("A3.simpl","A4.simpl"),4113)

似乎A1和A4最为相似。彻底的检查将表明A1和A4中的代码结构确实相同。那A2和A3类似也是合理的，因为两者都被定义为两个功能的组合。

如果要core广泛检查输出，还可以提供诸如-dsuppress-module-prefixes和的标志-dsuppress-uniques。它们使阅读变得非常容易。

我们的敌人的简短名单。

那么，基准测试和优化可能出什么问题？

• ghci专门为交互式播放和快速迭代而设计，可将Haskell源代码编译为某种形式的字节码，而不是最终的可执行文件，并避免进行昂贵的优化，以便更快地重新加载。
• 分析似乎是一个不错的工具，可以研究复杂程序的各个部分的性能，但它可能会严重破坏编译器的优化，因此结果将比基准低几个数量级。
  • 您的保护措施是使用自己的基准运行程序将每小段代码配置为单独的可执行文件。
• 垃圾收集是可调的。就在今天，一个新的主要功能发布了。垃圾收集的延迟将以无法直接预测的方式影响性能。
• 正如我提到的那样，不同的编译器版本将构建具有不同性能的不同代码，因此在作出任何承诺之前，您必须知道代码用户可能会使用哪个版本来构建它，并以此为基准进行测试。

这可能看起来很难过。但是实际上，大多数时候，Haskell程序员都不应该担心。真实故事：我有一个朋友最近刚开始学习Haskell。他们编写了一个数值积分程序，速度很慢。因此，我们坐在一起，用图表和内容对算法进行了分类描述。当他们重新编写代码以使其与抽象描述保持一致时，它就像魔术般迅速地变成了猎豹，并且在内存上也变得苗条。我们算过？立刻。这个故事所讲的道德？完善的抽象结构，您的代码将优化自身。