performance - haskell : matrix sorting much slower than vector sorting

Question

我必须在 Haskell 中对大整数矩阵的行进行排序，然后我开始使用随机数据进行基准测试。我发现 Haskell 比 C++ 慢 3 倍。

由于随机性，我希望行比较总是在第一列(应该没有重复)处终止。因此，我将矩阵缩小到作为 Vector (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

正如 Edward Kmett 向我解释的那样，Haskell 版本有一个额外的间接层。一个 UV.Vector看起来像

data Vector a = Vector !Int !Int ByteArray#

因此，向量向量中的每个条目实际上是一个指向保存切片索引的记录的指针和一个指向字节数组的指针。这是 C++ 代码没有的额外的间接性。解决方案是使用 ArrayArray# ，这是一个指向字节数组或进一步 ArrayArray# 的直接指针数组s。如果您需要 vector ，您必须弄清楚如何处理切片机械。另一种选择是切换到 primitive ，它提供了更简单的数组。