Concorrenza e parallelismo in Elixir

Questa è la seconda parte della serie di Percy Grunwald su Elixir. Non perderti il primo articolo su Unicode matching in Elixir.

Gli esercizi su Exercism sono piccoli, sintetici e spesso apparentemente banali. È facile immaginare che chi ha già esperienza non abbia nulla da imparare da loro. Tuttavia, risolvere questi problemi sintetici può spingerti a imparare e applicare parti del tuo linguaggio che potresti non aver mai esplorato. Queste nuove conoscenze possono portarti a risolvere problemi del mondo reale in modo più efficiente o più espressivo.

Frequenza delle lettere in parallelo è un esercizio di difficoltà media sul percorso Elixir di Exercism che racchiude un numero sorprendente di lezioni interessanti. Per risolvere questo problema con successo, la soluzione dovrebbe essere eseguita in parallelo su più processi worker. Raggiungere un vero parallelismo in Elixir è sorprendentemente facile rispetto ad altri linguaggi, ma se non hai mai scritto codice concorrente in Elixir può sembrare un po' scoraggiante. Una delle cose che scoprirai risolvendo questo esercizio è quanto Elixir renda facile scrivere codice in grado di essere eseguito in modo concorrente o parallelo. Applicare queste competenze al codice può avere un impatto significativo sulle prestazioni delle applicazioni.

Questo esercizio ti chiede di implementare una funzione, Frequency.frequency/2, che determina la frequenza delle lettere in un array di stringhe. Il calcolo dovrebbe essere eseguito in diversi processi worker, il cui numero è stabilito dall'argomento workers:

iex> Frequency.frequency(["Freude", "schöner", "Götterfunken"], workers)
%{
  "c" => 1,
  "d" => 1,
  "e" => 5,
  ...
  "ö" => 2
}

In questo articolo esploreremo la concorrenza in Elixir rendendo concorrente una soluzione sequenziale funzionante a questo esercizio. Prima di tuffarci nel codice, però, prendiamoci un momento per capire cosa significano davvero «concorrenza» e «parallelismo», e come ottenere entrambi in Elixir rispetto ad altri linguaggi.

Concorrenza e parallelismo

Concorrenza e parallelismo sono termini correlati, ma non significano esattamente la stessa cosa. Un programma concorrente è quello in cui più attività possono essere «in corso», ma in un dato istante solo un'attività alla volta viene eseguita sulla CPU (ad esempio, eseguire un'attività mentre un'altra è in attesa di I/O, come una lettura o una scrittura su disco o sulla rete). Un programma parallelo, invece, è in grado di eseguire più attività allo stesso tempo su più core della CPU.

Sia l'esecuzione concorrente sia quella parallela possono dare aumenti di velocità significativi, ma quanto guadagno sia possibile, ammesso che ce ne sia, dipende da molti fattori. Ci sono casi in cui la concorrenza o il parallelismo non sono nemmeno possibili: può darsi che il compito che stai cercando di portare a termine non si presti a un'esecuzione concorrente o parallela, oppure che il runtime non li supporti. Se il tuo caso consente davvero un'esecuzione concorrente o parallela, l'entità dell'aumento di velocità possibile dipende in gran parte dal fatto che il compito sia vincolato dall'I/O o dalla CPU, e se sia disponibile più di 1 core della CPU.

Nonostante il numero di fattori in gioco, esistono alcune «regole empiriche» per stabilire se la concorrenza o il parallelismo siano possibili e quanto aumento di velocità aspettarsi. In primo luogo, l'esecuzione concorrente è possibile su un singolo core della CPU, ma quella parallela no. In secondo luogo, il parallelismo e la concorrenza dovrebbero dare un aumento di velocità significativo ai compiti vincolati dall'I/O, e l'aumento dovrebbe essere, in teoria, lo stesso per entrambi. Infine, i compiti vincolati dalla CPU dovrebbero avere le stesse prestazioni (o peggiori) se eseguiti in modo concorrente, e in genere aumenti di velocità sono possibili solo se eseguiti in parallelo su più core della CPU.

Il calcolo della frequenza delle lettere in questo esercizio è un esempio di compito vincolato dalla CPU, quindi, secondo le regole empiriche appena viste, un aumento di velocità dovrebbe essere possibile solo eseguendo il calcolo in parallelo su più core della CPU.

Concorrenza e parallelismo in Elixir rispetto ad altri linguaggi

Molti linguaggi popolari ti offrono strumenti per scrivere codice concorrente, ma ottenere il parallelismo è di solito molto più complesso e pieno di compromessi.

