Haskell: Matrixsortierung viel langsamer als Vektorsortierung

Question

Ich muss die Zeilen der großen Ganzzahlmatrizen in Haskell sortieren und ich begann, mit zufälligen Daten zu vergleichen. Ich fand, dass Haskell 3 mal langsamer ist als C++.

Aufgrund der Zufälligkeit erwarte ich, dass der Zeilenvergleich immer in der ersten Spalte endet (die keine Duplikate enthalten sollte). Also verengte ich die Matrix auf eine einzelne Spalte, die als Vektor (Unboxed.Vector Int) implementiert war, und verglich ihre Sortierung mit einer üblichen Vector Int.

Vector Int sortiert so schnell wie C++ (gute Nachrichten!), Aber wieder ist die Spaltenmatrix 3 mal langsamer. Hast du eine Idee warum? Bitte finden Sie den Code unten.

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

Wie Edward Kmett wie erklärt, hat die Haskell-Version eine zusätzliche Schicht der Indirektion. Ein UV.Vector sieht so etwas wie

data Vector a = Vector !Int !Int ByteArray# 

Also jeder Eintrag in Ihrem Vektor von Vektoren ist eigentlich ein Zeiger auf einen Rekord Scheibe Indizes halten und ein Zeiger auf ein Array von Bytes. Dies ist eine zusätzliche Indirektion, die der C++ Code nicht hat. Die Lösung besteht darin, ein ArrayArray# zu verwenden, das ein Array direkter Zeiger auf Bytearrays oder weiter ArrayArray# s ist. Wenn Sie vector benötigen, müssen Sie herausfinden, was Sie mit den Schneidemaschinen tun können. Eine andere Möglichkeit ist, zu primitive zu wechseln, das einfachere Arrays bietet.

Answer 2

dfeuer Rat Folgenden wird ein Vektor der Vektoren als ArrayArray# Umsetzung ist 4-mal schneller als Vector (Unboxed.Vector Int) und nur 40% langsamer als ein C++ Sortier 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,() #) 

Für Beispiel, das Sortieren einer Matrix von ganzen Zahlen wird dann verwenden

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