Joe Francis Reporter
	Description • 25 years ago

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.

	Joe Francis Reporter
	Comment 1 • 25 years ago

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).

	troy
	Comment 2 • 25 years ago

Block/inline problem so reassigning to Buster

	buster
	Comment 3 • 25 years ago

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

	buster
	Comment 4 • 24 years ago

redistributing bugs across future milestones, sorry for the spam

	buster
	Comment 5 • 24 years ago

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?

	Joe Francis Reporter
	Comment 6 • 24 years ago

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

	David Baron :dbaron:
	Comment 7 • 24 years ago

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.

	Chris Waterson
	Comment 8 • 24 years ago

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.

	Joe Francis Reporter
	Comment 9 • 24 years ago

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().

	David Baron :dbaron:
	Comment 10 • 24 years ago

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.

	Joe Francis Reporter
	Comment 11 • 24 years ago

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.

	rubydoo123
	Comment 12 • 24 years ago

adding the blocker info

	scottputterman
	Comment 13 • 24 years ago

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.

	selmer (gone)
	Comment 14 • 24 years ago

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?)

	Joe Francis Reporter
	Comment 15 • 24 years ago

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

	Johnny Stenback (:jst) Assignee
	Comment 16 • 24 years ago

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

	Johnny Stenback (:jst) Assignee
	Comment 17 • 24 years ago

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

	Marek Z. Jeziorek
	Comment 18 • 24 years ago

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)

	Joe Francis Reporter
	Comment 20 • 23 years ago

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.

	Johnny Stenback (:jst) Assignee
	Comment 21 • 23 years ago

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

	Joe Francis Reporter
	Comment 22 • 23 years ago

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

	Prashant Desale
	Comment 23 • 23 years ago

Updating QA contact to Shivakiran Tummala.

	Johnny Stenback (:jst) Assignee
	Comment 25 • 23 years ago

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)...

	selmer (gone)
	Comment 26 • 23 years ago

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.

	Joe Francis Reporter
	Comment 27 • 23 years ago

Johnny, please merge these patches.  They conflict.

	stephend@netscape.com (gone - use stephen.donner@gmail.com instead)
	Comment 28 • 23 years ago

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.

	Jean-Francois Ducarroz
	Comment 29 • 23 years ago

Can we have new patches that work. Thanks

	Joe Francis Reporter
	Comment 31 • 23 years ago

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

	Johnny Stenback (:jst) Assignee
	Comment 36 • 23 years ago

Moving to mozilla0.9.3

	Johnny Stenback (:jst) Assignee
	Comment 37 • 23 years ago

Moving to mozilla1.0

	Johnny Stenback (:jst) Assignee
	Comment 38 • 23 years ago

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...

	Randell Jesup [:jesup] (needinfo me)
	Comment 39 • 23 years ago

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.

	Randell Jesup [:jesup] (needinfo me)
	Comment 40 • 23 years ago

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.

	Johnny Stenback (:jst) Assignee
	Comment 41 • 23 years ago

Moving to mozilla0.9.5

	Joe Francis Reporter
	Comment 42 • 23 years ago

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?

	Randell Jesup [:jesup] (needinfo me)
	Comment 43 • 23 years ago

To repeat:
------- Additional Comments From jfrancis@netscape.com 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?

	Randell Jesup [:jesup] (needinfo me)
	Comment 45 • 23 years ago

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=rjesup@wgate.com

	Jonas Sicking (:sicking) No longer reading bugmail consistently
	Comment 46 • 23 years ago

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

	Johnny Stenback (:jst) Assignee
	Comment 47 • 23 years ago

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? :-)

	Johnny Stenback (:jst) Assignee
	Comment 48 • 23 years ago

Fix checked in.