title: Style vs Performance Using Vectors
body: <p>Here's the code:</p>
  
  <pre><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) =&gt; v r -&gt; v r -&gt; v r
  --f :: (V.Vector v Int64) =&gt; v Int64 -&gt; v Int64 -&gt; v Int64
  --f :: (U.Unbox r, Num r) =&gt; U.Vector r -&gt; U.Vector r -&gt; U.Vector r
  f :: U.Vector Int64 -&gt; U.Vector Int64 -&gt; 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)
  </code></pre>
  
  <p>I compiled with <code>ghc 7.6.2</code> and <code>-O2</code>, and it took 1.7 seconds to run. </p>
  
  <p>I tried several different versions of <code>f</code>:</p>
  
  <ol>
  <li><code>f x = U.zipWith (+) x</code></li>
  <li><code>f x = (U.zipWith (+) x) . id</code></li>
  <li><code>f x y = U.zipWith (+) x y</code></li>
  </ol>
  
  <p>Version 1 is the same as the original while versions 2 and 3 run in in under 0.09 seconds (and <code>INLINING</code> <code>f</code> doesn't change anything).</p>
  
  <p>I also noticed that if I make <code>f</code> 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.</p>
  
  <p>I'm also interested in adding integers modulo <code>q</code>:</p>
  
  <pre><code>newtype Zq q i = Zq {unZq :: i}
  </code></pre>
  
  <p>As when adding <code>Int64</code>s, if I write a function with every type specified, </p>
  
  <pre><code>h :: U.Vector (Zq Q17 Int64) -&gt; U.Vector (Zq Q17 Int64) -&gt; U.Vector (Zq Q17 Int64)
  </code></pre>
  
  <p>I get an order of magnitude better performance than if I leave any polymorphism</p>
  
  <pre><code>h :: (Modulus q) =&gt; U.Vector (Zq q Int64) -&gt; U.Vector (Zq q Int64) -&gt; U.Vector (Zq q Int64)
  </code></pre>
  
  <p>But I should <em>at least</em> be able to remove the specific phantom type! It should be compiled out, since I'm dealing with a <code>newtype</code>.</p>
  
  <p>Here are my questions:</p>
  
  <ol>
  <li>Where is the slowdown coming from?</li>
  <li>What is going on in versions 2 and 3 of <code>f</code> 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?</li>
  <li>Why does polymorphism slow me down <em>an order of magnitude independent of where the polymorphism is</em> (i.e. in the vector type, in the <code>Num</code> type, both, or phantom type)? I know polymorphism makes code slower, but this is ridiculous. Is there a hack around it?</li>
  </ol>
  
  <blockquote>
    <p>EDIT 1</p>
    
    <p>I filed a <a href="https://github.com/haskell/vector/issues/4" rel="nofollow">issue</a> with the Vector library page. I found a <a href="http://ghc.haskell.org/trac/ghc/ticket/8099" rel="nofollow">GHC
    issue</a> relating to this problem.</p>
    
    <p>EDIT2</p>
    
    <p>I rewrote the question after gaining some insight from @kqr's answer.
    Below is the original for reference.</p>
  </blockquote>
  
  <p>--------------ORIGINAL QUESTION--------------------</p>
  
  <p>Here's the code:</p>
  
  <pre><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) =&gt; v r -&gt; v r -&gt; v r
  --f :: (V.Vector v Int64) =&gt; v Int64 -&gt; v Int64 -&gt; v Int64
  --f :: (U.Unbox r, Num r) =&gt; U.Vector r -&gt; U.Vector r -&gt; U.Vector r
  f :: U.Vector Int64 -&gt; U.Vector Int64 -&gt; 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)
  </code></pre>
  
  <p>I compiled with <code>ghc 7.6.2</code> and <code>-O2</code>, and it took 1.7 seconds to run. </p>
  
  <p>I tried several different versions of <code>f</code>:</p>
  
  <ol>
  <li><code>f x = U.zipWith (+) x</code></li>
  <li><code>f x = (U.zipWith (+) x) . U.force</code></li>
  <li><code>f x = (U.zipWith (+) x) . Control.DeepSeq.force)</code></li>
  <li><code>f x = (U.zipWith (+) x) . (\z -&gt; z `seq` z)</code></li>
  <li><code>f x = (U.zipWith (+) x) . id</code></li>
  <li><code>f x y = U.zipWith (+) x y</code></li>
  </ol>
  
  <p>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 <code>INLINING</code> <code>f</code> doesn't change anything).</p>
  
  <p>So the order-of-magnitude slowdown appears to be due to laziness since <code>force</code> helped, but I'm not sure where the laziness is coming from. Unboxed types aren't allowed to be lazy, right?</p>
  
  <p>I tried writing a strict version of <code>iterate</code>, thinking the vector itself must be lazy:</p>
  
  <pre><code>{-# INLINE iterate' #-}
  iterate' :: (NFData a) =&gt; (a -&gt; a) -&gt; a -&gt; [a]
  iterate' f x =  x `seq` x : iterate' f (f x)
  </code></pre>
  
  <p>but with the point-free version of <code>f</code>, this didn't help at all.</p>
  
  <p>I also noticed something else, which could be just a coincidence and red herring:
  If I make <code>f</code> 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.</p>
  
  <p>Here are my questions:</p>
  
  <ol>
  <li>Where is the slowdown coming from?</li>
  <li>Why does composing with <code>force</code> help, but using a strict <code>iterate</code> doesn't? </li>
  <li>Why is <code>U.force</code> worse than <code>DeepSeq.force</code>? I have no idea what <code>U.force</code> is supposed to do, but it sounds a lot like <code>DeepSeq.force</code>, and seems to have a similar effect.</li>
  <li>Why does polymorphism slow me down <em>an order of magnitude independent of where the polymorphism is</em> (i.e. in the vector type, in the <code>Num</code> type, or both)?</li>
  <li>Why are versions 5 and 6, neither of which should have any strictness implications at all, just as fast as a strict function?</li>
  </ol>
  
  <p>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 <code>zipWith</code> 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?</p>