User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.0.1) Gecko/2008070208 Firefox/3.0.1 Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.0.1) Gecko/2008070208 Firefox/3.0.1 I posted this to my friends on the Daily WTF, thinking that it was Duke Energy's fault, but they claim that other browsers handle this much better. http://forums.thedailywtf.com/forums/t/10056.aspx I have the source from that page, if it has been taken down by the time this bug is examined. Contact me directly for this source. I couldn't attach the source to this bug report Reproducible: Always Steps to Reproduce: 1. Go to URL. I suggest you do it in a fresh browser so you don't lose any data that FF has open. 2. Wait many minutes. Actual Results: Firefox locks up for many minutes while rendering Expected Results: Firefox should only lock up for a few seconds while rendering Again, contact me for the source that is taking so long to render.

Confirmed on Windows XP. Regression range: http://bonsai.mozilla.org/cvsquery.cgi?module=PhoenixTinderbox&date=explicit&mindate=2005-10-16+11%3A00&maxdate=2005-10-16+23%3A00 Works: 2005101612 Fails: 2005101622 I guess its caused by Bug 288064.

Results that I get with this testcase: Firefox 2: 7906ms Trunk seems to hang forever. Google Chrome: 700ms

We're basically spending all our time in IsFrameAfter(), called from nsLayoutUtils::DoCompareTreePosition, called from nsCSSFrameConstructor::ProcessFrameInsertions. We enter the whole thing through a ProcessOneRestyle call (not much of a surprise there, sorta). So the first question, I guess, is why we're even hitting this code (i.e. why we're not getting the image loaded before frame construction in this case, and hence have to reframe). I'll look into that. But given that we do, we're basically looking at reframing all 6000 absolutely positioned frames, one by one. We're doing it in more or less a random order (or at least hashtable enumeration order), so we end up doing a CompareTreePosition on the lastChild (which is on average O(N)), probably discovering that we come before that, and then walking the linked list doing CompareTreePosition checks on all the things in it up to the right point (O(N^2), since each check averages O(N) and we average O(N) of them). Since this happens for each image, the whole thing is O(N^3), and we lose.

OK. The reason we do the early frame construction is that we're parsing the big gob of document.write stuff all in one shot, and at some point after we add the Nth image (7th, in this case!) the IsTimeToNotify() on the sink evaluates to true. Then we notify every several hundred images after that, for the same reason. I wonder what we can do in ProcessFrameInsertions (or even earlier, in restyle processing) to speed this up...

Another option is to only switch into the loading state after we've been loading "for a bit".

One thing we can do in ProcessFrameInsertions is to collect the containingBlock's child list into an array, then do binary search using nsLayoutUtils::CompareTreePosition instead of the sequential search we do now. That would get this down to O(N^2 log N).

Another thing we could do is analyze the set of things to be restyled. If there's a large number of elements to be restyled, and most of the children of some element require frame reconstruction, reconstruct frames on the parent instead. That would nail this I guess.

We can probably also create something like nsLayoutUtils::FindTreePosition which finds the place in a frame list where another frame should be inserted, and we could probably make that run in O(N) time in common cases, including this case. Probably worth doing instead of comment #6, but it only knocks off a log N. Another thing we could do is, when we reconstruct a frame, record its current parent and previous sibling. After we've constructed the new frame and figured out what its parent should be, if the parent is the same as the old parent we can use the old previous sibling as our new insertion point, right? Even if not, we could use it as a hint, and I think in ProcessFrameInsertions we could verify very quickly, constant time in common cases, whether the hint is correct.

Comment 7 was the best idea I had when I was thinking about this earlier today, for what it's worth. Comment 8 paragraph 2 is probably workable; I need to think about it. For those whom it reminds of the code we removed in bug 289377 (me, for example), it's quite different. ;) I did consider the array thing, but O(N^2 log N) is still too slow to be practical, I suspect.

If we can make comment 8 paragraph 2 work, then I think it beats any of those other options.

That would still leave this testcase O(N^2), for what it's worth. :(

Setting in-testsuite-? so that we can track getting this test eventually checked into the unit tests, because as noted in bug 491063, we don't have any tests for this behavior right now.

The changes we plan in bug 479655 will at least make the restyles process in non-random order; this might be easier to optimize at that point.

Presumably we could burn more space and be O(n) instead of O(n^2), like the loyal (or disloyal ;-) opposition do? /be

Brendan, _please_ read the bug? ;) 1) We're O(N^3), not O(N^2). 2) Other browsers have the same issue if they get to recreating layout objects. See comment 9. The difference on the original testcase is that they don't recreate image layout objects on it to start with, presumably. See comment 5 for one possible way we could try to do that, though it would lead to races where if the loads take "too long" we'd suddenly be slow all over again.

Boris, I was replying with comment 12 in mind. Even if we do what roc suggests, we're still too slow compared to the competition, which *does not* have the same issue (no "ifs" please). It's all fine that we have bugs to fix -- situation normal -- but why are we so unable to ape the competition here? Web developers will not want to hear excuses. I'm tired of 'em too, on all fronts (including JS perf). /be

Brendan, the competition has the same issue if you restyle all the images. It just doesn't restyle images during normal image load; we do. Why we do that is an interesting question and I would be happy to point you to the relevant bugs or discuss on irc or whatever. I would be quite amenable to changing that restyling behavior, as I mentioned earlier in this bug, but there are tradeoffs to be had there in terms of "correctness" and possibly predictability.

This is still an issue in Firefox11.0.

Mozilla/5.0 (Windows NT 10.0; WOW64; rv:49.0) Gecko/20100101 Firefox/49.0 I have tested on the latest Firefox release (46.0.1, Build ID: 20160502172042) and on the latest Nightly(49.0a1, Build ID: 20160519030232) and I haven't managed to reproduce it. When opening the URL from attachment 339225 [details], it doesn't hang, the script finishes running displays the time it took to run. I've also tested on Firefox 3.0.3 and 3.0.5 and manage to reproduce it. When opening the same URL, Firefox crashes. Considering this I will mark this issue as RESOLVED-WORKSFORME. If anyone still encounters this issue, feel free to reopen this one or file a new one.

I expect the new HTML parser made the situation described in comment 4 not get hit. The underlying problem is still there, I expect.

Fwiw, on this test Nightly is about 5 times *faster* than Chrome Canary. I guess it doesn't hit the case Boris is thinking of.