python prime crunching: il pool di elaborazione è più lento?

Question

Quindi sono stato in giro con la lib di multiprocessing di python per gli ultimi giorni e mi piace molto il pool di elaborazione. È facile da implementare e posso visualizzare molti usi. Ho fatto un paio di progetti di cui ho sentito parlare prima di familiarizzarmi con esso e di recente ho terminato un programma che forza brutale giochi di boia.

Chiunque stia eseguendo un compendio per l'esecuzione di tutti i numeri primi tra 1 milione e 2 milioni sia con thread singolo sia tramite un pool di elaborazione. Ora, per il croccante dell'impiccato, mettere i giochi in un pool di elaborazione ha migliorato il tempo di esecuzione di circa 8 volte (i7 con 8 core), ma quando si estraevano questi numeri primi, in realtà aumentava il tempo di elaborazione di quasi un fattore di 4.

Qualcuno può dirmi perché questo è? Ecco il codice per chiunque sia interessato a guardare o testarlo:

#!/user/bin/python.exe 
import math 
from multiprocessing import Pool 

global primes 
primes = [] 

def log(result): 
    global primes 

    if result: 
     primes.append(result[1]) 

def isPrime(n): 
    if n < 2: 
     return False 
    if n == 2: 
     return True, n 

    max = int(math.ceil(math.sqrt(n))) 
    i = 2 
    while i <= max: 
     if n % i == 0: 
      return False 
     i += 1 
    return True, n 


def main(): 

    global primes 

    #pool = Pool() 

    for i in range(1000000, 2000000): 
     #pool.apply_async(isPrime,(i,), callback = log) 
     temp = isPrime(i) 
     log(temp) 

    #pool.close() 
    #pool.join() 

    print sum(primes) 

    return 

if __name__ == "__main__": 
    main() 

Sarà attualmente gestito in un singolo thread, a correre attraverso il pool di trasformazione, rimuovere il commento le dichiarazioni piscina e commentare le altre linee del principale per ciclo.

Answer 1

il modo più efficiente per utilizzare multiprocessing è dividere il lavoro in n pezzi di dimensioni uguali, con n la dimensione del pool, che dovrebbe essere approssimativamente il numero di core sul sistema. La ragione di ciò è che il lavoro di iniziare i sottoprocessi e di comunicare tra loro è piuttosto ampio. Se la dimensione del lavoro è ridotta rispetto al numero di blocchi di lavoro, il sovraccarico di IPC diventa significativo.

Nel tuo caso, stai chiedendo il multiprocesso per elaborare singolarmente ciascun numero. Un modo migliore per affrontare il problema è passare a ciascun operatore un intervallo di valori (probabilmente solo un valore iniziale e finale) e restituire tutti i numeri primi nell'intervallo trovato.

Nel caso dell'identificazione di primi lunghi di grandi dimensioni, il lavoro svolto cresce con il valore iniziale e quindi Probabilmente non si desidera dividere l'intervallo totale in esattamente n pezzi, ma piuttosto n * k pezzi uguali, con k qualche numero ragionevole, piccolo, diciamo 10 - 100. in questo modo, quando alcuni lavoratori finiscono prima degli altri, c'è ancora molto lavoro da fare e può essere bilanciato in modo efficiente tra tutti i lavoratori.

Modifica: ecco un esempio migliore per mostrare come potrebbe essere quella soluzione. Ho cambiato il meno possibile in modo da poter confrontare le mele con le mele.

#!/user/bin/python.exe 
import math 
from multiprocessing import Pool 

global primes 
primes = set() 

def log(result): 
    global primes 

    if result: 
     # since the result is a batch of primes, we have to use 
     # update instead of add (or for a list, extend instead of append) 
     primes.update(result) 

def isPrime(n): 
    if n < 2: 
     return False 
    if n == 2: 
     return True, n 

    max = int(math.ceil(math.sqrt(n))) 
    i = 2 
    while i <= max: 
     if n % i == 0: 
      return False 
     i += 1 
    return True, n 

def isPrimeWorker(start, stop): 
    """ 
    find a batch of primes 
    """ 
    primes = set() 
    for i in xrange(start, stop): 
     if isPrime(i): 
      primes.add(i) 

    return primes 



def main(): 

    global primes 

    pool = Pool() 

    # pick an arbitrary chunk size, this will give us 100 different 
    # chunks, but another value might be optimal 
    step = 10000 

    # use xrange instead of range, we don't actually need a list, just 
    # the values in that range. 
    for i in xrange(1000000, 2000000, step): 
     # call the *worker* function with start and stop values. 
     pool.apply_async(isPrimeWorker,(i, i+step,), callback = log) 

    pool.close() 
    pool.join() 

    print sum(primes) 

    return 

if __name__ == "__main__": 
    main()