Bug 4789 – so slow it feels like a hang calling UCFindTextBreak() tons of times at forum.presence-pc.com

• Status: RESOLVED
• Resolution: FIXED
• Component: Layout and Rendering

[Darin Adler]

<rdar://problem/3698926>

Safari hangs loading this page.

7/21/04 10:57 PM Trey Matteson:
We are not hung in UCFindTextBreak(), we are calling it a ridiculous number of times.  The isBreakable() 
API is a really bad match to the UC routine, since the former wants to ask about each individual position 
and the latter wants to scan the whole string for the break.

In this case I see us calling isBreakable with the same string and len=65388 and a pos that increments 
once with each call.  That's N^2 on the length of the string, since we keep scanning all the way to the 
end.

If we knew how to character wrap we wouldn't be killed by this either.

Created attachment 3720 [details]
Make breakability testing run in linear time

Comment on attachment 3720 [details]
Make breakability testing run in linear time

I think it would be interesting to measure the effect on performance in the
Latin-1 case as well.

Created attachment 3721 [details]
Make breakability testing run in linear time

Removed unnecessary (and incorrect) check for changes to breakNBSP.

[Darin Adler]

Comment on attachment 3721 [details]
Make breakability testing run in linear time

Should the "if (pos > nextBreakable)" be a while instead? If not, why doens't
it need to be?

I'll review this soon -- looks really great!

(In reply to comment #4)
> (From update of attachment 3721 [details] [edit])
> Should the "if (pos > nextBreakable)" be a while instead? If not, why doens't
> it need to be?

No. Since the 2nd parameter we pass to nextBreakablePosition is pos, its result will be >=pos.

[Darin Adler]

Comment on attachment 3721 [details]
Make breakability testing run in linear time

This is great! We've needed a fix like this for so long!

In RenderBlock::findNextLineBreak, it seems unfortunate that
nextBreakablePosition gets called more often than it needs to. For example,
it's called when isPre is true, and when the character is not '\n'.  I think
that could easily be fixed with a helper function that does both the "pos >
nextBreakable" work and the "pos == nextBreakable" check all in one, that is
called inside the expression.

Once you write that function, you might be able to use it in
RenderText::calcMinMaxWidth too, altough that code doesn't seem to do extra
nextBreakablePosition calls.

The expression "i+wordlen" appears so many times in the while loop in
RenderText::calcMinMaxWidth that I think it's worth changing the loop to use
something more like "j" and compute wordlen afer the loop. It's also not good
that the current character is fetched four different times. Lets rewrite that
loop as long as we're changing the code. I'm not certain it's a hot code path,
but it seems it could also be easier to read if redone a bit.

Frankly, re-getting str->s and str->l over and over again is aso pretty weak.
It's a memory access every time that might be avoided if we just put those
values into local variables.

Setting this to review- because of the RenderBlock::findNextLineBreak issue.
Please consider the other comments as suggestions. Maybe those changes would be
best left to another patch -- I don't feel strongly either way.

Created attachment 3733 [details]
revised patch

Comment on attachment 3733 [details]
revised patch

I'm not sure about using the name isBreakable for the new function, but I
couldn't think of anything better.

Comment on attachment 3733 [details]
revised patch

oops, bad diff

Created attachment 3735 [details]
revised patch

Comment on attachment 3735 [details]
revised patch

So, as I said, I'm not sure about using the name isBreakable for the new
function, but I
couldn't think of anything better.

[Dave Hyatt]

I'll need to study this closely heh.

[Darin Adler]

Comment on attachment 3735 [details]
revised patch

I see one mistake here.

The code says "j == 0" where it should say "j == i".

Otherwise, this looks super-great!!

[Darin Adler]

Comment on attachment 3735 [details]
revised patch

And I was wrong about j=0. r=me.