lazylru/generic — Proving It
Way back in the long-forgotten days of June 2021, I put up a post about LazyLRU, a least-recently-used cache that focuses on reducing lock contention. The release of Go 1.18, and with it generics spurred a revisit of the library. Today I put out v0.2.0, which contains a submodule with a generic-enabled version of the cache.
A note about using the generic version
While many developers have been champing at the bit for the 1.18 release, the 2020 Go Developer Survey highlighted that very few organizations jump to every new release. It appears that ~90% of those who have some kind of cadence for their upgrades will be on a new release within 6 months. This release contains the string keys and interface values Go 1.17 and below version in the root module. There is also a generic module below it that contains the generic version.
Preserving the interface
Arguably the greatest strength of the Go ecosystem has been the promise of compatibility. In the spirit of that, the new generic versions of the LazyLRU cache are compatible with the old interface completely.
import (
"time"
lazylru "github.com/TriggerMail/lazylru/generic"
)lruOld := lazylru.New(10, time.Minute)
lruNew := lazylru.NewT[string, string](10, time.Minute)
The lruOld variable will contain a *lazylru.LazyLRU[string, interface{}]. That has exactly the same interface as the non-generic version. And like the old version, the caller will need to cast whatever is returned by Get() before using it. The lruNew version, however, will always return strings.
What this means is that all existing code should work without modification.
But why?
If channels are a sometimes food, then generics should be a special, once-in-a-blue-moon treat. Go went fifteen years without generics, ten years since 1.0 was released. Java SE5 brought generics ten years after the initial release; .NET 2.0 did it in four. In other words, you’d better have a good reason to bring generics into your code, especially in the public interface of a library.
A cleaner interface
It’s hard to imagine a case when a caller will be satisfied with interface{}. The caller is pretty much guaranteed to want something else. This is a sanitized excerpt from some production code using the previous version of LazyLRU:
func Fetch(hashKey string) (*customers_pb.GetResponse, error) {
if ires, ok := ls.cache.Get(hashKey); ok {
if res, ok := ires.(*customers_pb.GetResponse); ok {
return res, nil
}
}
// fetch from underlying source
}And this is the same code using the generic version:
func Fetch(hashKey string) (*customers_pb.GetResponse, error) {
if res, ok := ls.cache.Get(hashKey); ok {
return res, nil
}
// fetch from underlying source
}That seems nicer.
More functionality
A nice feature of Go is that maps can be keyed on most types. Before generics, it was next to impossible to create containers that gave the caller a choice of types. There are some packages, like container/heap, that use function calls over other containers to get the job done, but still end up returning interface{}.
Using the comparable type constraint on keys and no constraint on values gives us a lot of flexibility. Just like with maps and slices, the type is declared when making the object and the compiler does the rest.
// factory method
NewT[K comparable, V any](maxItems int, ttl time.Duration) *LazyLRU[K, V] {}// functions on *LazyLRU[K, V]
Get(key K) (V, bool)
Set(key K, value V)
MGet(keys ...K) map[K]V
MSet(keys []K, values []V) error
By using the generic interface, it’s possible to build on top of the cache in ways that would have been really ugly. As an example, I was able to implement sharding on top of the LazyLRU cache, giving the caller the ability to provide a number of shards and a sharding function (func (key K) int64)). We don’t lose flexibility in the keys, don’t have to cast to interface{}, and the compiler can make sure that we do the right thing.
Higher performance
100% Read
------------------------------------------------
flavor time bytes alloc num. alloc
---------- ------------- ----------- -----------
interface 137.1 ns/op 0 B/op 0 allocs/op
generic 140.8 ns/op 0 B/op 0 allocs/op100% Write
------------------------------------------------
flavor time bytes alloc num. alloc
---------- ------------- ----------- -----------
interface 175.7 ns/op 32 B/op 2 allocs/op
generic 143.7 ns/op 8 B/op 1 allocs/op
While the interface is cleaner on the read path, the performance difference between the interface-based version and the generic version on the read path is within the margin of error. The cost of that extra casting, the extra conditional, was zero. This was surprising, but the benchmarks don’t lie. The numbers below were recorded on the 100% read trial with string for keys and []int for values. There were no bytes allocated, so that has been removed for simplicity. The interface version is even a little faster!
However, when you move into writes, things get more interesting. The generic version is not only 18% faster, the allocations are much lower.
The fact that we’re using []int as the type of our values is a little strange. The reason for it is that plain int values resulted in no difference at all. Even creating pointers to structs didn’t make much difference.
100% Read
----------------------------------------------------
flavor struct time bytes alloc num. alloc
--------- ------ ----------- ----------- -----------
interface array 70.88 ns/op 0 B/op 0 allocs/op
generic array 71.11 ns/op 0 B/op 0 allocs/op
interface struct 69.63 ns/op 0 B/op 0 allocs/op
generic struct 71.27 ns/op 0 B/op 0 allocs/op
interface value 77.60 ns/op 0 B/op 0 allocs/op
generic value 71.20 ns/op 0 B/op 0 allocs/op100% Write
----------------------------------------------------
flavor struct time bytes alloc num. alloc
--------- ------ ----------- ----------- -----------
interface array 172.9 ns/op 32 B/op 2 allocs/op
generic array 145.4 ns/op 8 B/op 1 allocs/op
interface struct 173.6 ns/op 48 B/op 1 allocs/op
generic struct 167.9 ns/op 48 B/op 1 allocs/op
interface value 141.9 ns/op 0 B/op 0 allocs/op
generic value 143.7 ns/op 0 B/op 0 allocs/op
The lesson to draw here is that the interface{} codepaths in the Go runtime are really well optimized. You may have a performance win, you may not.
Conclusions
- Generics in Go are limited, but still powerful. Think about your users before choosing to use them
- I was expecting a bigger performance win on the read side. As is always the case with performance-sensitive code: measure, measure, measure
- Releasing generic-enabled open-source code is going to be an interesting policy question. Modules are great, but the “2.0 problem” has lead to some strange choices
Is this your idea of a good time? Come work with me and other great engineers at Bluecore!
