<div dir="ltr">From places like <a href="http://programmers.stackexchange.com/questions/180417/fastest-haskell-library-sort-implementation">http://programmers.stackexchange.com/questions/180417/fastest-haskell-library-sort-implementation </a>and <a href="http://stackoverflow.com/questions/3655329/how-does-one-sort-with-data-vector-generic-mutable">http://stackoverflow.com/questions/3655329/how-does-one-sort-with-data-vector-generic-mutable</a> I'm led to believe that sorting mutable vectors is faster than sorting lists. However, when running on my own computer, I'm seeing the opposite effect. What's wrong with what I'm doing, or am I misunderstanding something? What's the fastest way to sort?<div><br></div><div>Here's the code: </div><div><br></div><div>Sort0.hs (List version)</div><div><br></div><div><div><font face="monospace, monospace">import Control.Monad</font></div><div><font face="monospace, monospace">import System.Random</font></div><div><font face="monospace, monospace">import qualified Data.Vector as IV</font></div><div><font face="monospace, monospace">import qualified Data.Vector.Mutable as MV</font></div><div><font face="monospace, monospace">import qualified Data.Vector.Generic as V</font></div><div><font face="monospace, monospace">import qualified Data.Vector.Algorithms.Intro as VA</font></div><div><font face="monospace, monospace">import qualified Data.List as L</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">randList :: IO [Int]</font></div><div><font face="monospace, monospace">randList = sequence $ replicate 1000000 (randomIO :: IO Int)</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">main = do</font></div><div><font face="monospace, monospace">  v <- randList</font></div><div><font face="monospace, monospace">  print $ L.sort v</font></div><div><br></div></div><div>Here's Sort1.hs</div><div><br></div><div><div><font face="monospace, monospace">import Control.Monad</font></div><div><font face="monospace, monospace">import System.Random</font></div><div><font face="monospace, monospace">import qualified Data.Vector as IV</font></div><div><font face="monospace, monospace">import qualified Data.Vector.Mutable as MV</font></div><div><font face="monospace, monospace">import qualified Data.Vector.Generic as V</font></div><div><font face="monospace, monospace">import qualified Data.Vector.Algorithms.Intro as VA</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">randVector :: IO (MV.IOVector Int)</font></div><div><font face="monospace, monospace">randVector = do</font></div><div><font face="monospace, monospace">  v <- MV.new 1000000</font></div><div><font face="monospace, monospace">  forM [0..999999] $ \x -> do</font></div><div><font face="monospace, monospace">    r <- randomIO :: IO Int</font></div><div><font face="monospace, monospace">    MV.write v x r</font></div><div><font face="monospace, monospace">  return v</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">main = do</font></div><div><font face="monospace, monospace">  v <- randVector</font></div><div><font face="monospace, monospace">  VA.sort v</font></div><div><font face="monospace, monospace">  iv <- V.unsafeFreeze v :: IO (IV.Vector Int)</font></div><div><font face="monospace, monospace">  print . V.toList $ iv</font></div></div><div><br></div><div>I'm compiling and running as follows:</div><div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">ghc -prof -fprof-auto -rtsopts -o Sort0 Sort0.hs</font></div><div><font face="monospace, monospace">./Sort0 +RTS -p -sstderr -K99999999 -RTS</font></div></div><div><br></div><div>Here are the traces; the first one is Sort0.hs (list version) and takes ~11s while the other takes ~17s:<br></div><div><br></div><div><div><span class="" style="white-space:pre">   </span>Sat May 30 05:06 2015 Time and Allocation Profiling Report  (Final)</div><div><br></div><div><span class="" style="white-space:pre">      </span>   Sort0.exe +RTS -p -sstderr -K99999999 -RTS</div><div><br></div><div><span class="" style="white-space:pre">    </span>total time  =       <b>11.43 secs</b>   (11434 ticks @ 1000 us, 1 processor)</div><div><span class="" style="white-space:pre">      </span>total alloc = 1,966,669,596 bytes  (excludes profiling overheads)</div><div><br></div><div>COST CENTRE MODULE  %time %alloc</div><div><br></div><div>main        Main     61.4   49.4</div><div>randList    Main     38.6   50.6</div><div><br></div><div><br></div><div>                                                          individual     inherited</div><div>COST CENTRE  MODULE                     no.     entries  %time %alloc   %time %alloc</div><div><br></div><div>MAIN         MAIN                        41           0    0.0    0.0   100.0  100.0</div><div> CAF         GHC.IO.Encoding.CodePage    69           0    0.0    0.0     0.0    0.0</div><div> CAF         GHC.IO.Encoding             67           0    0.0    0.0     0.0    0.0</div><div> CAF         System.CPUTime              59           0    0.0    0.0     0.0    0.0</div><div> CAF         GHC.IO.Handle.FD            58           0    0.0    0.0     0.0    0.0</div><div> CAF         Data.Fixed                  54           0    0.0    0.0     0.0    0.0</div><div> CAF         Data.Time.Clock.POSIX       50           0    0.0    0.0     0.0    0.0</div><div> CAF         System.Random               49           0    0.0    0.0     0.0    0.0</div><div> CAF         Main                        48           0    0.0    0.0   100.0  100.0</div><div>  randList   Main                        83           1    1.7    3.1     1.7    3.1</div><div>  main       Main                        82           1   61.4   49.4    98.3   96.9</div><div>   randList  Main                        84           0   36.9   47.6    36.9   47.6</div></div><div><br></div><div><div><span class="" style="white-space:pre"> </span>Sat May 30 04:59 2015 Time and Allocation Profiling Report  (Final)</div><div><br></div><div><span class="" style="white-space:pre">      </span>   Sort1.exe +RTS -p -sstderr -K99999999 -RTS</div><div><br></div><div><span class="" style="white-space:pre">    </span>total time  =      <b> 17.07 secs</b>   (17066 ticks @ 1000 us, 1 processor)</div><div><span class="" style="white-space:pre">      </span>total alloc = 5,783,472,528 bytes  (excludes profiling overheads)</div><div><br></div><div>COST CENTRE  MODULE  %time %alloc</div><div><br></div><div>main         Main     71.9   81.5</div><div>randVector.\ Main     25.0   16.5</div><div>randVector   Main      3.1    2.0</div><div><br></div><div><br></div><div>                                                              individual     inherited</div><div>COST CENTRE      MODULE                     no.     entries  %time %alloc   %time %alloc</div><div><br></div><div>MAIN             MAIN                        60           0    0.0    0.0   100.0  100.0</div><div> CAF             GHC.IO.Encoding.CodePage   108           0    0.0    0.0     0.0    0.0</div><div> CAF             GHC.IO.Encoding            106           0    0.0    0.0     0.0    0.0</div><div> CAF             System.CPUTime              98           0    0.0    0.0     0.0    0.0</div><div> CAF             GHC.IO.Handle.FD            95           0    0.0    0.0     0.0    0.0</div><div> CAF             Data.Fixed                  87           0    0.0    0.0     0.0    0.0</div><div> CAF             Data.Time.Clock.POSIX       82           0    0.0    0.0     0.0    0.0</div><div> CAF             System.Random               81           0    0.0    0.0     0.0    0.0</div><div> CAF             Main                        67           0    0.0    0.0   100.0  100.0</div><div>  randVector     Main                       121           1    0.0    0.0     0.0    0.0</div><div>  main           Main                       120           1   71.9   81.5   100.0  100.0</div><div>   randVector    Main                       122           0    3.1    2.0    28.1   18.5</div><div>    randVector.\ Main                       123     1000000   25.0   16.5    25.0   16.5</div><div><br></div><div>Thanks,</div><div>Holden</div><div><br></div><div><br></div></div></div>