35294 - PERF: nsIDOMNode::InsertBefore() performance.

Status: RESOLVED FIXED

(Core :: DOM: Core & HTML, defect, P3)

Description

[Joe Francis]

I've broken out editor Paste performace into 5 bugs.  This one is about the 
InsertBefore() bottleneck.  There are two issues here:
 
1) We have to call InsertBefore() twice for each line of text we paste.  This is 
because we have to replace newlines with <br> nodes.  This is done because 
otherwise we cant draw a caret on blank lines.  If we had a frame for blank lines 
caused by newlines, then we wouldn't need to call InsertBefore() so much, so 
that's one possible way to address this performance problem.
2) InsertBefore() is taking 18+ milliseconds on my 300mHz G3 Portable.  The time 
taken slowly creeps upward as later lines are pasted in.  I assume that scannig 
through the lengthening child list as hundreds of nodes are inserted is what 
causes the creep upwards.  Any speed improvement to InsertBefore() is a big win 
for us in Editorland.

Comment 1

[Joe Francis]

ignore the 18+ milliseconds figure.  I meant 1.8 ms.  Your milage may vary.  What 
is true though is that the loop for chucking the text and breaks into the dom is 
bound by InsertBefore() performance, and that loop is a big piece of the time for 
paste (and once we've fixed some editor and caret perf problems, it should make 
up most of the paste time).

Comment 2

[troy]

Block/inline problem so reassigning to Buster

Comment 3

[buster]

M18.  I know I won't get to this for beta 2.  Don't know where it falls in
priority order for FCS.

Comment 4

[buster]

redistributing bugs across future milestones, sorry for the spam

Comment 5

[buster]

marking FUTURE.  Unless this shows up as a major performance issue for a common 
task, it won't be looked at any time soon.  Joe, can you provide any hard data 
to change my mind?  "nsIDOMNode::InsertBefore() degrades exponentially with the 
number of lines" or "nsIDOMNode::InsertBefore() takes up 75% of the time to do 
any paste operation" or something like that?

Comment 6

[Joe Francis]

i have a nice graphic of where time is spent in paste that i'll bring to you.

Comment 7

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Joe - 

If I'm understanding this correctly, you're looking at a performance problem 
when pasting multiple lines of text at once.  My understanding (from the text 
above) of what you're currently doing is that you are doing insertBefore() for 
each line, and for the BR after it.

A possible solution (which *should* be faster, and I would think could be made 
faster if it is not) to this on your end could be to append all of the stuff 
into a DocumentFragment object, and then call insertBefore on the 
DocumentFragment.  See the DOM spec at 
http://www.w3.org/TR/DOM-Level-2/core.html#ID-952280727 (insertBefore)
http://www.w3.org/TR/DOM-Level-2/core.html#ID-B63ED1A3 (documentFragment)

