Skip to content

container/lru: Implement type safe generic LRUs.#3359

Merged
davecgh merged 2 commits intodecred:masterfrom
davecgh:container_lru_introduce
Jun 12, 2024
Merged

container/lru: Implement type safe generic LRUs.#3359
davecgh merged 2 commits intodecred:masterfrom
davecgh:container_lru_introduce

Conversation

@davecgh
Copy link
Member

@davecgh davecgh commented Jun 10, 2024

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)

@davecgh davecgh added this to the 2.1.0 milestone Jun 10, 2024
@davecgh davecgh force-pushed the container_lru_introduce branch 5 times, most recently from 82134cd to 05e5a91 Compare June 11, 2024 06:46
Copy link
Member

@jholdstock jholdstock left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I havent reviewed everything yet but dropping some notes/questions what I've seen so far.

@davecgh davecgh force-pushed the container_lru_introduce branch 2 times, most recently from 0c65a34 to e2332ab Compare June 11, 2024 17:31
Copy link
Member

@jholdstock jholdstock left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Completed review. Code looking great overall, just some minor comment/doco things I spotted

@davecgh davecgh force-pushed the container_lru_introduce branch from 0749193 to 13b57f8 Compare June 12, 2024 16:01
davecgh added 2 commits June 12, 2024 11:21
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)
This updates the docs/README.md file, module hierarchy graphviz, and
module hierarchy diagram to reflect the new container/lru module.
@davecgh davecgh force-pushed the container_lru_introduce branch from 13b57f8 to b7d7c5f Compare June 12, 2024 16:21
@davecgh davecgh merged commit b7d7c5f into decred:master Jun 12, 2024
@davecgh davecgh deleted the container_lru_introduce branch June 12, 2024 17:03
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants