Równoległa lista wydajności Haskella

Question

Posłużyłem się równoległymi funkcjami Haskella par i pseq i odkryłem coś interesującego.

Moja baza przykładów na przykłady z książki Real World Haskell „s (Parallel programming in Haskell):

wspólny kod:

import Control.Parallel (par, pseq) 

-- <<sorting code goes here>> 

force :: [a] ->() 
force xs = go xs `pseq`() 
    where go (_:xs) = go xs 
      go [] = 1 

main = do 
    print $ take 10 $ parSort [0..1000000] 

sortowania kod 1 (zaczerpnięte z książki):

parSort :: (Ord a) => [a] -> [a] 
parSort (x:xs) = force greater `par` (force lesser `pseq` 
             (lesser ++ x:greater)) 
    where lesser = parSort [y | y <- xs, y < x] 
      greater = parSort [y | y <- xs, y >= x] 
parSort _   = [] 

kod sortowania 2 (mój zwyczaj wariant):

parSort :: (Ord a) => [a] -> [a] 
parSort (x:xs) = force greater `par` (lesser ++ x:greater) 
    where lesser = parSort [y | y <- xs, y < x] 
      greater = parSort [y | y <- xs, y >= x] 
parSort _   = [] 

kompilacji & prowadzony z: ghc -O2 -threaded --make Main.hs && time ./Main +RTS -N8

Co ciekawe, mój wariant jest nieco szybciej niż książek One:

sorting code 1 - avg. 16 seconds 
sorting code 2 - avg. 14 seconds 

chcę zapytaj, dlaczego obserwujemy takie zachowanie i czy rozwiązanie książki daje jakiekolwiek korzyści w stosunku do mojej. Bardzo chciałbym zrozumieć, dlaczego to rozwiązanie może działać lepiej.

Answer 1

Powiedziałbym, że to dlatego, że Twój niestandardowy wariant nie wymusza pierwszej części listy. Rzućmy okiem na to, co dzieje się na najwyższym poziomie: Wymuszasz prawą połowę listy, ale nie lewą część. Kiedy drukujesz pierwsze 10 elementów, oceniasz leniwie pierwsze 10 elementów lewej części, a reszta pozostaje nieuznana.

Z drugiej strony rozwiązanie z książki wymusza obie części, więc przed wydrukowaniem pierwszych 10 elementów oceni się lewą i prawą część.

Zamiast drukować pierwsze 10 elementów, spróbuj wydrukować ostatni, jak

print $ last $ parSort data 

następnie oba warianty algorytmu będzie musiał ocenić całą listę. Lub wymuś całą listę po jej posortowaniu i przed wydrukowaniem.

---

Uwaga że sortowanie [0..100000] z tego algorytmu będzie bardzo nieefektywne, ponieważ zawsze wybierają najgorszą możliwą pivot i tak to trwa O (n^2) czasu. Pomiary nie przyniosą znaczących rezultatów. Jeśli chcesz uzyskać dobre wyniki z czasem O (n log n), podaj algorytm losowy. Możesz znaleźć prostą metodę tworzenia losowej permutacji here.

Uwaga: Zamiast time Sugeruję używanie criterion zmierzyć swój kod. Następnie możesz zmierzyć tylko istotne części kodu, wyłączając inicjalizację itd., Oraz wymuszając dane wejściowe i wyjściowe, aby dokładnie zmierzyć jedną część, którą chcesz.