I compilatori come Javac rilevano automaticamente le pure funzioni e le parallelizzano?

12

Si sa che le funzioni pure facilitano il parellelizing. Che cos'è riguarda la programmazione funzionale che la rende intrinsecamente adatta all'esecuzione parallela?

I compilatori come Javac sono abbastanza intelligenti da rilevare quando un metodo è una funzione pura? È sempre possibile implementare classi che implementano interfacce funzionali come Funzione ,  ma hanno effetti collaterali.

    
posta Naveen 09.07.2017 - 09:06
fonte

2 risposte

33

are compilers such as Javac smart enough to detect when a method is a pure function.

Non è una questione di "abbastanza intelligente". Si chiama Purity Analysis ed è dimostrabilmente impossibile nel caso generale: equivale a risolvere il problema di interruzione.

Ora, naturalmente, gli ottimizzatori fanno sempre cose impossibili, "nel complesso in generale è impossibile" non significa che non funzioni mai, significa solo che non può funzionare in tutti i casi. Quindi, ci sono in effetti algoritmi per verificare se una funzione è pura o no, è solo che molto spesso il risultato sarà "Non so", il che significa che per ragioni di sicurezza e correttezza, è necessario assumere che questa particolare funzione potrebbe essere impura.

E anche nei casi in cui fa funzionano, gli algoritmi sono complessi e costosi.

Quindi, questo è Problema 1: funziona solo per casi speciali .

Problema # 2: librerie . Perché una funzione sia pura, può sempre e solo chiamare funzioni pure (e quelle funzioni possono solo chiamare pure funzioni, e così via e così via). Javac ovviamente sa solo di Java e conosce solo il codice che può vedere. Quindi, se la tua funzione chiama una funzione in un'altra unità di compilazione, non puoi sapere se è pura o meno. Se chiama una funzione scritta in un'altra lingua, non puoi saperlo. Se chiama una funzione in una libreria che potrebbe non essere ancora installata, non puoi sapere. E così via.

Funziona solo quando si ha un'analisi dell'intero programma, quando l'intero programma è scritto nella stessa lingua e tutto viene compilato contemporaneamente in una volta sola. Non puoi usare alcuna libreria.

Problema # 3: pianificazione . Una volta che hai capito quali parti sono puri, devi ancora programmarle per separare i thread. O no. L'avvio e l'interruzione dei thread sono molto costosi (specialmente in Java). Anche se si mantiene un pool di thread e non si avvia o non si arresta, il cambio di contesto del thread è anche costoso. Devi essere sicuro che il calcolo verrà eseguito molto più a lungo del tempo necessario per pianificare e cambiare contesto, altrimenti perderai perderà , non per guadagnarlo.

Come probabilmente intuisci ora, capire quanto tempo impiegherà un calcolo è probabilmente impossibile nel caso generale (non riusciamo nemmeno a capire se ci vorrà un tempo limitato, per non parlare di quanto tempo) e duro e costoso anche nel caso speciale.

A parte: Javac e ottimizzazioni . Nota che la maggior parte delle implementazioni di javac in realtà non eseguono molte ottimizzazioni. L'implementazione di Oracle di javac, ad esempio, si basa sul motore di esecuzione sottostante per eseguire le ottimizzazioni . Questo porta ad un altro insieme di problemi: ad esempio, javac ha deciso che una particolare funzione è pura ed è abbastanza costosa, e quindi la compila per essere eseguita su un thread diverso. Quindi, l'ottimizzatore della piattaforma (ad esempio, il compilatore JIT HotSpot C2) arriva e ottimizza l'intera funzione. Ora hai una discussione vuota che non fa nulla. Oppure, immagina, ancora una volta, javac decida di programmare una funzione su un thread diverso, e lo ottimizzatore della piattaforma potrebbe ottimizzarlo completamente, tranne che non può eseguire l'inlining attraverso i limiti del thread e quindi una funzione che potrebbe essere ottimizzato via completamente è ora inutilmente eseguito.

Quindi, fare qualcosa del genere ha davvero senso se si ha un singolo compilatore che esegue la maggior parte delle ottimizzazioni in una volta sola, in modo che il compilatore sappia e possa sfruttare tutte le diverse ottimizzazioni a diversi livelli e le loro interazioni reciproche .

Si noti che, per esempio, il compilatore JIT HotSpot C2 fa esegue un auto-vettorizzazione, che è anche una forma di auto-parallelizzazione.

    
risposta data 09.07.2017 - 11:31
fonte
5

La risposta di upvoted non è riuscita a notare una cosa. La comunicazione sincrona tra thread è estremamente costosa. Se la funzione è in grado di essere eseguita a una velocità di molti milioni di chiamate al secondo, in realtà ti fa più male parallelizzarla piuttosto che lasciarla così com'è.

La forma più veloce di comunicazione sincrona inter-thread, che utilizza loop occupati con variabili atomiche, è sfortunatamente inefficiente dal punto di vista energetico. Se devi ricorrere all'utilizzo di variabili di condizione per risparmiare energia, le prestazioni della tua comunicazione inter-thread soffre.

Quindi, il compilatore non ha solo bisogno di determinare se una funzione è pura, ma dovrebbe anche stimare il tempo di esecuzione della funzione per vedere se la parallelizzazione è una vittoria netta. Inoltre, dovrebbe scegliere tra loop occupati utilizzando variabili atomiche o variabili di condizione. E avrebbe bisogno di creare discussioni dietro la schiena.

Se si creano i thread dinamicamente, è ancora più lento rispetto all'utilizzo di variabili di condizione. Quindi, il compilatore avrebbe bisogno di impostare un certo numero di thread già in esecuzione.

Quindi, la risposta alla tua domanda è no , i compilatori non sono abbastanza "intelligenti" per auto-parallelizzare le funzioni pure, specialmente nel mondo Java. Sono intelligenti non auto-parallelizzandoli!

    
risposta data 09.07.2017 - 14:29
fonte

Leggi altre domande sui tag