Bug 30209 – Cache::m_liveDecodedResource is not sorted by CachedResource::m_lastDecodedAccessTime

• Component: WebCore Misc.
• Status: RESOLVED FIXED

[Holger Freyther]

The Cache::pruneLiveResources is expecting the Cache::m_liveDecodedResource to be sorted by m_lastDecodedAccessTime but this is not true because of CachedResource::setDecodedSize inserting the resource with m_lastDecodedAccessTime = 0.


The problem now is that inserting with sorting is killing performance and updating m_lastDecodedAccessTime might have negative impact on the cache. I have decided to update the m_lastDecodedAccessTime but have not done measurement on my private PLT.

[Holger Freyther]

Created attachment 40868 [details]
Update m_lastDecodedAccessTime in CachedResource::setDecodedSize

Update the m_lastDecodedAccessTime when we insert the resource. The code in CachedImage is checking the FrameView painting time but the CachedResource is not doing this when using WTF::currentTime so I decided to not do it.

I just recognized that this has a problem with the CachedImage::didDraw code... as this is using FrameView time which is before ::currentTime(). So CachedResource::setDecodedSize should use the FrameView time as well.

I'm posting this patch anyway to get feedback on the issue and the proposed resolution.

[Adam Barth]

Comment on attachment 40868 [details]
Update m_lastDecodedAccessTime in CachedResource::setDecodedSize

This seems fine.  Can we add an ASSERT somewhere to ensure that we maintain this invariant?

[Yong Li]

Comment on attachment 40868 [details]
Update m_lastDecodedAccessTime in CachedResource::setDecodedSize

Let commit bot land it

[Geoffrey Garen]

Comment on attachment 40868 [details]
Update m_lastDecodedAccessTime in CachedResource::setDecodedSize

Removing from commit queue so I can comment before this lands.

[Geoffrey Garen]

Adam:

I disagree with r+ing this patch.

Holger said he experienced serious performance problems with earlier versions, and it's not clear that those problems have been resolved. He also said that this patch "has a problem".

Please consider my comments to Holger -- I think an r- might be appropriate here, at least until Holger has a chance to respond.

Holger:

Storing a painting time in FrameView was an effort to avoid excessive calls to currentTime(), which can be expensive. It would be nice if you could piggy-back on that stored value, but unfortunately it gets set to 0 when painting ends. Maybe we could invent something similar that you could piggy-back on.

I'm worried that these new calls to currentTime() will be a performance problem. Did you test performance with this latest patch? If so, what were your results?

Also, what user-visible bug are you fixing? I'm having a hard time understanding what problem arises as a result of a CachedImage being inserted into the LRU list with an initial m_lastDecodedAccessTime of 0. I see that m_liveDecodedResources is assumed to be ordered from most recently to least recently accessed, but I don't see a place where tying that order to m_lastDecodedAccessTime is important. The one thing I do see is this:

            double elapsedTime = currentTime - current->m_lastDecodedAccessTime;
            if (elapsedTime < cMinDelayBeforeLiveDecodedPrune)
                return;

Technically, an m_lastDecodedAccessTime of 0 could cause thrash in this case, by allowing the cache to destroy decoded data on a resource that had just decoded. However, that seems almost impossible in practice, since that one resource would need to be big enough to bust the Cache size limits all by itself. Have you seen something like that happen?

[Eric Seidel (no email)]

Comment on attachment 40868 [details]
Update m_lastDecodedAccessTime in CachedResource::setDecodedSize

Marking r- (abarth will forgive me) to remove it from the to-be-landed queue.  I'm sure Holger will get reply to ggaren soon.

[Holger Freyther]

