LFU Cache

LFU cache in Go offering O(1) Get and Insert outlined here.

Install

go get -u github.com/mtchavez/lfu

Usage

package main

import (
    "fmt"
    "github.com/mtchavez/lfu"
)

func main() {
    cache := lfu.NewLFU()

    // Insert
    cache.Insert(42, []byte("user:42:user@example.com"))

    // Insert existing key
    success, err := cache.Insert(42, "Nope")
    if !success {
        fmt.Println("Error inserting:", err)
    }

    var data interface{}
    var e error
    // Get
    data, e = cache.Get(42)
    fmt.Println("Data for 42 is", data)

    // Get not found
    data, e = cache.Get(987654321)
    if e != nil {
        fmt.Println("Error on get:", e)
    }
}

Tests

go test --cover

Benhcmarks

Get and insert methods are benchmarked. Results from OS X with a 2.3 GHz Intel Core i7 on go version go1.8.3 darwin/amd64

# Updated: 2017-08-15

BenchmarkInsert-8                1000000              1860 ns/op
BenchmarkParallelInsert-8        1000000              1861 ns/op
BenchmarkGet_EmptyCache-8        5000000               362 ns/op
BenchmarkGet_AllMisses-8         3000000               732 ns/op
BenchmarkGet_AllHits-8           1000000              1417 ns/op
BenchmarkParallelGet-8           2000000              1405 ns/op

TODO

• Some kind of eviction