This is kind of clean up since the MRU is implemented in two places (the CGColor and hyphenation) and we needed it also for https://bugs.webkit.org/show_bug.cgi?id=152939. So instead of of repeating it for the third time, it is going to be generic to used for any type. This bug only tracks the code refactoring.
Created attachment 269016 [details] Patch
Created attachment 269017 [details] Patch
Comment on attachment 269016 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=269016&action=review > Source/WTF/wtf/KeyedMRUCache.h:34 > +template<typename K, typename T, size_t capacity = 4> I don't think you should allow capacity to be configurable. Making a very large O(N) cache would be a mistake. Alternatively, you could use a different caching strategy that supported many items. > Source/WTF/wtf/KeyedMRUCache.h:35 > +class KeyedMRUCache { You should remove "Keyed" from the name of this class. All caches have keys and values. If you're going to stick with a capacity of 4, maybe you should also put "Tiny" in the name: TinyMRUCache. > Source/WTF/wtf/KeyedMRUCache.h:47 > + if (m_cache[i].first == key) { This would read better as early return. Less indentation that way. > Source/WTF/wtf/KeyedMRUCache.h:50 > + if (foundIndex != m_cache.size() - 1) { I think this would read more clearly as two separate return statements: One for the "already at end" case and one for the "move it" case. > Source/WTF/wtf/KeyedMRUCache.h:62 > + // m_cache[0] is the LRU entry, so remove it. > + if (m_cache.size() == capacity) > + m_cache.remove(0); This appears to be an LRU cache rather than an MRU cache. You should update the name accordingly. Idiomatically, caches are named according to their eviction policies. > Source/WTF/wtf/KeyedMRUCache.h:72 > + virtual bool isKeyNull(const K&) const { return false; } > + virtual T createValueForNullKey() { return { }; } > + virtual T createValueForKey(const K&) { return { }; } > + There's no need to pay the cost of virtual functions here. You can use template overrides or template parameters instead. > Source/WTF/wtf/KeyedMRUCache.h:34 > +template<typename K, typename T, size_t capacity = 4> I don't think you should allow capacity to be configurable. Making a very large O(N) cache would be a mistake. Alternatively, you could use a different caching strategy that supported many items. > Source/WTF/wtf/KeyedMRUCache.h:35 > +class KeyedMRUCache { You should remove "Keyed" from the name of this class. All caches have keys and values. If you're going to stick with a capacity of 4, maybe you should also put "Tiny" in the name: TinyMRUCache. > Source/WTF/wtf/KeyedMRUCache.h:47 > + if (m_cache[i].first == key) { This would read better as early return. Less indentation that way. > Source/WTF/wtf/KeyedMRUCache.h:50 > + if (foundIndex != m_cache.size() - 1) { I think this would read more clearly as two separate return statements: One for the "already at end" case and one for the "move it" case. > Source/WTF/wtf/KeyedMRUCache.h:62 > + // m_cache[0] is the LRU entry, so remove it. > + if (m_cache.size() == capacity) > + m_cache.remove(0); This appears to be an LRU cache rather than an MRU cache. You should update the name accordingly. Idiomatically, caches are named according to their eviction policies. > Source/WTF/wtf/KeyedMRUCache.h:72 > + virtual bool isKeyNull(const K&) const { return false; } > + virtual T createValueForNullKey() { return { }; } > + virtual T createValueForKey(const K&) { return { }; } > + There's no need to pay the cost of virtual functions here. You can use template overrides or template parameters instead.
Comment on attachment 269017 [details] Patch Geoff is smarter than I am.
Created attachment 269024 [details] Patch
Comment on attachment 269016 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=269016&action=review >>> Source/WTF/wtf/KeyedMRUCache.h:35 >>> +class KeyedMRUCache { >> >> You should remove "Keyed" from the name of this class. All caches have keys and values. >> >> If you're going to stick with a capacity of 4, maybe you should also put "Tiny" in the name: TinyMRUCache. > > You should remove "Keyed" from the name of this class. All caches have keys and values. > > If you're going to stick with a capacity of 4, maybe you should also put "Tiny" in the name: TinyMRUCache. I changed the name to be TinyLRUCache for now. I will later how I can make the size non configurable. >>> Source/WTF/wtf/KeyedMRUCache.h:47 >>> + if (m_cache[i].first == key) { >> >> This would read better as early return. Less indentation that way. > > This would read better as early return. Less indentation that way. Done. >>> Source/WTF/wtf/KeyedMRUCache.h:50 >>> + if (foundIndex != m_cache.size() - 1) { >> >> I think this would read more clearly as two separate return statements: One for the "already at end" case and one for the "move it" case. > > I think this would read more clearly as two separate return statements: One for the "already at end" case and one for the "move it" case. Done. >>> Source/WTF/wtf/KeyedMRUCache.h:62 >>> + m_cache.remove(0); >> >> This appears to be an LRU cache rather than an MRU cache. You should update the name accordingly. >> >> Idiomatically, caches are named according to their eviction policies. > > This appears to be an LRU cache rather than an MRU cache. You should update the name accordingly. > > Idiomatically, caches are named according to their eviction policies. Done. Name was changed to TinyLRUCache. >>> Source/WTF/wtf/KeyedMRUCache.h:72 >>> + >> >> There's no need to pay the cost of virtual functions here. You can use template overrides or template parameters instead. > > There's no need to pay the cost of virtual functions here. You can use template overrides or template parameters instead. Done through a new template called TinyLRUCachePolicy which is responsible for creating the cache values and also for creating a singleton for the cache itself.
Created attachment 269063 [details] Patch
Comment on attachment 269063 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=269063&action=review > Source/WTF/wtf/TinyLRUCache.h:34 > +template<typename K, typename T> How about KeyType and ValueType instead of K and T? > Source/WTF/wtf/TinyLRUCache.h:41 > +template<typename K, typename T, size_t capacity = 4> How about KeyType and ValueType instead of K and T? > Source/WTF/wtf/TinyLRUCache.h:59 > + Entry entry = m_cache[i]; Should WTFMove here so it’s more efficient for types that have a move constructor. > Source/WTF/wtf/TinyLRUCache.h:61 > + m_cache.append(entry); Should WTFMove here.
Comment on attachment 269063 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=269063&action=review > Source/WTF/wtf/TinyLRUCache.h:44 > + T get(const K& key) I think maybe this should return const T& instead of T for better efficiency.
Created attachment 269352 [details] Patch
Comment on attachment 269352 [details] Patch Clearing flags on attachment: 269352 Committed r195356: <http://trac.webkit.org/changeset/195356>
All reviewed patches have been landed. Closing bug.
It broke the WinCairo build.