是否有可能在Haskell中加快par的速度？

Question

我有這個看似微不足道的並行快速排序的實現，代碼如下：

import System.Random 
import Control.Parallel 
import Data.List 

quicksort :: [a] -> [a] 
quicksort xs = pQuicksort 16 xs -- 16 is the number of sparks used to sort 

-- pQuicksort, parallelQuicksort 
-- As long as n > 0 evaluates the lower and upper part of the list in parallel, 
-- when we have recursed deep enough, n==0, this turns into a serial quicksort. 
pQuicksort :: Int -> [a] -> [a] 
pQuicksort _ [] = [] 
pQuicksort 0 (x:xs) = 
    let (lower, upper) = partition (< x) xs 
    in pQuicksort 0 lower ++ [x] ++ pQuicksort 0 upper 
pQuicksort n (x:xs) = 
    let (lower, upper) = partition (< x) xs 
     l = pQuicksort (n `div` 2) lower 
     u = [x] ++ pQuicksort (n `div` 2) upper 
    in (par u l) ++ u 

main :: IO() 
main = do 
    gen <- getStdGen 
    let randints = (take 5000000) $ randoms gen :: [Int] 
    putStrLn . show . sum $ (quicksort randints) 

我編譯

ghc --make -threaded -O2 quicksort.hs 

與

./quicksort +RTS -N16 -RTS 

運行無論我做什麼我無法讓它比運行在一個cpu上的簡單順序實現運行得更快。

1. 是否有可能解釋爲什麼它在多個CPU上的運行速度比在一個上運行速度慢得多？
2. 是否有可能通過做一些技巧來使這個縮放比例（至少是線性的）與CPU的數量成正比？

編輯：@tempestadept暗示，快速排序它是自己的問題。爲了檢查這一點，我以與上例相同的精神實施了一個簡單的合併排序。它具有相同的行爲，執行速度越慢，添加的功能越多。

import System.Random 
import Control.Parallel 

splitList :: [a] -> ([a], [a]) 
splitList = helper True [] [] 
    where helper _ left right [] = (left, right) 
     helper True left right (x:xs) = helper False (x:left) right xs 
     helper False left right (x:xs) = helper True left (x:right) xs 

merge :: (Ord a) => [a] -> [a] -> [a] 
merge xs [] = xs 
merge [] ys = ys 
merge (x:xs) (y:ys) = case x<y of 
    True -> x : merge xs (y:ys) 
    False -> y : merge (x:xs) ys 

mergeSort :: (Ord a) => [a] -> [a] 
mergeSort xs = pMergeSort 16 xs -- we use 16 sparks 

-- pMergeSort, parallel merge sort. Takes an extra argument 
-- telling how many sparks to create. In our simple test it is 
-- set to 16 
pMergeSort :: (Ord a) => Int -> [a] -> [a] 
pMergeSort _ [] = [] 
pMergeSort _ [a] = [a] 
pMergeSort 0 xs = 
    let (left, right) = splitList xs 
    in merge (pMergeSort 0 left) (pMergeSort 0 right) 
pMergeSort n xs = 
    let (left, right) = splitList xs 
     l = pMergeSort (n `div` 2) left 
     r = pMergeSort (n `div` 2) right 
    in (r `par` l) `pseq` (merge l r) 

ris :: Int -> IO [Int] 
ris n = do 
    gen <- getStdGen 
    return . (take n) $ randoms gen 

main = do 
    r <- ris 100000 
    putStrLn . show . sum $ mergeSort r 

Answer 1

我不知道如何能爲慣用的快速排序工作，但它可以工作（一個有點弱程度）對於真正的當務之急快速排序爲Sparking Imperatives所示由羅馬。儘管如此，他從未獲得過很好的加速比。這真的需要一個真正的work-stealing deque，不像火花隊列那樣溢出來正確優化。

Answer 2

由於您的僞快速排序涉及列表連接，無法並行化並且需要二次時間（所有連接的總時間），所以您不會得到任何顯着改進。我建議你嘗試使用鏈接列表上的合併排序，即O(n log n)。

另外，要運行帶有大量線程的程序，您應該使用-rtsopts進行編譯。

Answer 3

par只評估弱頭標準形式的第一個參數。也就是說：如果第一個參數的類型是Maybe Int那麼par將檢查結果是Nothing還是Just something並停止。它根本不會評估something。同樣，對於列表，它僅評估足以檢查列表是否爲[]或something:something_else。要並行評估整個列表：您不會直接將列表傳遞給par，那麼您將按照列表的方式創建一個表達式，以便在將它傳遞給par時需要整個列表。例如：

evalList :: [a] ->() 
evalList [] =() 
evalList (a:r) = a `pseq` evalList r 

pMergeSort :: (Ord a) => Int -> [a] -> [a] 
pMergeSort _ [] = [] 
pMergeSort _ [a] = [a] 
pMergeSort 0 xs = 
    let (left, right) = splitList xs 
    in merge (pMergeSort 0 left) (pMergeSort 0 right) 
pMergeSort n xs = 
    let (left, right) = splitList xs 
     l = pMergeSort (n `div` 2) left 
     r = pMergeSort (n `div` 2) right 
    in (evalList r `par` l) `pseq` (merge l r) 

另注：在Haskell中推出新線程的開銷是非常低，所以pMergeSort 0 ...的情況下可能是沒有用的。