This PR adds support for generics.

Because there is no generic list type in the standard library yet, I added a minimal version of container/list with added generics support (I kept the licence header, please let me know if it should be removed).

It would also be possible to keep using container/list as is, and just update the public API (take care of interface casts internally), but most of the performance gain comes from removing interface conversions.

Benchmark results against master

name         old time/op    new time/op    delta
2Q_Rand-16     1.22µs ±10%    0.52µs ± 8%   -57.69%  (p=0.000 n=20+19)
2Q_Freq-16     1.03µs ±10%    0.44µs ±12%   -57.42%  (p=0.000 n=18+20)
ARC_Rand-16    1.51µs ± 9%    0.70µs ±15%   -53.63%  (p=0.000 n=20+20)
ARC_Freq-16    1.22µs ±12%    0.54µs ± 7%   -56.20%  (p=0.000 n=20+20)
LRU_Rand-16     401ns ± 9%     215ns ± 6%   -46.46%  (p=0.000 n=20+20)
LRU_Freq-16     376ns ±13%     194ns ± 7%   -48.51%  (p=0.000 n=19+20)

name         old alloc/op   new alloc/op   delta
2Q_Rand-16       136B ± 0%       67B ± 0%   -50.74%  (p=0.000 n=20+18)
2Q_Freq-16       124B ± 0%       59B ± 0%   -52.42%  (p=0.000 n=16+20)
ARC_Rand-16      165B ± 0%       84B ± 1%   -49.03%  (p=0.000 n=20+20)
ARC_Freq-16      139B ± 3%       68B ± 5%   -51.01%  (p=0.000 n=20+20)
LRU_Rand-16     76.0B ± 0%     36.0B ± 0%   -52.63%  (p=0.000 n=20+20)
LRU_Freq-16     71.0B ± 0%     33.0B ± 0%   -53.52%  (p=0.000 n=19+20)

name         old allocs/op  new allocs/op  delta
2Q_Rand-16       5.00 ± 0%      1.00 ± 0%   -80.00%  (p=0.000 n=20+20)
2Q_Freq-16       5.00 ± 0%      1.00 ± 0%   -80.00%  (p=0.000 n=20+20)
ARC_Rand-16      6.00 ± 0%      1.00 ± 0%   -83.33%  (p=0.000 n=20+20)
ARC_Freq-16      5.00 ± 0%      1.00 ± 0%   -80.00%  (p=0.000 n=20+20)
LRU_Rand-16      3.00 ± 0%      0.00       -100.00%  (p=0.000 n=20+20)
LRU_Freq-16      3.00 ± 0%      0.00       -100.00%  (p=0.000 n=20+20)

My attempt at expirable cache implementation, similar to what was done in #41. I've tried to make new cache as close as possible to the existing one in terms of code style and behavior.

The only difference which I did leave in place is that size=0 on this type of cache means unlimited, which makes sense with the expirable cache.

Original work was done in lcw but it turned out that I don't need it there and I thought it would be nice to add my changes to upstream (this repo).

Hi,

Your go.mod file prevents golang-lru from building on go 1.11. Is 1.12 a strict requirement of the library? If not, can the go.mod file be modified to allow other go versions at least to go 1.11?

Thanks!

I wanted to keep an LRU cache of open files, so I need a hook for closing the files as they're evicted from the cache.

A side effect is that the Purge operation is now probably slower, since we have to remove each element individually to ensure that OnEvicted gets called for each element. If that is important, I could check if the OnEvicted function is missing, and if so purge the original way.

Adds a Resize method to LRU cache.

We use golang-lru in production at Crunchyroll for embedded HTTP response caching in microservices through microcache.

We'd like to wrap LRU cache with our own type which would allow for the cache size to be specified in total data size rather than element count. This would make the cache safer and more memory efficient since right now we have to make an educated guess at average element size (compressed HTTP responses) and reserve significant memory overhead for potential variation. I have a good idea of how to implement this wrapper by calculating average element size in real time and adjusting the cache size dynamically to strictly control memory usage. However, this requires the cache to be resizable so that it can be expanded or contracted depending on the average size of elements added and evicted.

