1362886 - Consider devirtualizing nsIFrame::IsLeaf()

Status: RESOLVED FIXED

(Core :: Layout, enhancement)

Description

[(no longer active)]

I noticed this come up in the profile of bug 944127.

As I was trying to come up with a strategy to fix this, I noticed that there are only two implementations of this that aren't simply returning true:

 * nsContainerFrame::IsLeaf() returns false, but I'm not sure how important that is, since so concrete frames of type nsContainerFrame should ever be created, as far as I know.
 * nsMenuControlFrame::IsLeaf()'s implementation is very complex: <https://searchfox.org/mozilla-central/rev/8b70b0a5038ef9472fe7c53e04a70c978bb06aed/layout/xul/nsMenuPopupFrame.cpp#412>.

It seems like we can replace IsLeaf() with an inline function that checks mType against LayoutFrameType::MenuPopup and calls an nsMenuControlFrame helper in that case.

Comment 1

[(no longer active)]

Attachment: Devirtualize nsIFrame::IsLeaf()

The existing implementations of IsLeaf() all return true except for two:

  * nsContainerFrame::IsLeaf() returns false, but no concrete frame types of
    this type can be created.
  * nsMenuControlFrame::IsLeaf()'s implementation is complex.

This patch makes nsIFrame an inline non-virtual function that hands off the
hard work to nsMenuControlFrame through a virtual function if the frame type at
hand is a XUL menu control frame, and otherwise merely returns true.

Comment 2

[Mats Palmgren (inactive)]

