lru

README

lru

Thread safe GoLang LRU cache.

Example

import (
	"fmt"

	"github.com/floatdrop/lru"
)

func main() {
	cache := lru.New[string, int](256)

	cache.Set("Hello", 5)

	if e := cache.Get("Hello"); e != nil {
		fmt.Println(*e)
		// Output: 5
	}
}

TTL

You can wrap values into Expiring[T any] struct to release memory on timer (or manually in Valid method).

Example implementation

import (
    "fmt"
    "time"

    "github.com/floatdrop/lru"
)

type Expiring[T any] struct {
    value *T
}

func (E *Expiring[T]) Valid() *T {
    if E == nil {
        return nil
    }

    return E.value
}

func WithTTL[T any](value T, ttl time.Duration) Expiring[T] {
    e := Expiring[T]{
        value: &value,
    }

    time.AfterFunc(ttl, func() {
        e.value = nil // Release memory
    })

    return e
}

func main() {
    l := lru.New[string, Expiring[string]](256)

    l.Set("Hello", WithTTL("Bye", time.Hour))

    if e := l.Get("Hello").Valid(); e != nil {
        fmt.Println(*e)
    }
}

Note: Althou this short implementation frees memory after ttl duration, it will not erase entry for key in cache. It can be a problem, if you do not check nillnes after getting element from cache and call Set afterwards.

Benchmarks

floatdrop/lru:
    BenchmarkLRU_Rand-8   	 8802915	       131.7 ns/op	      24 B/op	       1 allocs/op
    BenchmarkLRU_Freq-8   	 9392769	       127.8 ns/op	      24 B/op	       1 allocs/op

hashicorp/golang-lru:
    BenchmarkLRU_Rand-8   	 5992782	       195.8 ns/op	      76 B/op	       3 allocs/op
    BenchmarkLRU_Freq-8   	 6355358	       186.1 ns/op	      71 B/op	       3 allocs/op

jellydator/ttlcache:
    BenchmarkLRU_Rand-8   	 4447654	       253.5 ns/op	     144 B/op	       2 allocs/op
    BenchmarkLRU_Freq-8   	 4837938	       240.9 ns/op	     137 B/op	       2 allocs/op

Documentation

Overview

Package lru implements cache with least recent used eviction policy.

Index

• type Evicted
• type LRU
  • func New[K comparable, V any](size int) *LRU[K, V]
  • func (L *LRU[K, V]) Get(key K) *V
  • func (L *LRU[K, V]) Len() int
  • func (L *LRU[K, V]) Peek(key K) *V
  • func (L *LRU[K, V]) Remove(key K) *V
  • func (L *LRU[K, V]) Set(key K, value V) *Evicted[K, V]
  • func (L *LRU[K, V]) Victim() *K

Examples

• LRU

Types

type Evicted

type Evicted[K comparable, V any] struct {
	Key   K
	Value V
}

Evicted holds key/value pair that was evicted from cache.

type LRU

type LRU[K comparable, V any] struct {
	// contains filtered or unexported fields
}

LRU implements Cache interface with least recent used eviction policy.

Example

package main

import (
	"fmt"

	"github.com/floatdrop/lru"
)

func main() {
	cache := lru.New[string, int](256)

	cache.Set("Hello", 5)

	if e := cache.Get("Hello"); e != nil {
		fmt.Println(*cache.Get("Hello"))

	}
}

Output:

5

func New

func New[K comparable, V any](size int) *LRU[K, V]

New creates LRU cache with size capacity. Cache will preallocate size count of internal structures to avoid allocation in process.

func (*LRU[K, V]) Get

func (L *LRU[K, V]) Get(key K) *V

Get returns pointer to value for key, if value was in cache (nil returned otherwise).

func (*LRU[K, V]) Len

func (L *LRU[K, V]) Len() int

Len returns number of cached items.

func (*LRU[K, V]) Peek

func (L *LRU[K, V]) Peek(key K) *V

Peek returns value for key (if key was in cache), but does not modify its recency.

func (*LRU[K, V]) Remove

func (L *LRU[K, V]) Remove(key K) *V

Remove method removes entry associated with key and returns pointer to removed value (or nil if entry was not in cache).

func (*LRU[K, V]) Set

func (L *LRU[K, V]) Set(key K, value V) *Evicted[K, V]

Set inserts key value pair and returns evicted value, if cache was full. If cache size is less than 1 – method will always return reference to value (as if it was immediately evicted).

func (*LRU[K, V]) Victim

func (L *LRU[K, V]) Victim() *K

Victim returns pointer to a key, that will be evicted on next Set call (or nil if there is a space for another key). If cache size is 0 - nil will be always returned.