It's worth looking at the code that would do this and making sure that it is 
fast or can be made fast before plunging ahead with this (although actually I 
wouldn't think it would be all that hard...).  If you have any questions, I 
might be able to help, although my knowledge in this area is mainly about the 
DOM itself rather than our implementation of it.

Comment 8

[Chris Waterson]

insertBefore's implementation is O(n) with respect to the number of lines in the 
target:

1. due to the call to nsVoidArray::IndexOf(), which must scan the void array to 
find the element.

http://lxr.mozilla.org/mozilla/source/layout/base/src/nsGenericElement.cpp#1903

2. due to the call to nsVoidArray::InsertChildAt(), which requires O(n/2) to 
shift elements and create space for the new element.

http://lxr.mozilla.org/mozilla/source/layout/base/src/nsGenericElement.cpp#1985

I think dbaron is right on the money with respect to how to improve performance 
for this. Assigning back to jfrancis for investigation.

Comment 9

[Joe Francis]

sounds like a plan.  I had considered something like this before but didn't know 
about document fragments, so I didn't have a way to use Append().

Comment 10

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

However, looking at the current implementation of insertBefore, it may not be 
optimized for inserting documentFragments, something that probably could be 
done.  In particular, it calls insertChildAt for every child inserted.  That 
implementation *is* a peformance bug that could be improved (although it might 
be a little messy).  Probably the two 
issues of:
 * speeding up documentFragment insertion
 * making editor paste use documentFragments
should be separate bugs.

Comment 11

[Joe Francis]

ooof.  Ok, it makes no sense to spend time on making the editor use docfrags 
until they are a performance improvement.  Given their current implementation, it 
would actually degrade performance to use them.  

I've opened a new bug 43863 for that issue and marked it as a blocker for this 
bug.

Comment 12

[rubydoo123]

adding the blocker info

Comment 13

[scottputterman]

I'd like to nominate this for nsbeta1.  I think this is one of the bugs that
affects message reply performance due to inserting text (if it's not one of the
bugs then ignore the nsbeta1 nomination and let me know).  reply performance is
one of our key areas and it looks like Jean-Francois data shows that we'd get a
big win if we could speed up inserting text.

Comment 14

[selmer (gone)]

nom catfood:  with the mail perf landing, this is about to become the biggest
remaining mail perf problem.

(Is this the active bug or is there another somewhere?)

Comment 15

[Joe Francis]

not sure why waterson assigned this back to me long ago.  The issue described 
here is a layout problem.  While I know there are editor performance issues as 
well, we really need a faster way to beat on the dom tree without firing off so 
many duplicate content notifications, etc.  

cc'ing me and assigning to layout

Comment 16

[Johnny Stenback (:jst)]

*** Bug 43863 has been marked as a duplicate of this bug. ***

Comment 17

[Johnny Stenback (:jst)]

*** Bug 74907 has been marked as a duplicate of this bug. ***

Comment 18

[Marek Z. Jeziorek]

moving to TM of 0.9.2 per PDT triage (you can check it into 0.9.1 until Friday,
18/May/01 or into 0.9.2 after the tree opens)

Comment 19

[Johnny Stenback (:jst)]

Attachment: First rough cut at optimizing insertion of document fragments

Comment 20

[Joe Francis]

Johnny, will this help with the AppendChild() case as well?  That ends up being 
the one usually hit in mail reply.  InsertBefore() work is not wasted though and 
will help us elsewhere.

Comment 21

[Johnny Stenback (:jst)]

Joe, AppendChild() calls InsertBefore() so yes, this will benefit both thoese cases.

Comment 22

[Joe Francis]

This improves my 4000 line mail reply testcase.  The AppendChild() call the 
editor makes is 15% faster with this patch.  Thanks!

Comment 23

[Prashant Desale]

Updating QA contact to Shivakiran Tummala.

Comment 24

[Johnny Stenback (:jst)]

Attachment: Additional optimizations to appending document fragments (completely untested)

Comment 25

[Johnny Stenback (:jst)]

Joe, can you run the same tests with the new patch I attached? The new patch
only contains the changes to nsGenericElement.cpp, you also need the other
changes in the first patch in this bug.

The new patch should cut down the notifications we make to the document to 1
single call to nsIDocument::ContentAppended() when *appending* a document
fragment (in stead of calling nsIDocument::ContentInserted() for every node in
the document fragment). This is about as far as we can optimize appending of
document fragments in the DOM code (we could still get rid of some reallocing of
child pointer arrays, but that's hardly where we spend most of the time), any
further optimizations need to happen in layout land (i.e. frame construction)...

Comment 26

[selmer (gone)]

CC Putterman, someone on the mail team needs to be helping with this issue.  If
this proves out, then we should push to get all the existing reply speed fixes
incorporated.

Comment 27

[Joe Francis]

Johnny, please merge these patches.  They conflict.

Comment 28

[[e-mail] (gone - use [e-mail] instead)]

C:\moz_src\mozilla\content\base\src>patch <jstpatch4.txt
patching file `nsGenericElement.cpp'
Hunk #1 succeeded at 2400 (offset 207 lines).
Hunk #2 FAILED at 2419.
1 out of 2 hunks FAILED -- saving rejects to nsGenericElement.cpp.rej

Yeah, I couldn't patch the last patch
(http://bugzilla.mozilla.org/showattachment.cgi?attach_id=37337)

But I am building with the other patches and will export this opt build down to
the lab and run my perf tests against msgreply.

Comment 29

[Jean-Francois Ducarroz]

Can we have new patches that work. Thanks

Comment 30

[Johnny Stenback (:jst)]

Attachment: Above patches merged

Comment 31

[Joe Francis]

latest patch gets AppendChild down to 2.62 seconds in my test scenario, down
from over 16 seconds.  Cool beans.

Comment 32

[[e-mail] (gone - use [e-mail] instead)]

Attachment: 2001-06-11-04 trunk, 1200 line message, win98, 266mhz, 128MB

Comment 33

[[e-mail] (gone - use [e-mail] instead)]

Attachment: reply perf branch, 1200 line message, win98, 266mhz, 128MB

Comment 34

[[e-mail] (gone - use [e-mail] instead)]

Attachment: Trunk 2001-06-11-04 (1k, 2khtml, 5k, 10k, 34k)

Comment 35

[[e-mail] (gone - use [e-mail] instead)]

Attachment: Perf branch (1k, 2khtml, 5k, 10k, 34k)

Comment 36

[Johnny Stenback (:jst)]

Moving to mozilla0.9.3

Comment 37

[Johnny Stenback (:jst)]

Moving to mozilla1.0

Comment 38

[Johnny Stenback (:jst)]

Back to mozilla0.9.3 per high demand for this fix, this still needs some more
work to handle errors more gracefully before this is checked in...

Comment 39

[Randell Jesup [:jesup] (needinfo me)]

a question about content, editor and nsVoidArray (used heavily): does it make
sense to add some type of way to insert multiple entries instead of doing them
one at a time?  Perhaps RemoveElementsAt(index,count) and
InsertElementsAt(index, ????)?

Or perhaps adding a call to the new nsVoidArray::ExpandTo method would allow us
to do all the growing at once; the overhead for adding the elements would only
be in shifting elements after the insertion point.  Currently the overhead
includes the expense of (possibly several) reallocations and copies.  All we
need is a count of the (likely) number of nodes we'll add.  Certainly when
adding DocumentFragments that's possible.

I'm not certain how much we gain here since I haven't seen a jprof/quantify
output for this case, but it's a pretty straightforward and general optimization.

Comment 40

[Randell Jesup [:jesup] (needinfo me)]

I've added (in the 90545 patch) support for Inserting and removing multiple
elements at once.  Also, nsSupportsArray now supports SizeTo().  After these
patches are merged, we may want to try using these new calls.

Comment 41

[Johnny Stenback (:jst)]

Moving to mozilla0.9.5

Comment 42

[Joe Francis]

What is the status of this work?  Though it was decided not to take the sum
total of the mail-reply perf branch work, some of the pieces will help out with
editor performance in general,  This patch is one.  Can we have this in 095?

Comment 43

[Randell Jesup [:jesup] (needinfo me)]

To repeat:
------- Additional Comments From [e-mail] 2001-09-23 23:54 -------

What is the status of this work?  Though it was decided not to take the sum
total of the mail-reply perf branch work, some of the pieces will help out with
editor performance in general,  This patch is one.  Can we have this in 095?

-------
Perhaps for 0.9.6?

Comment 44

[Johnny Stenback (:jst)]

Attachment: This should be "The One"

Comment 45

[Randell Jesup [:jesup] (needinfo me)]

Being pretty up on array references, that all looks pretty good to me.  I agree
that the IndexOf case is not a performance issue, since it shouldn't be hit
often/ever.  r=[e-mail]

Comment 46

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

Comment on attachment 55867 [details] [diff] [review]
This should be "The One"

This looks like a neat performace win, especially for the case when a fragment is appended
r=sicking

Comment 47

[Johnny Stenback (:jst)]

Ahem, hmm, I forgot that I already had a review for this patch, sorry to request
one more Sicking. Well, the more the merryer, right? :-)

Comment 48

[Johnny Stenback (:jst)]

Fix checked in.