Closed Bug 506844 Opened 15 years ago Closed 13 years ago

Clearing the kids of a div in SetInnerHTML and SetNodeTextContent leads to quadratic behavior due to nsLineBox::IndexOf

Categories

(Core :: General, defect, P1)

Product:
Core
Component:
General
Platform:
x86
Windows XP
Type:
defect

Tracking

()

Status:
RESOLVED FIXED
Milestone:
mozilla8

People

(Reporter: vivid_me, Assigned: bzbarsky)

References

Details

(Keywords: perf, testcase)

Attachments

(2 files, 1 obsolete file)

Testcase
2.32 KB, text/html
Details
Remove kids in order, not in reverse order, when clearing textContent and innerHTML.
2.73 KB, patch
sicking
: review+
Details | Diff | Splinter Review 
User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.1.1) Gecko/20090715 Firefox/3.5.1
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.1.1) Gecko/20090715 Firefox/3.5.1

In FF3 or higher, after a DIV is filled with huge amount of data using AJAX technology, when I want to empty that DIV using JavaScript code like below:
document.getElementById('myDIV').innerHTML = '';
depending on how much data is in that DIV, the browser halts and for huge data it crashes!!
I checked this issue in IE7, Opera 10, Chrome 3 and FF2 and worked without any problem.
Thanks further.

Reproducible: Always

Steps to Reproduce:
1.Make a DIV as 'myDIV'
2.Fill the DIV by AJAX Technology with huge amount of data
3.Write a JavaScript code as "document.getElementById('myDIV').innerHTML = '';" to empty that DIV
4.Execute code to empty that DIV
Actual Results:  
Depending how much data is in DIV the browser freezes and for huge data take too long period which leads to crash!

Expected Results:  
Like IE, FF2, Opera and Chrome the FF3 or higher browser should make that DIV empty after 2-3 seconds for huge amount of data.
Version: unspecified → 3.5 Branch
It seems that this is good reproducible. A test case is far more useful, then a crash report (although we the crash report it can easily be checked if this is one of the secret bugs solved in FF.3.5.2).

Can you attach input to this bug, that crashes FF? Of course, a full test case would be better, but I can make the input code by myself.

The size of input might not matter. If the file is twice is large, then the probability to hit the bug is twice as big. This may lead to the wrong perception that it is related to the size. Most crasher reduce to a few lines of code.

Lucas
I can confirm, that innerHTML start to be very slow for data larger than 500Kb.

But I can't confirm the crash with ''.

If I do the empty directly, then it will be speedy, because it will not even try to render the huge amount of data.

If I delay the empty, then it just empties without crash.

Does it really crash? Of just hang?

Input data with crash would be helpfull.

Lucas
This is probably a duplicate of bug 500237. We should kill one. Suggest the other, because this bug does also talk about crash.
We should better dupe this bug against bug 500237 which contains much more information. But therefor we have to make sure it's really the same problem.
Bug 500237 has a test case now. You can reproduce it with innerHTML and <span> (not <div>). See other bug.

I suggest to continue this bug if we can crash it with:

"document.getElementById('myDIV').innerHTML = '';"

Performance of innerHTML in bug 500237. Those two things are probably not related.
In bug 500237 I demonstrated that if performance deteriorates due to span, then it also deteriorates for setting innerHTML to ''.

So, if clearing it is a 'hang' and not a 'crash', then this is a dupe of 500237.

Submitter did not respond after filing.
Sorry for my late response to my bug post! This was my first bug post and I wasn't so familiar with the sequences!

Actually my reported bug makes FF3 to hang, maybe not crash (as I understand the difference through the responses).

But I don't think that this bug is related to bug 500237, because this bug just happens in FF3 not FF2, and also by emptying DIV content not SPAN. Because of this problem I'm still using FF2 and check new visions of FF frequently to see if it is solved!

Sorry again for my misunderstanding and misuse of word CRASH!
Severity: critical → major
Summary: Crash when using AJAX to empty content of a big div using innerHTML → Hang when using AJAX to empty content of a big div using innerHTML
Never mind, I sometimes use it incorrectly too.

In bug 500237 I demonstrated in the last test case, the hang on emptying.

About the content. It is not whether you empty a div or span, but what you put into it. If that contains many DIV, then it doesn't reproduce. But with SPAN it does reproduce and it might be the case all other kinds of elements also reproduce. We only know for sure the DIV doesn't reproduce and SPAN does reproduce. Everything between, is uncertain.

Did you had a hang that doesn't got away even after 10 minutes?

For further testing we need test data. When they start solving bug 500237, then they can directly use your test data, to see if your problem is away too. If not, bug 500237 might get resolved, while your bug has to planned in again.

