xpcom/build/SmallArrayLRUCache.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #ifndef SmallArrayLRUCache_h
   8 #define SmallArrayLRUCache_h
   9
  10 #include "mozilla/Mutex.h"
  11
  12 #include <algorithm>
  13 #include <type_traits>
  14 #include <utility>
  15
  16 // Uncomment the next line to get shutdown stats about cache usage.
  17 // #define SMALLARRAYLRUCACHE_STATS
  18
  19 #ifdef SMALLARRAYLRUCACHE_STATS
  20 #  include <cstdio>
  21 #endif
  22
  23 namespace mozilla {
  24
  25 // Array-based LRU cache, thread-safe.
  26 // Optimized for cases where `FetchOrAdd` is used with the same key most
  27 // recently, and assuming the cost of running the value-builder function is much
  28 // more expensive than going through the whole list.
  29 // Note: No time limits on keeping items.
  30 // TODO: Move to more public place, if this could be used elsewhere; make sure
  31 // the cost/benefits are highlighted.
  32 template <typename Key, typename Value, unsigned LRUCapacity>
  33 class SmallArrayLRUCache {
  34  public:
  35   static_assert(std::is_default_constructible_v<Key>);
  36   static_assert(std::is_trivially_constructible_v<Key>);
  37   static_assert(std::is_trivially_copyable_v<Key>);
  38   static_assert(std::is_default_constructible_v<Value>);
  39   static_assert(LRUCapacity >= 2);
  40   static_assert(LRUCapacity <= 1024,
  41                 "This seems a bit big, is this the right cache for your use?");
  42
  43   // Reset all stored values to their default, and set cache size to zero.
  44   void Clear() {
  45     mozilla::OffTheBooksMutexAutoLock lock(mMutex);
  46     if (mSize == ShutdownSize) {
  47       return;
  48     }
  49     Clear(lock);
  50   }
  51
  52   // Clear the cache, and then prevent further uses (other functions will do
  53   // nothing).
  54   void Shutdown() {
  55     mozilla::OffTheBooksMutexAutoLock lock(mMutex);
  56     if (mSize == ShutdownSize) {
  57       return;
  58     }
  59     Clear(lock);
  60     mSize = ShutdownSize;
  61   }
  62
  63   // Add a key-value.
  64   template <typename ToValue>
  65   void Add(Key aKey, ToValue&& aValue) {
  66     mozilla::OffTheBooksMutexAutoLock lock(mMutex);
  67
  68     if (mSize == ShutdownSize) {
  69       return;
  70     }
  71
  72     // Quick add to the front, don't remove possible duplicate handles later in
  73     // the list, they will eventually drop off the end.
  74     KeyAndValue* const item0 = &mLRUArray[0];
  75     mSize = std::min(mSize + 1, LRUCapacity);
  76     if (MOZ_LIKELY(mSize != 1)) {
  77       // List is not empty.
  78       // Make a hole at the start.
  79       std::move_backward(item0, item0 + mSize - 1, item0 + mSize);
  80     }
  81     item0->mKey = aKey;
  82     item0->mValue = std::forward<ToValue>(aValue);
  83     return;
  84   }
  85
  86   // Look for the value associated with `aKey` in the cache.
  87   // If not found, run `aValueFunction()`, add it in the cache before returning.
  88   // After shutdown, just run `aValueFunction()`.
  89   template <typename ValueFunction>
  90   Value FetchOrAdd(Key aKey, ValueFunction&& aValueFunction) {
  91     Value value;
  92     mozilla::OffTheBooksMutexAutoLock lock(mMutex);
  93
  94     if (mSize == ShutdownSize) {
  95       value = std::forward<ValueFunction>(aValueFunction)();
  96       return value;
  97     }
  98
  99     KeyAndValue* const item0 = &mLRUArray[0];
 100     if (MOZ_UNLIKELY(mSize == 0)) {
 101       // List is empty.
 102       value = std::forward<ValueFunction>(aValueFunction)();
 103       item0->mKey = aKey;
 104       item0->mValue = value;
 105       mSize = 1;
 106       return value;
 107     }
 108
 109     if (MOZ_LIKELY(item0->mKey == aKey)) {
 110       // This is already at the beginning of the list, we're done.
 111 #ifdef SMALLARRAYLRUCACHE_STATS
 112       ++mCacheFoundAt[0];
 113 #endif  // SMALLARRAYLRUCACHE_STATS
 114       value = item0->mValue;
 115       return value;
 116     }
 117
 118     for (KeyAndValue* item = item0 + 1; item != item0 + mSize; ++item) {
 119       if (item->mKey == aKey) {
 120         // Found handle in the middle.
 121 #ifdef SMALLARRAYLRUCACHE_STATS
 122         ++mCacheFoundAt[unsigned(item - item0)];
 123 #endif  // SMALLARRAYLRUCACHE_STATS
 124         value = item->mValue;
 125         // Move this item to the start of the list.
 126         std::rotate(item0, item, item + 1);
 127         return value;
 128       }
 129     }
 130
 131     // Handle was not in the list.
 132 #ifdef SMALLARRAYLRUCACHE_STATS
 133     ++mCacheFoundAt[LRUCapacity];
 134 #endif  // SMALLARRAYLRUCACHE_STATS
 135     {
 136       // Don't lock while doing the potentially-expensive ValueFunction().
 137       // This means that the list could change when we lock again, but
 138       // it's okay because we'll want to add the new entry at the beginning
 139       // anyway, whatever else is in the list then.
 140       // In the worst case, it could be the same handle as another `FetchOrAdd`
 141       // in parallel, it just means it will be duplicated, so it's a little bit
 142       // less efficient (using the extra space), but not wrong (the next
 143       // `FetchOrAdd` will find the first one).
 144       mozilla::OffTheBooksMutexAutoUnlock unlock(mMutex);
 145       value = std::forward<ValueFunction>(aValueFunction)();
 146     }
 147     // Make a hole at the start, and put the value there.
 148     mSize = std::min(mSize + 1, LRUCapacity);
 149     std::move_backward(item0, item0 + mSize - 1, item0 + mSize);
 150     item0->mKey = aKey;
 151     item0->mValue = value;
 152     return value;
 153   }
 154
 155 #ifdef SMALLARRAYLRUCACHE_STATS
 156   ~SmallArrayLRUCache() {
 157     if (mSize != 0 && mSize != ShutdownSize) {
 158       fprintf(stderr,
 159               "***** SmallArrayLRUCache stats: (position -> hit count)\n");
 160       for (unsigned i = 0; i < mSize; ++i) {
 161         fprintf(stderr, "***** %3u -> %6u\n", i, mCacheFoundAt[i]);
 162       }
 163       fprintf(stderr, "***** not found -> %6u\n", mCacheFoundAt[LRUCapacity]);
 164     }
 165   }
 166 #endif  // SMALLARRAYLRUCACHE_STATS
 167
 168  private:
 169   void Clear(const mozilla::OffTheBooksMutexAutoLock&) MOZ_REQUIRES(mMutex) {
 170     for (KeyAndValue* item = &mLRUArray[0]; item != &mLRUArray[mSize]; ++item) {
 171       item->mValue = Value{};
 172     }
 173     mSize = 0;
 174   }
 175
 176   struct KeyAndValue {
 177     Key mKey;
 178     Value mValue;
 179
 180     KeyAndValue() = default;
 181     KeyAndValue(KeyAndValue&&) = default;
 182     KeyAndValue& operator=(KeyAndValue&&) = default;
 183   };
 184
 185   // Special size value that indicates the cache is in shutdown mode.
 186   constexpr static unsigned ShutdownSize = unsigned(-1);
 187
 188   mozilla::OffTheBooksMutex mMutex{"LRU cache"};
 189   unsigned mSize MOZ_GUARDED_BY(mMutex) = 0;
 190   KeyAndValue mLRUArray[LRUCapacity] MOZ_GUARDED_BY(mMutex);
 191 #ifdef SMALLARRAYLRUCACHE_STATS
 192   // Hit count for each position in the case. +1 for counting not-found cases.
 193   unsigned mCacheFoundAt[LRUCapacity + 1] MOZ_GUARDED_BY(mMutex) = {0u};
 194 #endif  // SMALLARRAYLRUCACHE_STATS
 195 };
 196
 197 }  // namespace mozilla
 198
 199 #endif  // SmallArrayLRUCache_h