Haskell: сортировка матриц намного медленнее, чем сортировка по вектору

Question

Мне нужно отсортировать строки больших целых матриц в Haskell, и я начал проводить сравнительный анализ со случайными данными. Я обнаружил, что Haskell в 3 раза медленнее, чем C++.

Из-за случайности, я ожидаю, что сравнение строк всегда заканчивается в первом столбце (который не должен иметь дубликатов). Поэтому я сузил матрицу до одного столбца, реализованного как вектор (Unboxed.Vector Int), и сравнил его сортировку с обычным Vector Int.

Vector Int сортируется так же быстро, как C++ (хорошие новости!), Но опять же, матрица столбцов в 3 раза медленнее. У вас есть идея, почему? Пожалуйста, найдите код ниже.

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

Как Эдвард Kmett, как объяснил мне, версия Haskell имеет один дополнительный слой косвенности. UV.Vector выглядит что-то вроде

data Vector a = Vector !Int !Int ByteArray# 

Таким образом, каждая запись в вашем вектор векторов на самом деле является указателем на рекордные проведение индексов срезов и указатель на массив байтов. Это дополнительная ссылка, которую не имеет код C++. Решение состоит в использовании ArrayArray#, который представляет собой массив прямых указателей на байт-массивы или дополнительно ArrayArray# с. Если вам нужно vector, вам нужно выяснить, что делать с режущим оборудованием. Другим вариантом является переход на primitive, который предлагает более простые массивы.

Answer 2

Следуя совету dfeuer, в реализации вектор векторов как ArrayArray# в 4 раза быстрее, чем вектор (Unboxed.Vector Int) и только 40% медленнее, чем сортировка C++ 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 s a = 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 i s of 
    (# s1, bar #) -> (# s1, ByteArray bar #) 

    {-# INLINE basicUnsafeWrite #-} 
    basicUnsafeWrite (MutableArrayArray marr) (I# i) (ByteArray bar) = primitive $ \s -> 
    (# writeByteArrayArray# marr i bar s,() #) 

Для Например, сортировка матрица целых чисел будет использовать

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