Haskell: matris sıralama vektör sıralamadan çok daha yavaş

Question

Haskell'de büyük tamsayı matrislerinin satırlarını sıralamak zorundayım ve rasgele verilerle kıyaslamaya başladım. Haskell'in C++'dan 3 kat daha yavaş olduğunu buldum.

Rasgelelikten dolayı, satırın her zaman ilk sütunda sonlandırılmasını beklerim (bu, çoğaltmaları olmamalıdır). Bu yüzden, Matrix'i Vector (Unboxed.Vector Int) olarak uygulanan tek bir sütuna daraltdım ve sıralamasını Normal Vector Int'le karşılaştırdım.

Vektör Int C++ (iyi haber!) Kadar hızlı bir şekilde sıralar, ancak yine sütun matrisi 3 kat daha yavaştır. Neden bir fikrin var mı? Lütfen aşağıdaki kodu bulun. İçin

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,() #) 

: Bir ArrayArray# olarak vektörlerin bir vektör uygulayan dfeuer tavsiyelerine uyarak

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

kullanacak sıralama, Haskell versiyonu dolaylama biri fazladan bir katman vardır. Bir UV.Vector

data Vector a = Vector !Int !Int ByteArray# 

gibi bir şey Yani vektörlerin sizin vektörü içinde her bir giriş aslında bir rekor tutan dilim endeksleri bir işaretçi ve bayt dizisi bir göstericidir görünüyor. Bu, C++ kodunun sahip olmadığı ekstra bir dolaysızlıktır. Çözüm, bayt dizilerine veya daha fazla ArrayArray# s'ye bir dizi doğrudan işaretleyici olan bir ArrayArray# kullanmaktır. vector'a ihtiyacınız varsa, dilimleme makineleri hakkında ne yapmanız gerektiğini anlamanız gerekir. Başka bir seçenek daha basit diziler sunan primitive'a geçmek.

Answer 2

, bir C++ std::vector<std::vector<int> > sıralama oranla 4 kat Vektör (Unboxed.Vector Int) daha hızlı ve sadece% 40 daha yavaştır örnek, bana açıklandığı gibi tamsayılar bir matris sonra Edward Kmett olarak

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