20942903016

Committed 13 Jan 2026 02:53AM UTC coverage: 98.516% (-0.6%) from 99.089%

Build # 20942903016

Build Type

Pull #727

github

Committed by

web-flow

Commit Message

Merge 06e7a02d9 into 20f02a099

Pull Request Pull Request #727: Implement Lfu events: attempt 3

Run Details

1129 of 1172 branches covered (96.33%)

Branch coverage included in aggregate %.

95 of 113 new or added lines in 8 files covered. (84.07%)

2 existing lines in 1 file now uncovered.

4911 of 4959 relevant lines covered (99.03%)

49563449.13 hits per line

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

87.41

/BitFaster.Caching/Lfu/ConcurrentTLfu.cs

﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.Threading.Tasks;
using BitFaster.Caching.Lru;
using BitFaster.Caching.Scheduler;

namespace BitFaster.Caching.Lfu
{
    // LFU with time-based expiry policy. Provided as a wrapper around ConcurrentLfuCore to hide generic item and policy.
    internal sealed class ConcurrentTLfu<K, V> : ICacheExt<K, V>, IAsyncCacheExt<K, V>, IBoundedPolicy, ITimePolicy, IDiscreteTimePolicy
        where K : notnull
    {
        // Note: for performance reasons this is a mutable struct, it cannot be readonly.
        private ConcurrentLfuCore<K, V, TimeOrderNode<K, V>, ExpireAfterPolicy<K, V, EventPolicy<K, V>>, EventPolicy<K, V>> core;

        public ConcurrentTLfu(int capacity, IExpiryCalculator<K, V> expiryCalculator)
        {
            EventPolicy<K, V> eventPolicy = default;
            eventPolicy.SetEventSource(this);
            this.core = new(Defaults.ConcurrencyLevel, capacity, new ThreadPoolScheduler(), EqualityComparer<K>.Default, () => this.DrainBuffers(), new(expiryCalculator), eventPolicy);
        }

        public ConcurrentTLfu(int concurrencyLevel, int capacity, IScheduler scheduler, IEqualityComparer<K> comparer, IExpiryCalculator<K, V> expiryCalculator)
        {
            EventPolicy<K, V> eventPolicy = default;
            eventPolicy.SetEventSource(this);
            this.core = new(concurrencyLevel, capacity, scheduler, comparer, () => this.DrainBuffers(), new(expiryCalculator), eventPolicy);
        }

        // structs cannot declare self referencing lambda functions, therefore pass this in from the ctor
        private void DrainBuffers()
        {
            this.core.DrainBuffers();
        }

        ///<inheritdoc/>
        public int Count => core.Count;

        ///<inheritdoc/>
        public Optional<ICacheMetrics> Metrics => core.Metrics;

        ///<inheritdoc/>
        public Optional<ICacheEvents<K, V>> Events => new(new Proxy(this));

        internal ref EventPolicy<K, V> EventPolicyRef => ref this.core.eventPolicy;

        ///<inheritdoc/>
        public CachePolicy Policy => CreatePolicy();

        ///<inheritdoc/>
        public ICollection<K> Keys => core.Keys;

        ///<inheritdoc/>
        public int Capacity => core.Capacity;

        ///<inheritdoc/>
        public IScheduler Scheduler => core.Scheduler;

        public void DoMaintenance()
        {
            core.DoMaintenance();
        }

        ///<inheritdoc/>
        public void AddOrUpdate(K key, V value)
        {
            core.AddOrUpdate(key, value);
        }

        ///<inheritdoc/>
        public void Clear()
        {
            core.Clear();
            DoMaintenance();
        }

        ///<inheritdoc/>
        public V GetOrAdd(K key, Func<K, V> valueFactory)
        {
            return core.GetOrAdd(key, valueFactory);
        }

        ///<inheritdoc/>
        public V GetOrAdd<TArg>(K key, Func<K, TArg, V> valueFactory, TArg factoryArgument)
        {
            return core.GetOrAdd(key, valueFactory, factoryArgument);
        }

        ///<inheritdoc/>
        public ValueTask<V> GetOrAddAsync(K key, Func<K, Task<V>> valueFactory)
        {
            return core.GetOrAddAsync(key, valueFactory);
        }

        ///<inheritdoc/>
        public ValueTask<V> GetOrAddAsync<TArg>(K key, Func<K, TArg, Task<V>> valueFactory, TArg factoryArgument)
        {
            return core.GetOrAddAsync(key, valueFactory, factoryArgument);
        }

        ///<inheritdoc/>
        public void Trim(int itemCount)
        {
            core.Trim(itemCount);
            DoMaintenance();
        }

        ///<inheritdoc/>
        public bool TryGet(K key, [MaybeNullWhen(false)] out V value)
        {
            return core.TryGet(key, out value);
        }

        ///<inheritdoc/>
        public bool TryRemove(K key)
        {
            return core.TryRemove(key);
        }

        public bool TryRemove(KeyValuePair<K, V> item)
        {
            return core.TryRemove(item);
        }

        public bool TryRemove(K key, [MaybeNullWhen(false)] out V value)
        {
            return core.TryRemove(key, out value);
        }

        ///<inheritdoc/>
        public bool TryUpdate(K key, V value)
        {
            return core.TryUpdate(key, value);
        }

        ///<inheritdoc/>
        public IEnumerator<KeyValuePair<K, V>> GetEnumerator()
        {
            return core.GetEnumerator();
        }

        ///<inheritdoc/>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return core.GetEnumerator();
        }

