Haskell 显式递归 vs `iterate`

Question

Haskell 显式递归 vs `iterate`

performanceloopshaskellghccompiler-optimization

15

在使用 Haskell 中的 iterate 函数编写函数时，我发现使用显式递归版本的函数速度明显更快——尽管我认为在 Haskell 中应该避免使用显式递归。

同样地，我期望 GHC 能够适当地内联/优化列表组合器，使得生成的机器代码的性能与显式递归至少相似。

这里是另一个例子，它也展示了我观察到的减速现象。

steps m n 及其变种 steps' 计算达到 1 所需的 Collatz 步骤数，最多尝试 m 次。

steps 使用显式递归，而 steps' 使用列表函数。

import Data.List (elemIndex)
import Control.Exception (evaluate)
import Control.DeepSeq (rnf)

collatz :: Int -> Int
collatz n
  | even n    = n `quot` 2
  | otherwise = 3 * n + 1

steps :: Int -> Int -> Maybe Int
steps m = go 0
  where go k n
          | n == 1    = Just k
          | k == m    = Nothing
          | otherwise = go (k+1) (collatz n)

steps' :: Int -> Int -> Maybe Int
steps' m = elemIndex 1 . take m . iterate collatz

main :: IO ()
main = evaluate $ rnf $ map (steps 800) $ [1..10^7]

我通过评估所有值直到10^7，每次在800步后放弃来测试这些内容。在我的机器上（使用ghc -O2编译），明确的递归仅花费不到4秒钟（3.899s），但列表组合器需要约5倍的时间（19.922s）。

为什么在这种情况下明确的递归要好得多，是否有一种方式可以在不使用明确递归的情况下保持性能？

- B. Mehta

1

你是否考虑过检查一下你对 GHC 能做什么的期望是否正确？如果不是，那么你的 iterate 版本将会生成、匹配和收集数十亿个元素，这可以很好地解释差异。 - that other guy

可以合理地假设每个“迭代”在生成不超过800个后就会停止，但是800*10^7仍然是数十亿。 - that other guy

我很难理解这如何证明它们有所不同，因为两个版本都必须进行相同数量的计算。 - B. Mehta

@Carl，那我猜我的问题变成了：为什么不将 findIndices（elemIndex 是根据其书写的）编写成参与融合的形式-它肯定可以实现为一种 zip、filter 然后 map 的形式，这些都可以被融合。 - B. Mehta

嗯，我追踪了GHC使用的实际实现。里面的所有内容实际上都应该是基于foldr和build的。 - Carl

显示剩余12条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- K. A. Buhr · Accepted Answer

更新：我提交了Trac 15426来解决这个bug。

如果将elemIndex和findIndex的定义复制到你的模块中，问题就会消失：

import Control.Exception (evaluate)
import Control.DeepSeq (rnf)

import Data.Maybe (listToMaybe)
import Data.List (findIndices)

elemIndex       :: Eq a => a -> [a] -> Maybe Int
elemIndex x     = findIndex (x==)

findIndex       :: (a -> Bool) -> [a] -> Maybe Int
findIndex p     = listToMaybe . findIndices p

collatz :: Int -> Int
collatz n
  | even n    = n `quot` 2
  | otherwise = 3 * n + 1

steps' :: Int -> Int -> Maybe Int
steps' m = elemIndex 1 . take m . iterate collatz

main :: IO ()
main = evaluate $ rnf $ map (steps' 800) $ [1..10^7]

问题似乎是这些函数必须可内联才能使GHC正确地融合。不幸的是，Data.OldList中没有标记它们为可内联。

允许findIndex参与融合的更改是相对较新的（请参见Trac 14387），在其中将listToMaybe重新实现为一个foldr。因此，它可能还没有经过很多测试。