Czy istnieje równoległe znalezisko w Haskell?

Question

Mam jakiś problem z brutalną siłą, który lubię rozwiązywać w Haskell. Moja maszyna ma 16 rdzeni, więc chcę nieco przyspieszyć mój obecny algorytm.

Mam metodę "tryCombination", która zwraca Just (String) lub Nic. Moja pętla wygląda następująco:

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

wiem, istnieje specjalna parMap parallelize funkcję mapy. Mapa może być trudna, ponieważ nie jest przewidywalna, jeśli wątek rzeczywiście znajdzie pierwsze wystąpienie. Ale czy istnieje coś takiego jak mapa, aby przyspieszyć wyszukiwanie?

EDIT:

przepisałem kod za pomocą "withStrategy (parList rseq)" fragmentu. Raport o stanie wygląda następująco:

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 

Jak już wspomniano (patrz moje komentarze), wszystkie rdzenie pracują tylko trzy sekundy (wenn wszystkie iskry zmian). Następne trzydzieści trzy prace są wykonywane przez jeden rdzeń. Jak mogę zoptymalizować jeszcze więcej?

Niektóre bardziej EDIT:

teraz dał "withStrategy (parBuffer 10 rdeepseq)" spróbować i bawił się wokół różnych rozmiarów bufor:

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 

Przede wszystkim mogę powiedzieć, że jest to znaczna poprawa w porównaniu z latami 59, które zajęły bez wielowątkowości. Drugi wniosek jest taki, że rozmiar bufora powinien być jak najmniejszy, ale większy niż liczba rdzeni. Ale najlepsze jest to, że nie mam już ani przepełnionych, ani iskrzących iskier. Wszystkie zostały pomyślnie przekonwertowane.

Answer 1

zależności od lazyness z tryCombination i pożądanego parallelization, jedna z nich może zrobić to, co chcesz:

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]] 

Ten paralleizes pracę wykonywaną przez tryCombination aby dowiedzieć się, czy jest to Just lub Nothing, ale nie faktyczny wynik w Just.

Jeśli nie ma takiego lazyness być eksploatowane i typ wyniku jest proste, to może działać lepiej napisać

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]]