lru

package module
v0.0.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 8, 2023 License: MPL-2.0 Imports: 4 Imported by: 0

README

golang-lru

Build Status Coverage

This provides the lru package which implements a fixed-size thread safe LRU cache with expire feature. It is based on golang-lru.

Documentation

Full docs are available on Godoc

Example

Using the LRU is very simple:

l, _ := NewARCWithExpire(128, 30*time.Second)
for i := 0; i < 256; i++ {
    l.Add(i, nil)
}
if l.Len() != 128 {
    panic(fmt.Sprintf("bad len: %v", l.Len()))
}

Benchmarks

without pool

Running tool: /home/liqi/workspace/go/bin/go test -benchmem -run=^$ -coverprofile=/tmp/vscode-govFyHq9/go-code-cover -bench . github.com/arielsrv/golang-lru

goos: linux
goarch: amd64
pkg: github.com/arielsrv/golang-lru
Benchmark2Q_Rand-4    	 1000000	      1415 ns/op	     158 B/op	       5 allocs/op
--- BENCH: Benchmark2Q_Rand-4
    2q_test.go:34: hit: 0 miss: 1 ratio: 0.000000
    2q_test.go:34: hit: 1 miss: 99 ratio: 0.010101
    2q_test.go:34: hit: 1381 miss: 8619 ratio: 0.160227
    2q_test.go:34: hit: 248530 miss: 751470 ratio: 0.330725
Benchmark2Q_Freq-4    	 1000000	      1017 ns/op	     143 B/op	       5 allocs/op
--- BENCH: Benchmark2Q_Freq-4
    2q_test.go:66: hit: 1 miss: 0 ratio: +Inf
    2q_test.go:66: hit: 100 miss: 0 ratio: +Inf
    2q_test.go:66: hit: 9840 miss: 160 ratio: 61.500000
    2q_test.go:66: hit: 332417 miss: 667583 ratio: 0.497941
BenchmarkARC_Rand-4   	 1000000	      1402 ns/op	     193 B/op	       6 allocs/op
--- BENCH: BenchmarkARC_Rand-4
    arc_test.go:39: hit: 0 miss: 1 ratio: 0.000000
    arc_test.go:39: hit: 1 miss: 99 ratio: 0.010101
    arc_test.go:39: hit: 1398 miss: 8602 ratio: 0.162520
    arc_test.go:39: hit: 249099 miss: 750901 ratio: 0.331733
BenchmarkARC_Freq-4   	  963909	      1190 ns/op	     166 B/op	       5 allocs/op
--- BENCH: BenchmarkARC_Freq-4
    arc_test.go:71: hit: 1 miss: 0 ratio: +Inf
    arc_test.go:71: hit: 100 miss: 0 ratio: +Inf
    arc_test.go:71: hit: 9860 miss: 140 ratio: 70.428571
    arc_test.go:71: hit: 310475 miss: 653434 ratio: 0.475144
BenchmarkLRU_Rand-4   	 2287102	       613 ns/op	      88 B/op	       3 allocs/op
--- BENCH: BenchmarkLRU_Rand-4
    lru_test.go:34: hit: 0 miss: 1 ratio: 0.000000
    lru_test.go:34: hit: 0 miss: 100 ratio: 0.000000
    lru_test.go:34: hit: 1379 miss: 8621 ratio: 0.159958
    lru_test.go:34: hit: 248489 miss: 751511 ratio: 0.330653
    lru_test.go:34: hit: 570640 miss: 1716462 ratio: 0.332451
BenchmarkLRU_Freq-4   	 2456690	       487 ns/op	      83 B/op	       3 allocs/op
--- BENCH: BenchmarkLRU_Freq-4
    lru_test.go:66: hit: 1 miss: 0 ratio: +Inf
    lru_test.go:66: hit: 100 miss: 0 ratio: +Inf
    lru_test.go:66: hit: 9846 miss: 154 ratio: 63.935065
    lru_test.go:66: hit: 312529 miss: 687471 ratio: 0.454607
    lru_test.go:66: hit: 752485 miss: 1704205 ratio: 0.441546
PASS
coverage: 54.9% of statements
ok  	github.com/arielsrv/golang-lru	9.138s

with sync pool

Running tool: /home/liqi/workspace/go/bin/go test -benchmem -run=^$ -coverprofile=/tmp/vscode-govFyHq9/go-code-cover -bench . github.com/arielsrv/golang-lru

