Style vs Performance Using Vectors

Question

Here's the code: ``` {-# LANGUAGE FlexibleContexts #-} import Data.Int import qualified Data.Vector.Unboxed as U import qualified Data.Vector.Generic as V {-# NOINLINE f #-} -- Note the 'NO' --f :: (Num r, V.Vector v r) => v r -> v r -> v r --f :: (V.Vector v Int64) => v Int64 -> v Int64 -> v Int64 --f :: (U.Unbox r, Num r) => U.Vector r -> U.Vector r -> U.Vector r f :: U.Vector Int64 -> U.Vector Int64 -> U.Vector Int64 f = V.zipWith (+) -- or U.zipWith, it doesn't make a difference main = do let iters = 100 dim = 221184 y = U.replicate dim 0 :: U.Vector Int64 let ans = iterate ((f y)) y !! iters putStr $ (show $ U.sum ans) ``` I compiled with `ghc 7.6.2` and `-O2`, and it took 1.7 seconds to run. I tried several different versions of `f`: - `f x = U.zipWith (+) x` - `f x = (U.zipWith (+) x) . id` - `f x y = U.zipWith (+) x y` Version 1 is the same as the original while versions 2 and 3 run in in under 0.09 seconds (and `INLINING` `f` doesn't change anything). I also noticed that if I…

Accepted Answer

While I don't have the definitive answer you want, there are two things that might help you along.

The first thing is that `x `seq` x` is, both semantically and computationally, the same thing as just `x`. The wiki says about `seq`:

A common misconception regarding `seq` is that `seq x` "evaluates" `x`. Well, sort of. `seq` doesn't evaluate anything just by virtue of existing in the source file, all it does is introduce an artificial data dependency of one value on another: when the result of `seq` is evaluated, the first argument must also (sort of; see below) be evaluated.

As an example, suppose `x :: Integer`, then `seq x b` behaves essentially like `if x == 0 then b else b` – unconditionally equal to `b`, but forcing `x` along the way. In particular, the expression `x `seq` x` is completely redundant, and always has exactly the same effect as just writing `x`.

What the first paragraph says is that writing `seq a b` doesn't mean that `a` will magically get evaluated this instant, it means that `a` will get evaluated as soon as `b` needs to be evaluated. This might occur later in the program, or maybe never at all. When you view it in that light, it is obvious that `seq x x` is a redundancy, because all it says is, "evaluate `x` as soon as `x` needs to be evaluated." Which of course is what would happen anyway if you had just written `x`.

This has two implications for you:

Your "strict" `iterate'` function isn't really any stricter than it would be without the `seq`. In fact, I have a hard time imagining how the `iterate` function could become any stricter than it already is. You can't make the tail of the list strict, because it is infinite. The main thing you can do is force the "accumulator", `f x`, but doing so doesn't give any significant performance increase on my system.[1]

Scratch that. Your strict `iterate'` does exactly the same thing as my bang pattern version. See the comments.

Writing `(\z -> z `seq` z)` does not give you a strict identity function, which I assume is what you were going for. In fact, the common identity function is as strict as you'll get – it will evaluate its result as soon as it is needed.

However, I peeked at the core GHC generates for

```
U.zipWith (+) y
```

and

```
U.zipWith (+) y . id
```

and there is only one big difference that my untrained eye can spot. The first one uses just a plain `Data.Vector.Generic.zipWith` (here's where your polymorphism coincidence might come into play – if GHC chooses a generic `zipWith` it will of course perform as if the code was polymorphic!) while the latter has exploded this single function call into almost 90 lines of state monad code and unpacked machine types.

The state monad code looks almost like the loops and destructive updates you would write in an imperative language, so I assume it's tailored pretty well to the machine it's running on. If I wasn't in such a hurry, I would take a longer look to see more exactly how it works and why GHC suddenly decided it needed a tight loop. I have attached the generated core as much for myself as anyone else who wants to take a look.[2]

[1]: Forcing the accumulator along the way: (This is what you already do, I misunderstood the code!)

```
{-# LANGUAGE BangPatterns #-}
iterate' f !x = x : iterate f (f x)
```

[2]: What core `U.zipWith (+) y . id` gets translated into.

Style vs Performance Using Vectors

Solution

Problem