GHC - turning iterate into a tight loop

user_4436708 0
Viewed 201

I'm trying to learn/evaluate Haskell and I'm struggling with getting efficient executable for a simple case. The test I'm using is a PRNG sequence (replicating PCG32 RNG). I've written it as an iteration of a basic state transition function (I'm looking only at the state for now).

{-# 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)

I can get that code to compile and run. It still uses a lot more memory than it should and runs 10x slower than the C equivalent. The main issue seems to be that the iteration is not turned into a simple loop.

What am I missing to get GHC to produce faster / more efficient code here?

EDIT

This is the C version I compare against which captures in essence what I'm trying to achieve. I try for a fair comparison but let me know if I missed something.

#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);
}

I tried initally with the Prelude iterate function but this result in lazy evaluation and a stack overflow. The ìterate'`is aimed at fixing that issue.

My next step was to try to get GHC to inline pcg32_random_rand that's where I added the strictness to it but that doesn't seem to be enough. When I look at the GHC core, it is not inlined.

@WillemVanOnsem I confirm with performthe result is on par with C and actually the pcg32_random_rfunction was inlined. I'm reaching the limit of my grasp of Haskell and GHC at this stage. Can you elaborate on why perform performs better and how to decide when to use what?

Would this transformation be feasible automatically by the compiler or is it something that requires a design decision?

The reason to ask the last question is that I would like as much to separate functionality and implementation choice (speed / space tradeoffs, ...) to maximize reuse and I was hoping Haskell to help me there.

ghc haskell
1 Answers

It looks to me that the issue is more that you produce a list, and obtain the i-th element from that list. As a result you are going to unfold that list function, and each time you construct a new element if you need to move further in the list.

Instead of constructing such list (which will construct new nodes, and perform memory allocations, and consume a lot of memory). You can construct a function that will perform a given function n times:

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

So now we can perform a function f n times. We can thus rewrite it like:

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

If I compile this with ghc -O2 file.hs (GHC 8.0.2) run this file with time, I get:

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

the original file produces the following benchmarks:

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

EDIT:

As @WillNess says, if you do not name the list, at runtime the list will be garbage collected: if you process through a list, and do not keep a reference to the head of the list, then that head can be removed once we step over it.

If we however construct a file like:

{-# 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)

we obtain:

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

although the memory burden can be reduced, there is little impact on time. The reason is probably that working with list elements creates cons objects. So we do a lot of packing and unpacking into lists. This also results in constructing a lot of objects (and memory allocations) which still produces overhead.

user_675790
Related