Haskell: phân loại ma trận chậm hơn nhiều so với phân loại vector

Question

Tôi phải sắp xếp các dòng ma trận số nguyên lớn trong Haskell và tôi bắt đầu đo điểm chuẩn với dữ liệu ngẫu nhiên. Tôi thấy rằng Haskell chậm hơn 3 lần so với C++.

Do tính ngẫu nhiên, tôi mong đợi so sánh đường để luôn chấm dứt ở cột đầu tiên (không được trùng lặp). Vì vậy, tôi thu hẹp ma trận thành một cột đơn được triển khai dưới dạng Vector (Unboxed.Vector Int) và so sánh việc phân loại thành một Vector Int thông thường.

Vector Int sắp xếp nhanh như C++ (tin tốt!), Nhưng một lần nữa, ma trận cột chậm hơn 3 lần. Bạn có ý tưởng tại sao không? Vui lòng tìm mã bên dưới.

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

Như Edward Kmett đã giải thích cho tôi, phiên bản Haskell có thêm một lớp hướng dẫn. Một UV.Vector trông giống như

data Vector a = Vector !Int !Int ByteArray# 

Vì vậy, mỗi mục trong vector của bạn của vectơ thực sự là một con trỏ lên mức kỷ lục giữ chỉ số lát và một con trỏ đến một mảng các byte. Đây là một sự thừa hưởng thêm rằng mã C++ không có. Giải pháp là sử dụng một ArrayArray#, là một mảng các con trỏ trực tiếp tới các mảng byte hoặc để tiếp tục ArrayArray# s. Nếu bạn cần vector, bạn sẽ phải tìm ra những việc cần làm về máy cắt. Một tùy chọn khác là chuyển sang primitive, cung cấp các mảng đơn giản hơn.

Answer 2

Sau lời khuyên dfeuer của, thực hiện một vector của vector như một ArrayArray# là nhanh hơn 4 lần so với Vector (Unboxed.Vector Int) và chậm hơn chỉ 40% so với sắp xếp một 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,() #) 

Đối ví dụ, việc sắp xếp ma trận các số nguyên sau đó sẽ sử dụng

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