Adding a LRU Cache to WTF?

[Dominik Röttsches]

Hi,

I filed Chromium bug 1010925 to start a discussion on whether we could add a LRU Cache to WTF to provide a reliable LRU Cache blink wide, based on Blink container types and Blink's hashing.

Various places in Blink implement something similar, some have size boundaries, some don't and the implementations differ in sophistication, for example:

ImageDecodingStore: /third_party/blink/renderer/platform/graphics/image_decoding_store.h
CanvasFontCache: third_party/blink/renderer/core/html/canvas/canvas_font_cache.h

and possibly more.

The level of testing for these individually is in my opinion relatively sparse. 

In //base, there is a MRUCache which does something very similar but can't be used in Blink as is because it uses STL container types internally.

I started working on this or proposing this, because I need to add a cache to avoid out of process calls for font fallback in a particular scenario (issue 1005234). 

I was faced with the situation of writing another task specific cache implementation or proposing a generic one. 

In my opinion, it'd be useful to have this at the WTF level, if we can design it in a way that we could perhaps make one or two of the existing LRU-like implementation use it with benefit. Several clients could benefit from optimizations to the cache and less time is wasted rewriting such cache logic when it's needed multiple times. Also, it could become easier to reason about such caches' memory consumption behavior, as we don't have to analyse each different implementation individually.

haraken@ already had some comments on the bug and suggested to move the discussion here, so I'd leave it up to you, Kentaro, to repeat your comments here.

Thanks very much for considering adding a LRU Cache,

Dominik

[Kentaro Hara]

Thanks Dominik for starting the thread!

+1 to providing a generic LRU cache for Blink.

However, I prefer avoiding implementing a WTF-specific LRU cache because the GC integration is never trivial and the maintenance cost is high. For example, we have spent a huge amount of time to fix all bugs and maintain LinkedListHashSet.

Would there be any option to use //base/MRUCache in Blink? For example, we can wrap Oilpan objects using Persistent handles and store the wrapper objects in MRUCache.

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architect...@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/platform-architecture-dev/325bdec0-dd49-46d7-876e-ef0b2c0f7c70%40chromium.org.

--

Kentaro Hara, Tokyo, Japan

[Michael Lippautz]

What's the problem with creating an LRU cache based on existing GCed types?

We are trying to remove boundaries to non-GCed layers. Every boundary that uses Persistent to interface with non-managed memory when managed memory would do decreases efficiency of GC.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/platform-architecture-dev/CABg10jz-VGqQKjso91EcsUJ8So4w3qV%3D8iw2z7jgTpAENwpS6g%40mail.gmail.com.

[Kentaro Hara]

What's the problem with creating an LRU cache based on existing GCed types?

My worry is the maintenance cost. Getting the GC integration right for Vectors, HashTables and LinkedHashSet has been a huge amount of work. I prefer avoiding introducing a new complex container.

We are trying to remove boundaries to non-GCed layers. Every boundary that uses Persistent to interface with non-managed memory when managed memory would do decreases efficiency of GC.

Yeah, agreed.

Another idea: Would there be any way to implement the LRU cache on top of the existing LinkedHashSet (which is already integrated with GC)? That resolves my concern :)

 

[Michael Lippautz]

On Fri, Oct 4, 2019 at 4:46 PM Kentaro Hara <har...@chromium.org> wrote:

What's the problem with creating an LRU cache based on existing GCed types?

My worry is the maintenance cost. Getting the GC integration right for Vectors, HashTables and LinkedHashSet has been a huge amount of work. I prefer avoiding introducing a new complex container.

We are trying to remove boundaries to non-GCed layers. Every boundary that uses Persistent to interface with non-managed memory when managed memory would do decreases efficiency of GC.

Yeah, agreed.

Another idea: Would there be any way to implement the LRU cache on top of the existing LinkedHashSet (which is already integrated with GC)? That resolves my concern :)

Sorry, I meant based on top of already existing types such as LinkedHashSet. I'd try to avoid adding a new primitive type but rather reuse existing ones.

 

[Dominik Röttsches]

Ping on this older thread. Since I am facing issues with unbounded cache growth in CSSSegmentedFontFace, would it be acceptable to have a version of my above CL asserting on using it with GC-types? I only need it for non garbage collected types at the moment, but I would already have three client locations [1] <- where we landed a concrete, non templated version for this use case, [2] where there is a separate age list next to the hash map to do a similar thing, and the issue I mentioned with CSSSegmentedFontFace.

[Kentaro Hara]

CSSSegmentedFontFace does not seem to involve any GC type. Would you help me understand why we need the GC type version of LRU cache?

[Dominik Röttsches]

Hi Kentaro,

sorry if my expression was confusing: by "asserting on using with GC types", I meant that we ensure that it cannot be used with GC types, like

static_assert(!WTF::IsGarbageCollectedType<T>::value, "WTF::Unretained() + GCed type is forbidden");

Dominik

[Kentaro Hara]

