Esiste una ricerca parallela in Haskell?

Question

Ho una sorta di problema di forza bruta che mi piace risolvere in Haskell. La mia macchina ha 16 core quindi voglio accelerare un po 'il mio attuale algoritmo.

Ho un metodo "tryCombination" che restituisce Just (String) o Nothing. Il mio ciclo assomiglia a questo:

findSolution = find (isJust) [tryCombination a1 a2 a3 n z p | 
           a1 <- [600..700], 
           a2 <- [600..700], 
           a3 <- [600..700], 
           n <- [1..100], 
           .... 

So che esiste uno speciale parMap per parallelizzare una funzione mappa. Un mapFind potrebbe essere complicato in quanto non è prevedibile, se un thread trova davvero la prima occorrenza. Ma c'è qualcosa come una mappa? Per velocizzare la ricerca?

EDIT:

ho riscritto il codice utilizzando il "withStrategy (parList rseq)" snippet. Il rapporto di stato si presenta così:

38,929,334,968 bytes allocated in the heap 
2,215,280,048 bytes copied during GC 
    3,505,624 bytes maximum residency (795 sample(s)) 
     202,696 bytes maximum slop 
      15 MB total memory in use (0 MB lost due to fragmentation) 

            Tot time (elapsed) Avg pause Max pause 
Gen 0  44922 colls, 44922 par 37.33s 8.34s  0.0002s 0.0470s 
Gen 1  795 colls, 794 par 7.58s 1.43s  0.0018s 0.0466s 

Parallel GC work balance: 4.36% (serial 0%, perfect 100%) 

TASKS: 10 (1 bound, 9 peak workers (9 total), using -N8) 

SPARKS: 17576 (8198 converted, 9378 overflowed, 0 dud, 0 GC'd, 0 fizzled) 

INIT time 0.00s ( 0.00s elapsed) 
MUT  time 81.79s (36.37s elapsed) 
GC  time 44.91s ( 9.77s elapsed) 
EXIT time 0.00s ( 0.00s elapsed) 
Total time 126.72s (46.14s elapsed) 

Alloc rate 475,959,220 bytes per MUT second 

Productivity 64.6% of total user, 177.3% of total elapsed 

gc_alloc_block_sync: 834851 
whitehole_spin: 0 
gen[0].sync: 10 
gen[1].sync: 3724 

Come ho già detto (vedi i miei commenti), tutti i core stanno lavorando per soli tre secondi (wenn tutte le scintille sono trattati). Gli anni '30 seguenti tutto il lavoro è svolto da un singolo core. Come posso ottimizzare ancora di più?

Alcuni più EDIT:

ora mi ha dato "withStrategy (parBuffer 10 rdeepseq)" una prova e armeggiò con diverse dimensioni del buffer:

Buffersize GC work Balance  MUT  GC 
     10    50%  11,69s 0,94s 
     100    47%  12,31s 1,67s 
     500    40%  11,5 s 1,35s 
    5000    21%  11,47s 2,25s 

Prima di tutto quello che posso dire, che questo è un grande miglioramento rispetto agli anni '59, senza alcun multithreading. La seconda conclusione è che la dimensione del buffer dovrebbe essere il più piccola possibile ma più grande del numero di core. Ma la cosa migliore è che non ho più né scintille traboccate né scintille. Tutti sono stati convertiti con successo.

Answer 1

seconda della pigrizia del tryCombination e la parallelizzazione desiderato, uno di questi potrebbe fare quello che vuoi:

import Control.Parallel.Strategies 
findSolution = 
    find (isJust) $ 
    withStrategy (parList rseq) $ 
    [ tryCombination a1 a2 a3 n z p 
    | a1 <- [600..700] 
    , a2 <- [600..700] 
    , a3 <- [600..700] 
    , n <- [1..100]] 

Questa paralleizes del lavoro svolto dalla tryCombination di capire se si tratta di un Just o un Nothing, ma non il risultato effettivo nello Just.

Se non c'è tale pigrizia da sfruttare e il tipo di risultato è semplice, potrebbe funzionare meglio scrivere

findSolution = 
    find (isJust) $ 
    withStrategy (parList rdeepseq) $ 
    [ tryCombination a1 a2 a3 n z p 
    | a1 <- [600..700] 
    , a2 <- [600..700] 
    , a3 <- [600..700] 
    , n <- [1..100]]