Add a cache to a go function as if it were a static member

user_3867787 0
Viewed 1682

Say I have an expensive function

func veryExpensiveFunction(int) int

and this function gets called a lot for the same number.

Is there a good way to allow this function to store previous results to use if the function gets called again that is perhaps even reusable for veryExpensiveFunction2?

Obviously, it would be possible to add an argument

func veryExpensiveFunctionCached(p int, cache map[int]int) int {
    if val, ok := cache[p]; ok {
        return val
    }
    result := veryExpensiveFunction(p)
    cache[p] = result
    return result
}

But now I have to create the cache somewhere, where I don't care about it. I would rather have it as a "static function member" if this were possible.

What is a good way to simulate a static member cache in go?

go memoization
3 Answers

You can use closures; and let the closure manage the cache.

func InitExpensiveFuncWithCache() func(p int) int {
    var cache = make(map[int]int)
    return func(p int) int {
        if ret, ok := cache[p]; ok {
            fmt.Println("from cache")
            return ret
        }
        // expensive computation
        time.Sleep(1 * time.Second)
        r := p * 2
        cache[p] = r
        return r
    }
}

func main() {
    ExpensiveFuncWithCache := InitExpensiveFuncWithCache()
    
    fmt.Println(ExpensiveFuncWithCache(2))
    fmt.Println(ExpensiveFuncWithCache(2))
}

output:
4
from cache
4

veryExpensiveFunctionCached := InitExpensiveFuncWithCache()

and use the wrapped function with your code. You can try it here.

If you want it to be reusable, change the signature to InitExpensiveFuncWithCache(func(int) int) so it accept a function as a parameter. Wrap it in the closure, replacing the expensive computation part with it.

user_8405820

You need to be careful about synchronization if this cache will be used in http handlers. In Go standard lib, each http request is processed in a dedicated goroutine and at this moment we are at the domain of concurrency and race conditions. I would suggest a RWMutex to ensure data consistency.

As for the cache injection, you may inject it at a function where you create the http handler. Here it is a prototype

type Cache struct {
    store map[int]int
    mux   sync.RWMutex
}

func NewCache() *Cache {
    return &Cache{make(map[int]int), sync.RWMutex{}}
}

func (c *Cache) Set(id, value int) {
    c.mux.Lock()
    c.store[id] = id
    c.mux.Unlock()
}

func (c *Cache) Get(id int) (int, error) {
    c.mux.RLock()
    v, ok := c.store[id]
    c.mux.RUnlock()

    if !ok {
        return -1, errors.New("a value with given key not found")
    }

    return v, nil
}


func handleComplexOperation(c *Cache) http.HandlerFunc {
    return http.HandlerFunc(func(rw http.ResponseWriter, r *http.Request){
        
    })
}
user_50702410

The Go standard library uses the following style for providing "static" functions (e.g. flag.CommandLine) but which leverage underlying state:

// "static" function is just a wrapper
func Lookup(p int) int { return expCache.Lookup(p) }

var expCache = NewCache()

func newCache() *CacheExpensive { return &CacheExpensive{cache: make(map[int]int)} }

type CacheExpensive struct {
    l     sync.RWMutex // lock for concurrent access
    cache map[int]int
}

func (c *CacheExpensive) Lookup(p int) int { /*...*/ }

this design pattern not only allows for simple one-time use, but also allows for segregated usage:

var (
    userX = NewCache()
    userY = NewCache()
)

userX.Lookup(12)
userY.Lookup(42)
user_12185120
Related