This is an interface change adding one method.

This PR only affects LRU and not ARC or 2Q since those implementations would be more complex.

The performance of a cache resize depends on the delta. In general, downsizing is more expensive since it may result in many evictions while upsizing is relatively cheap.

Hi there!

I was looking closely at the code and found a piece added in #56 which doesn't seem to be used and is not tested:

https://github.com/hashicorp/golang-lru/blob/881666a9a6fd9b1a7ceecdb853b12c106791809b/simplelru/lru.go#L76-L78

I tried but was unable to trigger this condition. I think it should be either covered with tests and added to all other affected functions (e.g. at least LRU.Peek) or removed altogether if that condition is indeed impossible as I think it is.

In the documentation for ARCCache it says that the algorithm is patented by IBM

It looks like IBM sold (or traded or gave) the patent to Intel in 2013 https://assignment.uspto.gov/patent/index.html#/patent/search/resultAbstract?id=6996676&type=patNum

http://legacy-assignments.uspto.gov/assignments/assignment-pat-30228-415.pdf

We've been using this addition for a number of months with great success.

Basically, we have a stream of events we want to de-duplicate and merge, but we also want to guarantee that popular events eventually get flushed to storage periodically. This is pretty straight forward to do by adding a ~5 second TTL and calling a save method in the on_evict hook. Naturally this means we do one update per event group every N seconds rather than every requests, saving our DB significant load.

I can imagine other use cases too, such as ensuring your local cache is never too out of date when being used as a look aside cache. Edit: Our other use case is caching authentication information for the lifetime of the token by building a token -> user map. Naturally, we want this information to expire in a timely fashion :)

For more details on our particular use case: https://blogs.unity3d.com/2015/12/02/the-state-of-game-performance-reporting/

Adds an ARCCache implementation, which adaptively trades off between storing frequently used and recently used entries. This is nice as a small burst in access to new records does not cause the frequently used records to be evicted. In almost all cases an ARC outperforms a standard LRU, but there is an additional overhead.

This PR moves the pure LRU logic into an internal package which is not thread safe. The existing LRUCache provides thread safety on top of that. The ARCCache implementation uses the same internal LRU, and is also thread safe.

We're using the LRU in a situation where we are purging the cache fairly often. The original code was creating a new list and map during every purge. This pull request resets the original list and map, so it doesn't create any additional garbage.

This commit ensures that the patented files are not compiled in, so that consumers do not need to validate that the patented files are not actually used.

Consumers can still opt-in to use the patented files by copying them.

Fix #31 Fix #73

This file imports testing which is an import that is disallowed by tooling for production packages. It is only called by test files so we don;t need this in a non-test package.

Thread-safe. It could be used in place of simplelru.LRU but shouldn't as it has built-in locks, whereas simplelru.LRU doesn't, which allows more effective locking on top of it in top-level package cache implementations.

Similar to what was done in #41. I've tried to make the new cache as close as possible to the existing one regarding code style and behaviour, however existing simplelru.LRU is not thread-safe, as pointed out above, so it's not a drop-in replacement.

Another difference I left in place is that size=0 on this type of cache means unlimited, which makes sense with the expirable cache.

Original work was done in lcw, but it turned out that I don't need it there, and I thought it would be nice to add my changes to upstream (this repo).

This PR is a recreation of #68, which was not merged. cc @jefferai @Dentrax for review as an alternative to #113 (which I unlikely will be able to finish while preserving the current package's speed).

go map has a memory leak，can help fix it? I now use two go map to fix it, if not use this way to avoid the memory leak problem

the reason is that go map delete a key only to label it ,but not really delete it, so the memory can increase always. Using the two map way sets the go map to nil that solves the problem.

`package simplelru

type BetterMap struct { firstMap map[interface{}]interface{} secondMap map[interface{}]interface{} deleteNumThresh int32 totalDeleteNum int32 useMapIndex int32 }

func NewBetterMap(deleteNumThresh int32) *BetterMap { return &BetterMap{ firstMap: make(map[interface{}]interface{}, 0), secondMap: make(map[interface{}]interface{}, 0), deleteNumThresh: deleteNumThresh, totalDeleteNum: 0, useMapIndex: 1, } }

func (bmap *BetterMap) Set(key interface{}, value interface{}) { if bmap.useMapIndex == 1 { bmap.firstMap[key] = value } else { bmap.secondMap[key] = value }

}

func (bmap *BetterMap) GetValue(key interface{}) (interface{}, bool) { if value, ok := bmap.firstMap[key]; ok { return value, ok }

value, ok := bmap.secondMap[key]

return value, ok

}

func (bmap *BetterMap) GetValues() []interface{} { values := make([]interface{}, 0) if bmap.useMapIndex == 1 { for _, value := range bmap.firstMap { values = append(values, value) } } else { for _, value := range bmap.secondMap { values = append(values, value) } }

return values

}

func (bmap *BetterMap) GetMap() map[interface{}]interface{} { if bmap.useMapIndex == 1 { return bmap.firstMap }

return bmap.secondMap

}

func (bmap *BetterMap) GetLen() int { if bmap.useMapIndex == 1 { return len(bmap.firstMap) }

return len(bmap.secondMap)

}

func (bmap *BetterMap) Purge() { bmap.firstMap = nil bmap.secondMap = nil }

func (bmap *BetterMap) DelKey(key interface{}) { if bmap.useMapIndex == 1 { delete(bmap.firstMap, key) bmap.totalDeleteNum++ if bmap.totalDeleteNum >= bmap.deleteNumThresh { bmap.secondMap = make(map[interface{}]interface{}, len(bmap.firstMap)) for i, v := range bmap.firstMap { bmap.secondMap[i] = v }

		bmap.useMapIndex = 2
		bmap.totalDeleteNum = 0
		bmap.firstMap = nil
	}
} else {
	delete(bmap.secondMap, key)
	bmap.totalDeleteNum++
	if bmap.totalDeleteNum >= bmap.deleteNumThresh {
		bmap.firstMap = make(map[interface{}]interface{}, len(bmap.secondMap))
		for i, v := range bmap.secondMap {
			bmap.firstMap[i] = v
		}

		bmap.useMapIndex = 1
		bmap.totalDeleteNum = 0
		bmap.secondMap = nil
	}
}

}package simplelru

import ( "container/list" "errors" )

// EvictCallback is used to get a callback when a cache entry is evicted type EvictCallback func(key interface{}, value interface{})

// LRU implements a non-thread safe fixed size LRU cache type LRU struct { size int evictList *list.List //items map[interface{}]*list.Element betterMap *BetterMap onEvict EvictCallback }

// entry is used to hold a value in the evictList type entry struct { key interface{} value interface{} }

// NewLRU constructs an LRU of the given size func NewLRU(size int, onEvict EvictCallback) (*LRU, error) { if size <= 0 { return nil, errors.New("Must provide a positive size") } c := &LRU{ size: size, evictList: list.New(), betterMap: NewBetterMap(int32(size)), onEvict: onEvict, } return c, nil }

// Purge is used to completely clear the cache. func (c *LRU) Purge() { c.betterMap.Purge() c.betterMap = NewBetterMap(int32(c.size)) c.evictList.Init() }

// Add adds a value to the cache. Returns true if an eviction occurred. func (c *LRU) Add(key, value interface{}) (evicted bool) { // Check for existing item if ent, ok := c.betterMap.GetValue(key); ok { c.evictList.MoveToFront(ent.(*list.Element))

	ent.(*list.Element).Value.(*entry).value = value
	return false
}
// Add new item
ent := &entry{key, value}
entry := c.evictList.PushFront(ent)
//c.items[key] = entry
c.betterMap.Set(key, entry)
evict := c.evictList.Len() > c.size
// Verify size not exceeded
if evict {
	c.removeOldest()
}
return evict

}

// Get looks up a key's value from the cache. func (c *LRU) Get(key interface{}) (value interface{}, ok bool) {

if ent, ok := c.betterMap.GetValue(key); ok {
	c.evictList.MoveToFront(ent.(*list.Element))
	return ent.(*list.Element).Value.(*entry).value, true
}
return

}

// Contains checks if a key is in the cache, without updating the recent-ness // or deleting it for being stale. func (c *LRU) Contains(key interface{}) (ok bool) { _, ok = c.betterMap.GetValue(key) return ok }

// Peek returns the key value (or undefined if not found) without updating // the "recently used"-ness of the key. func (c *LRU) Peek(key interface{}) (value interface{}, ok bool) {

if ent, ok := c.betterMap.GetValue(key); ok {
	return ent.(*list.Element).Value.(*entry).value, true
}
return nil, ok

}

// Remove removes the provided key from the cache, returning if the // key was contained. func (c *LRU) Remove(key interface{}) (present bool) { if ent, ok := c.betterMap.GetValue(key); ok { c.removeElement(ent.(*list.Element)) return true }

return false

}

// RemoveOldest removes the oldest item from the cache. func (c *LRU) RemoveOldest() (key, value interface{}, ok bool) { ent := c.evictList.Back() if ent != nil { c.removeElement(ent) kv := ent.Value.(*entry) return kv.key, kv.value, true } return nil, nil, false }

// GetOldest returns the oldest entry func (c *LRU) GetOldest() (key, value interface{}, ok bool) { ent := c.evictList.Back() if ent != nil { kv := ent.Value.(*entry) return kv.key, kv.value, true } return nil, nil, false }

// Keys returns a slice of the keys in the cache, from oldest to newest. func (c *LRU) Keys() []interface{} { keys := make([]interface{}, c.betterMap.GetLen()) i := 0 for ent := c.evictList.Back(); ent != nil; ent = ent.Prev() { keys[i] = ent.Value.(*entry).key i++ } return keys }

// Len returns the number of items in the cache. func (c *LRU) Len() int { return c.evictList.Len() }

// Resize changes the cache size. func (c *LRU) Resize(size int) (evicted int) { diff := c.Len() - size if diff < 0 { diff = 0 } for i := 0; i < diff; i++ { c.removeOldest() } c.size = size return diff }

// removeOldest removes the oldest item from the cache. func (c *LRU) removeOldest() { ent := c.evictList.Back() if ent != nil { c.removeElement(ent) } }

// removeElement is used to remove a given list element from the cache func (c *LRU) removeElement(e *list.Element) { c.evictList.Remove(e) kv := e.Value.(*entry) c.betterMap.DelKey(kv.key) if c.onEvict != nil { c.onEvict(kv.key, kv.value) } }`

This LRU cache is not a thread safe. So it's better to add a thread safe layer to this.

Code to reproduce the concurrent access.

Code :-

// github.com/hashicorp/golang-lru/simplelru package main

import ( "log" "sync"

"github.com/hashicorp/golang-lru/simplelru"

)

var wg sync.WaitGroup

func main() { LRU, err := simplelru.NewLRU(100, nil) if err != nil { log.Fatal(err) return } for i := 0; i < 100; i++ { LRU.Add(100, 100) } wg.Add(2) go FreqAccess(LRU) go FreqWrite(LRU) wg.Wait() }

func FreqAccess(lru *simplelru.LRU) { defer wg.Done() for i := 0; i < 100; i++ { wg.Add(1) go func() { defer wg.Done() lru.Get(i) }() } } func FreqWrite(lru *simplelru.LRU) { defer wg.Done() for i := 0; i < 100; i++ { wg.Add(1) go func() { defer wg.Done() lru.Add(i, i) }() } }

Error :-

fatal error: concurrent map read and map write

It behaves similar to the standard Add method with the difference that it can also take an update method that will be performed in case the key already exists.

For example:

value1 := []string{"some_value"}
value2 := []string{"some_value_2"}

l.Add(1, value1)
l.AddOrUpdate(1, value2, func(v1, v2 interface{}) interface{} {
	slice1 := v1.([]string)
	slice2 := v2.([]string)
	return append(slice1, slice2...)
})

Then l.Get(1) will result to []string{"some_value", "some_value_2"}