dashcache/
lib.rs

1/*!
2A simple, highly concurrent cache for hash-consing values
3*/
4
5use ahash::RandomState;
6use dashmap::DashMap;
7use elysees::Arc;
8use std::borrow::Borrow;
9use std::fmt::{self, Debug, Formatter};
10use std::hash::{BuildHasher, Hash};
11
12pub mod arr;
13
14/// An object which can be garbage collected
15pub trait CanCollect {
16    /// Is this handle unique or, if weak references are allowed, destroyed
17    #[inline(always)]
18    fn can_collect(&self) -> bool {
19        false
20    }
21    /// Are there two *strong* copies or less of this handle?
22    #[inline(always)]
23    fn can_collect_clone(&self) -> bool {
24        self.can_collect()
25    }
26}
27
28/// A container which can be used to cache values of type `T`
29pub trait Caches<T: ?Sized>: Hash + Eq + Clone + CanCollect {
30    /// Get a reference to the cached value of type `T`
31    fn cached(&self) -> &T;
32}
33
34/// A gloabl cache implementation
35pub trait GlobalCache {
36    /// The cache entry type
37    type Entry;
38    /**
39    Compute how many items are in a given cache.
40
41    # Example
42    ```rust
43    use dashcache::{GlobalCache, DashCache};
44    use elysees::Arc;
45    let int_cache = DashCache::<Arc<u64>>::new();
46    assert_eq!(int_cache.len(), 0);
47    int_cache.cache(10);
48    assert_eq!(int_cache.len(), 1);
49    int_cache.cache(20);
50    assert_eq!(int_cache.len(), 2);
51    // Since 10 is already in the cache, this is a no-op:
52    int_cache.cache(10);
53    assert_eq!(int_cache.len(), 2);
54    ```
55    */
56    fn len(&self) -> usize;
57    /**
58    Check if a cache is empty
59
60    # Example
61    ```rust
62    use dashcache::{GlobalCache, DashCache};
63    use elysees::Arc;
64    let int_cache = DashCache::<Arc<u64>>::new();
65    assert!(int_cache.is_empty());
66    int_cache.cache(10);
67    assert!(!int_cache.is_empty());
68    ```
69    */
70    fn is_empty(&self) -> bool;
71    /**
72    Attempt to cache a value. If already cached, return the corresponding entry.
73
74    # Example
75    ```rust
76    use dashcache::{GlobalCache, DashCache};
77    use elysees::Arc;
78    let int_cache = DashCache::<Arc<u64>>::new();
79
80    let cached_32 = int_cache.cache(32);
81    let arc_32 = Arc::new(32);
82    // These are different allocations!
83    assert!(!Arc::ptr_eq(&arc_32, &cached_32));
84
85    // We can use the cache to de-duplicate allocations
86    let dedup_32 = int_cache.cache(arc_32.clone());
87    assert!(Arc::ptr_eq(&dedup_32, &cached_32));
88
89    // Similarly, we'll get the same `Arc` if we insert the value again
90    let new_32 = int_cache.cache(32);
91    assert!(Arc::ptr_eq(&new_32, &cached_32));
92
93    // We can also insert an `Arc` from the get-go:
94    let arc_44 = Arc::new(44);
95    let cached_44 = int_cache.cache(arc_44.clone());
96    assert!(Arc::ptr_eq(&arc_44, &cached_44));
97    // New insertions are also deduplicated:
98    let dedup_44 = int_cache.cache(44);
99    assert!(Arc::ptr_eq(&arc_44, &dedup_44));
100    ```
101    */
102    fn cache<Q>(&self, value: Q) -> Self::Entry
103    where
104        Self::Entry: Borrow<Q>,
105        Q: Into<Self::Entry> + Hash + Eq;
106    /**
107    Attempt to garbage-collect this cache, returning how many elements were removed.
108    # Example
109    ```rust
110    use dashcache::{GlobalCache, DashCache};
111    use elysees::Arc;
112    let int_cache = DashCache::<Arc<u64>>::new();
113
114    // Let's stick 2 used values and 3 unused values into the cache:
115    let used_1 = int_cache.cache(77);
116    let used_2 = int_cache.cache(88);
117    int_cache.cache(99);
118    int_cache.cache(500);
119    int_cache.cache(81);
120    // We can see that at this point there are 5 things in the cache:
121    assert_eq!(int_cache.len(), 5);
122    // Now, let's garbage collect the cache, which should bring us down 3 things:
123    assert_eq!(int_cache.gc(), 3);
124    // And we have 2 things left:
125    assert_eq!(int_cache.len(), 2);
126    assert!(Arc::ptr_eq(&used_1, &int_cache.cache(77)));
127    assert!(Arc::ptr_eq(&used_2, &int_cache.cache(88)));
128    ```
129
130    # Implementation Notes
131    Note that this implements conservative GC, and in general it is perfectly well defined for this to be a no-op
132    */
133    #[inline(always)]
134    fn gc(&self) -> usize {
135        0
136    }
137    /**
138    Garbage collect a single entry if doing so would not break the hash-consing property due to uniqueness.
139    Returns the removed key on success, or Err(key) on failure
140
141    # Implementation notes
142    Note that this implements conservative GC, and in general it is perfectly well defined for this to be a no-op
143    */
144    #[inline(always)]
145    fn try_gc(&self, _key: &mut Self::Entry) -> Option<Self::Entry> {
146        None
147    }
148    /**
149    Garbage collect a single entry if doing so would not break the hash-consing property due to uniqueness.
150    Returns the removed key on success, or Err(key) on failure.
151
152    # Correctness
153    This function will cause the entry borrowed from to no longer be in the hash cache, so use with caution!
154
155    # Implementation notes
156    Note that this implements conservative GC, and in general it is perfectly well defined for this to be a no-op.
157    */
158    #[inline(always)]
159    fn try_gc_global(&self, _key: &Self::Entry) -> Option<Self::Entry> {
160        None
161    }
162}
163
164/// A global cache built around a `DashMap`
165pub struct DashCache<C, S = RandomState> {
166    cache: DashMap<C, (), S>,
167}
168
169impl<C: Hash + Eq> DashCache<C> {
170    /// Create a new, empty `DashCache`
171    #[inline]
172    pub fn new() -> DashCache<C> {
173        DashCache::default()
174    }
175}
176
177impl<C: Hash + Eq, S: BuildHasher + Clone + Default> Default for DashCache<C, S> {
178    #[inline]
179    fn default() -> DashCache<C, S> {
180        DashCache {
181            cache: DashMap::default(),
182        }
183    }
184}
185
186impl<C, S> From<DashMap<C, (), S>> for DashCache<C, S> {
187    #[inline]
188    fn from(cache: DashMap<C, (), S>) -> DashCache<C, S> {
189        DashCache { cache }
190    }
191}
192
193impl<C, S> Debug for DashCache<C, S>
194where
195    C: Debug + Hash + Eq,
196    S: BuildHasher + Clone,
197{
198    fn fmt(&self, fmt: &mut Formatter) -> Result<(), fmt::Error> {
199        fmt.debug_struct("DashCache")
200            .field("cache", &self.cache)
201            .finish()
202    }
203}
204
205impl<C, S> GlobalCache for DashCache<C, S>
206where
207    S: BuildHasher + Clone,
208    C: Hash + Eq + Clone + CanCollect,
209{
210    type Entry = C;
211    #[inline]
212    fn cache<Q>(&self, value: Q) -> C
213    where
214        C: Borrow<Q>,
215        Q: Into<C> + Hash + Eq,
216    {
217        // Read-lock first!
218        // TODO: profile and see if this actually even helps efficiency at all
219        if let Some(cached) = self.cache.get(&value) {
220            return cached.key().clone();
221        }
222        self.cache.entry(value.into()).or_default().key().clone()
223    }
224    #[inline]
225    fn gc(&self) -> usize {
226        let mut collected = 0;
227        self.cache.retain(|arc, _| {
228            if arc.can_collect() {
229                collected += 1;
230                false
231            } else {
232                true
233            }
234        });
235        collected
236    }
237    #[inline]
238    fn try_gc(&self, key: &mut Self::Entry) -> Option<Self::Entry> {
239        if key.can_collect_clone() {
240            return self.cache.remove(key).map(|(key, _)| key);
241        }
242        None
243    }
244    #[inline]
245    fn try_gc_global(&self, key: &Self::Entry) -> Option<Self::Entry> {
246        if key.can_collect_clone() {
247            return self.cache.remove(key).map(|(key, _)| key);
248        }
249        None
250    }
251    #[inline]
252    fn len(&self) -> usize {
253        self.cache.len()
254    }
255    #[inline]
256    fn is_empty(&self) -> bool {
257        self.cache.is_empty()
258    }
259}
260
261impl<T: ?Sized> CanCollect for Arc<T> {
262    /// Is this handle unique or, if weak references are allowed, destroyed
263    #[inline]
264    fn can_collect(&self) -> bool {
265        self.is_unique()
266    }
267    /// Are there two *strong* copies or less of this handle?
268    #[inline(always)]
269    fn can_collect_clone(&self) -> bool {
270        Arc::count(self, std::sync::atomic::Ordering::Acquire) <= 2
271    }
272}
273
274impl<T: Hash + Eq + ?Sized> Caches<T> for Arc<T> {
275    #[inline]
276    fn cached(&self) -> &T {
277        self
278    }
279}
280
281impl<T: ?Sized> CanCollect for std::sync::Arc<T> {
282    /// Is this handle unique or, if weak references are allowed, destroyed
283    #[inline]
284    fn can_collect(&self) -> bool {
285        std::sync::Arc::strong_count(self) == 1
286    }
287    /// Are there two *strong* copies or less of this handle?
288    #[inline(always)]
289    fn can_collect_clone(&self) -> bool {
290        std::sync::Arc::strong_count(self) <= 2
291    }
292}
293
294impl<T: Hash + Eq + ?Sized> Caches<T> for std::sync::Arc<T> {
295    #[inline]
296    fn cached(&self) -> &T {
297        self
298    }
299}
300
301impl<T: ?Sized> CanCollect for std::rc::Rc<T> {
302    /// Is this handle unique or, if weak references are allowed, destroyed
303    #[inline]
304    fn can_collect(&self) -> bool {
305        std::rc::Rc::strong_count(self) == 1
306    }
307    /// Are there two *strong* copies or less of this handle?
308    #[inline(always)]
309    fn can_collect_clone(&self) -> bool {
310        std::rc::Rc::strong_count(self) <= 2
311    }
312}
313
314impl<T: Hash + Eq + ?Sized> Caches<T> for std::rc::Rc<T> {
315    #[inline]
316    fn cached(&self) -> &T {
317        self
318    }
319}
dashcache/lib.rs

dashcache/
lib.rs