        private CachePolicy CreatePolicy()
        {
            var afterWrite = Optional<ITimePolicy>.None();
            var afterAccess = Optional<ITimePolicy>.None();
            var afterCustom = Optional<IDiscreteTimePolicy>.None();

            var calc = core.policy.ExpiryCalculator;

            switch (calc)
            {
                case ExpireAfterAccess<K, V>:
                    afterAccess = new Optional<ITimePolicy>(this);
                    break;
                case ExpireAfterWrite<K, V>:
                    afterWrite = new Optional<ITimePolicy>(this);
                    break;
                default:
                    afterCustom = new Optional<IDiscreteTimePolicy>(this);
                    break;
            }
            ;

            return new CachePolicy(new Optional<IBoundedPolicy>(this), afterWrite, afterAccess, afterCustom);
        }

        TimeSpan ITimePolicy.TimeToLive => (this.core.policy.ExpiryCalculator) switch
        {
            ExpireAfterAccess<K, V> aa => aa.TimeToExpire,
            ExpireAfterWrite<K, V> aw => aw.TimeToExpire,
            _ => TimeSpan.Zero,
        };

        ///<inheritdoc/>
        public bool TryGetTimeToExpire<K1>(K1 key, out TimeSpan timeToExpire)
        {
            if (key is K k && core.TryGetNode(k, out TimeOrderNode<K, V>? node))
            {
                var tte = new Duration(node.GetTimestamp()) - Duration.SinceEpoch();
                timeToExpire = tte.ToTimeSpan();
                return true;
            }

            timeToExpire = default;
            return false;
        }

        ///<inheritdoc/>
        public void TrimExpired()
        {
            DoMaintenance();
        }

        // To get JIT optimizations, policies must be structs.
        // If the structs are returned directly via properties, they will be copied. Since
        // eventPolicy is a mutable struct, copy is bad. One workaround is to store the
        // state within the struct in an object. Since the struct points to the same object
        // it becomes immutable. However, this object is then somewhere else on the
        // heap, which slows down the policies with hit counter logic in benchmarks. Likely
        // this approach keeps the structs data members in the same CPU cache line as the LFU.
        private class Proxy : ICacheEvents<K, V>
        {
            private readonly ConcurrentTLfu<K, V> lfu;

            public Proxy(ConcurrentTLfu<K, V> lfu)
            {
                this.lfu = lfu;
            }

            public event EventHandler<ItemRemovedEventArgs<K, V>> ItemRemoved
            {
                add
                {
                    ref var policy = ref this.lfu.EventPolicyRef;
                    policy.ItemRemoved += value;
                }
                remove
                {
                    ref var policy = ref this.lfu.EventPolicyRef;
                    policy.ItemRemoved -= value;
                }
            }

            // backcompat: remove conditional compile
#if NETCOREAPP3_0_OR_GREATER
            public event EventHandler<ItemUpdatedEventArgs<K, V>> ItemUpdated
            {
                add
                {
                    ref var policy = ref this.lfu.EventPolicyRef;
                    policy.ItemUpdated += value;
                }
                remove
                {
                    ref var policy = ref this.lfu.EventPolicyRef;
                    policy.ItemUpdated -= value;
                }
            }
#endif
        }
    }
}

