sieve

README

go-sieve - SIEVE is simpler than LRU

What is it?

go-sieve is a golang implementation of the SIEVE cache eviction algorithm.

This implementation closely follows the paper's pseudo-code - but uses golang generics to provide an ergonomic interface.

Key Design Features

Custom Memory Allocator for Reduced GC Pressure

This implementation uses a custom memory allocator designed to minimize GC pressure:

• Pre-allocated Node Pool: Rather than allocating nodes individually, the cache pre-allocates all nodes at initialization time in a single contiguous array based on cache capacity.

• Efficient Freelist: Recycled nodes are managed through a zero-overhead freelist that repurposes the existing node pointers, avoiding the need for auxiliary data structures.

• Single-Allocation Strategy: By allocating all memory upfront in a single operation, the implementation reduces heap fragmentation and minimizes the number of objects the garbage collector must track.

Usage

The API is designed to be simple and intuitive. See the test files for examples of how to use the cache in your applications.

Documentation

Overview

Package sieve implements the SIEVE cache eviction algorithm. SIEVE stands in contrast to other eviction algorithms like LRU, 2Q, ARC with its simplicity. The original paper is in: https://yazhuozhang.com/assets/pdf/nsdi24-sieve.pdf

SIEVE is built on a FIFO queue - with an extra pointer (called "hand") in the paper. This "hand" plays a crucial role in determining who to evict next.

Index

• type Sieve
  • func New[K comparable, V any](capacity int) *Sieve[K, V]
  • func (s *Sieve[K, V]) Add(key K, val V) bool
  • func (s *Sieve[K, V]) Cap() int
  • func (s *Sieve[K, V]) Delete(key K) bool
  • func (s *Sieve[K, V]) Dump() string
  • func (s *Sieve[K, V]) Get(key K) (V, bool)
  • func (s *Sieve[K, V]) Len() int
  • func (s *Sieve[K, V]) Probe(key K, val V) (V, bool)
  • func (s *Sieve[K, V]) Purge()
  • func (s *Sieve[K, V]) String() string

Types

type Sieve

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

Sieve represents a cache mapping the key of type 'K' with a value of type 'V'. The type 'K' must implement the comparable trait. An instance of Sieve has a fixed max capacity; new additions to the cache beyond the capacity will cause cache eviction of other entries - as determined by the SIEVE algorithm.

func New

func New[K comparable, V any](capacity int) *Sieve[K, V]

New creates a new cache of size 'capacity' mapping key 'K' to value 'V'

func (*Sieve[K, V]) Add

func (s *Sieve[K, V]) Add(key K, val V) bool

Add adds a new element to the cache or overwrite one if it exists Return true if we replaced, false otherwise

func (*Sieve[K, V]) Cap

func (s *Sieve[K, V]) Cap() int

Cap returns the max cache capacity

func (*Sieve[K, V]) Delete

func (s *Sieve[K, V]) Delete(key K) bool

Delete deletes the named key from the cache It returns true if the item was in the cache and false otherwise

func (*Sieve[K, V]) Dump

func (s *Sieve[K, V]) Dump() string

Dump dumps all the cache contents as a newline delimited string.

func (*Sieve[K, V]) Get

func (s *Sieve[K, V]) Get(key K) (V, bool)

Get fetches the value for a given key in the cache. It returns true if the key is in the cache, false otherwise. The zero value for 'V' is returned when key is not in the cache.

func (*Sieve[K, V]) Len

func (s *Sieve[K, V]) Len() int

Len returns the current cache utilization

func (*Sieve[K, V]) Probe

func (s *Sieve[K, V]) Probe(key K, val V) (V, bool)

Probe adds <key, val> if not present in the cache. Returns:

<cached-val, true> when key is present in the cache
<val, false> when key is not present in the cache

func (*Sieve[K, V]) Purge

func (s *Sieve[K, V]) Purge()

Purge resets the cache

func (*Sieve[K, V]) String

func (s *Sieve[K, V]) String() string

String returns a string description of the sieve cache