Style vs Performance Using Vectors

问题:

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:

1. f x = U.zipWith (+) x
2. f x = (U.zipWith (+) x) . id
3. 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 make f polymorphic (with any of the three signatures above), even with a "fast" definition (i.e. 2 or 3), it slows back down...to exactly 1.7 seconds. This makes me wonder if the original problem is perhaps due to (lack of) type inference, even though I'm explicitly giving the types for the Vector type and element type.

I'm also interested in adding integers modulo q:

newtype Zq q i = Zq {unZq :: i}

As when adding Int64s, if I write a function with every type specified,

h :: U.Vector (Zq Q17 Int64) -> U.Vector (Zq Q17 Int64) -> U.Vector (Zq Q17 Int64)

I get an order of magnitude better performance than if I leave any polymorphism

h :: (Modulus q) => U.Vector (Zq q Int64) -> U.Vector (Zq q Int64) -> U.Vector (Zq q Int64)

But I should at least be able to remove the specific phantom type! It should be compiled out, since I'm dealing with a newtype.

Here are my questions:

1. Where is the slowdown coming from?
2. What is going on in versions 2 and 3 of f that affect performance in any way? It seems like a bug to me that (what amounts to) coding style can affect performance like this. Are there other examples outside of Vector where partially applying a function or other stylistic choices affect performance?
3. Why does polymorphism slow me down an order of magnitude independent of where the polymorphism is (i.e. in the vector type, in the Num type, both, or phantom type)? I know polymorphism makes code slower, but this is ridiculous. Is there a hack around it?

EDIT 1

I filed a issue with the Vector library page. I found a GHC issue relating to this problem.

EDIT2

I rewrote the question after gaining some insight from @kqr's answer. Below is the original for reference.

--------------ORIGINAL QUESTION--------------------

Here's the code:

{-# LANGUAGE FlexibleContexts #-}

import Control.DeepSeq
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 (+)

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:

1. f x = U.zipWith (+) x
2. f x = (U.zipWith (+) x) . U.force
3. f x = (U.zipWith (+) x) . Control.DeepSeq.force)
4. f x = (U.zipWith (+) x) . (\z -> z `seq` z)
5. f x = (U.zipWith (+) x) . id
6. f x y = U.zipWith (+) x y

Version 1 is the same as the original, version 2 runs in 0.111 seconds, and versions 3-6 run in in under 0.09 seconds (and INLINING f doesn't change anything).

So the order-of-magnitude slowdown appears to be due to laziness since force helped, but I'm not sure where the laziness is coming from. Unboxed types aren't allowed to be lazy, right?

I tried writing a strict version of iterate, thinking the vector itself must be lazy:

{-# INLINE iterate' #-}
iterate' :: (NFData a) => (a -> a) -> a -> [a]
iterate' f x =  x `seq` x : iterate' f (f x)

but with the point-free version of f, this didn't help at all.

I also noticed something else, which could be just a coincidence and red herring: If I make f polymorphic (with any of the three signatures above), even with a "fast" definition, it slows back down...to exactly 1.7 seconds. This makes me wonder if the original problem is perhaps due to (lack of) type inference, even though everything should be inferred nicely.

Here are my questions:

1. Where is the slowdown coming from?
2. Why does composing with force help, but using a strict iterate doesn't?
3. Why is U.force worse than DeepSeq.force? I have no idea what U.force is supposed to do, but it sounds a lot like DeepSeq.force, and seems to have a similar effect.
4. Why does polymorphism slow me down an order of magnitude independent of where the polymorphism is (i.e. in the vector type, in the Num type, or both)?
5. Why are versions 5 and 6, neither of which should have any strictness implications at all, just as fast as a strict function?

As @kqr pointed out, the problem doesn't seem to be strictness. So something about the way I write the function is causing the generic zipWith to be used rather than the Unboxed-specific version. Is this just a fluke between GHC and the Vector library, or is there something more general that can be said here?

回答1:

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:

1. 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.

2. 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.