+1.

Having static_asserts for non-supported cases is always great :)

[Dominik Röttsches]

Hi again Kentaro,

On Wed, Feb 5, 2020 at 11:38 AM Kentaro Hara <har...@chromium.org> wrote:

+1.

Having static_asserts for non-supported cases is always great :)

Is that a +1 to my original question of having a templated LRU Cache in WTF for non GC types? 

Dominik

[Kentaro Hara]

Sorry for not being clear:

- +1 to having static_asserts for non-supported cases.

- +1 to creating a templated LRU cache in WTF. However, I suggest implementing it on top of the existing primitives (i.e., LinkedHashSet). Creating yet another primitive has a risk of causing more bugs and making it hard to support GC types in the future.

[Dominik Röttsches]

Hi Kentaro,

On Wed, Feb 5, 2020 at 11:54 AM Kentaro Hara <har...@chromium.org> wrote:

Sorry for not being clear:

- +1 to having static_asserts for non-supported cases.

- +1 to creating a templated LRU cache in WTF. However, I suggest implementing it on top of the existing primitives (i.e., LinkedHashSet). Creating yet another primitive has a risk of causing more bugs and making it hard to support GC types in the future.

Thanks, I have an implementation based on existing primitives, but not all of them support GC: it's based on WTF::DoublyLinkedList and and WTF::HashMap, I have been trying to come up with a design based on LinkedHashSet, but I don't think trying to repurpose a LinkedHashSet back to working like a HashMap is an efficient implementation. 

[Kentaro Hara]

In terms of implementing LRU cache, what's an issue of using LinkedHashSet instead of DoublyLlinkedList?

--

You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architect...@chromium.org.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/platform-architecture-dev/CAN6muBvt22OFXrkGuhOEhYE5pSh3%2B%2BbC6gh2L7Qnu%2B7okfXp6g%40mail.gmail.com.

[Dominik Röttsches]

For one: For an LRU cache that maps from a key to stored mapped type, I would use a HashMap, plus a DoublyLinkedList for keeping track of the age of entries. If I use the LinkedHashSet for the keeping track of the age, the extra hashing/set functionality of that is not used but the hashing is still performed anyway - that's where I see an efficiency issue. It's not impossible to use the linking part of LinkedHashSet. 

Dominik

[Kentaro Hara]

I see...

I'm fine with going with DoublyLinkedList for now. It won't be hard to replace it with LinkedHashSet when we need to support GC types in the future :)

[Dominik Röttsches]

Thanks, sounds good to me, I'll prepare a CL to add it, and we can discuss the implementation there. 

[Bartek Nowierski]

FYI, my intern is now working on DeterministicHashSet which will replace LinkedHashSet (it'll use a vector instead of linked list). If we implemented DeterministicHashMap (with capabilities of inserting at/removing from the front or back), will this solve your problem?

Collections with internal pointers, like linked lists, aren't desirable in the GC world.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/platform-architecture-dev/CAN6muBs%2BbnwcjbBjf8ikCvoQtf-Bi62J2oC6H0xvLvvNSYuhWQ%40mail.gmail.com.

[Kentaro Hara]

Dominik's concern is the unnecessary overhead caused by hashing. DeterministicHashSet still needs hashing, so I'm not sure if it resolves it... :/

At the same time, I'm not sure if the overhead is worth worrying about. I'd suggest replacing DoublyLinkedList with LinkedHashSet when we need a GC-supporting LRU cache.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/platform-architecture-dev/CAC3g16ghz5BLf4DLmcT9yT8M1t%3DYfozDgPCZb1MmLrmkdAtPbg%40mail.gmail.com.

[Dominik Röttsches]

Hi Bartek & Kentaro,

Bartek, thanks for the offer and suggestion - I do agree with both Kentaro's points in this case - plus, a DoublyLinkedList has the advantage of efficient removal and insertion to keep track of the age of entries, whereas a WTF::Vector would not provide this advantage. But there may be other ways of implementing a LRU Cache on top of DeterministicHashSet that I did not think about yet. Agree that we can revisit this once we need an LRU Cache for GC types.

Dominik

[Bartek Nowierski]

> Dominik's concern is the unnecessary overhead caused by hashing

He wants to use HashMap in addition to DoublyLinkedList, so I assumed he needs hashing for something, but wants to avoid LinkHashSet's hashing in addition to HashMap hashing.

> a DoublyLinkedList has the advantage of efficient removal and insertion to keep track of the age of entries, whereas a WTF::Vector would not provide this advantage

We have ideas how to handle those efficiently with Vector.

Anyway, we're talking about 1-2 month timeframe before we get to it. It's better if you proceed with your implementation and we can revise the plan once we get to it.

Bartek

[Dominik Röttsches]

Hi all,

thanks for the discussion - as an update, a LRU Cache for non GC types has now landed, see https://bugs.chromium.org/p/chromium/issues/detail?id=1010925#c4 for more details.

Dominik