Lucas
I tested again my problem, but it doesn't go away even after 11 minutes! Also about 50 time the window titles "Warning: Unresponsive Script" appeared during hanging but inside the window didn't load (I mean the message and three buttons in it didn't appeared).

I extract the sample data which caused the above mentions hanging and it it about 3.5mb. I uploaded it in my own site that could be downloaded from link below:
www.savafa.com/sampledata.rar
(Data is in UTF-8 without BOM format)

By the way: It took around 20 seconds to insert these amount of data in the program which I have developed. And as I mentioned before emptying process is done in just seconds in FF2 or IE7.
Vivid your comment is not entirely clear.

You wrote:
>I extract the sample data which caused the above mentions hanging

But then a few sentences later:
>By the way: It took around 20 seconds to insert these amount of data in the
program

So, causes the data a hang or does it take 20 seconds?

I tested the data, and it took about a minute. So, this behavior is
similar to bug 500237.

Also, can you check the test cases in bug 500237 with your FF2 version?
I have only 3.5.2 installed.

Lucas
As I said in my post, I will took around 20 seconds to load that amount of data in the DIV and will hang if you try to make it empty by:
document.getElementById('myDIV').innerHTML = '';

Since https://bugzilla.mozilla.org has banned our country IPs I could not check my reported bug regularly .
I didn't succeed in reproducing your empty div problem. But, I saw, when doing innerHTML with the sample data, FF is not only slow, but also looses focus. I think that should not happen.
This demonstrates the slowdown on emptying a div with a bunch of contents via innerHTML (either via setting innerHTML to the empty string or to another value).
Please note that the slowdown is exponential to the size of the old content (the contents that is erased), but doesn't depend (much) of the size of the new contents.

Using the testcase:
1) fill the div with either 250, 500 or 1000 lines
2) Empty it with "Empty (innerHTML)" or by filling it with any number of lines.

I get these times (roughly):
Emptying 250 lines: 1.23s
Emptying 500 lines: 6.49s
Emptying 1000 lines: 26.03s
Confirmed on Ubuntu (was gonna file another bug while I found this one)

Build Identifier: Mozilla/5.0 (X11; U; Linux i686; fr; rv:1.9.1.3) Gecko/20090824 Firefox/3.5.3
Reporter, are you still seeing this issue with Firefox 3.6.13 or later in safe mode or a fresh profile? If not, please close. These links can help you in your testing.
http://support.mozilla.com/kb/Safe+Mode
http://support.mozilla.com/kb/Managing+profiles
Whiteboard: [CLOSEME 2011-2-25]
I still see this issue in safe mode in both my Ubuntu and Win XP (virtualboxed). Tested with:
  Mozilla/5.0 (Windows NT 5.1; rv:2.0b12pre) Gecko/20110205 Firefox/4.0b12pre
  Mozilla/5.0 (X11; Linux i686; rv:2.0b10) Gecko/20100101 Firefox/4.0b10
mozilla-central nightly build on Linux x86-64 with a fresh profile:
             250        500         1000  lines
innerHTML    0.14       0.45        1.57  sec
DOM          0.06       0.14        0.34  sec

Jordan, is it possible an add-on is causing the problem in your case?
What are your results btw?
Attached file Testcase — 
A more automated testcase. Just click the button to get the result.
Attachment #401081 - Attachment is obsolete: true
I am still getting the issue, unfortunately (also I tried in safe-mode, so modules should have been disabled for this, right ?).

My times:

VirtualBoxed Win XP, FF4 beta 12 in safe mode:
                250     500     1000
innerHTML       0.23    2.14    11.26
DOM             0.09    0.15    0.52

Ubuntu, FF4 beta 12 in safe mode:
                250     500     1000
innerHTML       0.31    2.24    10.59
DOM             0.10    0.23    0.54
BTW, just to make sure, I just tried with the latest nightly, with a profile created just for this test, and got roughly the same times on both Ubuntu and WinXP.
Whiteboard: [CLOSEME 2011-2-25]
Confirmed against Mozilla/5.0 (Windows NT 5.1; rv:8.0a1) Gecko/20110724 Firefox/8.0a1 ID:20110724030752 and esp. in Comparison with Opera Next/GC 14.
Severity: major → normal
Keywords: perf, testcase
Product: Firefox → Core
QA Contact: general → general
Version: 3.5 Branch → Trunk
I swear I've seen this before....

The issue is that the innerHTML setter removes the kids from back to front (just like SetNodeTextContent does in the non-reuse case); you could reproduce that behavior by using lastChild instead of firstChild in the testcase's "DOM" codepath.  When that happens you hit O(N^2) behavior finding the right line box for the frame; all the time is spent in nsLineBox::IndexOf.

Jonas, I assume we're doing this to avoid quadratic behavior in the child-removal code itself or something?  Can we not do that, please?  Any quadratic behavior there has a way lower constant, clearly!
Summary: Hang when using AJAX to empty content of a big div using innerHTML → Clearing the kids of a div in SetInnerHTML and SetNodeTextContent leads to quadratic behavior due to nsLineBox::IndexOf
And actually ccing Jonas too.  Jonas, see comment 23.
Status: UNCONFIRMED → NEW
Ever confirmed: true
And fantasai too.  We really need to make this "find the right line box" operation faster....
Blocks: 500237
Yeah, we should just do this front-to-back. That'll always be the faster once we get rid of the child list.
Assignee: nobody → bzbarsky
Priority: -- → P1
Whiteboard: [need review]
It's great that you fix these comments, but they don't seem relevant anymore if you loop in order.
They're relevant the next time someone tries to mess with this loop....
Comment on attachment 548208 [details] [diff] [review]
Remove kids in order, not in reverse order, when clearing textContent and innerHTML.

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

::: content/base/src/nsContentUtils.cpp
@@ +3757,5 @@
>        return NS_OK;
>      }
>    }
>    else {
> +    // i is unsigned, so i >= 0 is always true

I don't know that this comment, while true, is really relevant any more. I'd say just remove it.

Same in a couple of other places in the patch.
Attachment #548208 - Flags: review?(jonas) → review+
Whiteboard: [need review] → [need landing]
Bah, humbug.  OK, I'll take those comments out.
http://hg.mozilla.org/integration/mozilla-inbound/rev/a430f8b1921e
Flags: in-testsuite?
Whiteboard: [need landing]
Target Milestone: --- → mozilla8
http://hg.mozilla.org/mozilla-central/rev/a430f8b1921e
Status: NEW → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: