Implementare la memoization in Go

  • Go
  • Gabriele Romanato

La memoization è una tecnica di ottimizzazione che consiste nel memorizzare i risultati di una funzione in una cache, in modo da evitare ricalcoli costosi quando la funzione viene richiamata con gli stessi argomenti. In Go, pur non essendoci una feature di memoization integrata nel linguaggio, è possibile implementarla in modo elegante e sicuro, sia per casi semplici sia in contesti concorrenti.

Che cos'è la memoization

In termini pratici, la memoization trasforma una funzione pura f(x) in una funzione che:

  1. Controlla se il risultato per l'argomento x è già presente in cache.
  2. Se esiste, lo restituisce immediatamente.
  3. Se non esiste, calcola il risultato, lo salva in cache e poi lo restituisce.

Questo approccio è particolarmente efficace quando:

  • La funzione è costosa (ad esempio computazioni matematiche, chiamate I/O, ecc.).
  • La funzione viene chiamata spesso con gli stessi argomenti.
  • La funzione è (sufficientemente) deterministica, ovvero a parità di input restituisce sempre lo stesso output.

Prerequisiti in Go

Per implementare la memoization in Go utilizzeremo tre concetti chiave:

  • Map per rappresentare la cache.
  • Funzioni come valori per creare wrapper riutilizzabili.
  • Meccanismi di sincronizzazione come sync.Mutex per la sicurezza in presenza di goroutine.

Un esempio di base: Fibonacci senza e con memoization

Partiamo da una funzione classica, la sequenza di Fibonacci, implementata in modo ingenuo e poi ottimizzata con memoization.

Versione ingenua (non memorized)


// fibNaive calcola l'ennesimo numero di Fibonacci in modo ricorsivo
// senza alcuna ottimizzazione.
func fibNaive(n int) int {
    if n <= 1 {
        return n
    }
    return fibNaive(n-1) + fibNaive(n-2)
}

Questa implementazione ha una complessità esponenziale, perché ripete moltissimi calcoli uguali.

Versione con memoization manuale

Possiamo introdurre una cache tramite una map[int]int e un semplice wrapper: 


type FibMemo struct {
    cache map[int]int
}

func NewFibMemo() *FibMemo {
    return &FibMemo{
        cache: make(map[int]int),
    }
}

// Fib calcola Fibonacci usando una cache interna.
func (m *FibMemo) Fib(n int) int {
    if n <= 1 {
        return n
    }

    // Controllo in cache
    if val, ok := m.cache[n]; ok {
        return val
    }

    // Calcolo e salvataggio
    result := m.Fib(n-1) + m.Fib(n-2)
    m.cache[n] = result
    return result
}

In questo modo ogni valore di Fib(n) viene calcolato una sola volta. Tuttavia, questa versione non è ancora sicura in presenza di goroutine multiple.

Rendere la memoization thread-safe

Le map di Go non sono thread-safe: se più goroutine scrivono contemporaneamente sulla stessa mappa, si può incorrere in race condition e panic. Per proteggere la cache useremo un sync.RWMutex. 


import "sync"

type FibMemoSafe struct {
    mu    sync.RWMutex
    cache map[int]int
}

func NewFibMemoSafe() *FibMemoSafe {
    return &FibMemoSafe{
        cache: make(map[int]int),
    }
}

func (m *FibMemoSafe) Fib(n int) int {
    if n <= 1 {
        return n
    }

    // Lettura concorrente veloce
    m.mu.RLock()
    val, ok := m.cache[n]
    m.mu.RUnlock()
    if ok {
        return val
    }

    // Calcolo al di fuori del lock di scrittura
    result := m.Fib(n-1) + m.Fib(n-2)

    // Scrittura protetta
    m.mu.Lock()
    m.cache[n] = result
    m.mu.Unlock()

    return result
}

In questo esempio:

  • RLock e RUnlock permettono letture simultanee da parte di più goroutine.
  • Lock e Unlock garantiscono che solo una goroutine alla volta possa scrivere sulla mappa.

Un wrapper generico di memoization (Go 1.18+)

A partire da Go 1.18, possiamo usare i generics per creare un memoizer riutilizzabile per molte funzioni diverse.

Memoization per funzioni con un solo argomento

Supponiamo di avere una funzione del tipo func(K) V. Possiamo creare un wrapper Memoize che restituisce una nuova funzione già dotata di cache interna. 


package memo

import "sync"

// Memoize trasforma una funzione f: K -> V in una versione memoizzata.
// K deve essere comparable perché viene usato come chiave di mappa.
func Memoize[K comparable, V any](f func(K) V) func(K) V {
    var (
        mu    sync.RWMutex
        cache = make(map[K]V)
    )

    return func(k K) V {
        // Tentativo di lettura veloce
        mu.RLock()
        v, ok := cache[k]
        mu.RUnlock()
        if ok {
            return v
        }

        // Calcolo al di fuori del lock di scrittura
        result := f(k)

        // Controllo di nuovo (pattern "double-check") opzionale
        mu.Lock()
        if cached, ok := cache[k]; ok {
            mu.Unlock()
            return cached
        }
        cache[k] = result
        mu.Unlock()

        return result
    }
}

Utilizzo del wrapper generico

Possiamo usare Memoize per qualsiasi funzione con un solo argomento compatibile. 