Per esempio, la concorrenza è un cittadino di prima classe in JavaScript in esecuzione sul runtime Node.js, e le versioni predefinite delle funzioni legate all'I/O sono quasi sempre «asincrone» (cioè concorrenti). fs.ReadFile, per dirne una, è una funzione concorrente ed è il modo standard per leggere il contenuto di un file. È un'ottima cosa, ma ha anche i suoi lati negativi, sotto forma di callback hell o della necessità di ricorrere a Promise. Inoltre, dato che Node non distribuisce il tempo della CPU in modo uniforme tra le attività, è comunque possibile bloccare l'esecuzione con un singolo compito che impegna molto la CPU. Parallelizzare l'esecuzione in Node è possibile, ma di certo non facile. Dato che Node è single-threaded, l'unico modo per ottenere il parallelismo è creare manualmente processi worker con il modulo cluster, oppure eseguire più istanze del programma e implementare manualmente la comunicazione tra loro.

Python, a differenza di Node, non è concorrente per impostazione predefinita, ma offre diversi strumenti per scrivere codice concorrente e parallelo. Tuttavia ogni opzione ha i suoi compromessi, e sceglierne una non è necessariamente semplice. Potresti usare il modulo threading e fare i conti con il fatto che il global interpreter lock (GIL) limita l'esecuzione a un solo thread alla volta, rendendo impossibile il parallelismo. L'altra opzione è il modulo multiprocessing di Python, che aggira il limite del GIL generando processi del sistema operativo (anziché thread). Usare multiprocessing rende possibile il parallelismo, ma ha il rovescio della medaglia che i processi del sistema operativo sono più lenti da avviare e consumano più memoria dei thread.

Scrivere codice concorrente e parallelo in Elixir è molto più semplice, perché Elixir è concorrente a livello di runtime. La reputazione di Elixir per la scalabilità di massa deriva dal fatto che gira sulla macchina virtuale BEAM, che esegue tutto il codice all'interno di «processi» estremamente leggeri, tutti eseguiti in modo concorrente dentro la VM. I processi BEAM hanno un costo di avvio trascurabile e consumano una quantità minima di memoria rispetto ai thread e ai processi a livello di sistema operativo generati dai moduli di concorrenza di Python. Inoltre, a differenza dell'event loop di Node, la VM BEAM ha degli scheduler che allocano a tutti i processi il tempo di CPU disponibile, il che garantisce che un singolo compito che impegna molto la CPU non possa bloccare l'esecuzione degli altri processi.

Grazie a questa architettura, passare dall'esecuzione concorrente dei processi a quella parallela è solo una questione di aggiungere più core della CPU. Da molti anni ormai, infatti, BEAM attiva automaticamente le capacità di Symmetric Multiprocessing (SMP) sui sistemi multi-core, il che permette agli scheduler della VM di allocare ai processi in esecuzione il tempo di CPU di tutti i core. In Elixir, la concorrenza non è solo un cittadino di prima classe: non c'è alcuna distinzione tra codice concorrente e codice parallelo. Tutto quello che devi fare è scrivere codice concorrente, e la VM lo parallelizzerà automaticamente e per impostazione predefinita se è disponibile più di 1 core della CPU.

Scrivere codice Elixir concorrente con il modulo Task

Come accennato sopra, in Elixir la concorrenza si ottiene distribuendo le operazioni su più processi BEAM. Puoi generare processi con estrema facilità usando funzioni come Kernel.spawn_link/1, ma faresti molto meglio a usare le straordinarie astrazioni offerte dal modulo Task:

L'uso più comune di [Task] è convertire codice sequenziale in codice concorrente calcolando un valore in modo asincrono.

Il modulo Task ti permette di scrivere codice concorrente incredibilmente pulito in Elixir: niente callback hell e nessun bisogno di Promises.

Per questo esercizio, Task.async_stream/3 è un'ottima opzione:

async_stream(enumerable, function, options \\ [])

Task.async_stream/3 restituisce uno stream che esegue la function data in modo concorrente su ogni elemento di enumerable. Per impostazione predefinita, il numero di processi generati (i worker) è uguale al numero di elementi in enumerable. Questo ci offre un modo immediato per controllare il livello di parallelismo tramite l'argomento workers (ammesso che abbiamo abbastanza core della CPU). Dobbiamo solo suddividere l'elenco delle lettere nel numero corretto di porzioni e usare Task.async_stream/3 per elaborare ogni porzione in un worker separato.

Rendere concorrente la funzione sequenziale di frequenza delle lettere

Partiamo da un'implementazione sequenziale funzionante, tratta dalla mia soluzione:

def frequency(texts, _workers) do
  texts
  |> get_all_graphemes()
  |> count_letters()
end

