Perché le letture haskell degli elenchi non sono eseguite in parallelo?

Question

sto facendo problema Project Euler 21 per compiti a casa e ho questa lista di comprensione:

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

Questo richiede un tempo molto lungo per l'esecuzione (comprensibile in quanto mette alla prova 10000^2 coppie di numeri) e guardando la mia cpu l'utilizzo mostra che viene utilizzato solo 1 core.

Poiché non ci sono effetti collaterali nella comprensione della lista, non vi è alcun pericolo in più coppie di numeri testati contemporaneamente. C'è un modo per far sì che Haskell lo faccia automaticamente o se no come potrebbe essere modificato il mio codice per farlo?

(Edit) Errore durante l'esecuzione di stampa (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) Performance dei due metodi suggeriti:

Ø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 

Questo non è così grande velocità come Speravo ma ora ho la risposta corretta al problema e fino a quando non ho imparato un po 'di più Haskell questo è sufficiente.

Answer 1

@ risposta di bheklilr gestisce il metodo generale di parallelizzare le strategie, ma come ho implicito nel commento di cui sopra, il modo in cui la lista di comprensione originario viene forze tutte amicable test per accadere prima che una strategia basata su parList su di esso può arrivare a sua elementi e iniziare a valutarli, quindi non credo che il codice di @ bheklilr funzionerà abbastanza per questo specifico caso.

Ecco il mio suggerimento per un miglioramento. È necessario riscrivere la comprensione della lista in modo tale da dividere il lavoro in blocchi ben definiti e indipendenti, ad es. combinando i valori x negli elenchi intermedi. Ad esempio può essere scritto equivalentemente come

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

Ora si può mettere una strategia di valutazione parallelo tra la comprensione e la finale concat:

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

(io uso rdeepseq qui perché gli elementi del pre -la lista concatenata sono anche elenchi e vogliamo valutare tutti i loro elementi che sono numeri interi)

Answer 2

Ecco un semplice esempio:

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

Come ti parallelizzare questo? Come generalizzeresti questo a qualsiasi list comprehension per decidere se può essere parallelizzato? Che dire di qualsiasi altra lista di comprensione su una lista che è infinita, innescare un nuovo thread per ogni elemento significherebbe scatenare fili infiniti. Cosa succede se in realtà è molto più veloce calcolare l'elenco in modo sequenziale poiché il sovraccarico del threading è troppo grande e rallenta il calcolo? Cosa succede se sono necessari solo i primi 10 elementi dell'elenco? Non sarebbe molto utile calcolare avidamente l'intero elenco quando è richiesta una piccola frazione.

Invece, GHC ha scelto di dare il potere al programmatore su quando e come parallelizzare un calcolo di lista. Invece di fare le cose in modo implicito per voi, è possibile scegliere come si fa utilizzando il modulo Control.Parallel.Strategies:

print $ amicableNumberSums `using` parList rdeepseq 

o calcolare pezzi di lista in parallelo:

print $ amicableNumberSums `using` parListChunk 64 rdeepseq 

Tenete a mente che dovrete usare seq e co. per ottenere i dati in NF al momento giusto.

L'API esposta da Control.Parallel.Strategies offre la possibilità di definire diversi modi di calcolare una struttura dati pura in parallelo completamente separata dalla struttura dati stessa o anche da altri algoritmi. Ciò è in netto contrasto con la maggior parte degli altri linguaggi di programmazione che ti costringono ad accoppiare fortemente il tuo parallelismo con gli altri tuoi algoritmi, o persino come è costruita la struttura. Consiglio vivamente di leggere Simon Marlow's Parallel and Concurrent Haskell (è gratis online!), Che fa un lavoro molto migliore di quello che posso per spiegare come funziona e come usarlo.