GHC

Question

我正在尝试 learn/evaluate 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)

我可以编译该代码运行。它仍然比它应该使用更多的内存并且运行s 比 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 函数，但这会导致延迟计算和堆栈溢出。 iterate 旨在解决这个问题。

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

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

编译器会自动执行此转换还是需要设计决策？

问最后一个问题的原因是我希望将功能和实现选择分开（速度/space 权衡，...）以最大限度地重用，我希望 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

编辑:

正如所说，如果您不命名列表，在运行时列表将被垃圾收集：如果您处理一个列表，并且不保留对列表的引用列表的头，然后一旦我们越过它就可以删除它。

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

{-# 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 对象。所以我们做了很多打包和拆包到列表中。这也会导致构建大量对象（和内存分配），这仍然会产生开销。

GHC - 将迭代变成紧密循环

GHC - turning iterate into a tight loop

haskell