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

Status: RESOLVED FIXED

(Core :: General, defect, P1)

Description

[vivid]

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.

Comment 1

[Ria Klaassen (not reading all bugmail)]

Please read: https://developer.mozilla.org/En/How_to_get_a_stacktrace_for_a_bug_report

Comment 2

[u348128]

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

Comment 3

[u348128]

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

Comment 4

[u348128]

This is probably a duplicate of bug 500237. We should kill one. Suggest the other, because this bug does also talk about crash.

Comment 5

[Henrik Skupin [:whimboo][⌚️UTC+2]]

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.

Comment 6

[u348128]

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.

Comment 7

[u348128]

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.

Comment 8

[vivid]

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!

Comment 9

[u348128]

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

Comment 10

[vivid]

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.

Comment 11

[u348128]

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

Comment 12

[vivid]

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 .

Comment 13

[u348128]

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.

Comment 14

[Jordan Osete]

Attachment: Show the slowdown on emptying big div via innerHTML

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

Comment 15

[Jordan Osete]

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

Comment 16

[Tyler Downer [He/Him]]

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

Comment 17

[Jordan Osete]

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

Comment 18

[Mats Palmgren (inactive)]

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?

Comment 19

[Jordan Osete]

Attachment: Testcase

A more automated testcase. Just click the button to get the result.

Comment 20

[Jordan Osete]

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

Comment 21

[Jordan Osete]

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.

Comment 22

[(mostly gone) XtC4UaLL [:xtc4uall]]

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.

Comment 23

[Boris Zbarsky [:bzbarsky]]

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!

Comment 24

[Boris Zbarsky [:bzbarsky]]

And actually ccing Jonas too.  Jonas, see comment 23.

Comment 25

[Boris Zbarsky [:bzbarsky]]

And fantasai too.  We really need to make this "find the right line box" operation faster....

Comment 26

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Yeah, we should just do this front-to-back. That'll always be the faster once we get rid of the child list.

Comment 27

[Boris Zbarsky [:bzbarsky]]

Attachment: Remove kids in order, not in reverse order, when clearing textContent and innerHTML.

Comment 28

[:Ms2ger (he/him; ⌚ UTC+1/+2)]

It's great that you fix these comments, but they don't seem relevant anymore if you loop in order.

Comment 29

[Boris Zbarsky [:bzbarsky]]

They're relevant the next time someone tries to mess with this loop....

Comment 30

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

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.

Comment 31

[Boris Zbarsky [:bzbarsky]]

Bah, humbug.  OK, I'll take those comments out.

Comment 32

[Boris Zbarsky [:bzbarsky]]

http://hg.mozilla.org/integration/mozilla-inbound/rev/a430f8b1921e

Comment 33

[Marco Bonardo [:mak]]

http://hg.mozilla.org/mozilla-central/rev/a430f8b1921e