container/lru: Implement type safe generic LRUs.#3359
Merged
davecgh merged 2 commits intodecred:masterfrom Jun 12, 2024
Merged
Conversation
82134cd to
05e5a91
Compare
jholdstock
reviewed
Jun 11, 2024
Member
jholdstock
left a comment
There was a problem hiding this comment.
I havent reviewed everything yet but dropping some notes/questions what I've seen so far.
0c65a34 to
e2332ab
Compare
jrick
approved these changes
Jun 11, 2024
e2332ab to
0749193
Compare
jholdstock
reviewed
Jun 12, 2024
0749193 to
13b57f8
Compare
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.
13b57f8 to
b7d7c5f
Compare
jholdstock
approved these changes
Jun 12, 2024
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This implements a new module named
container/lruwhich 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
Setand is tailored towards use cases that involve storing a distinct collection of items with existence testing. The other one is namedMapand 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:
The following shows the performance versus the old interface-based LRU for the overlapping functionality (
KVCache->Map,Cache->Set):