Haskell:矩阵排序比矢量排序慢得多

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 版本有一个额外的间接层。AUV.Vector看起来像

data Vector a = Vector !Int !Int ByteArray#

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