1	using System;
2	using System.Collections;
3	using System.Collections.Generic;
4	using System.Diagnostics.CodeAnalysis;
5	using System.Threading.Tasks;
6	using BitFaster.Caching.Lru;
7	using BitFaster.Caching.Scheduler;
8
9	namespace BitFaster.Caching.Lfu
10	{
11	// LFU with time-based expiry policy. Provided as a wrapper around ConcurrentLfuCore to hide generic item and policy.
12	internal sealed class ConcurrentTLfu<K, V> : ICacheExt<K, V>, IAsyncCacheExt<K, V>, IBoundedPolicy, ITimePolicy, IDiscreteTimePolicy
13	where K : notnull
14	{
15	// Note: for performance reasons this is a mutable struct, it cannot be readonly.
16	private ConcurrentLfuCore<K, V, TimeOrderNode<K, V>, ExpireAfterPolicy<K, V, EventPolicy<K, V>>, EventPolicy<K, V>> core;
17
18	public ConcurrentTLfu(int capacity, IExpiryCalculator<K, V> expiryCalculator)	188✔
19	{	188✔
20	EventPolicy<K, V> eventPolicy = default;	188✔
21	eventPolicy.SetEventSource(this);	188✔
22	this.core = new(Defaults.ConcurrencyLevel, capacity, new ThreadPoolScheduler(), EqualityComparer<K>.Default, () => this.DrainBuffers(), new(expiryCalculator), eventPolicy);	275,598✔
23	}	188✔
24
25	public ConcurrentTLfu(int concurrencyLevel, int capacity, IScheduler scheduler, IEqualityComparer<K> comparer, IExpiryCalculator<K, V> expiryCalculator)	44✔
26	{	44✔
27	EventPolicy<K, V> eventPolicy = default;	44✔
28	eventPolicy.SetEventSource(this);	44✔
29	this.core = new(concurrencyLevel, capacity, scheduler, comparer, () => this.DrainBuffers(), new(expiryCalculator), eventPolicy);	71✔
30	}	44✔
31
32	// structs cannot declare self referencing lambda functions, therefore pass this in from the ctor
33	private void DrainBuffers()
34	{	275,437✔
35	this.core.DrainBuffers();	275,437✔
36	}	275,437✔
37
38	///<inheritdoc/>
39	public int Count => core.Count;	16✔
40
41	///<inheritdoc/>
42	public Optional<ICacheMetrics> Metrics => core.Metrics;	4✔
43
44	///<inheritdoc/>
45	public Optional<ICacheEvents<K, V>> Events => new(new Proxy(this));	36✔
46
NEW 47	internal ref EventPolicy<K, V> EventPolicyRef => ref this.core.eventPolicy;	×
48
49	///<inheritdoc/>
50	public CachePolicy Policy => CreatePolicy();	152✔
51
52	///<inheritdoc/>
53	public ICollection<K> Keys => core.Keys;	40✔
54
55	///<inheritdoc/>
56	public int Capacity => core.Capacity;	4✔
57
58	///<inheritdoc/>
59	public IScheduler Scheduler => core.Scheduler;	4✔
60
61	public void DoMaintenance()
62	{	24✔
63	core.DoMaintenance();	24✔
64	}	24✔
65
66	///<inheritdoc/>
67	public void AddOrUpdate(K key, V value)
68	{	35✔
69	core.AddOrUpdate(key, value);	35✔
70	}	35✔
71
72	///<inheritdoc/>
73	public void Clear()
74	{	4✔
75	core.Clear();	4✔
76	DoMaintenance();	4✔
77	}	4✔
78
79	///<inheritdoc/>
80	public V GetOrAdd(K key, Func<K, V> valueFactory)
81	{	189✔
82	return core.GetOrAdd(key, valueFactory);	189✔
83	}	189✔
84
85	///<inheritdoc/>
86	public V GetOrAdd<TArg>(K key, Func<K, TArg, V> valueFactory, TArg factoryArgument)
87	{	8✔
88	return core.GetOrAdd(key, valueFactory, factoryArgument);	8✔
89	}	8✔
90
91	///<inheritdoc/>
92	public ValueTask<V> GetOrAddAsync(K key, Func<K, Task<V>> valueFactory)
93	{	16,000,008✔
94	return core.GetOrAddAsync(key, valueFactory);	16,000,008✔
95	}	16,000,008✔
96
97	///<inheritdoc/>
98	public ValueTask<V> GetOrAddAsync<TArg>(K key, Func<K, TArg, Task<V>> valueFactory, TArg factoryArgument)
99	{	8✔
100	return core.GetOrAddAsync(key, valueFactory, factoryArgument);	8✔
101	}	8✔
102
103	///<inheritdoc/>
104	public void Trim(int itemCount)
105	{	4✔
106	core.Trim(itemCount);	4✔
107	DoMaintenance();	4✔
108	}	4✔
109
110	///<inheritdoc/>
111	public bool TryGet(K key, [MaybeNullWhen(false)] out V value)
112	{	55✔
113	return core.TryGet(key, out value);	55✔
114	}	55✔
115
116	///<inheritdoc/>
117	public bool TryRemove(K key)
118	{	4✔
119	return core.TryRemove(key);	4✔
120	}	4✔
121
122	public bool TryRemove(KeyValuePair<K, V> item)
123	{	8✔
124	return core.TryRemove(item);	8✔
125	}	8✔
126
127	public bool TryRemove(K key, [MaybeNullWhen(false)] out V value)
128	{	4✔
129	return core.TryRemove(key, out value);	4✔
130	}	4✔
131
132	///<inheritdoc/>
133	public bool TryUpdate(K key, V value)
134	{	4✔
135	return core.TryUpdate(key, value);	4✔
136	}	4✔
137
138	///<inheritdoc/>
139	public IEnumerator<KeyValuePair<K, V>> GetEnumerator()
140	{	4✔
141	return core.GetEnumerator();	4✔
142	}	4✔
143
144	///<inheritdoc/>
145	IEnumerator IEnumerable.GetEnumerator()
146	{	4✔
147	return core.GetEnumerator();	4✔
148	}	4✔
149
150	private CachePolicy CreatePolicy()
151	{	152✔
152	var afterWrite = Optional<ITimePolicy>.None();	152✔
153	var afterAccess = Optional<ITimePolicy>.None();	152✔
154	var afterCustom = Optional<IDiscreteTimePolicy>.None();	152✔
155
156	var calc = core.policy.ExpiryCalculator;	152✔
157
158	switch (calc)	152✔
159	{
160	case ExpireAfterAccess<K, V>:
161	afterAccess = new Optional<ITimePolicy>(this);	56✔
162	break;	56✔
163	case ExpireAfterWrite<K, V>:
164	afterWrite = new Optional<ITimePolicy>(this);	56✔
165	break;	56✔
166	default:
167	afterCustom = new Optional<IDiscreteTimePolicy>(this);	40✔
168	break;	40✔
169	}
170	;	152✔
171
172	return new CachePolicy(new Optional<IBoundedPolicy>(this), afterWrite, afterAccess, afterCustom);	152✔
173	}	152✔
174
175	TimeSpan ITimePolicy.TimeToLive => (this.core.policy.ExpiryCalculator) switch	40✔
176	{	40✔
177	ExpireAfterAccess<K, V> aa => aa.TimeToExpire,	20✔
178	ExpireAfterWrite<K, V> aw => aw.TimeToExpire,	16✔
179	_ => TimeSpan.Zero,	4✔
180	};	40✔
181
182	///<inheritdoc/>
183	public bool TryGetTimeToExpire<K1>(K1 key, out TimeSpan timeToExpire)
184	{	12✔
185	if (key is K k && core.TryGetNode(k, out TimeOrderNode<K, V>? node))	12✔
186	{	4✔
187	var tte = new Duration(node.GetTimestamp()) - Duration.SinceEpoch();	4✔
188	timeToExpire = tte.ToTimeSpan();	4✔
189	return true;	4✔
190	}
191
192	timeToExpire = default;	8✔
193	return false;	8✔
194	}	12✔
195
196	///<inheritdoc/>
197	public void TrimExpired()
198	{	4✔
199	DoMaintenance();	4✔
200	}	4✔
201
202	// To get JIT optimizations, policies must be structs.
203	// If the structs are returned directly via properties, they will be copied. Since
204	// eventPolicy is a mutable struct, copy is bad. One workaround is to store the
205	// state within the struct in an object. Since the struct points to the same object
206	// it becomes immutable. However, this object is then somewhere else on the
207	// heap, which slows down the policies with hit counter logic in benchmarks. Likely
208	// this approach keeps the structs data members in the same CPU cache line as the LFU.
209	private class Proxy : ICacheEvents<K, V>
210	{
211	private readonly ConcurrentTLfu<K, V> lfu;
212
213	public Proxy(ConcurrentTLfu<K, V> lfu)	36✔
214	{	36✔
215	this.lfu = lfu;	36✔
216	}	36✔
217
218	public event EventHandler<ItemRemovedEventArgs<K, V>> ItemRemoved
219	{
220	add
NEW 221	{	×
NEW 222	ref var policy = ref this.lfu.EventPolicyRef;	×
NEW 223	policy.ItemRemoved += value;	×
NEW 224	}	×
225	remove
NEW 226	{	×
NEW 227	ref var policy = ref this.lfu.EventPolicyRef;	×
NEW 228	policy.ItemRemoved -= value;	×
NEW 229	}	×
230	}
231
232	// backcompat: remove conditional compile
233	#if NETCOREAPP3_0_OR_GREATER
234	public event EventHandler<ItemUpdatedEventArgs<K, V>> ItemUpdated
235	{
236	add
NEW 237	{	×
NEW 238	ref var policy = ref this.lfu.EventPolicyRef;	×
NEW 239	policy.ItemUpdated += value;	×
NEW 240	}	×
241	remove
NEW 242	{	×
NEW 243	ref var policy = ref this.lfu.EventPolicyRef;	×
NEW 244	policy.ItemUpdated -= value;	×
NEW 245	}	×
246	}
247	#endif
248	}
249	}
250	}

bitfaster / BitFaster.Caching / 20942903016

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

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