Go Fibonacci!

Sommario

Creeremo un programma per la generazione dei numeri di Fibonacci per poi entrare nel campo dell’esecuzione concorrente in Go.

Fibonacci

La sequenza di Fibonacci si genera sommando i precendenti due numeri della serie. Questa regola necessita di definire i primi due numeri e questi sono semplicemente assunti pari a 0 ed 1.
In Go il calcolo dell’ennesimo numero della sequenza può essere ottenuto con il codice seguente sfruttando direttamente la definizione della serie e l’assegnazione multipla (linea 8) tra l’altro disponibile anche nei linguaggi Lua e Python:

package main

// trova l'ennesimo numero della serie
// di Fibonacci
func fibonacci(n int) int {
    var a, b int = 0, 1
    for i := 0; i < n-1; i++ {
        a, b = b, a+b
    }
    return a
}

func main() {
    for i := 1; i < 10; i++ {
        print(fibonacci(i), " ")
    }
    println()
}

Calcoli indipendenti

Il supporto alla programmazione concorrente del Go è probabilmente — in un mondo multiprocessore — la principale caratteristica per la sua diffusione, e pensare che nel linguaggio vi sono pochissimi costrutti sintattici per implementarla (caso mai la semplicità fosse un vantaggio).
Li abbiamo visti già tutti all’opera su Ok, panico!, grazie ai post di Juhan ;-).

Come forse avrete intuito, proveremo a calcolare molti numeri di Fibonacci in modo indipendente. Questa parola è importante perché la programmazione concorrente non è altro che un insieme di esecuzioni che si svolgono indipendentemente una dall’altra — come sottolinea Robert Pike. La distinzione è dovuta al fatto che ci si può sbagliare usando per questa modalità di esecuzione il termine parallelismo, che invece indica un insieme di esecuzioni che avvengono contemporamente. Nei moderni pc multicore, l’esecuzione concorrente può avvicinarsi al parallelismo.

Fibonacci independente

Un semplice schema per l’esecuzione concorrente di più funzioni di Fibonacci, è quello di avviarne l’esecuzione in una goroutine ed attenderne in quella principale i risultati provenienti da un canale.

Ecco il codice in cui si deve intendere che la funzione mancante fibonacci() sia quella del listato precedente:

func fibonacci(n int) int64 {
    // as before with int64 return value
}

var num = []int{50, 36, 80, 93, 66}

func main() {
    ans := make(chan int, len(num)) // buffered channel
    for _, f := range num {
        go func(f int) {
            ans <- fibonacci(f)
        }(f)
    }
    
    // stampo i risultati provenienti dal canale
    for i := 0; i < len(num); i++ {
        fib := <-ans
        fmt.Printf("Fibonacci(%d)=%d\n", num[i], fib)
    }
}

Nella funzione main() dopo aver creato un canale, avviamo tante goroutine quanti sono i numeri della serie da calcolare iterando sugli elementi di uno slice (num). Al termine del ciclo avremo nel nostro caso 5 goroutine in esecuzione indipendente da quella principale.
La prima diversità dalla programmazione classica è che l’istruzione go avvia una nuova linea di esecuzione senza attendere che questa termini. Quasi immediatamente raggiungiamo quindi il secondo ciclo for che preleva in sequenza i dati dal canale.

Questo schema è piuttosto semplice. Non conosciamo l’ordine con cui i dati arrivano e dobbiamo ricordarci che l’istruzione

        fib := <-ans

comporta il blocco dell’esecuzione della goroutine principale (quella in cui gira la funzione main()), che attende fino all’arrivo di un dato, assicurandoci che vengano attesi cinque valori dal canale altrimenti la funzione main() terminerà prima che le goroutine di calcolo abbiano portato a termine il lavoro.
La goroutine infatti non sanno niente di quello che stanno facendo le altre eventuali goroutine in esecuzione e se main() termina, termineranno forzatamente tutte.
Dal punto di vista della singola goroutine al termine del calcolo l’invio sul canale del risultato è immediato, essendo questo dotato di capacità pari al numero dei risultati che vi saranno inviati (buffered channel), altrimenti essa avrebbe dovuto attendere che la gorountine main() fosse pronta a ricevere un dato (sincronizzazione del mandante con il ricevente).

Per capire la concorrenza in Go conviene quindi immaginare il funzionamento delle cose in modo dinamico tenendo conto del blocco o meno dell’invio o della ricezione dei dati dai canali.

Prestazioni

Ho fatto alcune prove variando la quantità dei numeri da calcolare. Sulla mia macchina Linux dotata di un processore con un unico core, le prestazioni migliorano solo di alcuni punti percentuali, ed addirittura peggiorano quando crescono i numeri da calcolare in num.
Evidentemente il costo per la creazione delle goroutine — sia pure piccolo — non è compensato su una macchina ad un unico core da vantaggi particolari.
Oltre a capire sperimentando il codice, quello che importa adesso non sono le prestazioni ma che occorre considerare con precisione la natura del problema per poter scegliere o meno una soluzione a calcolo indipentente.

Si tratta di un argomento affascinante!

Difetto

Il codice precedente ha un difetto: è necessario attendere che tutte le goroutine siano state create e lanciate prima di passare a raccogliere i risultati. Per esempio se per creare una goroutine accorresse 1 millisecondo e ciascuna mediamente richiedesse 50ms di esecuzione concorrente, allora i risultati dovrebbero attendere stipati nel canale se le goroutine fossero circa più di 50.

La soluzione è quella di inserire il ciclo di creazione delle goroutine esso stesso all’interno di una goroutine:

func main() {
    // Use all the machine's cores
    runtime.GOMAXPROCS(runtime.NumCPU()) 
    res := make(chan int64)
    
    go func() {
        for _, f := range num {
            go func(f int) {
                res <- fibonacci(f)
            }(f)
        }
    }()
    
    for i := 0; i < len(num); i++ {
        <-res
    }
}

Altro simpatico esempio elegante

Questa volta spediamo sul canale la serie di Fibonacci da una goroutine separata basata su un ciclo for infinito (a terminare il programma sarà brutalmente il termine della funzione main() nella quale chiederemo la stampa dei primi dieci numeri della serie):

package main

import "fmt"

func main() {
    ch := make(chan int)
    go func(a1, a2 int) {
        for {
            ch <- a1
            a1, a2 = a2, a1 + a2
        }
    }(0, 1)
    
    for i := 0; i<10; i++ {
        fmt.Print(<- ch, " ")
    }
    fmt.Println()
}

Sfida…

Invito i visitatori del blog a presentare nuovi schemi di calcolo concorrente o semplicemente solo i risultati ottenuti con i vostri megacalcolatori.

Quello che serve è una installazione di Go, e magari sapere che esistono comode funzioni nel pacchetto time che misurano con precisione il tempo macchina, come nel seguente esempio:

package main

import (
    "fmt"
    "math"
    "time"
)

func main() {
    multiPi := make([]float64, 10000)
    t := time.Now()
    for i := 0; i < 10000; i++ {
        multiPi[i] = math.Pi * float64(i)
    }
    fmt.Printf("Executin time: %v\n", time.Since(t))
}

Un saluto.
R.

Posta un commento o usa questo indirizzo per il trackback.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: