An LRU in Go (Part 1)
In my job, I often catch myself having to implement a way to keep data in memory so I can use them at a later time. Sometimes this is for caching purposes, sometimes it’s to keep track of what I’ve sent some other service earlier so I can create a diff or something. Reasons are plenty.
I noticed that I keep writing versions of the same thing over and over and when we’re doing that, maybe it’s time to try and create a more generic solution. So let’s start simple, shall we? What we want is to implement a least-recently-used list (LRU) with no fuss.
Naïve LRU
We start with a simple and very naïve implementation (see the full implementation on Github.)
type LRU struct {
cap int // the max number of items to hold
idx map[interface{}]*list.Element // the index for our list
l *list.List // the actual list holding the data
}
We don’t have much there, we have a doubly-linked list l to hold the data and a map to serve as an index. In true Go fashion, we create an initializer —
func New(cap int) *LRU {
l := &LRU{
cap: cap,
l: list.New(),
idx: make(map[interface{}]*list.Element, cap+1),
}
return l
}
This is nice. Package users will initialize the list with something like l := lru.New(1000) and joy will spread thoughout the land. But I strongly believe the empty value of a struct should also be usable, which is not the case here :
var l LRU
l.Add("hello", "world")
This will panic because neither l nor idx are initialized. My go-to solution for this is to always provide a simples unexported initialization function that is run at the beginning of each exported method and makes sure the initialization is done.
func (l *LRU) lazyInit() {
if l.l == nil {
l.l = list.New()
l.idx = make(map[interface{}]*list.Element, l.cap+1)
}
}
Now, let’s see how we’d add a new item to the list —
func (l *LRU) Add(k, v interface{}) {
l.lazyInit()
// first let's see if we already have this key
if le, ok := l.idx[k]; ok {
// update the entry and move it to the front
le.Value.(*entry).val = v
l.l.MoveToFront(le)
return
}
l.idx[k] = l.l.PushFront(&entry{key: k, val: v})
if l.cap > 0 && l.l.Len() > l.cap {
l.removeOldest()
}
return
}
We call lazyInit to make sure everything is initialized than we check whether the key already is in our list. If it is, we only need to update the value and move it to the front of the list as it’s now become the most-recently-used.
If, however, the key was not already in our index, then we need to create a new entry and push it to the list. By the way, this is the first time we see entry, which is an unexported type that we actually store in our list.
type entry struct {
key, val interface{}
}
Finally, we check whether by adding the new element, we just passed the capacity of the list (if cap is less than 1, we treat as there being no limit to capacity, by the way). If we are over capacity, we go ahead and delete the oldest element in the list.
This is a naïve implementation, but it’s also very fast.
BenchmarkAdd/mostly_new-4 2000000 742 ns/op
BenchmarkAdd/mostly_existing-4 10000000 153 ns/op
BenchmarkGet/mostly_found-4 10000000 222 ns/op
BenchmarkGet/mostly_not_found-4 20000000 143 ns/op
BenchmarkRemove/mostly_found-4 10000000 246 ns/op
BenchmarkRemove/mostly_not_found-4 20000000 142 ns/op
Getting and removing elements is in the same ballpark as accessing a built-in Go map. Getting an existing item adds a bit of overhead on top of accessing the map because it also needs to move the element to the front of the list, but that’s a very fast pointer operation so it’s not that bad.
Adding has to check for an existing item as well as adding/moving the list element, so it’s relatively slower, but still good enough for my immediate needs.
There is a big problem though. This implementation is not at all safe for concurrent use. Sure, package users could protect it with a sync.Mutex but we may want to hide the complexity from them.
The (once again naïve) solution is to protect the list and map accesses with a sync.Mutex of our own.
Concurrent-safe Naïve LRU
Not much needs to be changed to make our naïve implementation safe for concurrent use (full implementation on Github.). We add a mutex —
type LRU struct {
cap int // the max number of items to hold
sync.Mutex // protects the idem and list
idx map[interface{}]*list.Element // the index for our list
l *list.List // the actual list holding the data
}
And at the top of every exported entrypoint we do something like —
func (l *LRU) Add(k, v interface{}) {
l.Lock()
defer l.Unlock()
l.lazyInit()
Et voilà, we’re safe for concurrent use. But let’s see what the benchmarks tell us.
BenchmarkAdd/mostly_new-4 2000000 819 ns/op
BenchmarkAdd/mostly_existing-4 10000000 200 ns/op
BenchmarkGet/mostly_found-4 10000000 277 ns/op
BenchmarkGet/mostly_not_found-4 10000000 219 ns/op
BenchmarkRemove/mostly_found-4 5000000 325 ns/op
BenchmarkRemove/mostly_not_found-4 10000000 220 ns/op
Overall the code is slightly slower due to the (for now minimal) overhead of the mutex operations. However, although we are safe for concurrent use, we’re not really taking advantage of it, the entire code is completely sequential. An Add will prevent anyone from getting an item. Even a call to Len() locks everyone out.
This will be clear if we modify the tests to run in parallel.
BenchmarkAddParallel/mostly_new-4 1000000 1040 ns/op
BenchmarkAddParallel/mostly_existing-4 5000000 433 ns/op
BenchmarkGetParallel/mostly_found-4 5000000 293 ns/op
BenchmarkGetParallel/mostly_not_found-4 10000000 289 ns/op
BenchmarkRemoveParallel/mostly_found-4 5000000 305 ns/op
BenchmarkRemoveParallel/mostly_not_found-4 10000000 291 ns/op
On average, the calls will take longer because most of the times they’ll have to wait for another operation to finish and free the mutex.
In the next post, we’ll try and cut on the locking considerably.