title: Why are boxed vectors so slow?
body: <p>I am trying to get amortized <em>O(n)</em> time concatenation of vectors. It seems to be working but if I need to store boxed values (such as vectors) the result is still very slow.</p>
  
  <pre><code>import qualified Data.Vector as V
  import qualified Data.Vector.Generic.Mutable as GM
  import Data.Vector(Vector)
  import Control.Monad.State.Strict
  import Control.Monad.ST
  
  data App = S !(Vector Int) !Int deriving (Show)
  
  main = do
    x &lt;- liftM (map read . words) getContents
    print $ execState (mapM_ (add . V.singleton) x) (S V.empty 0)
  
  add :: Vector Int -&gt; State App ()
  add v1 = do
      S v2 n &lt;- get
      let v3 = vectorGrowAdd v1 v2 n
      put (S v3 (n + V.length v1))
  
  vectorGrowAdd v1 v2 n = runST $ do
    m1 &lt;- V.unsafeThaw v1
    m2 &lt;- V.unsafeThaw v2
    m3 &lt;- if GM.length m2 &gt; (GM.length m1 + n)
           then do
             return m2
           else do
             GM.unsafeGrow m2 (GM.length m1 + 2*(GM.length m2))
    let copyTo = GM.unsafeSlice n (GM.length m1) m3 
    GM.unsafeCopy copyTo m1
    V.freeze m3
  </code></pre>
  
  <p>In this example, <code>testVals</code> is a text file with 100000 integers, <code>Boxed.hs</code> is the code above and <code>Unboxed.hs</code> is the same as <code>Boxed.hs</code> except for importing <code>Data.Vector.Unboxed</code> instaid of <code>Data.Vector</code>.</p>
  
  <pre><code>&gt; ghc -v
  Glasgow Haskell Compiler, Version 7.0.3
  &gt; ghc --make -O2 Boxed.hs
  &gt; time (cat testVals | ./Boxed.hs)
    ...
    real      1m39.855s
    user      1m39.282s 
    sys       0m0.252s
  &gt; ghc --make -O2 Unboxed.hs
  &gt; time (cat testVals | ./Unboxed.hs)
  ...
  real        0m4.372s
  user        0m4.268s
  sys         0m0.088s
  </code></pre>
  
  <p>My question is: Why is there such a drastic difference between Unboxed and Boxed? Is there something I can do to improved the speed if I need to store values that can't be unboxed?</p>