defp get_all_graphemes(texts) do
  texts
  |> Enum.join()
  |> String.graphemes()
end

defp count_letters(graphemes) do
  Enum.reduce(graphemes, %{}, fn grapheme, acc ->
    if String.match?(grapheme, ~r/^\p{L}$/u) do
      downcased_letter = String.downcase(grapheme)
      Map.update(acc, downcased_letter, 1, fn count -> count + 1 end)
    else
      acc
    end
  end)
end

Possiamo rendere concorrente l'implementazione qui sopra procedendo in questo modo:

1. Suddividere l'elenco dei grafemi restituito da get_all_graphemes/1 in un numero di porzioni pari al numero di workers
2. Elaborare ogni porzione con count_letters/1 in un worker usando Task.async_stream/3
3. Unire i risultati di ogni worker in un unico risultato

Ecco uno schema dei passaggi appena descritti:

Per abilitare la logica concorrente dobbiamo implementare solo 2 nuove funzioni ausiliarie: una per suddividere i grafemi in porzioni (split_into_chunks/2) e una per unire lo stream di risultati provenienti dai worker (merge_results/1). Ecco un modo per implementare queste funzioni ausiliarie:

defp split_into_chunks(all_graphemes, num_chunks) do
  all_graphemes_count = Enum.count(all_graphemes)
  graphemes_per_chunk = :erlang.ceil(all_graphemes_count / num_chunks)

  Enum.chunk_every(all_graphemes, graphemes_per_chunk)
end

defp merge_results_stream(results_stream) do
  Enum.reduce(results_stream, %{}, fn {:ok, worker_result}, acc ->
    Map.merge(acc, worker_result, fn _key, acc_val, worker_val ->
      acc_val + worker_val
    end)
  end)
end

Una volta implementate queste 2 funzioni, per far girare in modo concorrente la funzione frequency/2 non resta che aggiungere le chiamate alle nuove funzioni ausiliarie e sostituire la chiamata diretta a count_letters/1 con Task.async_stream/3:

def frequency(texts, workers) do
  texts
  |> get_all_graphemes()
  |> split_into_chunks(workers)
  |> Task.async_stream(&count_letters/1)
  |> merge_results_stream()
end

La funzione qui sopra è un'implementazione concorrente perfettamente funzionante e supera tutti i test. Pur essendo concorrente, il codice si legge esattamente come normale codice sequenziale, il che dimostra la potenza delle astrazioni offerte da Task.

La versione concorrente è davvero parallela?

Come ho accennato prima nell'articolo, in Elixir non c'è alcuna distinzione tra codice concorrente e codice parallelo. Se impostiamo workers su un numero maggiore di 1 e abbiamo più di 1 core della CPU disponibile, la VM BEAM parallelizza automaticamente l'esecuzione dei processi generati.

Per impostazione predefinita, BEAM avvia uno scheduler per ogni core della CPU (logico) disponibile. Puoi controllare il numero di scheduler avviati da BEAM con :erlang.system_info/1:

iex> :erlang.system_info(:schedulers_online)
8

Questo rappresenta il numero massimo di processi della VM che possono essere in esecuzione contemporaneamente. Impostare workers su un numero maggiore del numero di scheduler non aumenta il parallelismo e può danneggiare le prestazioni.

Conclusione

Convertire il codice da sequenziale a concorrente si rivela molto più facile del previsto usando il modulo Task di Elixir. Il codice concorrente aggiunge un po' di complessità in più nella suddivisione dell'elenco dei grafemi e nella combinazione dei risultati dei worker, ma il risultato finale è sorprendentemente pulito.

Prima di risolvere questo problema di Exercism avevo sentito parlare di Task, ma non l'avevo mai usato. Dopo averlo applicato nella mia soluzione, oggi lo considererei una parte indispensabile della mia cassetta degli attrezzi per Elixir.

Potresti usare questo nuovo strumento in molti modi per provare a ottimizzare le prestazioni delle applicazioni. La maggior parte delle applicazioni web è vincolata dall'I/O e quindi trarrebbe beneficio dalla concorrenza anche se è disponibile un solo core della CPU. Un modo abbastanza affidabile per velocizzare un'applicazione web è eseguire le richieste HTTP in modo concorrente:

def call_apis_async() do
  ["https://api.example.com/users/123", ...]
  |> Task.async_stream(&HTTPoison.get/1)
  |> Enum.into([], fn {:ok, res} -> res end)
end

Il codice qui sopra usa Task.async_stream/3 per chiamare tutte le URL dell'elenco in modo concorrente, invece di aspettare che ogni richiesta termini prima di avviare la successiva, il che dovrebbe dare un aumento di velocità significativo a seconda della durata di ciascuna richiesta.