263581 - [FIX]Improve WrappedLinesAreDirty() code

Status: RESOLVED FIXED

(Core :: Layout, defect, P2)

Description

[Boris Zbarsky [:bzbarsky]]

I had a patch to improve this in my tree based on some profile I did sometime,
and I just remembered it today (CVS conflicts can be useful, sometimes).  Then I
noticed we had an XXX comment about this code, even.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Attachment: Patch

Comment 2

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 161546 [details] [diff] [review]
Patch

The basic idea is to replace the "If this line is not dirty and has a dirty
continuation, dirty it" algorithm (which is indeed O(N^2)), with an "If this
line is not dirty and has a dirty continuation, dirty all the lines from here
to the continuation".  This should be O(N), since only two passes will be made
on the lines involved, instead of one pass per line up to the dirty
continuation.

I'm not completely happy with DirtyLineIfWrappedLinesAreDirty as a function
name, but couldn't think of a better one.

Comment 3

[Markus Hübner]

Might this have an impact on bug 142969 ?

Comment 4

[Boris Zbarsky [:bzbarsky]]

No idea.  That bug has a lot of discussion about not much, with no profile data
to back it up.

Comment 5

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 161546 [details] [diff] [review]
Patch

r+sr=dbaron, although I'm not sure the logic here makes sense (why only the
continuations before what's currently marked dirty?) -- but it's equivalent to
the old code.

It might be worth a comment at the call site of the new function with a one
line description of what that call does.

Comment 6

[Boris Zbarsky [:bzbarsky]]

> why only the continuations before what's currently marked dirty?

I suppose we could look forward to the _last_ dirty continuation we have and
dirty everything in between... I wasn't quite sure where in reflow to hook that
up, to be truthful.  The current code will still fail for the case when all
lines following the line in question are clean (so it'll be O(N^2) in the number
of lines between the last dirty line and the end of the block).  Would it be OK
to pre-dirty all lines with dirty continuations before we enter the reflow loop?
 Or can continuations become dirty while we're in the loop?

I'd be happy to do a followup patch to make this better yet, if someone can
answer those questions...

Comment 7

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

> Would it be OK to pre-dirty all lines with dirty continuations before we enter
> the reflow loop? Or can continuations become dirty while we're in the loop?

The current line can become dirty inside the loop, but future lines cannot, so
it wouldn't affect the behaviour of your function. I think it would be safe to
handle this situation by traversing the lines backwards in a single pass before
entering the loop.

Comment 8

[Boris Zbarsky [:bzbarsky]]

Attachment: Do it all outside the loop

Comment 9

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 166996 [details] [diff] [review]
Do it all outside the loop

So like so?

Comment 10

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

Comment on attachment 166996 [details] [diff] [review]
Do it all outside the loop

Yeah, except that you need to process the first line too

Comment 11

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

Comment on attachment 166996 [details] [diff] [review]
Do it all outside the loop

oops, you do

Comment 12

[Boris Zbarsky [:bzbarsky]]

Checked in followup patch too.  It seemed to help Tp on btek some...