GHC-将迭代变成紧密的循环

Question

我正在尝试学习/评估haskell，我正在努力为简单的情况提高可执行性。我正在使用的测试是PRNG序列（复制PCG32 RNG）。我已经将其写为基本状态过渡功能的迭代（我目前仅在看待状态）。

{-# LANGUAGE BangPatterns #-}
import System.Environment (getArgs)
import Data.Bits
import Data.Word
iterate' f !x = x : iterate' f (f x)
main = print $ pcg32_rng 100000000
pcg32_random_r :: Word64 -> Word64 -> Word64
pcg32_random_r !i !state = state * (6364136223846793005 :: Word64) + (i .|. 1)
{-# INLINE pcg32_random_r #-}
pcg32_rng_s = iterate' (pcg32_random_r 1) 0
pcg32_rng n = pcg32_rng_s !! (n - 1)

我可以将该代码进行编译和运行。它仍然使用比应有的内存更多，并且比c等效速度慢10倍。主要问题似乎是迭代没有变成一个简单的循环。

我缺少什么来让GHC在这里更快/更有效的代码？

编辑

这是我比较的C版本，从本质上讲，它本质上捕获了我要实现的目标。我尝试进行公平的比较，但让我知道我是否错过了什么。

#include <stdio.h>
#include <stdint.h>
int main() {
  uint64_t oldstate,state;
  int i;
  for(i=0;i<100000000;i++) {
    oldstate = state;
    // Advance internal state
    state = oldstate * 6364136223846793005ULL + (1|1);
  }
  printf("%ldn",state);
}

我最初尝试使用Prelude iterate功能，但这会导致懒惰评估和堆栈溢出。旨在解决该问题的旨在解决这个问题。

我的下一步是尝试使GHC进入Inline pcg32_random_r，这就是我对其添加严格性的地方，但这似乎还不够。当我查看GHC核心时，它不会被嵌入。

@willemvanonsem i使用perform确认结果与C相当，实际上pcg32_random_r函数已镶嵌。在此阶段，我要达到对Haskell和GHC的掌握限制。您可以详细说明perform的性能更好以及如何决定何时使用什么？

编译器会自动自动可行，还是需要设计决策的东西？

提出最后一个问题的原因是，我希望将功能和实施选择分开（速度/空间权衡，...）以最大化重复使用，我希望Haskell能够帮助我。

Answer 1

在我看来，问题更多的是您产生列表，获得 i -th element从该列表中。结果，您将展开该列表功能，并且如果您需要在列表中进一步移动，则每次构造新元素。

而不是构建此类列表（它将构建新节点并执行内存分配，并消耗大量内存）。您可以构建将执行给定函数n次的函数：

perform_n :: (a -> a) -> Int -> a -> a
perform_n !f = step
    where step !n !x | n <= 0 = x
                     | otherwise = step (n-1) (f x)

因此，现在我们可以执行函数f n次。因此，我们可以像以下方式重写：

pcg32_rng n = perform_n (pcg32_random_r 1) (n-1) 0

如果我用ghc -O2 file.hs（GHC 8.0.2）编译此文件，请使用time，我得到：

$ time ./file
2264354473547460187
0.14user 0.00system 0:00.14elapsed 99%CPU (0avgtext+0avgdata 3408maxresident)k
0inputs+0outputs (0major+161minor)pagefaults 0swaps

原始文件产生以下基准：

$ time ./file2
2264354473547460187
0.54user 0.00system 0:00.55elapsed 99%CPU (0avgtext+0avgdata 3912maxresident)k
0inputs+0outputs (0major+287minor)pagefaults 0swaps

编辑：

正如@willness所说，如果您不命名列表，在运行时，列表将被收集到垃圾：如果您通过列表进行处理，并且不保留对列表头的参考，那么该头可以是一旦我们跨过它。

但是，如果我们构造了一个文件：

{-# LANGUAGE BangPatterns #-}
import System.Environment (getArgs)
import Data.Bits
import Data.Word
iterate' f !x = x : iterate' f (f x)
main = print $ pcg32_rng 100000000
pcg32_random_r :: Word64 -> Word64 -> Word64
pcg32_random_r !i !state = state * (6364136223846793005 :: Word64) + (i .|. 1)
{-# INLINE pcg32_random_r #-}
pcg32_rng n = iterate' (pcg32_random_r 1) 0 !! (n - 1)

我们获得：

$ time ./speedtest3
2264354473547460187
0.54user 0.01system 0:00.56elapsed 99%CPU (0avgtext+0avgdata 3908maxresident)k
0inputs+0outputs (0major+291minor)pagefaults 0swaps

尽管记忆负担可以减轻，但对时间的影响很小。原因可能是使用列表元素创建 cons 对象。因此，我们进行了很多包装和拆箱。这也导致构建许多仍会产生开销的对象（和内存分配）。