349113 - [FIX]Speed up nsSpaceManager::ClearFloats

Status: RESOLVED FIXED

(Core :: Layout: Floats, defect, P1)

Description

[Boris Zbarsky [:bzbarsky]]

On the testcases for bug 64858, nsSpaceManager::ClearFloats is about 10% of the total pageload time.  I'll post a patch that significantly speeds it up on this testcase for me by avoiding almost all calls to ShouldClearFrame().  I _think_ this is the right patch in general, but I'm not sure.

With that patch, ClearFloats is only about 2-3% of total time; still a fair amount.  Would it be possible to keep track of the two values we really need here (the maximal YMost() of the left floats and the same for the right ones) as we go?  That would make calling ClearFloats O(1) in the number of floats, instead of the current O(N)....

Comment 1

[Boris Zbarsky [:bzbarsky]]

Attachment: Simple patch

Again, it would be nice if we could avoid having to do a loop here at all.  roc, do you think we can do that?  We'd just need to update a value every time we FlowAndPlaceFloat(), right?

Comment 2

[Boris Zbarsky [:bzbarsky]]

Attachment: More extensive patch

With this patch, on that testcase, I have ClearFloats at about than 0.05%.  The time spent in nsSpaceManager::CreateFrameInfo went up by about 0.03% of total profile time.  DestroyFrameInfo doesn't appear in the profile at all.  Overall times are about 10% faster than without this patch, as expected.

Comment 3

[Boris Zbarsky [:bzbarsky]]

I should note that the GetFrameInfoFor call that we expect to return nothing is generally _expensive_.  Could we remove it?  Or make it debug-only?  Or something?

Comment 4

[Boris Zbarsky [:bzbarsky]]

Attachment: With no GetFrameInfoFor in opt builds

I checked, and the only reasonable effect of the GetFrameInfoFor check in nsSpaceManager::AddRectRegion is an assert on the caller side (other than the early return itself, of course).  I think it makes more sense to just make the check debug-only to start with.

Comment 5

[Robert O'Callahan (:roc) (email my personal email if necessary)]

+  // Optimize for the case when the frame being removed is not likely to be
+  // near the bottom.  Is this reasonable?

Generally if frames are removed we remove the bottom frames :-) so this optimization doesn't really help.

I think PushState and PopState should save and restore your cached values.

+    // Optimize for the case when the frame being added is likely to be near
+    // the bottom.  Is this reasonable?

Yes.

+    mHaveCachedLeftYMost(PR_FALSE),
+    mHaveCachedRightYMost(PR_FALSE),
+    mMaximalLeftYMost(0),
+    mMaximalRightYMost(0)

Why not set the have-cache values to PR_TRUE here?

Comment 6

[Boris Zbarsky [:bzbarsky]]

Attachment: Updated to comments

Comment 7

[Robert O'Callahan (:roc) (email my personal email if necessary)]

+  // Optimize for the case when the frame being removed is likely to be near
+  // the bottom, but do nothing if we have neither cached value -- that case is
+  // likely to be hit from PopState().
+  if (mHaveCachedLeftYMost || mHaveCachedRightYMost) {
+    nscoord ymost = aFrameInfo->mRect.YMost();
+    PRUint8 floatType = aFrameInfo->mFrame->GetStyleDisplay()->mFloats;
+    if (mHaveCachedLeftYMost && ymost >= mMaximalLeftYMost &&
+        floatType == NS_STYLE_FLOAT_LEFT) {
+      mHaveCachedLeftYMost = PR_FALSE;
+    }
+    else if (mHaveCachedRightYMost && ymost >= mMaximalRightYMost &&
+             floatType == NS_STYLE_FLOAT_RIGHT) {
+      mHaveCachedRightYMost = PR_FALSE;
+    }
+  }

Like I said, this is not very useful. I would just flush the cache on the side that the float belongs to.

+        NS_ASSERTION(!mHaveCachedLeftYMost, "Shouldn't happen");

Why can't this happen?

I think this loop would be slightly better if you test the float style before checking ymost. Also, I would just accumulate the left and right ymost values in local variables and only change the spacemanager state at the end of the loop.

Comment 8

[Boris Zbarsky [:bzbarsky]]

> I would just flush the cache on the side that the float belongs to.

As in, skip the ymost check?  I'd like to keep the checks mHaveCachedLeftYMost and mHaveCachedRightYMost because we're generally removing several floats, and GetStyleDisplay() is a little expensive; I'd like to avoid doing it several thousand times (in edge cases) when it's not needed at all.

> Why can't this happen?

Hmm..  I probably need to push the assert down into the side check.

> If you test the float style before checking ymost

Hmm.  So if my left ymost needs updating and I have a whole slew of right-floats, most of them above a single left float, I'd like to avoid doing the expensive GetStyleDisplay() on them...  Or will said right floats come before the left float anyway in mFrameInfoMap?  I'm not sure what invariants I can assume that way, if any.

> I would just accumulate the left and right ymost values in local variables

Sure.  I can do that.

Comment 9

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to comment #8)
> > I would just flush the cache on the side that the float belongs to.
> 
> As in, skip the ymost check?  I'd like to keep the checks
> mHaveCachedLeftYMost and mHaveCachedRightYMost because we're generally
> removing several floats, and
> GetStyleDisplay() is a little expensive; I'd like to avoid doing it several
> thousand times (in edge cases) when it's not needed at all.

OK, just

  if (mHaveCachedLeftYMost || mHaveCachedRightYMost) {
    PRUint8 floatType = aFrameInfo->mFrame->GetStyleDisplay()->mFloats;
    if (floatType == NS_STYLE_FLOAT_LEFT) {
      mHaveCachedLeftYMost = PR_FALSE;
    }
    else {
      mHaveCachedRightYMost = PR_FALSE;
    }
  }

> > If you test the float style before checking ymost
> 
> Hmm.  So if my left ymost needs updating and I have a whole slew of
> right-floats, most of them above a single left float, I'd like to avoid doing
> the expensive GetStyleDisplay() on them...  Or will said right floats come
> before the left float anyway in mFrameInfoMap?  I'm not sure what invariants I
> can assume that way, if any.

Ok, I guess what you have is best then. Bottom floats will tend to be first in the list here so you will avoid almost all the calls to GetStyleDisplay().

Comment 10

[Boris Zbarsky [:bzbarsky]]

Attachment: Updated to comments again

Comment 11

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 235852 [details] [diff] [review]
Updated to comments again

great!

Comment 12

[Boris Zbarsky [:bzbarsky]]

Attachment: Merged to tip

Comment 13

[Boris Zbarsky [:bzbarsky]]

Fixed.