Сортировка в параллельном исполнении

Question

Я пробовал запускать несколько программ с многоядерностью и немного смущен результатами. По умолчанию сортировка в программе ниже занимает 20 секунд, когда я запускаю ее с +RTS -N2, она занимает около 16 секунд, но с +RTS -N4 это занимает 21 секунду!

Почему это так? А есть ли пример программы, которая становится быстрее с каждым дополнительным ядром? (имел аналогичные результаты с другими программами в учебниках)

Вот пример программы:

import Data.List
import Control.Parallel
import Data.Time.Clock.POSIX

qsort :: Ord a => [a] -> [a]
qsort (x:xs)
  = let a = qsort $ filter (<=x) xs
        b = qsort $ filter (>x)  xs
    in b `par` a ++ x:b
qsort [] = []


randomList :: Int -> [Int]
randomList n = take n $ tail (iterate lcg 1)
  where lcg x = (a * x + c) `rem` m
        a = 1664525
        c = 1013904223
        m = 2^32

main :: IO ()
main = do
  let randints = randomList 5000000
  t1 <- getPOSIXTime
  print . sum $ qsort randints
  t2 <- getPOSIXTime
  putStrLn $ "SORT TIME: " ++ show (t2 - t1) ++ "\n"

Answer 1

Я не могу повторить ваши результаты. (Это хорошо, поскольку я думаю, что именно я утверждал, что вижу улучшение производительности с помощью -N2 и -N4 с кодом, который вы опубликовали.)

На Linux с GH C 8.8.3 и компилируя в автономный исполняемый файл с помощью -O2 -threaded, я получаю следующие тайминги на 4-ядерном настольном компьютере:

$ stack ghc -- --version
Stack has not been tested with GHC versions above 8.6, and using 8.8.3, this may fail
Stack has not been tested with Cabal versions above 2.4, but version 3.0.1.0 was found, this may fail
The Glorious Glasgow Haskell Compilation System, version 8.8.3
$ stack ghc -- -O2 -threaded QuickSort3.hs
Stack has not been tested with GHC versions above 8.6, and using 8.8.3, this may fail
Stack has not been tested with Cabal versions above 2.4, but version 3.0.1.0 was found, this may fail
[1 of 1] Compiling Main             ( QuickSort3.hs, QuickSort3.o )
Linking QuickSort3 ...
$ ./QuickSort3 +RTS -N1
10741167410134688
SORT TIME: 7.671760902s

$ ./QuickSort3 +RTS -N2
10741167410134688
SORT TIME: 5.700858877s

$ ./QuickSort3 +RTS -N3
10741167410134688
SORT TIME: 4.88330669s

$ ./QuickSort3 +RTS -N4
10741167410134688
SORT TIME: 4.93364958s

Я получаю аналогичные результаты с 16-ядерным ноутбуком Linux и также аналогичные результаты с 4-ядерной виртуальной машиной Windows (также использующей GH C 8.8.3), работающей на этом ноутбуке.

Я могу придумать несколько возможных объяснений ваших результатов.

Во-первых, у меня нет очень быстрой настольной машины, поэтому ваши 20 секунд кажутся подозрительными. Возможно ли, что вы делаете что-то вроде:

$ stack runghc QuickSort3.hs +RTS -N4

Если да, это передает флаги +RTS в stack, а затем запускает программу Haskell в однопоточном режиме с использованием медленного Интерпретатор байт-кода. В моих тестах сортировка занимает около 30 секунд независимо от того, какое значение флага -Nx я передаю.

Во-вторых, возможно ли, что вы запускаете это на виртуальной машине с ограниченным количеством ядер (или крайне старая двухъядерная железка)? Как уже отмечалось, я пробовал тестировать на виртуальной машине Windows и получил результаты, аналогичные результатам Linux с 4-ядерной виртуальной машиной, но довольно ошибочные c результаты с 2-ядерной виртуальной машиной (например, 11.4, 13.0 , и 51,3 секунды для -N1, -N2 и -N4 соответственно, поэтому производительность для большего количества ядер в целом хуже, а для 4 ядер - за пределами графика).

Вы можете попробовать следующий простой тест параллельных сумм, который может лучше масштабироваться:

import Data.List
import Control.Parallel
import Data.Time.Clock.POSIX

randomList :: Int -> Int -> [Int]
randomList seed n = take n $ tail (iterate lcg seed)
  where lcg x = (a * x + c) `rem` m
        a = 1664525
        c = 1013904223
        m = 2^32

main :: IO ()
main = do
  t1 <- getPOSIXTime
  let n = 50000000
      a = sum $ randomList 1 n
      b = sum $ randomList 2 n
      c = sum $ randomList 3 n
      d = sum $ randomList 4 n
      e = sum $ randomList 5 n
      f = sum $ randomList 6 n
      g = sum $ randomList 7 n
      h = sum $ randomList 8 n
  print $ a `par` b `par` c `par` d `par` e `par` f `par` g `par` h `par` (a+b+c+d+e+f+g+h)
  t2 <- getPOSIXTime
  putStrLn $ "SORT TIME: " ++ show (t2 - t1) ++ "\n"