goos: linux
goarch: amd64
pkg: github.com/arielsrv/golang-lru
Benchmark2Q_Rand-4    	 1000000	      1090 ns/op	      92 B/op	       4 allocs/op
--- BENCH: Benchmark2Q_Rand-4
    2q_test.go:34: hit: 0 miss: 1 ratio: 0.000000
    2q_test.go:34: hit: 0 miss: 100 ratio: 0.000000
    2q_test.go:34: hit: 1375 miss: 8625 ratio: 0.159420
    2q_test.go:34: hit: 249496 miss: 750504 ratio: 0.332438
Benchmark2Q_Freq-4    	 1223035	       944 ns/op	      85 B/op	       4 allocs/op
--- BENCH: Benchmark2Q_Freq-4
    2q_test.go:66: hit: 1 miss: 0 ratio: +Inf
    2q_test.go:66: hit: 100 miss: 0 ratio: +Inf
    2q_test.go:66: hit: 9872 miss: 128 ratio: 77.125000
    2q_test.go:66: hit: 334464 miss: 665536 ratio: 0.502548
    2q_test.go:66: hit: 405282 miss: 817753 ratio: 0.495604
BenchmarkARC_Rand-4   	 1000000	      1330 ns/op	     111 B/op	       4 allocs/op
--- BENCH: BenchmarkARC_Rand-4
    arc_test.go:39: hit: 0 miss: 1 ratio: 0.000000
    arc_test.go:39: hit: 0 miss: 100 ratio: 0.000000
    arc_test.go:39: hit: 1368 miss: 8632 ratio: 0.158480
    arc_test.go:39: hit: 248419 miss: 751581 ratio: 0.330529
BenchmarkARC_Freq-4   	 1000000	      1090 ns/op	      93 B/op	       4 allocs/op
--- BENCH: BenchmarkARC_Freq-4
    arc_test.go:71: hit: 1 miss: 0 ratio: +Inf
    arc_test.go:71: hit: 100 miss: 0 ratio: +Inf
    arc_test.go:71: hit: 9876 miss: 124 ratio: 79.645161
    arc_test.go:71: hit: 337535 miss: 662465 ratio: 0.509514
BenchmarkLRU_Rand-4   	 2327682	       509 ns/op	      52 B/op	       2 allocs/op
--- BENCH: BenchmarkLRU_Rand-4
    lru_test.go:34: hit: 0 miss: 1 ratio: 0.000000
    lru_test.go:34: hit: 1 miss: 99 ratio: 0.010101
    lru_test.go:34: hit: 1478 miss: 8522 ratio: 0.173433
    lru_test.go:34: hit: 249019 miss: 750981 ratio: 0.331592
    lru_test.go:34: hit: 580746 miss: 1746936 ratio: 0.332437
BenchmarkLRU_Freq-4   	 2630702	       475 ns/op	      49 B/op	       2 allocs/op
--- BENCH: BenchmarkLRU_Freq-4
    lru_test.go:66: hit: 1 miss: 0 ratio: +Inf
    lru_test.go:66: hit: 100 miss: 0 ratio: +Inf
    lru_test.go:66: hit: 9784 miss: 216 ratio: 45.296296
    lru_test.go:66: hit: 311783 miss: 688217 ratio: 0.453030
    lru_test.go:66: hit: 810266 miss: 1820436 ratio: 0.445094
PASS
coverage: 55.3% of statements
ok  	github.com/arielsrv/golang-lru	9.714s

with list pool

Running tool: /home/liqi/workspace/go/bin/go test -benchmem -run=^$ -coverprofile=/tmp/vscode-govFyHq9/go-code-cover -bench . github.com/arielsrv/golang-lru

goos: linux
goarch: amd64
pkg: github.com/arielsrv/golang-lru
Benchmark2Q_Rand-4    	 1000000	      1311 ns/op	      26 B/op	       2 allocs/op
--- BENCH: Benchmark2Q_Rand-4
    2q_test.go:34: hit: 0 miss: 1 ratio: 0.000000
    2q_test.go:34: hit: 0 miss: 100 ratio: 0.000000
    2q_test.go:34: hit: 1320 miss: 8680 ratio: 0.152074
    2q_test.go:34: hit: 249497 miss: 750503 ratio: 0.332440
Benchmark2Q_Freq-4    	 1515253	       811 ns/op	      25 B/op	       2 allocs/op
--- BENCH: Benchmark2Q_Freq-4
    2q_test.go:66: hit: 1 miss: 0 ratio: +Inf
    2q_test.go:66: hit: 100 miss: 0 ratio: +Inf
    2q_test.go:66: hit: 9880 miss: 120 ratio: 82.333333
    2q_test.go:66: hit: 333341 miss: 666659 ratio: 0.500017
    2q_test.go:66: hit: 416877 miss: 839436 ratio: 0.496616
    2q_test.go:66: hit: 500425 miss: 1014828 ratio: 0.493113
BenchmarkARC_Rand-4   	 1000000	      1162 ns/op	      27 B/op	       2 allocs/op
--- BENCH: BenchmarkARC_Rand-4
    arc_test.go:39: hit: 0 miss: 1 ratio: 0.000000
    arc_test.go:39: hit: 0 miss: 100 ratio: 0.000000
    arc_test.go:39: hit: 1437 miss: 8563 ratio: 0.167815
    arc_test.go:39: hit: 248890 miss: 751110 ratio: 0.331363
BenchmarkARC_Freq-4   	 1418329	       860 ns/op	      26 B/op	       2 allocs/op
--- BENCH: BenchmarkARC_Freq-4
    arc_test.go:71: hit: 1 miss: 0 ratio: +Inf
    arc_test.go:71: hit: 100 miss: 0 ratio: +Inf
    arc_test.go:71: hit: 9847 miss: 153 ratio: 64.359477
    arc_test.go:71: hit: 337917 miss: 662083 ratio: 0.510385
    arc_test.go:71: hit: 472261 miss: 946068 ratio: 0.499183
BenchmarkLRU_Rand-4   	 2970676	       397 ns/op	      16 B/op	       1 allocs/op
--- BENCH: BenchmarkLRU_Rand-4
    lru_test.go:34: hit: 0 miss: 1 ratio: 0.000000
    lru_test.go:34: hit: 0 miss: 100 ratio: 0.000000
    lru_test.go:34: hit: 1375 miss: 8625 ratio: 0.159420
    lru_test.go:34: hit: 249937 miss: 750063 ratio: 0.333221
    lru_test.go:34: hit: 741873 miss: 2228803 ratio: 0.332857
BenchmarkLRU_Freq-4   	 3186918	       359 ns/op	      16 B/op	       1 allocs/op
--- BENCH: BenchmarkLRU_Freq-4
    lru_test.go:66: hit: 1 miss: 0 ratio: +Inf
    lru_test.go:66: hit: 100 miss: 0 ratio: +Inf
    lru_test.go:66: hit: 9874 miss: 126 ratio: 78.365079
    lru_test.go:66: hit: 312430 miss: 687570 ratio: 0.454397
    lru_test.go:66: hit: 977757 miss: 2209161 ratio: 0.442592
PASS
coverage: 55.3% of statements
ok  	github.com/arielsrv/golang-lru	11.639s

Documentation

Overview

Package lru This package provides a simple LRU cache. It is based on the LRU implementation in groupcache: https://github.com/golang/groupcache/tree/master/lru

Index

Constants

View Source 
const (
	// Default2QRecentRatio is the ratio of the 2Q cache dedicated
	// to recently added entries that have only been accessed once.
	Default2QRecentRatio = 0.25

	// Default2QGhostEntries is the default ratio of ghost
	// entries kept to track entries recently evicted.
	Default2QGhostEntries = 0.50
)

Variables

This section is empty.

Functions

This section is empty.

Types

type ARCCache 

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

ARCCache is a thread-safe fixed size Adaptive Replacement Cache (ARC). ARC is an enhancement over the standard LRU cache in that tracks both frequency and recency of use. This avoids a burst in access to new entries from evicting the frequently used older entries. It adds some additional tracking overhead to a standard LRU cache, computationally it is roughly 2x the cost, and the extra memory overhead is linear with the size of the cache. ARC has been patented by IBM, but is similar to the TwoQueueCache (2Q) which requires setting parameters.

func NewARC 

func NewARC(size int) (*ARCCache, error)

NewARC creates an ARC of the given size.

func NewARCWithExpire 

func NewARCWithExpire(size int, expire time.Duration) (*ARCCache, error)

NewARCWithExpire creates an ARC of the given size.

func (*ARCCache) Add 

func (c *ARCCache) Add(key, value interface{})

Add adds a value to the cache.

func (*ARCCache) AddEx 

func (c *ARCCache) AddEx(key, value interface{}, expire time.Duration)

AddEx adds a value to the cache.

func (*ARCCache) Contains 

func (c *ARCCache) Contains(key interface{}) bool

Contains is used to check if the cache contains a key without updating recency or frequency.

func (*ARCCache) Get 

func (c *ARCCache) Get(key interface{}) (interface{}, bool)

Get looks up a key's value from the cache.

func (*ARCCache) Keys 

func (c *ARCCache) Keys() []interface{}

Keys returns all the cached keys.

func (*ARCCache) Len 

func (c *ARCCache) Len() int

Len returns the number of cached entries.

func (*ARCCache) Peek 

func (c *ARCCache) Peek(key interface{}) (interface{}, bool)

Peek is used to inspect the cache value of a key without updating recency or frequency.

func (*ARCCache) Purge 

func (c *ARCCache) Purge()

Purge is used to clear the cache.

func (*ARCCache) Remove 

func (c *ARCCache) Remove(key interface{})

Remove is used to purge a key from the cache.

type Cache 

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

Cache is a thread-safe fixed size LRU cache.

func New 

func New(size int) (*Cache, error)

New creates an LRU of the given size.

func NewWithEvict 

func NewWithEvict(size int, onEvicted func(key interface{}, value interface{})) (*Cache, error)

NewWithEvict constructs a fixed size cache with the given eviction callback.

func NewWithExpire 

func NewWithExpire(size int, expire time.Duration) (*Cache, error)

NewWithExpire constructs a fixed size cache with expire feature.

func (*Cache) Add 

func (c *Cache) Add(key, value interface{}) bool

Add adds a value to the cache. Returns true if an eviction occurred.

func (*Cache) AddEx 

func (c *Cache) AddEx(key, value interface{}, expire time.Duration) bool

AddEx adds a value to the cache. Returns true if an eviction occurred.

func (*Cache) Contains 

func (c *Cache) Contains(key interface{}) bool

Check if a key is in the cache, without updating the recent-ness or deleting it for being stale.

func (*Cache) ContainsOrAdd 

func (c *Cache) ContainsOrAdd(key, value interface{}) (bool, bool)

ContainsOrAdd checks if a key is in the cache without updating the recent-ness or deleting it for being stale, and if not, adds the value. Returns whether found and whether an eviction occurred.

func (*Cache) Get 

func (c *Cache) Get(key interface{}) (interface{}, bool)

Get looks up a key's value from the cache.

func (*Cache) Keys 

func (c *Cache) Keys() []interface{}

Keys returns a slice of the keys in the cache, from oldest to newest.

func (*Cache) Len 

func (c *Cache) Len() int

Len returns the number of items in the cache.

func (*Cache) Peek 

func (c *Cache) Peek(key interface{}) (interface{}, bool)

Returns the key value (or undefined if not found) without updating the "recently used"-ness of the key.

func (*Cache) Purge 

func (c *Cache) Purge()

Purge is used to completely clear the cache.

func (*Cache) Remove 

func (c *Cache) Remove(key interface{})

Remove removes the provided key from the cache.

func (*Cache) RemoveOldest 

func (c *Cache) RemoveOldest()

RemoveOldest removes the oldest item from the cache.

type TwoQueueCache 

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

TwoQueueCache is a thread-safe fixed size 2Q cache. 2Q is an enhancement over the standard LRU cache in that it tracks both frequently and recently used entries separately. This avoids a burst in access to new entries from evicting frequently used entries. It adds some additional tracking overhead to the standard LRU cache, and is computationally about 2x the cost, and adds some metadata over head. The ARCCache is similar, but does not require setting any parameters.

func New2Q 

func New2Q(size int) (*TwoQueueCache, error)

New2Q creates a new TwoQueueCache using the default values for the parameters.

func New2QParams 

func New2QParams(size int, recentRatio float64, ghostRatio float64) (*TwoQueueCache, error)

New2QParams creates a new TwoQueueCache using the provided parameter values.

func New2QParamsWithExpire 

func New2QParamsWithExpire(size int, expire time.Duration, recentRatio float64, ghostRatio float64) (*TwoQueueCache, error)

New2QParamsWithExpire creates a new TwoQueueCache using the provided parameter values with expire feature.

func New2QWithExpire 

func New2QWithExpire(size int, expire time.Duration) (*TwoQueueCache, error)

New2QWithExpire creates a new TwoQueueCache using the default values for the parameters with expire feature.

func (*TwoQueueCache) Add 

func (c *TwoQueueCache) Add(key, value interface{})

func (*TwoQueueCache) AddEx 

func (c *TwoQueueCache) AddEx(key, value interface{}, expire time.Duration)

func (*TwoQueueCache) Contains 

func (c *TwoQueueCache) Contains(key interface{}) bool

func (*TwoQueueCache) Get 

func (c *TwoQueueCache) Get(key interface{}) (interface{}, bool)

func (*TwoQueueCache) Keys 

func (c *TwoQueueCache) Keys() []interface{}

func (*TwoQueueCache) Len 

func (c *TwoQueueCache) Len() int

func (*TwoQueueCache) Peek 

func (c *TwoQueueCache) Peek(key interface{}) (interface{}, bool)

func (*TwoQueueCache) Purge 

func (c *TwoQueueCache) Purge()

func (*TwoQueueCache) Remove 

func (c *TwoQueueCache) Remove(key interface{})

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.