1  // Copyright (c) Microsoft Corporation
  2  // The Microsoft Corporation licenses this file to you under the MIT license.
  3  // See the LICENSE file in the project root for more information.
  4  
  5  using System.Collections.Concurrent;
  6  using System.Diagnostics.CodeAnalysis;
  7  using System.Runtime.CompilerServices;
  8  using Microsoft.CmdPal.Core.Common.Helpers;
  9  
 10  namespace Microsoft.CmdPal.UI.Helpers;
 11  
 12  /// <summary>
 13  /// A high-performance, near-lock-free adaptive cache optimized for UI Icons.
 14  /// Eviction merely drops references to allow the GC to manage UI-bound lifetimes.
 15  /// </summary>
 16  internal sealed class AdaptiveCache<TKey, TValue>
 17      where TKey : IEquatable<TKey>
 18  {
 19      private readonly int _capacity;
 20      private readonly double _decayFactor;
 21      private readonly TimeSpan _decayInterval;
 22  
 23      private readonly ConcurrentDictionary<TKey, CacheEntry> _map;
 24      private readonly ConcurrentStack<CacheEntry> _pool = [];
 25      private readonly WaitCallback _maintenanceCallback;
 26  
 27      private long _currentTick;
 28      private long _lastDecayTicks = DateTime.UtcNow.Ticks;
 29      private InterlockedBoolean _maintenanceSwitch = new(false);
 30  
 31      public AdaptiveCache(int capacity = 384, TimeSpan? decayInterval = null, double decayFactor = 0.5)
 32      {
 33          _capacity = capacity;
 34          _decayInterval = decayInterval ?? TimeSpan.FromMinutes(5);
 35          _decayFactor = decayFactor;
 36          _map = new ConcurrentDictionary<TKey, CacheEntry>(Environment.ProcessorCount, capacity);
 37  
 38          _maintenanceCallback = static state =>
 39          {
 40              var cache = (AdaptiveCache<TKey, TValue>)state!;
 41              try
 42              {
 43                  cache.PerformCleanup();
 44              }
 45              finally
 46              {
 47                  cache._maintenanceSwitch.Clear();
 48              }
 49          };
 50      }
 51  
 52      public TValue GetOrAdd<TArg>(TKey key, Func<TKey, TArg, TValue> factory, TArg arg)
 53      {
 54          if (_map.TryGetValue(key, out var entry))
 55          {
 56              entry.Update(Interlocked.Increment(ref _currentTick));
 57              return entry.Value!;
 58          }
 59  
 60          if (!_pool.TryPop(out var newEntry))
 61          {
 62              newEntry = new CacheEntry();
 63          }
 64  
 65          var value = factory(key, arg);
 66          var tick = Interlocked.Increment(ref _currentTick);
 67          newEntry.Initialize(key, value, 1.0, tick);
 68  
 69          if (!_map.TryAdd(key, newEntry))
 70          {
 71              newEntry.Clear();
 72              _pool.Push(newEntry);
 73  
 74              if (_map.TryGetValue(key, out var existing))
 75              {
 76                  existing.Update(tick);
 77                  return existing.Value!;
 78              }
 79          }
 80  
 81          if (ShouldMaintenanceRun())
 82          {
 83              TryRunMaintenance();
 84          }
 85  
 86          return value;
 87      }
 88  
 89      public bool TryGet(TKey key, [MaybeNullWhen(false)] out TValue value)
 90      {
 91          if (_map.TryGetValue(key, out var entry))
 92          {
 93              entry.Update(Interlocked.Increment(ref _currentTick));
 94              value = entry.Value;
 95              return true;
 96          }
 97  
 98          value = default;
 99          return false;
100      }
101  
102      public void Add(TKey key, TValue value)
103      {
104          var tick = Interlocked.Increment(ref _currentTick);
105  
106          if (_map.TryGetValue(key, out var existing))
107          {
108              existing.Update(tick);
109              existing.SetValue(value);
110              return;
111          }
112  
113          if (!_pool.TryPop(out var newEntry))
114          {
115              newEntry = new CacheEntry();
116          }
117  
118          newEntry.Initialize(key, value, 1.0, tick);
119  
120          if (!_map.TryAdd(key, newEntry))
121          {
122              newEntry.Clear();
123              _pool.Push(newEntry);
124          }
125  
126          if (ShouldMaintenanceRun())
127          {
128              TryRunMaintenance();
129          }
130      }
131  
132      public bool TryRemove(TKey key)
133      {
134          if (_map.TryRemove(key, out var evicted))
135          {
136              evicted.Clear();
137              _pool.Push(evicted);
138              return true;
139          }
140  
141          return false;
142      }
143  
144      public void Clear()
145      {
146          foreach (var key in _map.Keys)
147          {
148              TryRemove(key);
149          }
150  
151          Interlocked.Exchange(ref _currentTick, 0);
152      }
153  
154      private bool ShouldMaintenanceRun()
155      {
156          return _map.Count > _capacity || (DateTime.UtcNow.Ticks - Interlocked.Read(ref _lastDecayTicks)) > _decayInterval.Ticks;
157      }
158  
159      private void TryRunMaintenance()
160      {
161          if (_maintenanceSwitch.Set())
162          {
163              ThreadPool.UnsafeQueueUserWorkItem(_maintenanceCallback, this);
164          }
165      }
166  
167      private void PerformCleanup()
168      {
169          var nowTicks = DateTime.UtcNow.Ticks;
170          var isDecay = (nowTicks - Interlocked.Read(ref _lastDecayTicks)) > _decayInterval.Ticks;
171          if (isDecay)
172          {
173              Interlocked.Exchange(ref _lastDecayTicks, nowTicks);
174          }
175  
176          var currentTick = Interlocked.Read(ref _currentTick);
177  
178          foreach (var (key, entry) in _map)
179          {
180              if (isDecay)
181              {
182                  entry.Decay(_decayFactor);
183              }
184  
185              var score = CalculateScore(entry, currentTick);
186  
187              if (score < 0.1 || _map.Count > _capacity)
188              {
189                  if (_map.TryRemove(key, out var evicted))
190                  {
191                      evicted.Clear();
192                      _pool.Push(evicted);
193                  }
194              }
195          }
196      }
197  
198      /// <summary>
199      /// Calculates the survival score of an entry.
200      /// Higher score = stay in cache; Lower score = priority for eviction.
201      /// </summary>
202      [MethodImpl(MethodImplOptions.AggressiveInlining)]
203      private static double CalculateScore(CacheEntry entry, long currentTick)
204      {
205          // Tuning parameter: How much weight to give recency vs frequency.
206          // - a larger ageWeight makes the cache behave more like LRU (Least Recently Used).
207          // - a smaller ageWeight makes it behave more like LFU (Least Frequently Used).
208          const double ageWeight = 0.001;
209  
210          var frequency = entry.GetFrequency();
211          var age = currentTick - entry.GetLastAccess();
212  
213          return frequency - (age * ageWeight);
214      }
215  
216      /// <summary>
217      /// Represents a single pooled entry in the cache, containing the value and
218      /// atomic metadata for adaptive eviction logic.
219      /// </summary>
220      private sealed class CacheEntry
221      {
222          /// <summary>
223          /// Gets the key associated with this entry. Used primarily for identification during cleanup.
224          /// </summary>
225          public TKey Key { get; private set; } = default!;
226  
227          /// <summary>
228          /// Gets the cached value. This reference is cleared on eviction to allow GC collection.
229          /// </summary>
230          public TValue Value { get; private set; } = default!;
231  
232          /// <summary>
233          /// Stores the frequency count as double bits to allow for Interlocked atomic math.
234          /// Frequencies are decayed over time to ensure the cache adapts to new usage patterns.
235          /// </summary>
236          /// <remarks>
237          /// This allows the use of Interlocked.CompareExchange to perform thread-safe floating point
238          /// arithmetic without a global lock.
239          /// </remarks>
240          private long _frequencyBits;
241  
242          /// <summary>
243          /// The tick (monotonically increasing counter) of the last time this entry was accessed.
244          /// </summary>
245          private long _lastAccessTick;
246  
247          public void Initialize(TKey key, TValue value, double frequency, long lastAccessTick)
248          {
249              Key = key;
250              Value = value;
251              _frequencyBits = BitConverter.DoubleToInt64Bits(frequency);
252              _lastAccessTick = lastAccessTick;
253          }
254  
255          public void SetValue(TValue value)
256          {
257              Value = value;
258          }
259  
260          public void Clear()
261          {
262              Key = default!;
263              Value = default!;
264          }
265  
266          public void Update(long tick)
267          {
268              Interlocked.Exchange(ref _lastAccessTick, tick);
269              long initial, updated;
270              do
271              {
272                  initial = Interlocked.Read(ref _frequencyBits);
273                  updated = BitConverter.DoubleToInt64Bits(BitConverter.Int64BitsToDouble(initial) + 1.0);
274              }
275              while (Interlocked.CompareExchange(ref _frequencyBits, updated, initial) != initial);
276          }
277  
278          public void Decay(double factor)
279          {
280              long initial, updated;
281              do
282              {
283                  initial = Interlocked.Read(ref _frequencyBits);
284                  updated = BitConverter.DoubleToInt64Bits(BitConverter.Int64BitsToDouble(initial) * factor);
285              }
286              while (Interlocked.CompareExchange(ref _frequencyBits, updated, initial) != initial);
287          }
288  
289          public double GetFrequency()
290          {
291              return BitConverter.Int64BitsToDouble(Interlocked.Read(ref _frequencyBits));
292          }
293  
294          public long GetLastAccess()
295          {
296              return Interlocked.Read(ref _lastAccessTick);
297          }
298      }
299  }