memoize

Documentation

Overview

Package memoize defines a "promise" abstraction that enables memoization of the result of calling an expensive but idempotent function.

Call p = NewPromise(f) to obtain a promise for the future result of calling f(), and call p.Get() to obtain that result. All calls to p.Get return the result of a single call of f(). Get blocks if the function has not finished (or started).

A Store is a map of arbitrary keys to promises. Use Store.Promise to create a promise in the store. All calls to Handle(k) return the same promise as long as it is in the store. These promises are reference-counted and must be explicitly released. Once the last reference is released, the promise is removed from the store.

Index

• type EvictionPolicy
• type Function
• type Promise
  • func NewPromise(debug string, function Function) *Promise
  • func (p *Promise) Cached() interface{}
  • func (p *Promise) Get(ctx context.Context, arg interface{}) (interface{}, error)
• type RefCounted
• type Store
  • func NewStore(policy EvictionPolicy) *Store
  • func (s *Store) DebugOnlyIterate(f func(k, v interface{}))
  • func (store *Store) Promise(key interface{}, function Function) (*Promise, func())
  • func (s *Store) Stats() map[reflect.Type]int

Types

type EvictionPolicy

type EvictionPolicy int

An EvictionPolicy controls the eviction behavior of keys in a Store when they no longer have any references.

const (
	// ImmediatelyEvict evicts keys as soon as they no longer have references.
	ImmediatelyEvict EvictionPolicy = iota

	// NeverEvict does not evict keys.
	NeverEvict
)

type Function

type Function func(ctx context.Context, arg interface{}) interface{}

Function is the type of a function that can be memoized.

If the arg is a RefCounted, its Acquire/Release operations are called.

The argument must not materially affect the result of the function in ways that are not captured by the promise's key, since if Promise.Get is called twice concurrently, with the same (implicit) key but different arguments, the Function is called only once but its result must be suitable for both callers.

The main purpose of the argument is to avoid the Function closure needing to retain large objects (in practice: the snapshot) in memory that can be supplied at call time by any caller.

type Promise

type Promise struct {
	// contains filtered or unexported fields
}

A Promise represents the future result of a call to a function.

func NewPromise

func NewPromise(debug string, function Function) *Promise

NewPromise returns a promise for the future result of calling the specified function.

The debug string is used to classify promises in logs and metrics. It should be drawn from a small set.

func (*Promise) Cached

func (p *Promise) Cached() interface{}

Cached returns the value associated with a promise.

It will never cause the value to be generated. It will return the cached value, if present.

func (*Promise) Get

func (p *Promise) Get(ctx context.Context, arg interface{}) (interface{}, error)

Get returns the value associated with a promise.

All calls to Promise.Get on a given promise return the same result but the function is called (to completion) at most once.

If the value is not yet ready, the underlying function will be invoked.

If ctx is cancelled, Get returns (nil, Canceled). If all concurrent calls to Get are cancelled, the context provided to the function is cancelled. A later call to Get may attempt to call the function again.

type RefCounted

type RefCounted interface {
	// Acquire prevents the value from being destroyed until the
	// returned function is called.
	Acquire() func()
}

A RefCounted is a value whose functional lifetime is determined by reference counting.

Its Acquire method is called before the Function is invoked, and the corresponding release is called when the Function returns. Usually both events happen within a single call to Get, so Get would be fine with a "borrowed" reference, but if the context is cancelled, Get may return before the Function is complete, causing the argument to escape, and potential premature destruction of the value. For a reference-counted type, this requires a pair of increment/decrement operations to extend its life.

type Store

type Store struct {
	// contains filtered or unexported fields
}

A Store maps arbitrary keys to reference-counted promises.

The zero value is a valid Store, though a store may also be created via NewStore if a custom EvictionPolicy is required.

func NewStore

func NewStore(policy EvictionPolicy) *Store

NewStore creates a new store with the given eviction policy.

func (*Store) DebugOnlyIterate

func (s *Store) DebugOnlyIterate(f func(k, v interface{}))

DebugOnlyIterate iterates through the store and, for each completed promise, calls f(k, v) for the map key k and function result v. It should only be used for debugging purposes.

func (*Store) Promise

func (store *Store) Promise(key interface{}, function Function) (*Promise, func())

Promise returns a reference-counted promise for the future result of calling the specified function.

Calls to Promise with the same key return the same promise, incrementing its reference count. The caller must call the returned function to decrement the promise's reference count when it is no longer needed. The returned function must not be called more than once.

Once the last reference has been released, the promise is removed from the store.

func (*Store) Stats

func (s *Store) Stats() map[reflect.Type]int

Stats returns the number of each type of key in the store.