haskell - 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("%ld\n",state);
}

我最初尝试使用 Prelude iterate函数，但这会导致延迟评估和堆栈溢出。 “terate”旨在解决这个问题。

我的下一步是尝试让 GHC 内联 pcg32_random_r这就是我在其中添加了严格性的地方，但这似乎还不够。当我查看 GHC 核心时，它不是内联的。

@WillemVanOnsem 我确认 perform结果与 C 相当，实际上是 pcg32_random_r函数被内联。在这个阶段，我已经达到了对 Haskell 和 GHC 的掌握的极限。你能详细说明为什么 perform性能更好以及如何决定何时使用什么？

这种转换是否可以由编译器自动执行，还是需要设计决策？

问最后一个问题的原因是我希望尽可能地将功能和实现选择(速度/空间权衡，...)分开，以最大限度地重用，我希望 Haskell 在那里帮助我。

Answer 1

在我看来，问题更多的是你 生成列表 , 和 获取第 i 个元素 从那个名单。因此，您将展开该列表函数，并且如果您需要在列表中进一步移动，则每次构造一个新元素时。

而不是构造这样的列表(这将构造新节点，并执行内存分配，并消耗大量内存)。您可以构造一个函数来执行给定的函数 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 对象。所以我们做了很多打包和解包到列表中。这也会导致构建大量仍然会产生开销的对象(和内存分配)。