La programmazione funzionale è più veloce nel multithreading perché scrivo le cose in modo diverso o perché le cose sono compilate in modo diverso?

61

Mi sto immergendo nel mondo della programmazione funzionale e continuo a leggere ovunque che i linguaggi funzionali siano migliori per i programmi multithreading / multicore. Capisco come i linguaggi funzionali facciano molte cose in modo diverso, come ad esempio ricorsione , numeri casuali ecc. ma non riesco a sembrare capire se il multithreading è più veloce in un linguaggio funzionale perché è compilato in modo diverso o perché I scrive in modo diverso.

Ad esempio, ho scritto un programma in Java che implementa un certo protocollo. In questo protocollo le due parti inviano e ricevono reciprocamente migliaia di messaggi, crittografano tali messaggi e li inviano nuovamente (e li ricevono) ancora e ancora. Come previsto, il multithreading è fondamentale quando si ha a che fare con una scala di migliaia. In questo programma non è previsto alcun blocco .

Se scrivo lo stesso programma in Scala (che usa la JVM), questa implementazione sarà più veloce? Se sì, perché? È a causa dello stile di scrittura? Se è a causa dello stile di scrittura, ora che Java include espressioni lambda, non potrei ottenere gli stessi risultati usando Java con lambda? O è più veloce perché Scala compilerà le cose in modo diverso?

    
posta Aventinus 15.02.2016 - 16:17
fonte

4 risposte

94

Il motivo per cui le persone dicono che i linguaggi funzionali sono migliori per l'elaborazione parallela è dovuto al fatto che di solito evitano lo stato mutabile. Lo stato mutevole è la "radice di ogni male" nel contesto dell'elaborazione parallela; rendono davvero facile imbattersi in condizioni di gara quando sono condivise tra processi concorrenti. La soluzione alle condizioni di gara coinvolge quindi meccanismi di blocco e sincronizzazione, come hai menzionato, che causano sovraccarico di runtime, poiché i processi si attendono l'un l'altro per utilizzare la risorsa condivisa e una maggiore complessità di progettazione, poiché tutti questi concetti tendono ad essere profondamente annidato all'interno di tali applicazioni.

Quando si evita lo stato mutabile, scompare la necessità di meccanismi di sincronizzazione e di blocco. Poiché i linguaggi funzionali di solito evitano lo stato mutabile, sono naturalmente più efficienti ed efficaci per l'elaborazione parallela: non si avrà il sovraccarico di runtime delle risorse condivise e non si avrà la complessità di progettazione aggiunta che di solito segue.

Tuttavia, questo è tutto incidentale. Se la soluzione in Java evita anche lo stato mutabile (specificamente condiviso tra thread), convertirlo in un linguaggio funzionale come Scala o Clojure non produrrebbe alcun beneficio in termini di efficienza concorrente, perché la soluzione originale è già priva del sovraccarico causato da i meccanismi di bloccaggio e sincronizzazione

TL; DR: Se una soluzione in Scala è più efficiente nell'elaborazione parallela di una in Java, non è a causa del modo in cui il codice viene compilato o eseguito attraverso la JVM, ma perché la soluzione Java sta condividendo lo stato mutabile tra i thread, causando condizioni di competizione o aggiungendo il sovraccarico della sincronizzazione per evitarli.

    
risposta data 15.02.2016 - 16:49
fonte
8

Tipi di entrambi. È più veloce perché è più facile scrivere il codice in un modo che è più facile da compilare più velocemente. Non avrai necessariamente una differenza di velocità passando da una lingua all'altra, ma se avessi iniziato con un linguaggio funzionale, probabilmente avresti fatto il multithreading con molto meno sforzo programmatore . Sulla stessa falsariga, è molto più facile per un programmatore commettere errori di threading che costano velocità in un linguaggio imperativo, e molto più difficile notare questi errori.

La ragione è che i programmatori imperativi in genere cercano di mettere tutto il codice thread-free e privo di lock in una scatola il più piccola possibile, e di fuggire il prima possibile, nel loro constrongvole e mutevole mondo sincrono. La maggior parte degli errori che ti costano velocità sono fatti su quella interfaccia di confine. In un linguaggio di programmazione funzionale, non devi preoccuparti di fare errori su quel confine. La maggior parte del tuo codice chiamante è anche "dentro la scatola", per così dire.

    
risposta data 15.02.2016 - 19:54
fonte
7

La programmazione funzionale non consente programmi più veloci, come regola generale. Ciò che rende è per più facile programmazione parallela e simultanea. Ci sono due chiavi principali per questo:

  1. L'evitamento dello stato mutabile tende a ridurre il numero di cose che possono andare storte in un programma, e ancora di più in un programma concorrente.
  2. L'evitamento della memoria condivisa e delle primitive di sincronizzazione basate su lock a favore di concetti di livello superiore tende a semplificare la sincronizzazione tra i thread del codice.

