Haskell: sorting matrices is much slower than sorting vectors

Question

I need to sort rows of large integer matrices in Haskell, and I started doing a comparative analysis with random data. I found that Haskell is 3 times slower than C ++.

Due to randomness, I expect that row comparisons always end in the first column (which should not have duplicates). Therefore, I narrowed the matrix to one column, implemented as a vector (Unboxed.Vector Int), and compared its sorting with the usual Vector Int.

Vector Int is sorted as fast as C ++ (good news!), But again, the column matrix is ​​3 times slower. Do you have an idea why? Please find the code below.

import qualified Data.Vector.Unboxed as UV(Vector, fromList) import qualified Data.Vector as V(Vector, fromList, modify) import Criterion.Main(env, bench, nf, defaultMain) import System.Random(randomIO) import qualified Data.Vector.Algorithms.Intro as Alg(sort) randomVector :: Int -> IO (V.Vector Int) randomVector count = V.fromList <$> mapM (\_ -> randomIO) [1..count] randomVVector :: Int -> IO (V.Vector (UV.Vector Int)) randomVVector count = V.fromList <$> mapM (\_ -> do x <- randomIO return $ UV.fromList [x]) [1..count] benchSort :: IO () benchSort = do let bVVect = env (randomVVector 300000) $ bench "sortVVector" . nf (V.modify Alg.sort) bVect = env (randomVector 300000) $ bench "sortVector" . nf (V.modify Alg.sort) defaultMain [bVect, bVVect] main = benchSort 

Answer 1

As Edward Kmett explained to me, the Haskell version has one additional layer of indirection. A UV.Vector looks something like

 data Vector a = Vector !Int !Int ByteArray# 

Thus, each record in a vector of vectors is actually a pointer to a record containing slice indices, and a pointer to an array of bytes. This is a sitelink that C ++ code does not have. The solution is to use ArrayArray# , which is an array of direct pointers to byte arrays or further ArrayArray# s. If you need vector , you will need to figure out what to do with the cutting mechanism. Another option is to switch to primitive , which offers simpler arrays.

Answer 2

Following dfeuer's advice, implementing a vector of vectors as ArrayArray# is 4 times faster than Vector (Unboxed.Vector Int) and only 40% slower than C ++ sorting std::vector<std::vector<int> > :

 import Control.Monad.Primitive import Data.Primitive.ByteArray import qualified Data.Vector.Generic.Mutable.Base as GM(MVector(..)) import GHC.Prim data MutableArrayArray sa = MutableArrayArray (MutableArrayArray# s) instance GM.MVector MutableArrayArray ByteArray where {-# INLINE basicLength #-} basicLength (MutableArrayArray marr) = I# (sizeofMutableArrayArray# marr) {-# INLINE basicUnsafeRead #-} basicUnsafeRead (MutableArrayArray marr) (I# i) = primitive $ \s -> case readByteArrayArray# marr is of (# s1, bar #) -> (# s1, ByteArray bar #) {-# INLINE basicUnsafeWrite #-} basicUnsafeWrite (MutableArrayArray marr) (I# i) (ByteArray bar) = primitive $ \s -> (# writeByteArrayArray# marr i bar s, () #) 

For example, sorting a matrix of integers will use

 sortIntArrays :: ByteArray -> ByteArray -> Ordering sortIntArrays xy = let h1 = indexByteArray x 0 :: Int h2 = indexByteArray y 0 :: Int in compare h1 h2