container/lru: Implement type safe generic LRUs.

[davecgh]

This implements a new module named container/lru which provides two efficient and full-featured generic least recently used (LRU) data structures with additional support for optional configurable per-item expiration timeouts via a time to live (TTL) mechanism.

As compared to the existing module that this intends to replace, this new implementation makes use of generics introduced in Go 1.18 in order to provide full type safety and avoid forced allocations that the previous implementation based on interfaces required.

Both implementations are safe for use in multi-threaded (concurrent) workloads and exhibit nearly early O(1) lookups, inserts, and deletions with no additional heap allocations beyond the stored items.

As is one of the defining characteristics for LRU data structures, both are limited to a configurable maximum number of items with eviction for the least recently used entry when the limit is exceeded.

One of the new data structures is named Set and is tailored towards use cases that involve storing a distinct collection of items with existence testing. The other one is named Map and is aimed at use cases that require caching and retrieving values by key.

Both implementations support optional default TTLs for item expiration as well as provide the option to override the default TTL on a per-item basis.

An efficient lazy removal scheme is used such that expired items are periodically removed when items are added or updated. This approach allows for efficient amortized removal of expired items without the need for additional background tasks, timers or heap allocations.

The following shows the performance of the new LRU map and set:

MapPutNoExp       10619336   108.6 ns/op   0 B/op   0 allocs/op
MapPutWithExp     10065508   110.2 ns/op   0 B/op   0 allocs/op
MapGet            28248453    41.2 ns/op   0 B/op   0 allocs/op
MapExists         33551979    34.3 ns/op   0 B/op   0 allocs/op
MapPeek           29699367    37.6 ns/op   0 B/op   0 allocs/op
SetPutNoExp       10343293   109.7 ns/op   0 B/op   0 allocs/op
SetPutWithExp     10357228   110.1 ns/op   0 B/op   0 allocs/op
SetContains       28183766    41.2 ns/op   0 B/op   0 allocs/op
SetExists         34581334    34.6 ns/op   0 B/op   0 allocs/op

The following shows the performance versus the old interface-based LRU for the overlapping functionality (KVCache -> Map, Cache -> Set):

name            old time/op    new time/op    delta
--------------------------------------------------------------------
MapPutNoExp     157.0ns ± 1%   108.0ns ± 2%   -31.06%  (p=0.008 n=5+5)
MapGet           46.2ns ± 1%   40.9ns ± 1%    -11.51%  (p=0.008 n=5+5)
MapContains      45.1ns ± 1%   34.2ns ± 2%    -24.24%  (p=0.008 n=5+5)
SetPutNoExp     145.0ns ± 2%   109.0ns ± 2%   -24.91%  (p=0.008 n=5+5)
SetContains      44.3ns ± 2%   41.5ns ± 3%     -6.50%  (p=0.016 n=5+5)

name            old alloc/op   new alloc/op   delta
--------------------------------------------------------------------
MapPutNoExp     16.0B ± 0%     0.0B            -100.00%  (p=0.008 n=5+5)
MapGet          0.00B          0.00B               ~     (all equal)
MapContains     0.00B          0.00B               ~     (all equal)
SetPutNoExp     8.00B ± 0%     0.00B           -100.00%  (p=0.008 n=5+5)
SetContains     0.00B          0.00B               ~     (all equal)

name            old allocs/op  new allocs/op  delta
--------------------------------------------------------------------
MapPutNoExp     2.00 ± 0%      0.00           -100.00%  (p=0.008 n=5+5)
MapGet          0.00           0.00               ~     (all equal)
MapExists       0.00           0.00               ~     (all equal)
SetPutNoExp     1.00 ± 0%      0.00           -100.00%  (p=0.008 n=5+5)
SetContains     0.00           0.00               ~     (all equal)