The Queue
come scrivere una thRead-safe queue in C, C++ e Go
Earl: Sto portando noci pecan a mia nipote. Fa la peggior torta di noci del mondo! mi dispiace per il marito ma mi dispiace anche per le noci!
Il gioco di parole del titolo di questo post richiama, evidentemente, il gran film The Mule dell’altrettanto grande Clint Eastwood. Lui nel film interpreta un corriere un po’ particolare (un “Drug Mule”), un corriere che deve rispettare norme di sicurezza di trasporto molto strette… Ebbene, anche noi oggi parleremo di trasporto sicuro, trasporteremo dati (roba più tranquilla di quella che trasportava Clint) usando code sicure (thread-safe queues per gli amici).
 |
| ..la sicurezza prima di tutto… |
Le code sicure sono un argomento un po’ convenzionale, quindi come facciamo a renderlo un po’ più frizzante? Semplicissimo: facendo un comparazione di stili e risultati! Quindi presenterò una classica thread-safe queue scritta nel nostro amato C, poi la stessa coda scritta nel nostro (un po’ meno amato) C++, e, dulcis in fundo, la stessa soluzione scritta in Go, che è un linguaggio che uso da un po’ e che trovo fantastico. Quest’ultima comparazione (un po’ OT, devo ammetterlo) l’ho inserita per motivi che spiegherò in fondo all’articolo.
Allora, ovviamente cominciamo con il C, con una implementazione di una coda decisamente classica a cui ho aggiunto un mutex per renderla sicura: vai col codice!
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <pthread.h>
// struct node - struttura di un nodo della coda thread-safe
typedef struct node {
int value;
struct node *next;
} node;
// struct Queue_r - struttura della coda thread-safe (usa una linked list)
typedef struct {
node *front;
node *rear;
pthread_mutex_t mutex;
} Queue_r;
// qcreate() - crea una coda vuota
Queue_r* qcreate()
{
// crea la coda
Queue_r *queue = malloc(sizeof(Queue_r));
// inizializza la coda
queue->front = NULL;
queue->rear = NULL;
pthread_mutex_init(&queue->mutex, NULL);
return queue;
}
// enqueue() - aggiunge un elemento alla coda
void enqueue(Queue_r* queue, int value)
{
// crea un nuovo nodo
node *temp = malloc(sizeof(struct node));
temp->value = value;
temp->next = NULL;
// blocco l'accesso
pthread_mutex_lock(&queue->mutex);
// test se la coda è vuota
if (queue->front == NULL) {
// con la coda vuota front e rear coincidono
queue->front = temp;
queue->rear = temp;
}
else {
// aggiungo un elemento
node *old_rear = queue->rear;
old_rear->next = temp;
queue->rear = temp;
}
// sblocco l'accesso ed esco
pthread_mutex_unlock(&queue->mutex);
}
// dequeue() - toglie un elemento dalla coda
bool dequeue(Queue_r* queue, int *value)
{
// blocco l'accesso
pthread_mutex_lock(&queue->mutex);
// test se la coda è vuota
node *front = queue->front;
if (front == NULL) {
// sblocco l'accesso ed esco
pthread_mutex_unlock(&queue->mutex);
return false;
}
// leggo il valore ed elimino l'elemento dalla coda
*value = front->value;
queue->front = front->next;
free(front);
// sblocco l'accesso ed esco
pthread_mutex_unlock(&queue->mutex);
return true;
}
// main() - funzione main
int main()
{
// creo la coda
Queue_r *my_queue = qcreate();
// aggiungo un po' di elementi
enqueue(my_queue, 10);
enqueue(my_queue, 20);
enqueue(my_queue, 30);
enqueue(my_queue, 40);
// mostro i risultati
printf("la coda my_queue contiene: ");
int qval;
while (dequeue(my_queue, &qval))
printf("%d ", qval);
printf("\n");
return 0;
}
Come avrete notato è un esempio veramente semplice di coda linked list, un oggetto di comprovata funzionalità e efficienza, un vero classico del linguaggio C. Evidentemente il codice presentato è un po’ semplificato, ma neanche tanto: per usarlo in produzione basta aggiungere un po’ di test di controllo (sull’esito delle malloc() e sulla creazione del mutex) con il relativo trattamento degli errori, e poi bisognerebbe scrivere una funzione di cancellazione per liberare tutte le risorse. Poca roba in più, insomma.
Volendo proprio sofisticare il disegno si potrebbe aggiungere una condition variable per gestire in modo più efficiente l’uso in multithreading, ma già così com’è si può usare egregiamente. Il main() è semplicissimo e serve solo a mostrare che le operazioni di queue/dequeue vengono realizzate correttamente.
E passiamo alla versione C++: se l’avessi scritta a C-style sarebbe stata praticamente identica alla versione C (con classi invece di strutture e metodi invece di funzioni), quindi l’operazione sarebbe stata fine a se stessa. Ma perché non si dica che sono prevenuto verso il C++ (ma si, un po’ lo sono), ho deciso di usare la STL, e quindi ho scelto il container più simile all’oggetto di questo articolo, il container std::queue, e ho cercato di renderlo sicuro. Vai col codice!
#include <queue>
#include <mutex>
#include <iostream>
using namespace std;
// classe Queue_r- una classe queue thread-safe (usa std::queue)
class Queue_r {
public:
// metodi per aggiungere/togliere elementi dalla coda
void enqueue(int value);
bool dequeue(int& value);
private:
// oggetto std::queue interno
queue<int> queue_r;
// mutex per controllo accessi
mutex q_mutex;
};
// enqueue() - aggiunge un elemento alla coda
void Queue_r::enqueue(int value)
{
// blocco l'accesso
lock_guard<mutex> lock(q_mutex);
// aggiungo un elemento
queue_r.push(value);
}
// dequeue() - toglie un elemento dalla coda
bool Queue_r::dequeue(int& value)
{
// blocco l'accesso
lock_guard<mutex> lock(q_mutex);
// test se la coda è vuota
if (queue_r.empty()) {
// esco
return false;
}
// assegno il valore e tolgo un elemento
value = queue_r.front();
queue_r.pop();
return true;
}
// main() - funzione main
int main()
{
// creo la coda
Queue_r my_queue;
// aggiungo un po' di elementi
my_queue.enqueue(10);
my_queue.enqueue(20);
my_queue.enqueue(30);
my_queue.enqueue(40);
// mostro i risultati
cout << "la coda my_queue contiene: ";
int value;
while (my_queue.dequeue(value))
std::cout << value << ' ';
std::cout << '\n';
return 0;
}
Codice classico anche in questo caso, e decisamente più compatto della versione C, ma c’era da aspettarselo, visto che molto codice è nascosto dentro std::queue. Notare che ho usato C++11, quindi ho potuto usufruire della nuova interfaccia RAII per usare i mutex, e cioè std::lock_guard (e sul fatto che considero brillante la gestione dei thread del C++11 ne avevo già parlato qui… visto che imparzialità?). Anche in questo caso il codice presentato è quasi definitivo, manca qualche controllo e una (eventuale) condition variable. Il main() di questa versione è praticamente identico a quello della versione C, e quindi anche il risultato dell’esecuzione viene presentato in modo identico.
E i risultati? Ho scritto un piccolo benchmark, e ho testato i risultati facendo un numero esagerato di operazioni di enqueue/dequeue (100000000 di operazioni!), e i risultati sono interessanti, eccoli:
TEST con coda di dimensione 100000000 C queue - TEST con compilazione gcc senza ottimizzazioni Test: Tempo trascorso: 7.671992 secondi C++ queue - TEST con compilazione g++ senza ottimizzazioni Test: Tempo trascorso: 12.378136 secondi C queue - TEST con compilazione gcc con ottimizzazione -O2 Test: Tempo trascorso: 6.349089 secondi C++ queue - TEST con compilazione g++ con ottimizzazione -O2 Test: Tempo trascorso: 1.405633 secondi
Come si nota la versione C è, di base, più veloce di quella C++, ma con le ottimizzazioni il risultato si ribalta. Quindi pare che std::queue sia un ottimo container, di uso molto raccomandabile (specialmente se si possono abilitare le ottimizzazioni). Si può concludere che in C si deve, per forza, seguire una via come quella indicata, mentre in C++ si può optare per lavorare con l’aiuto della STL o seguire un approccio C-style (scelta filosofica).
E ora, visto che quando il gioco si fa duro i duri cominciano a giocare, veniamo alla parte più interessante: ho scritto una versione Go della thread-safe queue, per verificare compattezza di codice e risultati. Come mi aspettavo il codice Go risultante è veramente tirato all’osso, perché Go è un vero linguaggio di alto livello (nella concezione moderna della definizione, in quella antica anche C e C++ lo erano). Vediamo il codice!
package main
import "fmt"
// enqueue() - aggiunge un elemento alla coda
func enqueue(queue chan int, value int) {
// uso select per non rendere bloccanti le operazioni
select {
case queue <- value:
default:
}
}
// dequeue() - toglie un elemento dalla coda
func dequeue(queue chan int, value* int) bool {
// uso select per non rendere bloccanti le operazioni
select {
case *value = <- queue:
return true
default:
return false
}
}
// main() - funzione main
func main() {
// creo la coda
my_queue := make(chan int, 100000000)
// aggiungo un po' di elementi
enqueue(my_queue, 10)
enqueue(my_queue, 20)
enqueue(my_queue, 30)
enqueue(my_queue, 40)
// mostro i risultati
fmt.Printf("la coda my_queue contiene: ")
qval := 0
for dequeue(my_queue, &qval) {
fmt.Printf("%d ", qval);
}
fmt.Printf("\n")
}
Visto che il Go appartiene alla grande famiglia del C, il codice (almeno in questo semplice esempio) non dovrebbe risultare molto ostico anche per i lettori che non conoscono il Go. Tanto per cominciare il main() è praticamente identico a quello delle versioni C e C++, mentre le funzioni di enqueue e dequeue sono… sono fantastiche, visto che sono praticamente vuote! Infatti il concetto di queue thread-safe è praticamente già implicito nel linguaggio, attraverso i canali chan, che sono (anche) uno strumento di gestione della concorrenza, quindi sono thread-safe per definizione.
Ovviamente le code thread-safe si possono realizzare in Go anche in altre maniere, magari più “classiche” (usando liste e mutex, per esempio, e probabilmente è la soluzione migliore come prestazioni), ma la implementazione che ho proposto è così immediata che non si può evitare di prenderla in considerazione.
L’unico limite è che questo tipo di coda ha una dimensione finita, infatti nel main() viene inizializzata a 100000000 di elementi (ho esagerato, ma solo per dimostrare che la dimensione è “finita” ma può essere quasi “infinita” senza problemi). In realtà una coda thread-safe di solito si usa come mezzo di comunicazione tra thread, usando la logica del produttore/consumatore, quindi la dimensione conta fino a un certo punto: si suppone che se la coda ha una dimensione ragionevole non dovrebbe riempirsi mai, e se si riempie vuol dire che i consumatori si sono fermati e/o che i produttori producono troppo, quindi il programma in esecuzione ha ben altri problemi che la dimensione della coda...
A questo punto il dubbio è: Go è un vero linguaggio di alto livello e ha un suo runtime che lo isola dal sistema operativo, quindi le prestazioni saranno penalizzate, no? Guardate e stupite:
TEST con coda di dimensione 100000000 Go queue - TEST con compilazione Go di default Test: Tempo trascorso: 8.772547848 secondi
è perfino più veloce della versione C++ non ottimizzata! Comunque, se può interessare, ho visto e realizzato vari benchmark e posso confermare la conoscenza comune: Go è un linguaggio veloce. È sicuramente più lento di C, C++ e Rust (che è velocissimo), ma si difende bene, quindi ha un range di utilizzazione veramente notevole. Usatelo, non ve ne pentirete.
E ora, per finire, qualche considerazione filosofica (e se qualcuno odia le mie disquisizioni filosofiche può anche saltare la lettura, me ne farò una ragione). Comincerò con una nota un po’ OT: il C ha vinto (e non è la prima volta) il titolo di “Programming Language of the Year” di TIOBE per il 2019, un risultato di un certo prestigio. Considerando che è un linguaggio che ha una certa età (é del 1972) è la dimostrazione che la qualità paga, anche a lungo termine. Tra l’altro è il primo o secondo linguaggio più usato degli ultimi 20 anni (C e Java si alternano ogni anno al primo posto). Il fatto è che il C è un linguaggio insostituibile in alcuni tipi di applicazioni: Sistemi Operativi (chiedere un parere a Linus…), Software di Sistema, Firmware di basso livello (senza OS o con OS minimale, tipo FreeRTOS). E il C++? Beh, se si limitasse al suo ruolo nativo, quello di C a oggetti, sarebbe (ed è) una buonissima alternativa al C, almeno quando si vuole scrivere in OOP (anche se, secondo il grande Alan Kay, non è un vero linguaggio OOP). Il problema è che vuol darsi le arie da “linguaggio ad alto livello”… e poi usi il Go e scopri che cosa è un vero linguaggio ad alto livello. Ma niente paura, nonostante gli interventi dei Comitati ISO, il core del C++ rimane sempre lo stesso (inclusa la quasi-compatibilità con il C), quindi si può ancora usare solo per quello che è: un buonissimo C a oggetti.
E visto che con queste ultime note mi sono guadagnato le critiche di un notevole gruppo di colleghi, per oggi mi posso considerare soddisfatto…
Ciao, e al prossimo post!