package main

import (
    "fmt"
    "time"

    "example.com/memo"
)

func slowSquare(n int) int {
    time.Sleep(500 * time.Millisecond) // Simula una computazione costosa
    return n * n
}

func main() {
    memoSquare := memo.Memoize[int, int](slowSquare)

    start := time.Now()
    fmt.Println("Prima chiamata:", memoSquare(42))
    fmt.Println("Durata:", time.Since(start))

    start = time.Now()
    fmt.Println("Seconda chiamata:", memoSquare(42))
    fmt.Println("Durata:", time.Since(start))
}

La seconda chiamata sarà molto più veloce, perché il risultato viene recuperato dalla cache.

Gestire funzioni con più argomenti

Per funzioni con più argomenti, possiamo creare una chiave composta. Un approccio semplice è usare una struct come chiave della mappa. 


type Key2[A comparable, B comparable] struct {
    A A
    B B
}

func Memoize2[A comparable, B comparable, V any](
    f func(A, B) V,
) func(A, B) V {
    var (
        mu    sync.RWMutex
        cache = make(map[Key2[A, B]]V)
    )

    return func(a A, b B) V {
        key := Key2[A, B]{A: a, B: b}

        mu.RLock()
        v, ok := cache[key]
        mu.RUnlock()
        if ok {
            return v
        }

        result := f(a, b)

        mu.Lock()
        if cached, ok := cache[key]; ok {
            mu.Unlock()
            return cached
        }
        cache[key] = result
        mu.Unlock()

        return result
    }
}

Esempio di utilizzo: 


func slowAdd(a, b int) int {
    time.Sleep(200 * time.Millisecond)
    return a + b
}

func main() {
    memoAdd := Memoize2[int, int, int](slowAdd)
    fmt.Println(memoAdd(10, 20)) // Calcolo lento
    fmt.Println(memoAdd(10, 20)) // Lettura da cache
}

Memoization con errori e side effect

Le implementazioni viste finora sono pensate per funzioni pure, cioè senza side effect e senza errori. In molti casi reali, però, le funzioni possono restituire un errore. Possiamo gestire anche questa situazione estendendo il pattern. 


type result[V any] struct {
    value V
    err   error
}

func MemoizeWithError[K comparable, V any](
    f func(K) (V, error),
) func(K) (V, error) {
    var (
        mu    sync.RWMutex
        cache = make(map[K]result[V])
    )

    return func(k K) (V, error) {
        mu.RLock()
        r, ok := cache[k]
        mu.RUnlock()
        if ok {
            return r.value, r.err
        }

        v, err := f(k)

        mu.Lock()
        if cached, ok := cache[k]; ok {
            mu.Unlock()
            return cached.value, cached.err
        }
        cache[k] = result[V]{value: v, err: err}
        mu.Unlock()

        return v, err
    }
}

In questo caso memorizziamo sia il valore sia l'errore. A seconda delle esigenze, si può decidere se:

  • cacheare anche gli errori, come nell'esempio;
  • oppure cacheare solo i successi, evitando di salvare gli errori nella mappa.

Considerazioni sulle prestazioni

La memoization non è sempre la soluzione migliore. Occorre valutare diversi fattori:

  • Memoria: la cache cresce con il numero di input diversi; per domini molto grandi può essere problematico.
  • Frequenza dei cache hit: se gli input sono quasi sempre diversi, il vantaggio sarà minimo o nullo.
  • Contesa sui lock: in contesti altamente concorrenti, i lock possono diventare un collo di bottiglia.

In alcuni scenari può essere utile:

  • Limitare la dimensione della cache (LRU, FIFO, ecc.).
  • Usare tecniche di sharding della cache per ridurre la contesa.
  • Valutare l'uso di pacchetti esterni già ottimizzati, se accettabile per il progetto.

Testare e misurare la memoization

Come sempre in Go, è importante misurare: implementiamo un semplice benchmark per confrontare la versione memoizzata con quella non memoizzata. 


package memo_test

import (
    "testing"
    "time"

    "example.com/memo"
)

func slowDouble(n int) int {
    time.Sleep(10 * time.Millisecond)
    return 2 * n
}

func BenchmarkSlowDouble(b *testing.B) {
    for i := 0; i < b.N; i++ {
        slowDouble(42)
    }
}

func BenchmarkMemoizedDouble(b *testing.B) {
    memoDouble := memo.Memoize[int, int](slowDouble)

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        memoDouble(42)
    }
}

Eseguendo go test -bench=. vedremo il guadagno ottenuto dalla memoization.

Linee guida pratiche

Per usare la memoization in modo efficace in Go, tieni a mente questi punti:

  • Applicala a funzioni deterministiche e ripetute spesso con gli stessi input.
  • Proteggi sempre le cache condivise tra goroutine con meccanismi di sincronizzazione adeguati.
  • Valuta l'uso dei generics per creare wrapper riutilizzabili.
  • Misura le prestazioni prima e dopo per verificare il reale beneficio.
  • Gestisci con attenzione i casi con errori e side effect.

Con questi pattern hai a disposizione una base solida per integrare la memoization nei tuoi progetti Go, migliorando le prestazioni dove serve, senza sacrificare chiarezza e sicurezza del codice.

Torna su