The default bug view has changed. See this FAQ.

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

RESOLVED FIXED in mozilla8

Status

()

Core
General
P1
normal
RESOLVED FIXED
8 years ago
6 years ago

People

(Reporter: vivid, Assigned: bz)

Tracking

(Blocks: 1 bug, {perf, testcase})

Trunk
mozilla8
x86
Windows XP
perf, testcase
Points:
---
Bug Flags:
in-testsuite ?

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments, 1 obsolete attachment)

(Reporter)

Description

8 years ago
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.
(Reporter)

Updated

8 years ago
Version: unspecified → 3.5 Branch
Please read: https://developer.mozilla.org/En/How_to_get_a_stacktrace_for_a_bug_report

Comment 2

8 years ago
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

8 years ago
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

8 years ago
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.

Comment 6

8 years ago
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

8 years ago
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.
(Reporter)

Comment 8

8 years ago
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!
(Reporter)

Updated

8 years ago
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

Comment 9

8 years ago
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
(Reporter)

Comment 10

8 years ago
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

8 years ago
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
(Reporter)

Comment 12

8 years ago
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

8 years ago
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

8 years ago
Created attachment 401081 [details]
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

8 years ago
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]

Comment 17

6 years ago
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?

Comment 19

6 years ago
Created attachment 518150 [details]
Testcase

A more automated testcase. Just click the button to get the result.
Attachment #401081 - Attachment is obsolete: true

Comment 20

6 years ago
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

6 years ago
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.

Updated

6 years ago
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
Component: General → General
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.
Created attachment 548208 [details] [diff] [review]
Remove kids in order, not in reverse order, when clearing textContent and innerHTML.
Attachment #548208 - Flags: review?(jonas)
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
Last Resolved: 6 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.