(In reply to :Ehsan Akhgari (super long backlog, slow to respond) from comment #1)
>   * nsContainerFrame::IsLeaf() returns false, but no concrete frame types of
>     this type can be created.

I don't understand why that matters.  nsBlockFrame is a sub-class that we do create
concrete instances of, so wouldn't this patch make nsBlockFrames return true now?
(and Grid/Flexbox containers, various table frames etc)

Did this patch pass regression tests?

Comment 3

[(no longer active)]

Comment on attachment 8865263 [details] [diff] [review]
Devirtualize nsIFrame::IsLeaf()

Oh of course not!

Now that we have FrameTypeList, we can add a field to each frame tupe to indicate whether it is leaf or not, and have a third value for the menu popup frame case.  Then we can have a table of these values and have IsLeaf() look at that table to decide what to do.

Sorry about not being careful enough...

Comment 4

[Mats Palmgren (inactive)]

I think an array of bools should work fine for the non-MenuPopup types.
You need to add a couple of new FrameTypes for this though since that
hierarchy doesn't correspond exactly to the IsLeaf results we want.
Let me know if you want help with that...

Comment 5

[(no longer active)]

Attachment: WIP

Comment 6

[(no longer active)]

(In reply to Mats Palmgren (:mats) from comment #4)
> I think an array of bools should work fine for the non-MenuPopup types.
> You need to add a couple of new FrameTypes for this though since that
> hierarchy doesn't correspond exactly to the IsLeaf results we want.
> Let me know if you want help with that...

The WIP patch I just attached sort of does the array of bool thing.  The try server isn't very happy: <https://treeherder.mozilla.org/#/jobs?repo=try&revision=c83c16f121133b9c6880bdfee42bfdb32f16dab0>  I suspect that's because of the issue you had in mind.  I do in fact appreciate some help here if you don't mind.  :-)  I didn't really expect this to turn into this much work.  I do think it's worth finishing it but I don't have a sense of how much work adding the new frame types is going to be, if you think it's a lot of work then maybe it's not worth investing a lot of time in it right now?

Comment 7

[Mats Palmgren (inactive)]

Your patch looks great so far.  I think it just needs a few tweaks to make it work
so it seems worth doing to push it over the line...

Comment 8

[(no longer active)]

Thank you so much! :-)

Comment 9

[Mats Palmgren (inactive)]

Attachment: WIP part 2

Here's a patch that I wrote on top of your's.  I'll comment on my changes
in logical order, i.e. not necessarily the order they occur in the patch.

>+FRAME_TYPE(Container, NotLeaf)

So, we have some sub-classes that wants to be Leaf (see the removed
IsLeaf() methods) and some that don't.  The default for nsContainerFrame
sub-classes needs to be NotLeaf b/c that's what nsContainerFrame::IsLeaf()
currently says.

>+FRAME_TYPE(AtomicContainer, Leaf)

A sub-class of nsContainerFrame that obviously should be Leaf,
as its current IsLeaf() method says.

>+FRAME_TYPE(FileControl, Leaf)

A sub-class of nsBlockFrame, I'll come back to this one later...

>+FRAME_TYPE(MathMLmspace, Leaf)

A sub-class of nsMathMLContainerFrame, a sub-class of nsContainerFrame,
but is a leaf per its current IsLeaf() method.

>-FRAME_TYPE(None, NotLeaf)
>+FRAME_TYPE(None, Leaf)

None represents the "anything-else" case, i.e. should return what
nsIFrame::IsLeaf() says, i.e. Leaf.

>-FRAME_TYPE(Progress, NotLeaf)
>+FRAME_TYPE(Progress, Leaf)
>-FRAME_TYPE(Range, NotLeaf)
>+FRAME_TYPE(Range, Leaf)
>-FRAME_TYPE(SVGUse, NotLeaf)
>+FRAME_TYPE(SVGUse, Leaf)
>-FRAME_TYPE(TextInput, NotLeaf)
>+FRAME_TYPE(TextInput, Leaf)

All these inherit nsContainerFrame, but needs to be Leaf according to
their current IsLeaf() methods.

>-FRAME_TYPE(TableCol, NotLeaf)
>+FRAME_TYPE(TableCol, Leaf)

Just a mistake - this class inherits nsFrame so is a leaf.

>+  using FT = mozilla::LayoutFrameType;
>+  nsAtomicContainerFrame(nsStyleContext* aContext, FT aType)
>+    : nsContainerFrame(aContext, aType != FT::None ? aType : FT::AtomicContainer)

To support the FRAME_TYPE added above.
 
>+  using FT = mozilla::LayoutFrameType;
>+  nsContainerFrame(nsStyleContext* aContext, FT aType)
>+    : nsSplittableFrame(aContext, aType != FT::None ? aType : FT::Container)

ditto

>+  explicit nsMathMLmspaceFrame(nsStyleContext* aContext)
>+    : nsMathMLContainerFrame(aContext, mozilla::LayoutFrameType::MathMLmspace) {}

ditto

>+  using FT = mozilla::LayoutFrameType;
>+  nsMathMLContainerFrame(nsStyleContext* aContext, FT aType = FT::None)
>+    : nsContainerFrame(aContext, aType)

This is needed for MathMLmspace which now pass up aType.

> nsFileControlFrame::nsFileControlFrame(nsStyleContext* aContext)
>-  : nsBlockFrame(aContext)
>+  : nsBlockFrame(aContext, mozilla::LayoutFrameType::FileControl)

nsFileControlFrame is interesting b/c it inherits nsBlockFrame but
(currently) have no LayoutFrameType of its own.  It is a leaf though,
per its IsLeaf() method.  So we need to add a FRAME_TYPE for it to
be able to mark it as Leaf (unlike nsBlockFrame), but this changes
its Type() result but this *might* cause problems.  Based on how
LayoutFrameType::Block is used though, it looks OK to me.
http://searchfox.org/mozilla-central/search?q=LayoutFrameType%3A%3ABlock&case=false&regexp=false&path=

BTW, here's a Try run with these changes.  I also kept the current
IsLeaf() methods (renamed as IsLeafOLD()) and verify that the new
value is the same as before:
> MOZ_ASSERT(sLeafTypes[size_t(mType)] == IsLeafOLD())
https://treeherder.mozilla.org/#/jobs?repo=try&revision=1198216fb1ad19e0387270ebcb411c231c0ca308

Comment 10

[Mats Palmgren (inactive)]

BUT, after making these changes (nsFileControlFrame in particular)
I think that mapping Leaf/NotLeaf from the FrameType hierarchy isn't
a good match.  It seems brittle and hard to maintain.  Also, I think we
should probably move away from using LayoutFrameType in general.

So, I'll try a different approach that I think may be easier to deal
with and may have other benefits as well...

Comment 11

[(no longer active)]

Ouch, sorry to have lead you down this path, I admit that I didn't think this through all that carefully in hindsight...  :-/

Comment 12

[Mats Palmgren (inactive)]

No worries, Ehsan.  I've figured out a better way to devirtualize all these methods,
Type(), IsLeaf(), IsFrameOfType(), do_QueryFrame(), etc, that I think should be
easier to understand and maintain.  I've filed bug 1364805 to implement that.
I'll then devirtualize IsLeaf() here using that scheme.

Comment 13

[Mats Palmgren (inactive)]

Attachment: part 1 - Annotate the FRAME_ID for each concrete frame class whether it's a leaf or not. Generate a <bitset> with the values.

Comment 14

[Mats Palmgren (inactive)]

Attachment: part 2 - Devirtualize the IsLeaf() method to do a <bitset> lookup instead.

Comment 15

[Mats Palmgren (inactive)]

Fwiw, I did a Try run with both the old IsLeaf() methods and the new <bitset>
that asserted that the values matched:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=ce762cd03436a773eec41845e13f5347c3f2612f

Comment 16

[Jonathan Kew [:jfkthame]]

Is it really worth creating a bitset here, rather than just an array of bool? I'd assume the latter would be (marginally) cheaper to access.

Comment 17

[Mats Palmgren (inactive)]

Attachment: perf numbers

(In reply to Jonathan Kew (:jfkthame) from comment #16)
> Is it really worth creating a bitset here, rather than just an array of
> bool? I'd assume the latter would be (marginally) cheaper to access.

Good question, dbaron asked about virtual calls vs array lookup too,
in bug 1364805.  It's a bit hard to measure though since a single IsLeaf()
call is in the nano-second range so timing each individual call using
TimeStamp might not be accurate.  OTOH, doing a mockup that does millions of
"IsLeaf()" calls in a loop is easier to time, but likely not representative
of a real workload since there will be no cache misses.  Anyway, I tried both,
and it seems like array lookup wins in most cases.

It looks like a clear win when replacing a virtual call with a simple array
lookup, i.e. if IsLeaf had been: IsLeaf() { return array[mClass]; }.
But IsLeaf() actually involves two array lookups and a branch:

  bool IsLeaf() const
  {
    if (Type() == mozilla::LayoutFrameType::MenuPopup) {
      return IsXULMenuPopupFrameLeaf();
    }
    MOZ_ASSERT(uint8_t(mClass) < mozilla::ArrayLength(sIsLeafArray));
    return sIsLeafArray[uint8_t(mClass)];
  }

Note that the Type() call there is another array[mClass] lookup.
On Linux, virtual calls are actually faster than that when run in a tight
loop, but note that this is the ideal case with no I-cache misses.
On OSX and Win64 though, the above still wins over virtual calls.
Same platform difference for bitset: it (barely) wins on Linux,
but not on OSX/Win64.

BTW, here's my mockup test:
https://hg.mozilla.org/try/rev/35dc41cf72fd08bb154a5bc6d3fdc0929826d18c
(I hacked the TestTimeStamp gtest to instead do my tests)

Better ideas for more accurate measuring are welcome...

Comment 18

[Mats Palmgren (inactive)]

Attachment: part 1 - Annotate the FRAME_ID for each concrete frame class whether it's a leaf or not. Generate an array of bool with the values.

(now using array instead of bitset)

Comment 19

[Mats Palmgren (inactive)]

Attachment: part 2 - Devirtualize the IsLeaf() method by doing an array lookup instead.

Comment 20

[Mats Palmgren (inactive)]

Ehsan, feel free to test the Try builds with your workload to see if it makes a difference:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=52e9a21c630a84a98056d1504dbcf1c7050ce307

Comment 21

[Jonathan Kew [:jfkthame]]

Comment on attachment 8870887 [details] [diff] [review]
part 2 - Devirtualize the IsLeaf() method by doing an array lookup instead.

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

::: layout/generic/nsIFrame.h
@@ +2844,5 @@
> +    if (Type() == mozilla::LayoutFrameType::MenuPopup) {
> +      return IsXULMenuPopupFrameLeaf();
> +    }
> +    MOZ_ASSERT(uint8_t(mClass) < mozilla::ArrayLength(sIsLeafArray));
> +    return sIsLeafArray[uint8_t(mClass)];

It seems unfortunate that (in the common case) we end up doing two global array lookups for IsLeaf(), first one to look up Type() and then the second one here.

So here's a thought: how about instead of an array of bool, make the sIsLeafArray into an array of something like

  enum class EIsLeaf : uint8_t { kNotLeaf, kLeaf, kUnknown };

and then do

  bool IsLeaf() const
  {
    EIsLeaf isLeaf = sIsLeafArray[mClass];
    if (isLeaf == EIsLeaf::kUnknown) {
      return IsLeafDynamic(); // virtual, override in menupopup
    } else {
      return isLeaf == EIsLeaf::kLeaf;
    }
  }

(with added casts, assertions, etc as appropriate) so that we only need a single array lookup. WDYT?

Comment 22

[Mats Palmgren (inactive)]

Attachment: part 1 - Annotate the FRAME_ID for each concrete frame class whether it's a leaf or not. Generate an array containing the IsLeaf state for each frame class.

Good point, that's definitely better.

The only change in nsFrameIdList.h compared to the last patch is that
nsMenuPopupFrame now uses DynamicLeaf.

I'm making it intentionally a bit more generic than what is needed for
the IsLeaf state, so that we can add more state bits to this array in
the future if needed.

Comment 23

[Mats Palmgren (inactive)]

Attachment: part 2 - Devirtualize the IsLeaf() method by doing an array lookup instead.

Comment 24

[Jonathan Kew [:jfkthame]]

Comment on attachment 8871409 [details] [diff] [review]
part 2 - Devirtualize the IsLeaf() method by doing an array lookup instead.

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

Looks good, thanks!

Comment 25

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/13074ff6822b
part 1 - Annotate the FRAME_ID for each concrete frame class whether it's a leaf or not.  Generate an array containing the IsLeaf state for each frame class.  r=jfkthame
https://hg.mozilla.org/integration/mozilla-inbound/rev/d904a186e908
part 2 - Devirtualize the IsLeaf() method by doing an array lookup instead.  r=jfkthame

Comment 26

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/13074ff6822b
https://hg.mozilla.org/mozilla-central/rev/d904a186e908