optimization - 优化 Haskell 递归列表

Question

我的另一个 Haskell 优化问题 previous .我需要递归生成一个列表，类似于许多介绍性 Haskell 文章中的 fibs 函数:

generateSchedule :: [Word32] -> [Word32]
generateSchedule blkw = take 80 ws
    where
    ws          = blkw ++ zipWith4 gen (drop 13 ws) (drop 8 ws) (drop 2 ws) ws
    gen a b c d = rotate (a `xor` b `xor` c `xor` d) 1

上述函数对我来说已经成为最耗时和最消耗分配的函数。探查器为我提供以下统计信息:

COST CENTRE        MODULE             %time %alloc  ticks     bytes
generateSchedule   Test.Hash.SHA1     22.1   40.4   31        702556640

我想过应用未装箱的向量来计算列表，但由于列表是递归的，因此无法找到一种方法。这将在 C 中有一个自然的实现，但我看不出有什么方法可以使它更快(除了展开和编写 80 行变量声明)。有什么帮助吗？

更新:我实际上确实快速展开它以查看它是否有帮助。代码是 here .它很丑陋，实际上它更慢。

COST CENTRE        MODULE             %time %alloc  ticks     bytes
generateSchedule   GG.Hash.SHA1       22.7   27.6   40        394270592

Answer 1

import Data.Array.Base
import Data.Array.ST
import Data.Array.Unboxed

generateSchedule :: [Word32] -> UArray Int Word32
generateSchedule ws0 = runSTUArray $ do
    arr <- unsafeNewArray_ (0,79)
    let fromList i [] = fill i 0
        fromList i (w:ws) = do
            unsafeWrite arr i w
            fromList (i+1) ws
        fill i j
          | i == 80 = return arr
          | otherwise = do
              d <- unsafeRead arr j
              c <- unsafeRead arr (j+2)
              b <- unsafeRead arr (j+8)
              a <- unsafeRead arr (j+13)
              unsafeWrite arr i (gen a b c d)
              fill (i+1) (j+1)
    fromList 0 ws0

将创建一个与您的列表相对应的未装箱数组。它依赖于 list 参数包含至少 14 个和最多 80 个项目的假设，否则它会表现得很糟糕。我认为它总是 16 个项目(64 个字节)，所以这对你来说应该是安全的。 (但最好直接从 ByteString 开始填充，而不是构造一个中间列表。)

通过在执行散列轮之前严格评估这一点，您可以节省列表构造和使用懒惰构造列表的散列之间的切换，这应该会减少所需的时间。通过使用未装箱的数组，我们避免了列表的分配开销，这可能会进一步提高速度(但 ghc 的分配器非常快，所以不要期望会产生太大影响)。

在您的散列回合中，获得所需的 Word32通过 unsafeAt array t避免不必要的边界检查。

附录:如果您在每个 wn 上放一个大爆炸，展开列表的创建可能会更快，虽然我不确定。既然你已经有了代码，那么添加刘海和检查不是太多工作，是吗？我很好奇。