Un eccellente esempio del punto # 2 è che in Haskell abbiamo una chiara distinzione tra parallelismo deterministico vs concorrenza non deterministica . Non c'è spiegazione migliore della citazione dell'eccellente libro di Simon Marlow Programmazione parallela e simultanea in Haskell ( le citazioni provengono da Capitolo 1 ):

A parallel program is one that uses a multiplicity of computational hardware (e.g., several processor cores) to perform a computation more quickly. The aim is to arrive at the answer earlier, by delegating different parts of the computation to different processors that execute at the same time.

By contrast, concurrency is a program-structuring technique in which there are multiple threads of control. Conceptually, the threads of control execute “at the same time”; that is, the user sees their effects interleaved. Whether they actually execute at the same time or not is an implementation detail; a concurrent program can execute on a single processor through interleaved execution or on multiple physical processors.

In aggiunta a ciò, Marlow menziona anche la dimensione del determinismo :

A related distinction is between deterministic and nondeterministic programming models. A deterministic programming model is one in which each program can give only one result, whereas a nondeterministic programming model admits programs that may have different results, depending on some aspect of the execution. Concurrent programming models are necessarily nondeterministic because they must interact with external agents that cause events at unpredictable times. Nondeterminism has some notable drawbacks, however: Programs become significantly harder to test and reason about.

For parallel programming, we would like to use deterministic programming models if at all possible. Since the goal is just to arrive at the answer more quickly, we would rather not make our program harder to debug in the process. Deterministic parallel programming is the best of both worlds: Testing, debugging, and reasoning can be performed on the sequential program, but the program runs faster with the addition of more processors.

In Haskell il parallelismo e le caratteristiche di concorrenza sono disegnate attorno a questi concetti. In particolare, quali altre lingue sono raggruppate come un set di funzionalità, Haskell si divide in due:

  • Funzioni deterministiche e librerie per parallelismo .
  • Funzioni e librerie non deterministiche per concorrenza .

Se stai solo cercando di accelerare un calcolo puro e deterministico, avere un parallelismo deterministico spesso rende le cose molto più semplici. Spesso fai qualcosa del genere:

  1. Scrivi una funzione che produce un elenco di risposte, ognuna delle quali è costosa da calcolare ma non dipende molto l'una dall'altra. Questo è Haskell, quindi gli elenchi sono pigri - i valori dei loro elementi non vengono effettivamente calcolati finché un consumatore non li richiede.
  2. Utilizza la libreria Strategie per utilizzare gli elementi delle liste dei risultati della tua funzione in parallelo su più core .

In realtà l'ho fatto con uno dei miei programmi di progetti giocattolo alcune settimane fa . È stato banale parallelizzare il programma: la cosa fondamentale che dovevo fare era, in effetti, aggiungere del codice che diceva "calcola gli elementi di questo elenco in parallelo" (riga 90), e ho ottenuto un aumento del throughput quasi lineare in alcuni dei miei casi di test più costosi.

Il mio programma è più veloce di se fossi andato con le utility di multithreading basate su lock convenzionali? Ne dubito molto. La cosa bella nel mio caso è stata ottenere così tanto da un così piccolo dollaro - il mio codice è probabilmente molto subottimale, ma poiché è così facile da parallelizzare ho avuto una grande accelerazione con molto meno sforzo di una corretta profilazione e ottimizzazione, e nessun rischio di condizioni di gara. E questo, direi, è il modo principale in cui la programmazione funzionale consente di scrivere programmi "più veloci".

    
risposta data 17.02.2016 - 03:35
fonte
2

In Haskell, la modifica è letteralmente impossibile senza ottenere speciali variabili modificabili attraverso una libreria di modifiche. Invece, le funzioni creano le variabili di cui hanno bisogno contemporaneamente ai loro valori (che sono calcolati pigramente), e garbage collection quando non sono più necessari.

Anche quando hai bisogno di variabili di modifica, di solito puoi usare parsimoniosamente, e insieme alle variabili non modificabili. (Un'altra cosa carina in haskell è STM, che sostituisce i blocchi con operazioni atomiche, ma non sono sicuro che sia solo per la programmazione funzionale o meno.) Di solito, solo una parte del programma dovrà essere resa parallela per migliorare le cose prestazioni-saggio.

Questo rende il parallelismo a Haskell molto facile, e in effetti sono in corso degli sforzi per renderlo automatico. Per il codice semplice, il parallelismo e la logica possono anche essere separati.

Inoltre, a causa del fatto che l'ordine di valutazione non è rilevante in Haskell, il compilatore crea solo una coda che deve essere valutata, e li invia a qualsiasi core disponibile, così puoi creare una serie di "thread" che non diventare effettivamente thread fino a quando necessario. L'ordine di valutazione non rilevante è caratteristico della purezza, che di solito richiede una programmazione funzionale.

Ulteriori letture
Parallelismo in Haskell (HaskellWiki)
Concorrente e programmazione multicore in" Real-World Haskell "
Parallel e programmazione simultanea in Haskell di Simon Marlow

    
risposta data 15.02.2016 - 19:37
fonte

Leggi altre domande sui tag