Dlaczego wyliczenia list Haskella nie są wykonywane równolegle?

Question

robie Projekt Euler problemu 21 do prac domowych i mam ten list ze zrozumieniem:

amicableNumberSums = [ x+y | x<-[1..10000], y <-[1..10000], (amicable x y)] 

To zajmuje bardzo dużo czasu, aby wykonać (zrozumiałe, gdyż testuje 10000^2 pary liczb) i patrząc na mój cpu użycie pokazuje, że używany jest tylko 1 rdzeń.

Ponieważ nie ma żadnych skutków ubocznych w zrozumieniu listy, nie ma niebezpieczeństwa dla wielu par liczb testowanych w tym samym czasie. Czy istnieje sposób, aby Haskell zrobił to automatycznie, czy nie, w jaki sposób mój kod mógł zostać zmodyfikowany, aby to zrobić?

(Edit) Błąd podczas uruchamiania drukowania (amicableNumberSums using parList):

Couldn't match type `a0 -> Eval a0' with `[Int]' 
Expected type: Strategy [Int] 
    Actual type: Strategy a0 -> Strategy [a0] 
In the second argument of `using', namely `parList' 
In the first argument of `print', namely 
    `(amicableNumberSums `using` parList)' 
In the expression: print (amicableNumberSums `using` parList) 

(Edit) Wydajność z dwóch proponowanych metod:

Ørjan Johansen's method: 218.79s elapsed parallel (4 cores + 4 hyperthreading) 
         279.37s elapsed sequential (single core) 
bheklilr's method: 247.82s elapsed parallel (4 cores + 4 hyperthreading) 
        274.10s elapsed sequential (single core) 
Original method: 278.69s elapsed 

To nie jest tak duża prędkość jako Miałem nadzieję, ale teraz mam poprawną odpowiedź na problem i dopóki nie nauczyłem się więcej Haskella, to wystarczy.

Answer 1

@ odpowiedź bheklilr za uchwyty ogólną metodę parallelizing strategie, ale jak dorozumiany w komentarzu powyżej, sposób oryginalna lista rozumienie jest napisane siłom wszystkie amicable testy wydarzy przed parList -na strategia na nim można dostać się do jego elementy i zacznij je oceniać, więc nie sądzę, że kod @ bheklilr będzie działał w tym konkretnym przypadku.

Oto moja propozycja poprawy. Musisz przepisać swoje zrozumienie list tak, aby dzieliło dzieło na dobrze zdefiniowane i niezależne porcje, np. poprzez połączenie wartości x na listach pośrednich. Na przykład może to być napisane równoważnie jako

concat [[ x+y | y <-[1..10000], (amicable x y)] | x <- [1..10000]] 

Teraz można umieścić strategię oceny równoległego pomiędzy zrozumieniem a ostateczną concat:

concat ([[ x+y | y <-[1..10000], (amicable x y)] | x <- [1..10000]] 
     `using` parList rdeepseq) 

(używam rdeepseq tutaj ponieważ elementy wstępnego -konkretna lista to także listy i chcemy ocenić wszystkie ich elementy, które są liczbami całkowitymi.)

Answer 2

Oto prosty przykład:

simple = 1 : 1 : [a + b | a <- simple, b <- simple] 

Jak byś parallelize to? W jaki sposób uogólnisz to na dowolne rozumienie list, aby zdecydować, czy można je zrównoleglić? A co z każdym innym rozumieniem listy na liście, która jest nieskończona, iskrzenie nowego wątku dla każdego elementu oznaczałoby iskrzenie nieskończonych wątków. A co, jeśli w rzeczywistości jest znacznie szybciej wyliczać listę sekwencyjnie, ponieważ obciążenie związane z gwintowaniem jest zbyt duże i spowalnia obliczenia? Co, jeśli potrzebne są tylko pierwsze 10 elementów listy? Byłoby niezbyt dobrze obliczyć całą listę łapczywie, gdy wymagana jest niewielka frakcja.

Zamiast tego GHC zdecydowało się dać moc programistom, kiedy i jak dokonać równoległego obliczenia listy. Zamiast robić rzeczy w sposób dorozumiany do Ciebie, możesz wybrać, jak to się robi za pomocą modułu Control.Parallel.Strategies:

print $ amicableNumberSums `using` parList rdeepseq 

Albo obliczania kawałki liście równolegle:

print $ amicableNumberSums `using` parListChunk 64 rdeepseq 

Pamiętaj, że musisz używać seq i co. aby uzyskać twoje dane w NF we właściwym czasie.

API ujawniony przez Control.Parallel.Strategies daje możliwość zdefiniowania różnych sposobów obliczania czystej struktury danych równolegle całkowicie oddzielonej od samej struktury danych lub nawet innych algorytmów. Stanowi to wyraźny kontrast w stosunku do większości innych języków programowania, które zmuszają cię do silnego łączenia paralelizmu z innymi algorytmami, a nawet budowania struktury. Gorąco polecam przeczytanie Simona Marlowa o numerze Parallel and Concurrent Haskell (jest to bezpłatne w sieci!), Które wykonuje o wiele lepszą pracę, niż mogę wyjaśnić, jak to działa i jak z niego korzystać.