quick_cache/lib.rs
1//! Lightweight, high performance concurrent cache. It allows very fast access to the cached items
2//! with little overhead compared to a plain concurrent hash table. No allocations are ever performed
3//! unless the cache internal state table needs growing (which will eventually stabilize).
4//!
5//! # Eviction policy
6//!
7//! The current eviction policy is a modified version of the Clock-PRO algorithm, very similar to the
8//! later published S3-FIFO algorithm. It's "scan resistent" and provides high hit rates,
9//! significantly better than a LRU eviction policy and comparable to other state-of-the art algorithms
10//! like W-TinyLFU.
11//!
12//! # Thread safety and Concurrency
13//!
14//! Both `sync` (thread-safe) and `unsync` (non thread-safe) implementations are provided. The latter
15//! offers slightly better performance when thread safety is not required.
16//!
17//! # Equivalent keys
18//!
19//! The cache uses the [`Equivalent`](https://docs.rs/equivalent/1.0.1/equivalent/trait.Equivalent.html) trait
20//! for gets/removals. It can help work around the `Borrow` limitations.
21//! For example, if the cache key is a tuple `(K, Q)`, you wouldn't be able to access such keys without
22//! building a `&(K, Q)` and thus potentially cloning `K` and/or `Q`.
23//!
24//! # User defined weight
25//!
26//! By implementing the [Weighter] trait the user can define different weights for each cache entry.
27//!
28//! # Atomic operations
29//!
30//! By using the `get_or_insert` or `get_value_or_guard` family of functions (both sync and async variants
31//! are available, they can be mix and matched) the user can coordinate the insertion of entries, so only
32//! one value is "computed" and inserted after a cache miss.
33//!
34//! The `entry` family of functions provide a closure-based API for atomically
35//! inspecting and acting on existing entries (keep, remove, or replace) while also coordinating
36//! insertion on cache misses.
37//!
38//! # Lifecycle hooks
39//!
40//! A user can optionally provide a custom [Lifecycle] implementation to hook into the lifecycle of cache entries.
41//!
42//! Example use cases:
43//! * item pinning, so even if the item occupies weight but isn't allowed to be evicted
44//! * send evicted items to a channel, achieving the equivalent to an eviction listener feature.
45//! * zero out item weights so they are left in the cache instead of evicted.
46//!
47//! # Approximate memory usage
48//!
49//! The memory overhead per entry is `21` bytes.
50//!
51//! The memory usage of the cache data structures can be estimated as:
52//! `(size_of::<K>() + size_of::<V>() + 21) * (length * 1.5).next_power_of_two()`
53//!
54//! Actual memory usage may vary depending on the cache options and the key and value types, which can have external
55//! allocations (e.g. `String`, `Vec`, etc.). The above formula only accounts for the cache's data structures.
56//!
57//! The `1.5` value in the formula above results from `1 + G`, where `G` is the configured ghost allocation specified
58//! in [`OptionsBuilder::ghost_allocation`], which is `0.5` by default.
59//!
60//! # Hasher
61//!
62//! By default the crate uses [ahash](https://crates.io/crates/ahash), which is enabled (by default) via
63//! a crate feature with the same name. If the `ahash` feature is disabled the crate defaults to the std lib
64//! implementation instead (currently Siphash13). Note that a custom hasher can also be provided if desirable.
65//!
66//! # Synchronization primitives
67//!
68//! By default the crate uses [parking_lot](https://crates.io/crates/parking_lot), which is enabled (by default) via
69//! a crate feature with the same name. If `parking_lot` is disabled and `sharded-lock` is enabled, the crate uses
70//! [`crossbeam_utils::sync::ShardedLock`](https://docs.rs/crossbeam-utils/latest/crossbeam_utils/sync/struct.ShardedLock.html)
71//! from [crossbeam-utils](https://crates.io/crates/crossbeam-utils) instead. If both are disabled the crate defaults
72//! to the std lib implementation. The `parking_lot` and `sharded-lock` features are mutually exclusive.
73//!
74//! # Cargo Features
75//!
76//! | Feature | Default | Description |
77//! |---------|---------|-------------|
78//! | `ahash` | ✓ | Use [ahash](https://crates.io/crates/ahash) as the default hasher. When disabled, falls back to std lib's `RandomState` (currently SipHash-1-3). |
79//! | `parking_lot` | ✓ | Use [parking_lot](https://crates.io/crates/parking_lot) for synchronization primitives. Mutually exclusive with `sharded-lock`. |
80//! | `sharded-lock` | | Use [`crossbeam_utils::sync::ShardedLock`](https://docs.rs/crossbeam-utils/latest/crossbeam_utils/sync/struct.ShardedLock.html) for synchronization primitives. Mutually exclusive with `parking_lot`. |
81//! | `shuttle` | | Enable [shuttle](https://crates.io/crates/shuttle) testing support for concurrency testing. |
82//! | `stats` | | Enable cache statistics tracking via the `hits()` and `misses()` methods. |
83#![allow(clippy::type_complexity)]
84#![cfg_attr(docsrs, feature(doc_cfg))]
85
86#[cfg(all(feature = "parking_lot", feature = "sharded-lock"))]
87compile_error!("features `parking_lot` and `sharded-lock` are mutually exclusive");
88
89#[cfg(not(fuzzing))]
90mod linked_slab;
91#[cfg(fuzzing)]
92pub mod linked_slab;
93mod options;
94#[cfg(not(feature = "shuttle"))]
95mod rw_lock;
96mod shard;
97mod shim;
98/// Concurrent cache variants that can be used from multiple threads.
99pub mod sync;
100mod sync_placeholder;
101/// Non-concurrent cache variants.
102pub mod unsync;
103pub use equivalent::Equivalent;
104
105#[cfg(all(test, feature = "shuttle"))]
106mod shuttle_tests;
107
108pub use options::{Options, OptionsBuilder};
109
110#[cfg(feature = "ahash")]
111pub type DefaultHashBuilder = ahash::RandomState;
112#[cfg(not(feature = "ahash"))]
113pub type DefaultHashBuilder = std::collections::hash_map::RandomState;
114
115/// Defines the weight of a cache entry.
116///
117/// # Example
118///
119/// ```
120/// use quick_cache::{sync::Cache, Weighter};
121///
122/// #[derive(Clone)]
123/// struct StringWeighter;
124///
125/// impl Weighter<u64, String> for StringWeighter {
126/// fn weight(&self, _key: &u64, val: &String) -> u64 {
127/// // Be cautious about zero weights!
128/// val.len() as u64
129/// }
130/// }
131///
132/// let cache = Cache::with_weighter(100, 100_000, StringWeighter);
133/// cache.insert(1, "1".to_string());
134/// ```
135pub trait Weighter<Key, Val> {
136 /// Returns the weight of the cache item.
137 ///
138 /// For performance reasons, this function should be trivially cheap as
139 /// it's called during the cache eviction routine.
140 /// If weight is expensive to calculate, consider caching it alongside the value.
141 ///
142 /// Zero (0) weight items are allowed and will be ignored when looking for eviction
143 /// candidates. Such items can only be manually removed or overwritten.
144 ///
145 /// Note that it's undefined behavior for a cache item to change its weight.
146 /// The only exception to this is when Lifecycle::before_evict is called.
147 ///
148 /// It's also undefined behavior in release mode if the summing of weights overflows,
149 /// although this is unlikely to be a problem in practice.
150 fn weight(&self, key: &Key, val: &Val) -> u64;
151}
152
153/// Each cache entry weights exactly `1` unit of weight.
154#[derive(Debug, Clone, Default)]
155pub struct UnitWeighter;
156
157impl<Key, Val> Weighter<Key, Val> for UnitWeighter {
158 #[inline]
159 fn weight(&self, _key: &Key, _val: &Val) -> u64 {
160 1
161 }
162}
163
164/// Hooks into the lifetime of the cache items.
165///
166/// The functions should be small and very fast, otherwise the cache performance might be negatively affected.
167pub trait Lifecycle<Key, Val> {
168 type RequestState;
169
170 /// Returns whether the item is pinned. Items that are pinned can't be evicted.
171 /// Note that a pinned item can still be replaced with get_mut, insert, replace and similar APIs.
172 ///
173 /// Compared to zero (0) weight items, pinned items still consume (non-zero) weight even if they can't
174 /// be evicted. Furthermore, zero (0) weight items are separated from the other entries, which allows
175 /// having a large number of them without impacting performance, but moving them in/out or the evictable
176 /// section has a small cost. Pinning on the other hand doesn't separate entries, so during eviction
177 /// the cache may visit pinned entries but will ignore them.
178 #[allow(unused_variables)]
179 #[inline]
180 fn is_pinned(&self, key: &Key, val: &Val) -> bool {
181 false
182 }
183
184 /// Called before the insert request starts, e.g.: insert, replace.
185 fn begin_request(&self) -> Self::RequestState;
186
187 /// Called when a cache item is about to be evicted.
188 /// Note that value replacement (e.g. insertions for the same key) won't call this method.
189 ///
190 /// This is the only time the item can change its weight. If the item weight becomes zero (0) it
191 /// will be left in the cache, otherwise it'll still be removed. Zero (0) weight items aren't evictable
192 /// and are kept separated from the other items so it's possible to have a large number of them without
193 /// negatively affecting eviction performance.
194 #[allow(unused_variables)]
195 #[inline]
196 fn before_evict(&self, state: &mut Self::RequestState, key: &Key, val: &mut Val) {}
197
198 /// Called when an item is evicted.
199 ///
200 /// To distinguish evictions from the hot vs cold queues, override
201 /// [`Lifecycle::on_evict_hot`] and/or [`Lifecycle::on_evict_cold`] instead;
202 /// they default to delegating here.
203 ///
204 /// If none of `on_evict`, `on_evict_hot`, or `on_evict_cold` is overridden,
205 /// eviction notifications are silently dropped.
206 ///
207 /// Note: items that are rejected without ever being admitted to the cache
208 /// (oversized inserts and oversized placeholder values) are routed through
209 /// [`Lifecycle::on_evict_cold`], which by default reaches this method.
210 #[allow(unused_variables)]
211 #[inline]
212 fn on_evict(&self, state: &mut Self::RequestState, key: Key, val: Val) {}
213
214 /// Called when an item is evicted from the cold queue.
215 ///
216 /// By default delegates to [`Lifecycle::on_evict`].
217 ///
218 /// Note: items that are rejected without ever being admitted to the cache
219 /// (oversized inserts and oversized placeholder values) are also reported
220 /// via this method.
221 #[inline]
222 fn on_evict_cold(&self, state: &mut Self::RequestState, key: Key, val: Val) {
223 self.on_evict(state, key, val)
224 }
225
226 /// Called when an item is evicted from the hot queue.
227 ///
228 /// By default delegates to [`Lifecycle::on_evict`].
229 ///
230 /// Note: rejected (never-admitted) items are reported via
231 /// [`Lifecycle::on_evict_cold`], not this method.
232 #[inline]
233 fn on_evict_hot(&self, state: &mut Self::RequestState, key: Key, val: Val) {
234 self.on_evict(state, key, val)
235 }
236
237 /// Called after a request finishes, e.g.: insert, replace.
238 ///
239 /// Notes:
240 /// This will _not_ be called when using `_with_lifecycle` apis, which will return the RequestState instead.
241 /// This will _not_ be called if the request errored (e.g. a replace didn't find a value to replace).
242 /// If needed, Drop for RequestState can be used to detect these cases.
243 #[allow(unused_variables)]
244 #[inline]
245 fn end_request(&self, state: Self::RequestState) {}
246}
247
248/// The memory used by the cache
249///
250/// This struct exposes some implementation details, may change in the future
251#[non_exhaustive]
252#[derive(Debug, Copy, Clone)]
253pub struct MemoryUsed {
254 pub entries: usize,
255 pub map: usize,
256}
257
258impl MemoryUsed {
259 pub fn total(&self) -> usize {
260 self.entries + self.map
261 }
262}
263
264#[cfg(test)]
265mod tests {
266 use std::{
267 hash::Hash,
268 sync::{atomic::AtomicUsize, Arc},
269 time::Duration,
270 };
271
272 use super::*;
273 #[derive(Clone)]
274 struct StringWeighter;
275
276 impl Weighter<u64, String> for StringWeighter {
277 fn weight(&self, _key: &u64, val: &String) -> u64 {
278 val.len() as u64
279 }
280 }
281
282 #[test]
283 fn test_new() {
284 sync::Cache::<(u64, u64), u64>::new(0);
285 sync::Cache::<(u64, u64), u64>::new(1);
286 sync::Cache::<(u64, u64), u64>::new(2);
287 sync::Cache::<(u64, u64), u64>::new(3);
288 sync::Cache::<(u64, u64), u64>::new(usize::MAX);
289 sync::Cache::<u64, u64>::new(0);
290 sync::Cache::<u64, u64>::new(1);
291 sync::Cache::<u64, u64>::new(2);
292 sync::Cache::<u64, u64>::new(3);
293 sync::Cache::<u64, u64>::new(usize::MAX);
294 }
295
296 #[test]
297 fn test_capacity_one() {
298 // Sync cache with capacity 1 should be able to hold one item
299 let cache = sync::Cache::<u64, u64>::new(1);
300 cache.insert(1, 10);
301 assert_eq!(cache.get(&1), Some(10));
302 // Inserting a second key should evict the first
303 cache.insert(2, 20);
304 assert_eq!(cache.get(&2), Some(20));
305 assert_eq!(cache.get(&1), None);
306
307 // Unsync cache with capacity 1 should also work
308 let mut cache = unsync::Cache::<u64, u64>::new(1);
309 cache.insert(1, 10);
310 assert_eq!(cache.get(&1), Some(&10));
311 cache.insert(2, 20);
312 assert_eq!(cache.get(&2), Some(&20));
313 assert_eq!(cache.get(&1), None);
314
315 // Capacity 0 should store nothing
316 let cache = sync::Cache::<u64, u64>::new(0);
317 cache.insert(1, 10);
318 assert_eq!(cache.get(&1), None);
319 }
320
321 #[test]
322 fn test_custom_cost() {
323 let cache = sync::Cache::with_weighter(100, 100_000, StringWeighter);
324 cache.insert(1, "1".to_string());
325 cache.insert(54, "54".to_string());
326 cache.insert(1000, "1000".to_string());
327 assert_eq!(cache.get(&1000).unwrap(), "1000");
328 }
329
330 #[test]
331 fn test_change_get_mut_change_weight() {
332 let mut cache = unsync::Cache::with_weighter(100, 100_000, StringWeighter);
333 cache.insert(1, "1".to_string());
334 assert_eq!(cache.get(&1).unwrap(), "1");
335 assert_eq!(cache.weight(), 1);
336 let _old = {
337 cache
338 .get_mut(&1)
339 .map(|mut v| std::mem::replace(&mut *v, "11".to_string()))
340 };
341 let _old = {
342 cache
343 .get_mut(&1)
344 .map(|mut v| std::mem::replace(&mut *v, "".to_string()))
345 };
346 assert_eq!(cache.get(&1).unwrap(), "");
347 assert_eq!(cache.weight(), 0);
348 cache.validate(false);
349 }
350
351 #[derive(Debug, Hash)]
352 pub struct Pair<A, B>(pub A, pub B);
353
354 impl<A, B, C, D> PartialEq<(A, B)> for Pair<C, D>
355 where
356 C: PartialEq<A>,
357 D: PartialEq<B>,
358 {
359 fn eq(&self, rhs: &(A, B)) -> bool {
360 self.0 == rhs.0 && self.1 == rhs.1
361 }
362 }
363
364 impl<A, B, X> Equivalent<X> for Pair<A, B>
365 where
366 Pair<A, B>: PartialEq<X>,
367 A: Hash + Eq,
368 B: Hash + Eq,
369 {
370 fn equivalent(&self, other: &X) -> bool {
371 *self == *other
372 }
373 }
374
375 #[test]
376 fn test_equivalent() {
377 let mut cache = unsync::Cache::new(5);
378 cache.insert(("square".to_string(), 2022), "blue".to_string());
379 cache.insert(("square".to_string(), 2023), "black".to_string());
380 assert_eq!(cache.get(&Pair("square", 2022)).unwrap(), "blue");
381 }
382
383 #[test]
384 fn test_borrow_keys() {
385 let cache = sync::Cache::<(Vec<u8>, Vec<u8>), u64>::new(0);
386 cache.get(&Pair(&b""[..], &b""[..]));
387 let cache = sync::Cache::<(String, String), u64>::new(0);
388 cache.get(&Pair("", ""));
389 }
390
391 #[test]
392 #[cfg_attr(miri, ignore)]
393 fn test_get_or_insert() {
394 use rand::prelude::*;
395 for _i in 0..2000 {
396 dbg!(_i);
397 let mut entered = AtomicUsize::default();
398 let cache = sync::Cache::<(u64, u64), u64>::new(100);
399 const THREADS: usize = 100;
400 let wg = std::sync::Barrier::new(THREADS);
401 let solve_at = rand::rng().random_range(0..THREADS);
402 std::thread::scope(|s| {
403 for _ in 0..THREADS {
404 s.spawn(|| {
405 wg.wait();
406 let result = cache.get_or_insert_with(&(1, 1), || {
407 let before = entered.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
408 if before == solve_at {
409 Ok(1)
410 } else {
411 Err(())
412 }
413 });
414 assert!(matches!(result, Ok(1) | Err(())));
415 });
416 }
417 });
418 assert_eq!(*entered.get_mut(), solve_at + 1);
419 }
420 }
421
422 #[test]
423 fn test_get_or_insert_unsync() {
424 let mut cache = unsync::Cache::<u64, u64>::new(100);
425 let guard = cache.get_ref_or_guard(&0).unwrap_err();
426 guard.insert(0);
427 assert_eq!(cache.get_ref_or_guard(&0).ok().copied(), Some(0));
428 let guard = cache.get_mut_or_guard(&1).err().unwrap();
429 guard.insert(1);
430 let v = *cache.get_mut_or_guard(&1).ok().unwrap().unwrap();
431 assert_eq!(v, 1);
432 let result = cache.get_or_insert_with::<_, ()>(&0, || panic!());
433 assert_eq!(result, Ok(Some(&0)));
434 let result = cache.get_or_insert_with::<_, ()>(&1, || panic!());
435 assert_eq!(result, Ok(Some(&1)));
436 let result = cache.get_or_insert_with::<_, ()>(&3, || Ok(3));
437 assert_eq!(result, Ok(Some(&3)));
438 let result = cache.get_or_insert_with::<_, ()>(&4, || Err(()));
439 assert_eq!(result, Err(()));
440 }
441
442 #[tokio::test]
443 async fn test_get_or_insert_sync() {
444 use crate::sync::*;
445 let cache = sync::Cache::<u64, u64>::new(100);
446 let GuardResult::Guard(guard) = cache.get_value_or_guard(&0, None) else {
447 panic!();
448 };
449 guard.insert(0).unwrap();
450 let GuardResult::Value(v) = cache.get_value_or_guard(&0, None) else {
451 panic!();
452 };
453 assert_eq!(v, 0);
454 let Err(guard) = cache.get_value_or_guard_async(&1).await else {
455 panic!();
456 };
457 guard.insert(1).unwrap();
458 let Ok(v) = cache.get_value_or_guard_async(&1).await else {
459 panic!();
460 };
461 assert_eq!(v, 1);
462
463 let result = cache.get_or_insert_with::<_, ()>(&0, || panic!());
464 assert_eq!(result, Ok(0));
465 let result = cache.get_or_insert_with::<_, ()>(&3, || Ok(3));
466 assert_eq!(result, Ok(3));
467 let result = cache.get_or_insert_with::<_, ()>(&4, || Err(()));
468 assert_eq!(result, Err(()));
469 let result = cache
470 .get_or_insert_async::<_, ()>(&0, async { panic!() })
471 .await;
472 assert_eq!(result, Ok(0));
473 let result = cache
474 .get_or_insert_async::<_, ()>(&4, async { Err(()) })
475 .await;
476 assert_eq!(result, Err(()));
477 let result = cache
478 .get_or_insert_async::<_, ()>(&4, async { Ok(4) })
479 .await;
480 assert_eq!(result, Ok(4));
481 }
482
483 #[test]
484 fn test_retain_unsync() {
485 let mut cache = unsync::Cache::<u64, u64>::new(100);
486 let ranges = 0..10;
487 for i in ranges.clone() {
488 let guard = cache.get_ref_or_guard(&i).unwrap_err();
489 guard.insert(i);
490 assert_eq!(cache.get_ref_or_guard(&i).ok().copied(), Some(i));
491 }
492 let small = 3;
493 cache.retain(|&key, &val| val > small && key > small);
494 for i in ranges.clone() {
495 let actual = cache.get(&i);
496 if i > small {
497 assert!(actual.is_some());
498 assert_eq!(*actual.unwrap(), i);
499 } else {
500 assert!(actual.is_none());
501 }
502 }
503 let big = 7;
504 cache.retain(|&key, &val| val < big && key < big);
505 for i in ranges {
506 let actual = cache.get(&i);
507 if i > small && i < big {
508 assert!(actual.is_some());
509 assert_eq!(*actual.unwrap(), i);
510 } else {
511 assert!(actual.is_none());
512 }
513 }
514 }
515
516 #[tokio::test]
517 async fn test_retain_sync() {
518 use crate::sync::*;
519 let cache = Cache::<u64, u64>::new(100);
520 let ranges = 0..10;
521 for i in ranges.clone() {
522 let GuardResult::Guard(guard) = cache.get_value_or_guard(&i, None) else {
523 panic!();
524 };
525 guard.insert(i).unwrap();
526 let GuardResult::Value(v) = cache.get_value_or_guard(&i, None) else {
527 panic!();
528 };
529 assert_eq!(v, i);
530 }
531 let small = 4;
532 cache.retain(|&key, &val| val > small && key > small);
533 for i in ranges.clone() {
534 let actual = cache.get(&i);
535 if i > small {
536 assert!(actual.is_some());
537 assert_eq!(actual.unwrap(), i);
538 } else {
539 assert!(actual.is_none());
540 }
541 }
542 let big = 8;
543 cache.retain(|&key, &val| val < big && key < big);
544 for i in ranges {
545 let actual = cache.get(&i);
546 if i > small && i < big {
547 assert!(actual.is_some());
548 assert_eq!(actual.unwrap(), i);
549 } else {
550 assert!(actual.is_none());
551 }
552 }
553 }
554
555 #[test]
556 #[cfg_attr(miri, ignore)]
557 fn test_value_or_guard() {
558 use crate::sync::*;
559 use rand::prelude::*;
560 for _i in 0..2000 {
561 dbg!(_i);
562 let mut entered = AtomicUsize::default();
563 let cache = sync::Cache::<(u64, u64), u64>::new(100);
564 const THREADS: usize = 100;
565 let wg = std::sync::Barrier::new(THREADS);
566 let solve_at = rand::rng().random_range(0..THREADS);
567 std::thread::scope(|s| {
568 for _ in 0..THREADS {
569 s.spawn(|| {
570 wg.wait();
571 loop {
572 match cache.get_value_or_guard(&(1, 1), Some(Duration::from_millis(1)))
573 {
574 GuardResult::Value(v) => assert_eq!(v, 1),
575 GuardResult::Guard(g) => {
576 let before =
577 entered.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
578 if before == solve_at {
579 g.insert(1).unwrap();
580 }
581 }
582 GuardResult::Timeout => continue,
583 }
584 break;
585 }
586 });
587 }
588 });
589 assert_eq!(*entered.get_mut(), solve_at + 1);
590 }
591 }
592
593 #[tokio::test(flavor = "multi_thread")]
594 #[cfg_attr(miri, ignore)]
595 async fn test_get_or_insert_async() {
596 use rand::prelude::*;
597 for _i in 0..5000 {
598 dbg!(_i);
599 let entered = Arc::new(AtomicUsize::default());
600 let cache = Arc::new(sync::Cache::<(u64, u64), u64>::new(100));
601 const TASKS: usize = 100;
602 let wg = Arc::new(tokio::sync::Barrier::new(TASKS));
603 let solve_at = rand::rng().random_range(0..TASKS);
604 let mut tasks = Vec::new();
605 for _ in 0..TASKS {
606 let cache = cache.clone();
607 let wg = wg.clone();
608 let entered = entered.clone();
609 let task = tokio::spawn(async move {
610 wg.wait().await;
611 let result = cache
612 .get_or_insert_async(&(1, 1), async {
613 let before = entered.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
614 if before == solve_at {
615 Ok(1)
616 } else {
617 Err(())
618 }
619 })
620 .await;
621 assert!(matches!(result, Ok(1) | Err(())));
622 });
623 tasks.push(task);
624 }
625 for task in tasks {
626 task.await.unwrap();
627 }
628 assert_eq!(cache.get(&(1, 1)), Some(1));
629 assert_eq!(
630 entered.load(std::sync::atomic::Ordering::Relaxed),
631 solve_at + 1
632 );
633 }
634 }
635
636 #[tokio::test(flavor = "multi_thread")]
637 #[cfg_attr(miri, ignore)]
638 async fn test_value_or_guard_async() {
639 use rand::prelude::*;
640 for _i in 0..5000 {
641 dbg!(_i);
642 let entered = Arc::new(AtomicUsize::default());
643 let cache = Arc::new(sync::Cache::<(u64, u64), u64>::new(100));
644 const TASKS: usize = 100;
645 let wg = Arc::new(tokio::sync::Barrier::new(TASKS));
646 let solve_at = rand::rng().random_range(0..TASKS);
647 let mut tasks = Vec::new();
648 for _ in 0..TASKS {
649 let cache = cache.clone();
650 let wg = wg.clone();
651 let entered = entered.clone();
652 let task = tokio::spawn(async move {
653 wg.wait().await;
654 loop {
655 match tokio::time::timeout(
656 Duration::from_millis(1),
657 cache.get_value_or_guard_async(&(1, 1)),
658 )
659 .await
660 {
661 Ok(Ok(r)) => assert_eq!(r, 1),
662 Ok(Err(g)) => {
663 let before =
664 entered.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
665 if before == solve_at {
666 g.insert(1).unwrap();
667 }
668 }
669 Err(_) => continue,
670 }
671 break;
672 }
673 });
674 tasks.push(task);
675 }
676 for task in tasks {
677 task.await.unwrap();
678 }
679 assert_eq!(cache.get(&(1, 1)), Some(1));
680 assert_eq!(
681 entered.load(std::sync::atomic::Ordering::Relaxed),
682 solve_at + 1
683 );
684 }
685 }
686}