Bug 153109 – Refactor AtomicStringKeyedMRUCache to be a generic LRU cache

• Status: RESOLVED
• Resolution: FIXED
• Component: Layout and Rendering

[Said Abou-Hallawa]

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.

[Said Abou-Hallawa]

Created attachment 269016 [details]
Patch

[Said Abou-Hallawa]

Created attachment 269017 [details]
Patch

[Geoffrey Garen]

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.

[Simon Fraser (smfr)]

Comment on attachment 269017 [details]
Patch

Geoff is smarter than I am.

[Said Abou-Hallawa]

Created attachment 269024 [details]
Patch

[Said Abou-Hallawa]

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.

[Said Abou-Hallawa]

Created attachment 269063 [details]
Patch

[Darin Adler]

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.

[Darin Adler]

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.

[Said Abou-Hallawa]

Created attachment 269352 [details]
Patch

[WebKit Commit Bot]

Comment on attachment 269352 [details]
Patch

Clearing flags on attachment: 269352

Committed r195356: <http://trac.webkit.org/changeset/195356>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Csaba Osztrogonác]

It broke the WinCairo build.