1367207 - ImageLoader::DropRequestsForFrame is a bit hashtable-lookup happy

Status: RESOLVED FIXED

(Core :: Layout, enhancement)

Description

[Boris Zbarsky [:bzbarsky]]

This shows up somewhat when destroying frames.  We do an unconditional lookup in mFrameToRequestMap which presumably usually misses.  If it _does_ hit, we proceed to do more lookups, and in fact repeat that same lookup (twice, if you count the ensuing Remove call).

Might be nice to gate this on a boolean flag or something.

Comment 1

[Mats Palmgren (inactive)]

Sure, this might be worth spending a frame bit on...
However, the more serious issue here seems to be that ImageLoader::DropRequestsForFrame
does one mFrameToRequestMap.Get and then, for *each* of the requests, calls
DisassociateRequestFromFrame which does *another* mFrameToRequestMap.Get.
http://searchfox.org/mozilla-central/rev/507743376d1ba753d14ab6b9305b7c6358570be8/layout/style/ImageLoader.cpp#153,182,192

Comment 2

[Boris Zbarsky [:bzbarsky]]

Which issue is more serious depends on how many things have entries in the mFrameToRequestMap to start with.

Comment 3

[Daniel Holbert [:dholbert]]

mats: if you haven't gotten too far into this, I have a WIP patch that I spun up in the background over the past ~hour to avoid the redundant mFrameToRequestMap.Get call.  (I should've self-assigned -- wanted to spin up a partial patch to see what I was getting myself into first. :) It's maybe ~10 lines total.)

So if you aren't already mostly-done with the Get() redundancy-elimination, feel free to kick this in my direction.  I'm good either way. :)