(In reply to comment #5)
> Adam:
> 
> I disagree with r+ing this patch.
> 
> Holger said he experienced serious performance problems with earlier versions,
> and it's not clear that those problems have been resolved. He also said that
> this patch "has a problem".

The performance remark:
     - I don't have a iBench setup or any other access to a good to a performance benchmark. So my comments on performance are hyptothetical. My remark was that when we change the code to go through the list and insert it at the right position we will end up with a O(n) runtime instead of the almost constant we have now.

     - I have picked the solution that has less computation but I'm not able to propely profile this change.


Problems:
      - Yes I will need to add a if statement to the patch and I will upload a new one.



> Storing a painting time in FrameView was an effort to avoid excessive calls to
> currentTime(), which can be expensive. It would be nice if you could piggy-back
> on that stored value, but unfortunately it gets set to 0 when painting ends.
> Maybe we could invent something similar that you could piggy-back on.
>



> I'm worried that these new calls to currentTime() will be a performance
> problem. Did you test performance with this latest patch? If so, what were your
> results?

See the above, I'm sadly not in the position to properly benchmark it yet.


 
> Also, what user-visible bug are you fixing?
> I'm having a hard time
> understanding what problem arises as a result of a CachedImage being inserted
> into the LRU list with an initial m_lastDecodedAccessTime of 0. I see that
> m_liveDecodedResources is assumed to be ordered from most recently to least
> recently accessed, but I don't see a place where tying that order to
> m_lastDecodedAccessTime is important. The one thing I do see is this:
> 
>             double elapsedTime = currentTime -
> current->m_lastDecodedAccessTime;
>             if (elapsedTime < cMinDelayBeforeLiveDecodedPrune)
>                 return;
> 
> Technically, an m_lastDecodedAccessTime of 0 could cause thrash in this case,
> by allowing the cache to destroy decoded data on a resource that had just
> decoded. However, that seems almost impossible in practice, since that one
> resource would need to be big enough to bust the Cache size limits all by
> itself. Have you seen something like that happen?

Right, in the case of the m_lastDecodedAccessTime of 0 the above if statement will almost certainly evaluate to false and the decoded data will be destroyed but even this can only happen when the item "sank" deep enough into the queue. So my initial idea that it will lead to other data not being freed was wrong.


I'm still in the process of trying to understand memory usage in the Qt port, so I spent some time with the Cache trying to figure out how much is in there, why is it kept in the cache and seein that the list is not sorted.

How would you proceed? Just add a comment that the list is not always sorted but it is okay, do it correctly and see the performance impact?

[Holger Freyther]

Created attachment 41473 [details]
Update m_latDecodedAccessTime in CachedResource::setDecodedSize

This would be "the final" patch. I'm not setting review as I wait for Garen's comment on how to proceed.

[Geoffrey Garen]

Let's see... I think we understand each other now, so good for us :).

I like the spirit of your patch -- code that's subtly wrong, but actually right for an even more subtle reason, is hard to work with.

It's too bad that we don't have any good public page load benchmarks.

If you're happy with it, I'm happy with the comment solution, because it's easiest, and the comment probably only has to go in one place.

If you prefer the patch, I can make some time to do some page load benchmarking, or I can ask someone else here to do some page load benchmarking.

[Holger Freyther]

Created attachment 41860 [details]
Comment the behavior of the live resources list

First attempt at the solution using a comment to describe the quirk and why it is not that bad.

[Darin Adler]

Comment on attachment 41860 [details]
Comment the behavior of the live resources list

Looks good.

> +    // The list is not stricly sorted by the m_lastDecodedAccessTime but

Typo here "stricly".

> +    // the impact of this behavior is minor as the below if with the return
> +    // statement will not evaluate to true as the currentTime is >> than
> +    // current->m_lastDecodedAccessTime. For more details see:
> +    // https://bugs.webkit.org/show_bug.cgi?id=30209

I am not sure that the term "not strictly sorted" is the right one here. Typically "strict" sorting simply means a sort where no two items are considered equal.

Maybe you mean "does not maintain a strict invariant" or something like that?

> +        // Insert into or remove from the live decoded list if necessary. When inserting
> +        // into the LiveDecodedResourcesList the m_lastDecodedAccessTime might still be
> +        // zero or smaller than the m_lastDecodedAccessTime of the current head of this
> +        // list. This is a violation of the current invariant but it is not a problem.

The term "the current invariant" here is confusing. I don't know what could make something both "current" and "invariant". Different wording would be clearer. You could just remove "current", I guess. I think it would be best to say "a violation of the invariant that the list be kept sorted by access time".

Since the patch is entirely about comments, I'll say review- because of the typo.

[Holger Freyther]

Created attachment 41943 [details]
Comment the weaker invariant

Attempt to be more precise. Darin thanks a lot for taking a look.

[Darin Adler]

Comment on attachment 41943 [details]
Comment the weaker invariant

Looks good.

> +        // that the tm_lastDecodedAccessTime is still zero or smaller than

That should be "m_" rather than "tm_".

> +        // by access time. The weakening of the invariant does not impose
> +        // a problem. For more details please see: https://bugs.webkit.org/show_bug.cgi?id=30209

That should be "does not pose a problem" rather than "does not impose a problem".

As with the last round of review, since this patch is entirely about comments, I'm holding the comments to a higher than usual standard. review- so you can fix those two mistakes. Or you can fix them and land -- no need for a formal review+ in my opinion.

[Holger Freyther]

Thanks for the higher standards. I will take it as a r=+ and carry out the two proposed fixes. Thanks a lot for taking your time.

[Holger Freyther]

Landed in r50213.