Why is writeSTRef faster than an expression?

Question

writeSTRef twice for each iteration

fib3 :: Int -> Integer fib3 n = runST $ do a <- newSTRef 1 b <- newSTRef 1 replicateM_ (n-1) $ do !a' <- readSTRef a !b' <- readSTRef b writeSTRef ab' writeSTRef b $! a'+b' readSTRef b 

writeSTRef times for each iteration

 fib4 :: Int -> Integer fib4 n = runST $ do a <- newSTRef 1 b <- newSTRef 1 replicateM_ (n-1) $ do !a' <- readSTRef a !b' <- readSTRef b if a' > b' then writeSTRef b $! a'+b' else writeSTRef a $! a'+b' a'' <- readSTRef a b'' <- readSTRef b if a'' > b'' then return a'' else return b'' 

Test given by n = 20000 :

Benchmark 20,000 / fib3 average: 5.073608 ms, pound 5.071842 ms, ub 5.075466 ms, ci 0.950 std dev: 9.284321 us, lb 8.119454 us, ub 10.78107 us, ci 0.950

benchmark 20,000 / fib4 average: 5.384010 ms, pound 5.381876 ms, ub 5.386099 ms, ci 0.950 std dev: 10.85245 us, lb 9.510215 us, ub 12.65554 us, ci 0.950

fib3 is slightly faster than fib4.

Answer 1

I think you already have answers from #haskell; basically, each writeSTRef comes down to one or two memory notes, which is cheap in this case, since they probably will never go past the level 1 cache.

On the other hand, the branch resulting from if-then-else in fib3 creates two paths that execute sequentially in successive iterations, which is a bad case for many processor branch predictors by adding bubbles to the pipeline. See http://en.wikipedia.org/wiki/Instruction_pipeline .

How about a clean version?

 fib0 :: Int -> Integer fib0 = go 0 1 where go :: Integer -> Integer -> Int -> Integer go abn = case n > 0 of True -> go b (a + b) (n - 1) False -> b 

This is even faster:

 benchmarking fib0 40000 mean: 17.14679 ms, lb 17.12902 ms, ub 17.16739 ms, ci 0.950 std dev: 97.28594 us, lb 82.39644 us, ub 120.1041 us, ci 0.950 benchmarking fib3 40000 mean: 17.32658 ms, lb 17.30739 ms, ub 17.34931 ms, ci 0.950 std dev: 106.7610 us, lb 89.69371 us, ub 126.8279 us, ci 0.950 benchmarking fib4 40000 mean: 18.13887 ms, lb 18.11173 ms, ub 18.16868 ms, ci 0.950 std dev: 145.9772 us, lb 127.6892 us, ub 168.3347 us, ci 0.950