(RE the frame-state bit, it looks like we have exactly one frame state bit available right now, and it's unclear that *this specific hashtable lookup* is how we should spend it. Having said that, maybe we should buy ourselves some more frame state bits.)

Comment 4

[Daniel Holbert [:dholbert]]

Attachment: strawman patch

(For reference, here's the patch I've got, as a strawman option -- just splitting most of the existing public method into a private method, which takes a RequestSet (whose typedef is private, hence abstracting its usage away in a private helper).

This way, the internal callsite can pass in the already-obtained RequestSet*, and the external caller can use the public "wrapper", which now just looks up a RequestSet and passes that in to the private helper.

I'm happy to finish this off [probably just needs a commit message] or to discard it in favor of whatever likely-similar strategy you might be pursuing here. :)

Comment 5

[Mats Palmgren (inactive)]

I just pushed what I have to Try:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=2e9aa4a6127807d28290e82bee1324810a653630
I think that's pretty much what I intended to do.

> RE the frame-state bit

I just used a bool:1 for this.  FYI, I have some other patches that'll shuffle around
some frame state bits to make more of them global.  I've made two of them global so far,
but I think there's potential for a few more after that.
(details in bug 1367209 comment 8)

Comment 6

[Daniel Holbert [:dholbert]]

Comment on attachment 8874598 [details] [diff] [review]
strawman patch

OK, nice! And: packing a new bool:1 alongside existing bool:1 seems reasonable to me, yeah.

Comment 7

[Mats Palmgren (inactive)]

Attachment: part 1 - Add a nsIFrame bool:1 member to track whether the frame has some image requests associated with it

Comment 8

[Mats Palmgren (inactive)]

Attachment: part 2 - Update mFrameToRequestMap/mRequestToFrameMap more efficiently on frame removal

Comment 9

[Mats Palmgren (inactive)]

BTW, part 2 fixes the extra hashtable lookup as discussed above, but also fixes
a couple of additional perf problems in DropRequestsForFrame:
It first makes a copy of the array and then removes each entry separately.
http://searchfox.org/mozilla-central/rev/507743376d1ba753d14ab6b9305b7c6358570be8/layout/style/ImageLoader.cpp#159,188
Both seems unnecessary since we're removing all entries and then
deleting the array here.

Comment 10

[Mats Palmgren (inactive)]

Attachment: part 3 - Introduce nsClassHashtable::LookupRemoveIf() for consumers that wants to do a Get() then inspect/modify the value then, maybe, Remove() the entry

This is a pattern I've seen quite a lot recently when investigating
these hashtable perf issues:
1. Get()
2. do some stuff with the value
3. possibly Remove() the entry based on the new state of the value

It would be nice to have a way to do this without having to do
a second hashtable lookup in 3.

(See part 4 for a couple of examples.)

Comment 11

[Mats Palmgren (inactive)]

Attachment: part 4 - Use LookupRemoveIf() to avoid a second hashtable lookup for Remove()

Comment 12

[Mats Palmgren (inactive)]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=00fcd338a435f6be1b8b30eb7436bcd8b7f1f948

Comment 13

[Nathan Froyd [:froydnj]]

Comment on attachment 8874872 [details] [diff] [review]
part 3 - Introduce nsClassHashtable::LookupRemoveIf() for consumers that wants to do a Get() then inspect/modify the value then, maybe, Remove() the entry

Review of attachment 8874872 [details] [diff] [review]:
-----------------------------------------------------------------

r=me with the change below.  It's entirely possible that I'm tracing the calls and overload resolution wrong here, though.

I'm trying to think of a good way to test this that would have caught the below (and would ensure we don't regress things!), but I can't think of a way that doesn't require overhauling hashtables at the same time. :(

::: xpcom/ds/nsClassHashtable.h
@@ +140,5 @@
> +  /**
> +   * Looks up aKey in the hashtable and if found calls the given callback
> +   * aFunction with the value.  If the callback returns true then the entry
> +   * is removed.  If aKey doesn't exist nothing happens.
> +   * The hashtable must not be modified in the callback function.

Thank you for this documentation comment.

@@ +167,5 @@
> +    bool shouldRemove = aFunction(ent->mData);
> +    MOZ_ASSERT(tableGeneration == base_type::GetGeneration(),
> +               "hashtable was modified by the LookupRemoveIf callback!");
> +    if (shouldRemove) {
> +      this->Remove(aKey);

I think this should be RemoveEntry(ent).  Otherwise, Remove() will do a second hashtable lookup to find the entry for aKey, no?  (nsBaseHashtable::Remove(KeyType) will call nsTHashtable::RemoveEntry(KeyType), which sounds like it doesn't do an actual lookup, but nsTHashtable::RemoveEntry(KeyType) will call PLDHashTable::Remove, which very much does a lookup.)

Can you file a followup for renaming nsTHashtable::RemoveEntry(KeyType) or seeing if we can remove it entirely?  Might as well file a followup for changing RemoveAndForget to not do a redundant lookup as well.

Comment 14

[Mats Palmgren (inactive)]

Attachment: part 3 - Introduce nsClassHashtable::LookupRemoveIf() for consumers that wants to do a Get() then inspect/modify the value then, maybe, Remove() the entry

Bah, I looked at RemoveAndForget() and assumed it did the right thing, oh well...

We might as well fix that too while we're here since it's a trivial change.

Comment 15

[Nathan Froyd [:froydnj]]

Comment on attachment 8874890 [details] [diff] [review]
part 3 - Introduce nsClassHashtable::LookupRemoveIf() for consumers that wants to do a Get() then inspect/modify the value then, maybe, Remove() the entry

Review of attachment 8874890 [details] [diff] [review]:
-----------------------------------------------------------------

Thank you!

Comment 16

[Mats Palmgren (inactive)]

> Can you file a followup for renaming nsTHashtable::RemoveEntry(KeyType) or seeing if we can remove it entirely?

Filed bug 1370573.

Comment 17

[Daniel Holbert [:dholbert]]

Comment on attachment 8874865 [details] [diff] [review]
part 1 - Add a nsIFrame bool:1 member to track whether the frame has some image requests associated with it

Review of attachment 8874865 [details] [diff] [review]:
-----------------------------------------------------------------

r=me

Comment 18

[Daniel Holbert [:dholbert]]

Comment on attachment 8874867 [details] [diff] [review]
part 2 - Update mFrameToRequestMap/mRequestToFrameMap more efficiently on frame removal

Review of attachment 8874867 [details] [diff] [review]:
-----------------------------------------------------------------

r=me, just a few nits (with the function-rename being the most important one)

::: layout/style/ImageLoader.cpp
@@ +136,5 @@
>  }
>  
>  void
> +ImageLoader::DisassociateRequestFromFrameSet(imgIRequest* aRequest,
> +                                             nsIFrame*    aFrame)

This function needs a different name, I think.  Right now it's hard to figure out (or recall) what the actual behavior is based on the name -- superficially, the naming implies that this function would sever a request<-->frameset relationship.  BUT, that's not what it does -- instead, it removes a single frame *from* the frameset that is associated with a given request.  I have a pretty hard time mapping the function-name onto that behavior.

(Also: "Disassociate" kind of implies that we're updating *both* maps, since the association is a bidirectional relationship. But this function only updates one map.)

Could you rename this to more clearly correspond to its behavior?  Maybe:
  RemoveFrameFromRequestFrameSet()
...or something like that?

@@ +169,5 @@
> +  MOZ_ASSERT(aFrame->HasImageRequest(), "why call me?");
> +  DisassociateRequestFromFrameSet(aRequest, aFrame);
> +
> +  RequestSet* requestSet = nullptr;
> +  mFrameToRequestMap.Get(aFrame, &requestSet);

Now that this function has a bit less symmetry, it'd be nice to include two comments to reinforce the symmetry that does actually exist (to indicate that we're updating both maps)

e.g. right after the initial assertion:
  // Remove the frame from the request-to-FrameSet map:

...and then after that:
  // Remove the request from the frame-to-RequestSet map:

::: layout/style/ImageLoader.h
@@ +100,5 @@
>    nsresult OnImageIsAnimated(imgIRequest* aRequest);
>    nsresult OnFrameUpdate(imgIRequest* aRequest);
>  
> +  // Helper for DropRequestsForFrame / DisassociateRequestFromFrame above.
> +  void DisassociateRequestFromFrameSet(imgIRequest* aRequest, nsIFrame* aFrame);

Could you add an extra line here to briefly sum up what this function actually does? Something like:
  // Removes aFrame from aRequest's FrameSet (and drops the FrameSet if empty)

(And as noted for the .cpp file, I think this function wants a rename.)

Comment 19

[Daniel Holbert [:dholbert]]

It might actually be clearest to split up DisassociateRequestFromFrame's work into two helper functions:
  void RemoveRequestToFrameMapping(imgIRequest* aRequest, nsIFrame* aFrame); // Updates mRequestToFrameMap
  void RemoveFrameToRequestMapping(imgIRequest* aRequest, nsIFrame* aFrame); // Updates mFrameToRequestMap

(The former is what your "part 3" currently calls DisassociateRequestFromFrameSet -- and the latter would just encapsulate the rest of the code that you've currently got living in DisassociateRequestFromFrame)

Then, DisassociateRequestFromFrame would just be a two-liner:
{
  RemoveRequestToFrameMapping(aRequest, aFrame);
  RemoveFrameToRequestMapping(aRequest, aFrame);
}

That'd be nice from a symmetry/grokkability perspective.  And at the end of your patch stack, those two RemoveXXXFromYYY functions would basically look identical to each other -- each would call LookupRemoveIf on one or the other hash-map.  The only difference is which map they operate on, plus the fact that one function would have 1 caller and the other has 2 callers.

Comment 20

[Daniel Holbert [:dholbert]]

Comment on attachment 8874867 [details] [diff] [review]
part 2 - Update mFrameToRequestMap/mRequestToFrameMap more efficiently on frame removal

Review of attachment 8874867 [details] [diff] [review]:
-----------------------------------------------------------------

[retroactively calling part 2 "r-" since I think it can be structured a bit more clearly, per comment 19, such that my suggestions in comment 18 mostly become obsolete.]

Comment 21

[Daniel Holbert [:dholbert]]

Comment on attachment 8874873 [details] [diff] [review]
part 4 - Use LookupRemoveIf() to avoid a second hashtable lookup for Remove()

Review of attachment 8874873 [details] [diff] [review]:
-----------------------------------------------------------------

r=me on part 4.

(Though, as noted in comment 19, I'd like for the code you're rewriting here to live inside of two symmetric functions named something like RemoveRequestToFrameMapping & RemoveFrameToRequestMapping.  So I'm hoping the contextual code will end up looking slightly different in the end here. But the rewrite itself looks good, so r+.)

Comment 22

[Mats Palmgren (inactive)]

Attachment: part 2 - Update mFrameToRequestMap/mRequestToFrameMap more efficiently on frame removal

(compiles locally, but not tested on Try yet since it appears we have infra problems ATM)

Comment 23

[Mats Palmgren (inactive)]

Attachment: part 4 - Use LookupRemoveIf() to avoid a second hashtable lookup for Remove()

(just updating conflicts from the changes, carrying forward r+)

Comment 24

[Daniel Holbert [:dholbert]]

Comment on attachment 8875022 [details] [diff] [review]
part 2 - Update mFrameToRequestMap/mRequestToFrameMap more efficiently on frame removal

Review of attachment 8875022 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks for updating this! r=me with one nit:

::: layout/style/ImageLoader.h
@@ +101,5 @@
>    nsresult OnFrameUpdate(imgIRequest* aRequest);
>  
> +  // Helper for DropRequestsForFrame / DisassociateRequestFromFrame above.
> +  void RemoveRequestToFrameMapping(imgIRequest* aRequest, nsIFrame* aFrame);
> +  void RemoveFrameToRequestMapping(imgIRequest* aRequest, nsIFrame* aFrame);

s/Helper/Helpers/ in the comment here (now that there are two functions)

Comment 25

[Daniel Holbert [:dholbert]]

Comment on attachment 8875022 [details] [diff] [review]
part 2 - Update mFrameToRequestMap/mRequestToFrameMap more efficiently on frame removal

Review of attachment 8875022 [details] [diff] [review]:
-----------------------------------------------------------------

::: layout/style/ImageLoader.cpp
@@ +144,5 @@
>      nsCOMPtr<imgINotificationObserver> observer;
>      aRequest->GetNotificationObserver(getter_AddRefs(observer));
>      MOZ_ASSERT(!observer || observer == this);
>    }
>  #endif

Oh, actually -- one more observation/request -- could you add one more patch that moves this #ifdef DEBUG chunk (with GetNotificationObserver etc) back to the DisassociateRequestFromFrame() implementation?  rs=me on that patch in advance.

It's the only non-symmetrical think between the two RemoveXXXFromYYY cleanup functions at this point.  (And it feels a bit odd/arbitrary there, when these functions are otherwise equivalent, and when the assertion should be equally-valid in each of them.)  It makes more sense to me in DisassociateRequestFromFrame, since that's a public API and requires a higher level of parameter-sanity-checking than these private helper-functions do.

Comment 26

[Mats Palmgren (inactive)]

(In reply to Daniel Holbert [:dholbert] from comment #25)
> Oh, actually -- one more observation/request -- could you add one more patch
> that moves this #ifdef DEBUG chunk (with GetNotificationObserver etc) back
> to the DisassociateRequestFromFrame() implementation?

It checks that each of the request objects in the calls from
DropRequestsForFrame() are OK too, which seems like a good thing.
So I think it should stay.

Comment 27

[Daniel Holbert [:dholbert]]

True -- though the request objects in DropRequestsForFrame are less suspect (with regards to this assertion about "is this request related to |this| ImageLoader"), since in that function, we're pulling the request objects out of a member variable on the ImageLoader. *shrug*

Mostly, it feels a little odd to have this the assertion in one RemoveXXXFromYYY function but not in the other -- it gives the impression that we have different expectations in the two functions.

Anyway, not a big deal -- the patches are good as they are currently, too (modulo the comment 24 typo).

Comment 28

[Mats Palmgren (inactive)]

I'm keeping the assertions as the currently are.  I don't want to
pile on unrelated changes in this bug.

Comment 29

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/67181c32580e
part 1 - Add a nsIFrame bool:1 member to track whether the frame has some image requests associated with it.  Skip the call to DropRequestsForFrame() on frame destruction if the bit isn't set.  r=dholbert
https://hg.mozilla.org/integration/mozilla-inbound/rev/6d87a5768954
part 2 - Update mFrameToRequestMap/mRequestToFrameMap more efficiently on frame removal.  r=dholbert
https://hg.mozilla.org/integration/mozilla-inbound/rev/7307d037a922
part 3 - Introduce nsClassHashtable::LookupRemoveIf() for consumers that wants to do a Get() then inspect/modify the value then, maybe, Remove() the entry.  This is to avoid a second hashtable lookup for the Remove().  r=froydnj
https://hg.mozilla.org/integration/mozilla-inbound/rev/7fc0cbe0d71c
part 4 - Use LookupRemoveIf() to avoid a second hashtable lookup for Remove().  r=dholbert

Comment 30

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/67181c32580e
https://hg.mozilla.org/mozilla-central/rev/6d87a5768954
https://hg.mozilla.org/mozilla-central/rev/7307d037a922
https://hg.mozilla.org/mozilla-central/rev/7fc0cbe0d71c