• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

bitfaster / BitFaster.Caching / 15982186126

30 Jun 2025 07:44PM UTC coverage: 99.089% (-0.08%) from 99.169%
15982186126

Pull #697

github

web-flow
Merge ae7ae9bfd into fa14abd8f
Pull Request #697: Use System.Threading.Lock in ConcurrentLfu

1141 of 1164 branches covered (98.02%)

Branch coverage included in aggregate %.

531 of 532 new or added lines in 1 file covered. (99.81%)

5 existing lines in 2 files now uncovered.

4841 of 4873 relevant lines covered (99.34%)

64716378.48 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

99.4
/BitFaster.Caching/Lru/ConcurrentLruCore.cs
1
using System;
2
using System.Collections;
3
using System.Collections.Concurrent;
4
using System.Collections.Generic;
5
using System.Diagnostics;
6
using System.Diagnostics.CodeAnalysis;
7
using System.Linq;
8
using System.Runtime.CompilerServices;
9
using System.Threading;
10
using System.Threading.Tasks;
11

12
namespace BitFaster.Caching.Lru
13
{
14
    /// <summary>
15
    /// A pseudo LRU based on the TU-Q eviction policy. The LRU list is composed of 3 segments: hot, warm and cold. 
16
    /// Cost of maintaining segments is amortized across requests. Items are only cycled when capacity is exceeded. 
17
    /// Pure read does not cycle items if all segments are within capacity constraints. There are no global locks. 
18
    /// On cache miss, a new item is added. Tail items in each segment are dequeued, examined, and are either enqueued 
19
    /// or discarded.
20
    /// The TU-Q scheme of hot, warm and cold is similar to that used in MemCached (https://memcached.org/blog/modern-lru/)
21
    /// and OpenBSD (https://flak.tedunangst.com/post/2Q-buffer-cache-algorithm), but does not use a background thread
22
    /// to maintain the internal queues.
23
    /// </summary>
24
    /// <remarks>
25
    /// Each segment has a capacity. When segment capacity is exceeded, items are moved as follows:
26
    /// <list type="number">
27
    ///   <item><description>New items are added to hot, WasAccessed = false.</description></item>
28
    ///   <item><description>When items are accessed, update WasAccessed = true.</description></item>
29
    ///   <item><description>When items are moved WasAccessed is set to false.</description></item>
30
    ///   <item><description>When hot is full, hot tail is moved to either Warm or Cold depending on WasAccessed.</description></item>
31
    ///   <item><description>When warm is full, warm tail is moved to warm head or cold depending on WasAccessed.</description></item>
32
    ///   <item><description>When cold is full, cold tail is moved to warm head or removed from dictionary on depending on WasAccessed.</description></item>
33
    ///</list>
34
    /// </remarks>
35
    public class ConcurrentLruCore<K, V, I, P, T> : ICacheExt<K, V>, IAsyncCacheExt<K, V>, IEnumerable<KeyValuePair<K, V>>
36
        where K : notnull
37
        where I : LruItem<K, V>
38
        where P : struct, IItemPolicy<K, V, I>
39
        where T : struct, ITelemetryPolicy<K, V>
40
    {
41
        private readonly ConcurrentDictionary<K, I> dictionary;
42

43
        private readonly ConcurrentQueue<I> hotQueue;
44
        private readonly ConcurrentQueue<I> warmQueue;
45
        private readonly ConcurrentQueue<I> coldQueue;
46

47
        // maintain count outside ConcurrentQueue, since ConcurrentQueue.Count holds a global lock
48
        private PaddedQueueCount counter;
49

50
        private readonly ICapacityPartition capacity;
51

52
        private readonly P itemPolicy;
53
        private bool isWarm = false;
2,545✔
54

55
        /// <summary>
56
        /// The telemetry policy.
57
        /// </summary>
58
        /// <remarks>
59
        /// Since T is a struct, making it readonly will force the runtime to make defensive copies
60
        /// if mutate methods are called. Therefore, field must be mutable to maintain count.
61
        /// </remarks>
62
        protected T telemetryPolicy;
63

64
        /// <summary>
65
        /// Initializes a new instance of the ConcurrentLruCore class with the specified concurrencyLevel, capacity, equality comparer, item policy and telemetry policy.
66
        /// </summary>
67
        /// <param name="concurrencyLevel">The concurrency level.</param>
68
        /// <param name="capacity">The capacity.</param>
69
        /// <param name="comparer">The equality comparer.</param>
70
        /// <param name="itemPolicy">The item policy.</param>
71
        /// <param name="telemetryPolicy">The telemetry policy.</param>
72
        /// <exception cref="ArgumentNullException"></exception>
73
        public ConcurrentLruCore(
2,545✔
74
            int concurrencyLevel,
2,545✔
75
            ICapacityPartition capacity,
2,545✔
76
            IEqualityComparer<K> comparer,
2,545✔
77
            P itemPolicy,
2,545✔
78
            T telemetryPolicy)
2,545✔
79
        {
2,545✔
80
            if (capacity == null)
2,545✔
81
                Throw.ArgNull(ExceptionArgument.capacity);
5✔
82

83
            if (comparer == null)
2,540✔
84
                Throw.ArgNull(ExceptionArgument.comparer);
5✔
85

86
            capacity.Validate();
2,535✔
87
            this.capacity = capacity;
2,530✔
88

89
            this.hotQueue = new ConcurrentQueue<I>();
2,530✔
90
            this.warmQueue = new ConcurrentQueue<I>();
2,530✔
91
            this.coldQueue = new ConcurrentQueue<I>();
2,530✔
92

93
            int dictionaryCapacity = ConcurrentDictionarySize.Estimate(this.Capacity);
2,530✔
94

95
            this.dictionary = new ConcurrentDictionary<K, I>(concurrencyLevel, dictionaryCapacity, comparer);
2,530✔
96
            this.itemPolicy = itemPolicy;
2,520✔
97
            this.telemetryPolicy = telemetryPolicy;
2,520✔
98
            this.telemetryPolicy.SetEventSource(this);
2,520✔
99
        }
2,520✔
100

101
        // No lock count: https://arbel.net/2013/02/03/best-practices-for-using-concurrentdictionary/
102
        ///<inheritdoc/>
103
        public int Count => this.dictionary.Where(i => !itemPolicy.ShouldDiscard(i.Value)).Count();
17,458,812✔
104

105
        ///<inheritdoc/>
106
        public int Capacity => this.capacity.Hot + this.capacity.Warm + this.capacity.Cold;
2,000,003,965✔
107

108
        ///<inheritdoc/>
109
        public Optional<ICacheMetrics> Metrics => CreateMetrics(this);
165✔
110

111
        ///<inheritdoc/>
112
        public Optional<ICacheEvents<K, V>> Events => CreateEvents(this);
1,308✔
113

114
        ///<inheritdoc/>
115
        public CachePolicy Policy => CreatePolicy(this);
346✔
116

117
        /// <summary>
118
        /// Gets the number of hot items.
119
        /// </summary>
120
        public int HotCount => Volatile.Read(ref this.counter.hot);
1,586,115✔
121

122
        /// <summary>
123
        /// Gets the number of warm items.
124
        /// </summary>
125
        public int WarmCount => Volatile.Read(ref this.counter.warm);
1,586,115✔
126

127
        /// <summary>
128
        /// Gets the number of cold items.
129
        /// </summary>
130
        public int ColdCount => Volatile.Read(ref this.counter.cold);
1,586,120✔
131

132
        /// <summary>
133
        /// Gets a collection containing the keys in the cache.
134
        /// </summary>
135
        public ICollection<K> Keys => this.dictionary.Keys;
1,000✔
136

137
        /// <summary>Returns an enumerator that iterates through the cache.</summary>
138
        /// <returns>An enumerator for the cache.</returns>
139
        /// <remarks>
140
        /// The enumerator returned from the cache is safe to use concurrently with
141
        /// reads and writes, however it does not represent a moment-in-time snapshot.  
142
        /// The contents exposed through the enumerator may contain modifications
143
        /// made after <see cref="GetEnumerator"/> was called.
144
        /// </remarks>
145
        public IEnumerator<KeyValuePair<K, V>> GetEnumerator()
146
        {
315✔
147
            foreach (var kvp in this.dictionary)
1,620✔
148
            {
340✔
149
                if (!itemPolicy.ShouldDiscard(kvp.Value))
340✔
150
                { 
325✔
151
                    yield return new KeyValuePair<K, V>(kvp.Key, kvp.Value.Value); 
325✔
152
                }
320✔
153
            }
335✔
154
        }
310✔
155

156
        ///<inheritdoc/>
157
        public bool TryGet(K key, [MaybeNullWhen(false)] out V value)
158
        {
2,248,061,029✔
159
            if (dictionary.TryGetValue(key, out var item))
2,248,061,029✔
160
            {
2,025,963,858✔
161
                return GetOrDiscard(item, out value);
2,025,963,858✔
162
            }
163

164
            value = default;
222,097,171✔
165
            this.telemetryPolicy.IncrementMiss();
222,097,171✔
166
            return false;
222,097,171✔
167
        }
2,248,061,029✔
168

169
        // AggressiveInlining forces the JIT to inline policy.ShouldDiscard(). For LRU policy 
170
        // the first branch is completely eliminated due to JIT time constant propogation.
171
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
172
        private bool GetOrDiscard(I item, [MaybeNullWhen(false)] out V value)
173
        {
2,025,963,858✔
174
            if (this.itemPolicy.ShouldDiscard(item))
2,025,963,858✔
175
            {
4,548,654✔
176
                this.Move(item, ItemDestination.Remove, ItemRemovedReason.Evicted);
4,548,654✔
177
                this.telemetryPolicy.IncrementMiss();
4,548,654✔
178
                value = default;
4,548,654✔
179
                return false;
4,548,654✔
180
            }
181

182
            value = item.Value;
2,021,415,204✔
183

184
            this.itemPolicy.Touch(item);
2,021,415,204✔
185
            this.telemetryPolicy.IncrementHit();
2,021,415,204✔
186
            return true;
2,021,415,204✔
187
        }
2,025,963,858✔
188

189
        private bool TryAdd(K key, V value)
190
        {
226,638,897✔
191
            var newItem = this.itemPolicy.CreateItem(key, value);
226,638,897✔
192

193
            if (this.dictionary.TryAdd(key, newItem))
226,638,897✔
194
            {
215,396,170✔
195
                this.hotQueue.Enqueue(newItem);
215,396,170✔
196
                Cycle(Interlocked.Increment(ref counter.hot));
215,396,170✔
197
                return true;
215,396,170✔
198
            }
199

200
            Disposer<V>.Dispose(newItem.Value);
11,242,727✔
201
            return false;
11,242,727✔
202
        }
226,638,897✔
203

204
        ///<inheritdoc/>
205
        public V GetOrAdd(K key, Func<K, V> valueFactory)
206
        {
2,171,316,490✔
207
            while (true)
2,180,396,376✔
208
            {
2,180,396,376✔
209
                if (this.TryGet(key, out var value))
2,180,396,376✔
210
                {
2,009,825,895✔
211
                    return value;
2,009,825,895✔
212
                }
213

214
                // The value factory may be called concurrently for the same key, but the first write to the dictionary wins.
215
                value = valueFactory(key);
170,570,481✔
216

217
                if (TryAdd(key, value))
170,570,481✔
218
                {
161,490,595✔
219
                    return value;
161,490,595✔
220
                }
221
            }
9,079,886✔
222
        }
2,171,316,490✔
223

224
        /// <summary>
225
        /// Adds a key/value pair to the cache if the key does not already exist. Returns the new value, or the 
226
        /// existing value if the key already exists.
227
        /// </summary>
228
        /// <typeparam name="TArg">The type of an argument to pass into valueFactory.</typeparam>
229
        /// <param name="key">The key of the element to add.</param>
230
        /// <param name="valueFactory">The factory function used to generate a value for the key.</param>
231
        /// <param name="factoryArgument">An argument value to pass into valueFactory.</param>
232
        /// <returns>The value for the key. This will be either the existing value for the key if the key is already 
233
        /// in the cache, or the new value if the key was not in the cache.</returns>
234
        public V GetOrAdd<TArg>(K key, Func<K, TArg, V> valueFactory, TArg factoryArgument)
235
        {
20,000,015✔
236
            while (true)
20,841,645✔
237
            {
20,841,645✔
238
                if (this.TryGet(key, out var value))
20,841,645✔
239
                {
2,340,378✔
240
                    return value;
2,340,378✔
241
                }
242

243
                // The value factory may be called concurrently for the same key, but the first write to the dictionary wins.
244
                value = valueFactory(key, factoryArgument);
18,501,267✔
245

246
                if (TryAdd(key, value))
18,501,267✔
247
                {
17,659,637✔
248
                    return value;
17,659,637✔
249
                }
250
            }
841,630✔
251
        }
20,000,015✔
252

253
        ///<inheritdoc/>
254
        public async ValueTask<V> GetOrAddAsync(K key, Func<K, Task<V>> valueFactory)
255
        {
20,000,380✔
256
            while (true)
20,737,810✔
257
            {
20,737,810✔
258
                if (this.TryGet(key, out var value))
20,737,810✔
259
                {
1,946,816✔
260
                    return value;
1,946,816✔
261
                }
262

263
                // The value factory may be called concurrently for the same key, but the first write to the dictionary wins.
264
                // This is identical logic in ConcurrentDictionary.GetOrAdd method.
265
                value = await valueFactory(key).ConfigureAwait(false);
18,790,994✔
266

267
                if (TryAdd(key, value))
18,790,979✔
268
                {
18,053,549✔
269
                    return value;
18,053,549✔
270
                }
271
            }
737,430✔
272
        }
20,000,365✔
273

274
        /// <summary>
275
        /// Adds a key/value pair to the cache if the key does not already exist. Returns the new value, or the 
276
        /// existing value if the key already exists.
277
        /// </summary>
278
        /// <typeparam name="TArg">The type of an argument to pass into valueFactory.</typeparam>
279
        /// <param name="key">The key of the element to add.</param>
280
        /// <param name="valueFactory">The factory function used to asynchronously generate a value for the key.</param>
281
        /// <param name="factoryArgument">An argument value to pass into valueFactory.</param>
282
        /// <returns>A task that represents the asynchronous GetOrAdd operation.</returns>
283
        public async ValueTask<V> GetOrAddAsync<TArg>(K key, Func<K, TArg, Task<V>> valueFactory, TArg factoryArgument)
284
        {
20,000,345✔
285
            while (true)
20,584,126✔
286
            {
20,584,126✔
287
                if (this.TryGet(key, out var value))
20,584,126✔
288
                {
1,807,956✔
289
                    return value;
1,807,956✔
290
                }
291

292
                // The value factory may be called concurrently for the same key, but the first write to the dictionary wins.
293
                value = await valueFactory(key, factoryArgument).ConfigureAwait(false);
18,776,170✔
294

295
                if (TryAdd(key, value))
18,776,170✔
296
                {
18,192,389✔
297
                    return value;
18,192,389✔
298
                }
299
            }
583,781✔
300
        }
20,000,345✔
301

302
        /// <summary>
303
        /// Attempts to remove the specified key value pair.
304
        /// </summary>
305
        /// <param name="item">The item to remove.</param>
306
        /// <returns>true if the item was removed successfully; otherwise, false.</returns>
307
        public bool TryRemove(KeyValuePair<K, V> item)
308
        {
22,960,654✔
309
            if (this.dictionary.TryGetValue(item.Key, out var existing))
22,960,654✔
310
            {
2,263,219✔
311
                lock (existing)
2,263,219✔
312
                {
2,263,219✔
313
                    if (EqualityComparer<V>.Default.Equals(existing.Value, item.Value))
2,263,219✔
314
                    {
145,970✔
315
                        var kvp = new KeyValuePair<K, I>(item.Key, existing);
145,970✔
316
#if NET6_0_OR_GREATER
317
                    if (this.dictionary.TryRemove(kvp))
119,251✔
318
#else
319
                        // https://devblogs.microsoft.com/pfxteam/little-known-gems-atomic-conditional-removals-from-concurrentdictionary/
320
                        if (((ICollection<KeyValuePair<K, I>>)this.dictionary).Remove(kvp))
26,719✔
321
#endif
322
                        {
137,676✔
323
                            OnRemove(item.Key, kvp.Value, ItemRemovedReason.Removed);
137,676✔
324
                            return true;
137,676✔
325
                        }
326
                    }
8,294✔
327
                }
2,125,543✔
328

329
                // it existed, but we couldn't remove - this means value was replaced afer the TryGetValue (a race)
330
            }
2,125,543✔
331

332
            return false;
22,822,978✔
333
        }
22,960,654✔
334

335
        /// <summary>
336
        /// Attempts to remove and return the value that has the specified key.
337
        /// </summary>
338
        /// <param name="key">The key of the element to remove.</param>
339
        /// <param name="value">When this method returns, contains the object removed, or the default value of the value type if key does not exist.</param>
340
        /// <returns>true if the object was removed successfully; otherwise, false.</returns>
341
        public bool TryRemove(K key, [MaybeNullWhen(false)] out V value)
342
        {
20,000,298✔
343
            if (this.dictionary.TryRemove(key, out var item))
20,000,298✔
344
            {
33,914✔
345
                OnRemove(key, item, ItemRemovedReason.Removed);
33,914✔
346
                value = item.Value;
33,914✔
347
                return true;
33,914✔
348
            }
349

350
            value = default;
19,966,384✔
351
            return false;
19,966,384✔
352
        }
20,000,298✔
353

354
        ///<inheritdoc/>
355
        public bool TryRemove(K key)
356
        {
20,000,220✔
357
            return TryRemove(key, out _);
20,000,220✔
358
        }
20,000,220✔
359

360
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
361
        private void OnRemove(K key, I item, ItemRemovedReason reason)
362
        {
232,633,724✔
363
            // Mark as not accessed, it will later be cycled out of the queues because it can never be fetched 
364
            // from the dictionary. Note: Hot/Warm/Cold count will reflect the removed item until it is cycled 
365
            // from the queue.
366
            item.WasAccessed = false;
232,633,724✔
367
            item.WasRemoved = true;
232,633,724✔
368

369
            this.telemetryPolicy.OnItemRemoved(key, item.Value, reason);
232,633,724✔
370

371
            // serialize dispose (common case dispose not thread safe)
372
            lock (item)
232,633,724✔
373
            {
232,633,724✔
374
                Disposer<V>.Dispose(item.Value);
232,633,724✔
375
            }
232,633,724✔
376
        }
232,633,724✔
377

378
        ///<inheritdoc/>
379
        ///<remarks>Note: Calling this method does not affect LRU order.</remarks>
380
        public bool TryUpdate(K key, V value)
381
        {
63,362,855✔
382
            if (this.dictionary.TryGetValue(key, out var existing))
63,362,855✔
383
            {
8,214,627✔
384
                lock (existing)
8,214,627✔
385
                {
8,214,627✔
386
                    if (!existing.WasRemoved)
8,214,627✔
387
                    {
8,111,863✔
388
                        V oldValue = existing.Value;
8,111,863✔
389

390
                        existing.Value = value;
8,111,863✔
391

392
                        this.itemPolicy.Update(existing);
8,111,863✔
393
// backcompat: remove conditional compile
394
#if NETCOREAPP3_0_OR_GREATER
395
                        this.telemetryPolicy.OnItemUpdated(existing.Key, oldValue, existing.Value);
8,111,863✔
396
#endif
397
                        Disposer<V>.Dispose(oldValue);
8,111,863✔
398

399
                        return true;
8,111,863✔
400
                    }
401
                }
102,764✔
402
            }
102,764✔
403

404
            return false;
55,250,992✔
405
        }
63,362,855✔
406

407
        ///<inheritdoc/>
408
        ///<remarks>Note: Updates to existing items do not affect LRU order. Added items are at the top of the LRU.</remarks>
409
        public void AddOrUpdate(K key, V value)
410
        {
23,146,741✔
411
            while (true)
23,362,730✔
412
            {
23,362,730✔
413
                // first, try to update
414
                if (this.TryUpdate(key, value))
23,362,730✔
415
                {
5,875,292✔
416
                    return;
5,875,292✔
417
                }
418

419
                // then try add
420
                var newItem = this.itemPolicy.CreateItem(key, value);
17,487,438✔
421

422
                if (this.dictionary.TryAdd(key, newItem))
17,487,438✔
423
                {
17,271,449✔
424
                    this.hotQueue.Enqueue(newItem);
17,271,449✔
425
                    Cycle(Interlocked.Increment(ref counter.hot));
17,271,449✔
426
                    return;
17,271,449✔
427
                }
428

429
                // if both update and add failed there was a race, try again
430
            }
215,989✔
431
        }
23,146,741✔
432

433
        ///<inheritdoc/>
434
        public void Clear()
435
        {
1,562,660✔
436
            // don't overlap Clear/Trim/TrimExpired
437
            lock (this.dictionary)
1,562,660✔
438
            {
1,562,660✔
439
                // evaluate queue count, remove everything including items removed from the dictionary but
440
                // not the queues. This also avoids the expensive o(n) no lock count, or locking the dictionary.
441
                int queueCount = this.HotCount + this.WarmCount + this.ColdCount;
1,562,660✔
442
                this.TrimLiveItems(itemsRemoved: 0, queueCount, ItemRemovedReason.Cleared);
1,562,660✔
443
            }
1,562,660✔
444
        }
1,562,660✔
445

446
        /// <summary>
447
        /// Trim the specified number of items from the cache. Removes all discardable items per IItemPolicy.ShouldDiscard(), then 
448
        /// itemCount-discarded items in LRU order, if any.
449
        /// </summary>
450
        /// <param name="itemCount">The number of items to remove.</param>
451
        /// <returns>The number of items removed from the cache.</returns>
452
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="itemCount"/> is less than 0./</exception>
453
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="itemCount"/> is greater than capacity./</exception>
454
        /// <remarks>
455
        /// Note: Trim affects LRU order. Calling Trim resets the internal accessed status of items.
456
        /// </remarks>
457
        public void Trim(int itemCount)
458
        {
305✔
459
            int capacity = this.Capacity;
305✔
460

461
            if (itemCount < 1 || itemCount > capacity)
305✔
462
                Throw.ArgOutOfRange(nameof(itemCount), "itemCount must be greater than or equal to one, and less than the capacity of the cache.");
10✔
463

464
            // clamp itemCount to number of items actually in the cache
465
            itemCount = Math.Min(itemCount, this.HotCount + this.WarmCount + this.ColdCount);
295✔
466

467
            // don't overlap Clear/Trim/TrimExpired
468
            lock (this.dictionary)
295✔
469
            {
295✔
470
                // first scan each queue for discardable items and remove them immediately. Note this can remove > itemCount items.
471
                int itemsRemoved = TrimAllDiscardedItems();
295✔
472

473
                TrimLiveItems(itemsRemoved, itemCount, ItemRemovedReason.Trimmed);
295✔
474
            }
295✔
475
        }
295✔
476

477
        private void TrimExpired()
478
        {
46✔
479
            if (this.itemPolicy.CanDiscard())
46✔
480
            {
46✔
481
                lock (this.dictionary)
46✔
482
                {
46✔
483
                    this.TrimAllDiscardedItems();
46✔
484
                } 
46✔
485
            }
46✔
486
        }
46✔
487

488
        /// <summary>
489
        /// Trim discarded items from all queues.
490
        /// </summary>
491
        /// <returns>The number of items removed.</returns>
492
        // backcompat: make internal
493
        protected int TrimAllDiscardedItems()
494
        {
341✔
495
            // don't overlap Clear/Trim/TrimExpired
496
            lock (this.dictionary)
341✔
497
            {
341✔
498
                int RemoveDiscardableItems(ConcurrentQueue<I> q, ref int queueCounter)
499
                {
1,023✔
500
                    int itemsRemoved = 0;
1,023✔
501
                    int localCount = queueCounter;
1,023✔
502

503
                    for (int i = 0; i < localCount; i++)
6,238✔
504
                    {
2,096✔
505
                        if (q.TryDequeue(out var item))
2,096✔
506
                        {
2,096✔
507
                            if (this.itemPolicy.ShouldDiscard(item))
2,096✔
508
                            {
288✔
509
                                Interlocked.Decrement(ref queueCounter);
288✔
510
                                this.Move(item, ItemDestination.Remove, ItemRemovedReason.Trimmed);
288✔
511
                                itemsRemoved++;
288✔
512
                            }
288✔
513
                            else if (item.WasRemoved)
1,808✔
514
                            {
30✔
515
                                Interlocked.Decrement(ref queueCounter);
30✔
516
                            }
30✔
517
                            else
518
                            {
1,778✔
519
                                q.Enqueue(item);
1,778✔
520
                            }
1,778✔
521
                        }
2,096✔
522
                    }
2,096✔
523

524
                    return itemsRemoved;
1,023✔
525
                }
1,023✔
526

527
                int coldRem = RemoveDiscardableItems(coldQueue, ref this.counter.cold);
341✔
528
                int warmRem = RemoveDiscardableItems(warmQueue, ref this.counter.warm);
341✔
529
                int hotRem = RemoveDiscardableItems(hotQueue, ref this.counter.hot);
341✔
530

531
                if (warmRem > 0)
341✔
532
                {
41✔
533
                    Volatile.Write(ref this.isWarm, false);
41✔
534
                }
41✔
535

536
                return coldRem + warmRem + hotRem;
341✔
537
            }
538
        }
341✔
539

540
        private void TrimLiveItems(int itemsRemoved, int itemCount, ItemRemovedReason reason)
541
        {
1,562,955✔
542
            // When items are touched, they are moved to warm by cycling. Therefore, to guarantee 
543
            // that we can remove itemCount items, we must cycle (2 * capacity.Warm) + capacity.Hot times.
544
            // If clear is called during trimming, it would be possible to get stuck in an infinite
545
            // loop here. The warm + hot limit also guards against this case.
546
            int trimWarmAttempts = 0;
1,562,955✔
547
            int maxWarmHotAttempts = (this.capacity.Warm * 2) + this.capacity.Hot;
1,562,955✔
548

549
            while (itemsRemoved < itemCount && trimWarmAttempts < maxWarmHotAttempts)
16,017,637✔
550
            {
14,454,682✔
551
                if (Volatile.Read(ref this.counter.cold) > 0)
14,454,682✔
552
                {
10,997,337✔
553
                    if (TryRemoveCold(reason) == (ItemDestination.Remove, 0))
10,997,337✔
554
                    {
10,996,678✔
555
                        itemsRemoved++;
10,996,678✔
556
                        trimWarmAttempts = 0;
10,996,678✔
557
                    }
10,996,678✔
558
                    else
559
                    {
659✔
560
                        TrimWarmOrHot(reason);
659✔
561
                    }
659✔
562
                }
10,997,337✔
563
                else
564
                {
3,457,345✔
565
                    TrimWarmOrHot(reason);
3,457,345✔
566
                    trimWarmAttempts++;
3,457,345✔
567
                }
3,457,345✔
568
            }
14,454,682✔
569

570
            if (Volatile.Read(ref this.counter.warm) < this.capacity.Warm)
1,562,955✔
571
            {
920,450✔
572
                Volatile.Write(ref this.isWarm, false);
920,450✔
573
            }
920,450✔
574
        }
1,562,955✔
575

576
        private void TrimWarmOrHot(ItemRemovedReason reason)
577
        {
3,458,004✔
578
            if (Volatile.Read(ref this.counter.warm) > 0)
3,458,004✔
579
            {
1,225,236✔
580
                CycleWarmUnchecked(reason);
1,225,236✔
581
            }
1,225,236✔
582
            else if (Volatile.Read(ref this.counter.hot) > 0)
2,232,768✔
583
            {
2,232,014✔
584
                CycleHotUnchecked(reason);
2,232,014✔
585
            }
2,232,014✔
586
        }
3,458,004✔
587

588
        private void Cycle(int hotCount)
589
        {
232,667,619✔
590
            if (isWarm)
232,667,619✔
591
            {
228,817,293✔
592
                (var dest, var count) = CycleHot(hotCount);
228,817,293✔
593

594
                int cycles = 0;
228,817,293✔
595
                while (cycles++ < 3 && dest != ItemDestination.Remove)
495,428,311✔
596
                {
266,611,018✔
597
                    if (dest == ItemDestination.Warm)
266,611,018✔
598
                    {
41,547,498✔
599
                        (dest, count) = CycleWarm(count);
41,547,498✔
600
                    }
41,547,498✔
601
                    else if (dest == ItemDestination.Cold)
225,063,520✔
602
                    {
225,063,520✔
603
                        (dest, count) = CycleCold(count);
225,063,520✔
604
                    }
225,063,520✔
605
                }
266,611,018✔
606

607
                // If nothing was removed yet, constrain the size of warm and cold by discarding the coldest item.
608
                if (dest != ItemDestination.Remove)
228,817,293✔
609
                {
4,906,880✔
610
                    if (dest == ItemDestination.Warm && count > this.capacity.Warm)
4,906,880✔
611
                    {
3,148,758✔
612
                        count = LastWarmToCold();
3,148,758✔
613
                    }
3,148,758✔
614

615
                    ConstrainCold(count, ItemRemovedReason.Evicted);
4,906,880✔
616
                }
4,906,880✔
617
            }
228,817,293✔
618
            else
619
            {
3,850,326✔
620
                // fill up the warm queue with new items until warm is full.
621
                // else during warmup the cache will only use the hot + cold queues until any item is requested twice.
622
                CycleDuringWarmup(hotCount);
3,850,326✔
623
            }
3,850,326✔
624
        }
232,667,619✔
625

626
        [MethodImpl(MethodImplOptions.NoInlining)]
627
        private void CycleDuringWarmup(int hotCount)
628
        {
3,850,326✔
629
            // do nothing until hot is full
630
            if (hotCount > this.capacity.Hot)
3,850,326✔
631
            {
1,619,588✔
632
                Interlocked.Decrement(ref this.counter.hot);
1,619,588✔
633

634
                if (this.hotQueue.TryDequeue(out var item))
1,619,588✔
635
                {
1,619,578✔
636
                    // special case: removed during warmup
637
                    if (item.WasRemoved)
1,619,578✔
638
                    {
102,860✔
639
                        return;
102,860✔
640
                    }
641

642
                    int count = this.Move(item, ItemDestination.Warm, ItemRemovedReason.Evicted);
1,516,718✔
643

644
                    // if warm is now full, overflow to cold and mark as warm
645
                    if (count > this.capacity.Warm)
1,516,718✔
646
                    {
331,775✔
647
                        Volatile.Write(ref this.isWarm, true);
331,775✔
648
                        count = LastWarmToCold();
331,775✔
649
                        ConstrainCold(count, ItemRemovedReason.Evicted);
331,775✔
650
                    }
331,775✔
651
                }
1,516,718✔
652
                else
653
                {
10✔
654
                    Interlocked.Increment(ref this.counter.hot);
10✔
655
                }
10✔
656
            }
1,516,728✔
657
        }
3,850,326✔
658

659
        private (ItemDestination, int) CycleHot(int hotCount)
660
        {
228,817,293✔
661
            if (hotCount > this.capacity.Hot)
228,817,293✔
662
            {
228,807,243✔
663
                return CycleHotUnchecked(ItemRemovedReason.Evicted);
228,807,243✔
664
            }
665

666
            return (ItemDestination.Remove, 0);
10,050✔
667
        }
228,817,293✔
668

669
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
670
        private (ItemDestination, int) CycleHotUnchecked(ItemRemovedReason removedReason)
671
        {
231,039,257✔
672
            Interlocked.Decrement(ref this.counter.hot);
231,039,257✔
673

674
            if (this.hotQueue.TryDequeue(out var item))
231,039,257✔
675
            {
231,039,243✔
676
                var where = this.itemPolicy.RouteHot(item);
231,039,243✔
677
                return (where, this.Move(item, where, removedReason));
231,039,243✔
678
            }
679
            else
680
            {
14✔
681
                Interlocked.Increment(ref this.counter.hot);
14✔
682
                return (ItemDestination.Remove, 0);
14✔
683
            }
684
        }
231,039,257✔
685

686
        private (ItemDestination, int) CycleWarm(int count)
687
        {
41,547,498✔
688
            if (count > this.capacity.Warm)
41,547,498✔
689
            {
41,490,751✔
690
                return CycleWarmUnchecked(ItemRemovedReason.Evicted);
41,490,751✔
691
            }
692

693
            return (ItemDestination.Remove, 0);
56,747✔
694
        }
41,547,498✔
695

696
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
697
        private (ItemDestination, int) CycleWarmUnchecked(ItemRemovedReason removedReason)
698
        {
42,715,987✔
699
            int wc = Interlocked.Decrement(ref this.counter.warm);
42,715,987✔
700

701
            if (this.warmQueue.TryDequeue(out var item))
42,715,987!
702
            {
42,715,987✔
703
                if (item.WasRemoved)
42,715,987✔
704
                {
888,037✔
705
                    return (ItemDestination.Remove, 0);
888,037✔
706
                }
707

708
                var where = this.itemPolicy.RouteWarm(item);
41,827,950✔
709

710
                // When the warm queue is full, we allow an overflow of 1 item before redirecting warm items to cold.
711
                // This only happens when hit rate is high, in which case we can consider all items relatively equal in
712
                // terms of which was least recently used.
713
                if (where == ItemDestination.Warm && wc <= this.capacity.Warm)
41,827,950✔
714
                {
9,645,967✔
715
                    return (ItemDestination.Warm, this.Move(item, where, removedReason));
9,645,967✔
716
                }
717
                else
718
                {
32,181,983✔
719
                    return (ItemDestination.Cold, this.Move(item, ItemDestination.Cold, removedReason));
32,181,983✔
720
                }
721
            }
722
            else
UNCOV
723
            {
×
UNCOV
724
                Interlocked.Increment(ref this.counter.warm);
×
UNCOV
725
                return (ItemDestination.Remove, 0);
×
726
            }
727
        }
42,715,987✔
728

729
        private (ItemDestination, int) CycleCold(int count)
730
        {
225,063,520✔
731
            if (count > this.capacity.Cold)
225,063,520✔
732
            {
217,786,964✔
733
                return TryRemoveCold(ItemRemovedReason.Evicted);
217,786,964✔
734
            }
735

736
            return (ItemDestination.Remove, 0);
7,276,556✔
737
        }
225,063,520✔
738

739
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
740
        private (ItemDestination, int) TryRemoveCold(ItemRemovedReason removedReason)
741
        {
228,784,301✔
742
            Interlocked.Decrement(ref this.counter.cold);
228,784,301✔
743

744
            if (this.coldQueue.TryDequeue(out var item))
228,784,301✔
745
            {
228,783,957✔
746
                var where = this.itemPolicy.RouteCold(item);
228,783,957✔
747

748
                if (where == ItemDestination.Warm && Volatile.Read(ref this.counter.warm) <= this.capacity.Warm)
228,783,957✔
749
                {
3,157,552✔
750
                    return (ItemDestination.Warm, this.Move(item, where, removedReason));
3,157,552✔
751
                }
752
                else
753
                {
225,626,405✔
754
                    this.Move(item, ItemDestination.Remove, removedReason);
225,626,405✔
755
                    return (ItemDestination.Remove, 0);
225,626,405✔
756
                }
757
            }
758
            else
759
            {
344✔
760
                return (ItemDestination.Cold, Interlocked.Increment(ref this.counter.cold));
344✔
761
            }
762
        }
228,784,301✔
763

764
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
765
        private int LastWarmToCold()
766
        {
3,480,533✔
767
            Interlocked.Decrement(ref this.counter.warm);
3,480,533✔
768

769
            if (this.warmQueue.TryDequeue(out var item))
3,480,533✔
770
            {
3,480,520✔
771
                var destination = item.WasRemoved ? ItemDestination.Remove : ItemDestination.Cold;
3,480,520✔
772
                return this.Move(item, destination, ItemRemovedReason.Evicted);
3,480,520✔
773
            }
774
            else
775
            {
13✔
776
                Interlocked.Increment(ref this.counter.warm);
13✔
777
                return 0;
13✔
778
            }
779
        }
3,480,533✔
780

781
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
782
        private void ConstrainCold(int coldCount, ItemRemovedReason removedReason)
783
        {
5,238,655✔
784
            if (coldCount > this.capacity.Cold && this.coldQueue.TryDequeue(out var item))
5,238,655✔
785
            {
4,869,697✔
786
                Interlocked.Decrement(ref this.counter.cold);
4,869,697✔
787
                this.Move(item, ItemDestination.Remove, removedReason);
4,869,697✔
788
            }
4,869,697✔
789
        }
5,238,655✔
790

791
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
792
        private int Move(I item, ItemDestination where, ItemRemovedReason removedReason)
793
        {
516,067,027✔
794
            item.WasAccessed = false;
516,067,027✔
795

796
            switch (where)
516,067,027✔
797
            {
798
                case ItemDestination.Warm:
799
                    this.warmQueue.Enqueue(item);
46,215,434✔
800
                    return Interlocked.Increment(ref this.counter.warm);
46,215,434✔
801
                case ItemDestination.Cold:
802
                    this.coldQueue.Enqueue(item);
233,660,879✔
803
                    return Interlocked.Increment(ref this.counter.cold);
233,660,879✔
804
                case ItemDestination.Remove:
805

806
                    var kvp = new KeyValuePair<K, I>(item.Key, item);
236,190,714✔
807

808
#if NET6_0_OR_GREATER
809
                    if (this.dictionary.TryRemove(kvp))
189,968,148✔
810
#else
811
                    // https://devblogs.microsoft.com/pfxteam/little-known-gems-atomic-conditional-removals-from-concurrentdictionary/
812
                    if (((ICollection<KeyValuePair<K, I>>)this.dictionary).Remove(kvp))
46,222,566✔
813
#endif
814
                    {
232,462,134✔
815
                        OnRemove(item.Key, item, removedReason);
232,462,134✔
816
                    }
232,462,134✔
817
                    break;
236,190,714✔
818
            }
819

820
            return 0;
236,190,714✔
821
        }
516,067,027✔
822

823
        /// <summary>Returns an enumerator that iterates through the cache.</summary>
824
        /// <returns>An enumerator for the cache.</returns>
825
        /// <remarks>
826
        /// The enumerator returned from the cache is safe to use concurrently with
827
        /// reads and writes, however it does not represent a moment-in-time snapshot.  
828
        /// The contents exposed through the enumerator may contain modifications
829
        /// made after <see cref="GetEnumerator"/> was called.
830
        /// </remarks>
831
        IEnumerator IEnumerable.GetEnumerator()
832
        {
15✔
833
            return ((ConcurrentLruCore<K, V, I, P, T>)this).GetEnumerator();
15✔
834
        }
15✔
835

836
#if DEBUG
837
        /// <summary>
838
        /// Format the LRU as a string by converting all the keys to strings.
839
        /// </summary>
840
        /// <returns>The LRU formatted as a string.</returns>
841
        internal string FormatLruString()
842
        {
75✔
843
            var sb = new System.Text.StringBuilder();
75✔
844

845
            sb.Append("Hot [");
75✔
846
            sb.Append(string.Join(",", this.hotQueue.Select(n => n.Key.ToString())));
280✔
847
            sb.Append("] Warm [");
75✔
848
            sb.Append(string.Join(",", this.warmQueue.Select(n => n.Key.ToString())));
250✔
849
            sb.Append("] Cold [");
75✔
850
            sb.Append(string.Join(",", this.coldQueue.Select(n => n.Key.ToString())));
225✔
851
            sb.Append(']');
75✔
852

853
            return sb.ToString();
75✔
854
        }
75✔
855
#endif
856

857
        private static CachePolicy CreatePolicy(ConcurrentLruCore<K, V, I, P, T> lru)
858
        {
346✔
859
            var p = new Proxy(lru);
346✔
860

861
            if (typeof(P) == typeof(AfterAccessPolicy<K, V>))
346✔
862
            {
55✔
863
                return new CachePolicy(new Optional<IBoundedPolicy>(p), Optional<ITimePolicy>.None(), new Optional<ITimePolicy>(p), Optional<IDiscreteTimePolicy>.None());
55✔
864
            }
865

866
            // IsAssignableFrom is a jit intrinsic https://github.com/dotnet/runtime/issues/4920
867
            if (typeof(IDiscreteItemPolicy<K, V>).IsAssignableFrom(typeof(P)))
291✔
868
            {
75✔
869
                return new CachePolicy(new Optional<IBoundedPolicy>(p), Optional<ITimePolicy>.None(), Optional<ITimePolicy>.None(), new Optional<IDiscreteTimePolicy>(new DiscreteExpiryProxy(lru)));
75✔
870
            }
871

872
            return new CachePolicy(new Optional<IBoundedPolicy>(p), lru.itemPolicy.CanDiscard() ? new Optional<ITimePolicy>(p) : Optional<ITimePolicy>.None());
216✔
873
        }
346✔
874

875
        private static Optional<ICacheMetrics> CreateMetrics(ConcurrentLruCore<K, V, I, P, T> lru)
876
        {
165✔
877
            if (typeof(T) == typeof(NoTelemetryPolicy<K, V>))
165✔
878
            {
25✔
879
                return Optional<ICacheMetrics>.None();
25✔
880
            }
881

882
            return new(new Proxy(lru));
140✔
883
        }
165✔
884

885
        private static Optional<ICacheEvents<K, V>> CreateEvents(ConcurrentLruCore<K, V, I, P, T> lru)
886
        {
1,308✔
887
            if (typeof(T) == typeof(NoTelemetryPolicy<K, V>))
1,308✔
888
            {
65✔
889
                return Optional<ICacheEvents<K, V>>.None();
65✔
890
            }
891

892
            return new(new Proxy(lru));
1,243✔
893
        }
1,308✔
894

895
        // To get JIT optimizations, policies must be structs.
896
        // If the structs are returned directly via properties, they will be copied. Since  
897
        // telemetryPolicy is a mutable struct, copy is bad. One workaround is to store the 
898
        // state within the struct in an object. Since the struct points to the same object
899
        // it becomes immutable. However, this object is then somewhere else on the 
900
        // heap, which slows down the policies with hit counter logic in benchmarks. Likely
901
        // this approach keeps the structs data members in the same CPU cache line as the LRU.
902
        // backcompat: remove conditional compile
903
#if NETCOREAPP3_0_OR_GREATER
904
        [DebuggerDisplay("Hit = {Hits}, Miss = {Misses}, Upd = {Updated}, Evict = {Evicted}")]
905
#else
906
        [DebuggerDisplay("Hit = {Hits}, Miss = {Misses}, Evict = {Evicted}")]
907
#endif
908
        private class Proxy : ICacheMetrics, ICacheEvents<K, V>, IBoundedPolicy, ITimePolicy
909
        {
910
            private readonly ConcurrentLruCore<K, V, I, P, T> lru;
911

912
            public Proxy(ConcurrentLruCore<K, V, I, P, T> lru)
1,729✔
913
            {
1,729✔
914
                this.lru = lru;
1,729✔
915
            }
1,729✔
916

917
            public double HitRatio => lru.telemetryPolicy.HitRatio;
10✔
918

919
            public long Total => lru.telemetryPolicy.Total;
5✔
920

921
            public long Hits => lru.telemetryPolicy.Hits;
30✔
922

923
            public long Misses => lru.telemetryPolicy.Misses;
30✔
924

925
            public long Evicted => lru.telemetryPolicy.Evicted;
40✔
926

927
// backcompat: remove conditional compile
928
#if NETCOREAPP3_0_OR_GREATER
929
            public long Updated => lru.telemetryPolicy.Updated;
10✔
930
#endif
931
            public int Capacity => lru.Capacity;
135✔
932

933
            public TimeSpan TimeToLive => lru.itemPolicy.TimeToLive;
20✔
934

935
            public event EventHandler<ItemRemovedEventArgs<K, V>> ItemRemoved
936
            {
937
                add { this.lru.telemetryPolicy.ItemRemoved += value; }
225✔
938
                remove { this.lru.telemetryPolicy.ItemRemoved -= value; }
30✔
939
            }
940

941
// backcompat: remove conditional compile
942
#if NETCOREAPP3_0_OR_GREATER
943
            public event EventHandler<ItemUpdatedEventArgs<K, V>> ItemUpdated
944
            {
945
                add { this.lru.telemetryPolicy.ItemUpdated += value; }
132✔
946
                remove { this.lru.telemetryPolicy.ItemUpdated -= value; }
15✔
947
            }
948
#endif
949
            public void Trim(int itemCount)
950
            {
50✔
951
                lru.Trim(itemCount);
50✔
952
            }
50✔
953

954
            public void TrimExpired()
955
            {
36✔
956
                lru.TrimExpired();
36✔
957
            }
36✔
958
        }
959

960
        private class DiscreteExpiryProxy : IDiscreteTimePolicy
961
        {
962
            private readonly ConcurrentLruCore<K, V, I, P, T> lru;
963

964
            public DiscreteExpiryProxy(ConcurrentLruCore<K, V, I, P, T> lru)
75✔
965
            {
75✔
966
                this.lru = lru;
75✔
967
            }
75✔
968

969
            public void TrimExpired()
970
            {
10✔
971
                lru.TrimExpired();
10✔
972
            }
10✔
973

974
            public bool TryGetTimeToExpire<TKey>(TKey key, out TimeSpan timeToLive)
975
            {
15✔
976
                if (key is K k && lru.dictionary.TryGetValue(k, out var item))
15✔
977
                {
5✔
978
                    LongTickCountLruItem<K, V>? tickItem = item as LongTickCountLruItem<K, V>;
5✔
979
                    timeToLive = (new Duration(tickItem!.TickCount) - Duration.SinceEpoch()).ToTimeSpan();
5✔
980
                    return true;
5✔
981
                }
982

983
                timeToLive = default;
10✔
984
                return false;
10✔
985
            }
15✔
986
        }
987
    }
988
}
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc