63760 - selection is way too slow, makes browser seem hung on large documents

Status: RESOLVED FIXED

(Core :: DOM: Selection, defect, P1)

Description

[buster]

this is broken off from bug 56432.  I have a fix for that bug that makes
selection must better, but still unacceptably slow.

With the changes to GetPrimaryFrame in my tree (see 56432 for diffs soon),
quantify says that nsContentSubtreeIterator::Next()
is the major performance problem with selection.  The decendant method that
seems to really be the problem is nsRange::GetAncestorsAndOffsets().

I will attach reduced quantify output for details, and the test case I used to
generate the output.  To reproduce, I simply opened the test case in viewer
(mozilla works as well), clicked on the first word, used the scroll bar to
scroll to the end of the page, and shift-clicked on the last word.

Comment 1

[buster]

Attachment: quantify output, copied into a text file an annotated

Comment 2

[buster]

Attachment: test case used to generate the data I just attached

Comment 3

[Blake Ross]

Mind posting your patch for 56432 so I can try it out?

Comment 4

[buster]

cc-ing Kin - this is the bug you and I were just talking about.

Comment 5

[Joe Francis]

Of course, another way to view it is that IndexOf() is slow.  After all, 2/3rds 
of the time spent in GetAncestorsAndOffsets() is spent inside IndexOf().

What's really going on here is that the nsContentSubtreeIterator::Next() function 
is slow.  I believe the strategy I adopted to speed up copy operations in the 
document encoder can also be used in the subtree iterator.  The basic idea is 
that you precalculate all the interesting "edges" on both sides of the selection 
(places where node A is in the selction but adjacent node B is only partially in 
selection) and store that data in the iterator at init time.  Then the Prev and 
Next operations use that data instead of the very expensive 
"GetTopAncestorInRange()" call that it currently uses.  This should speed up 
selection a lot.

Grabbing bug.

Comment 6

[Joe Francis]

kin and i expiremented with my iterator changes and found a factor of 3
improvement, roughly.  Not as much as i'd hoped but plenty enough to be worthwhile.

Comment 7

[Joe Francis]

i ahve some additional improvements in the works too.  i'm markinog this 0.9.1 
because i suspect we won't want to close it out, even if i land my improvements 
right away - performance still needs more work here.  the milestone moving 
reflects my belief that we will continue to find improvements for some time, 
rather than any change in the pace that we work on this.

Comment 8

[Joe Francis]

Attachment: patch to layout/base/src/nsContentIterator.cpp

Comment 9

[Joe Francis]

attached a patch for the subtree flavor of the content iterator to speed it up.
 this iter is used by selection and by many editor operations.  it should speed
up selection, block level editor operations, inline editor operations, and
editor ui feedback.  we still havea ways to go but this patch helps quite a bit
(factor of 3 on many things, including large selections).

requesting r and sr.  akkana?, simon?

Comment 10

[Joe Francis]

forgot to cc simon; dude, i need an sr.

Comment 11

[Simon Fraser [no longer active]]

sr=sfraser

Comment 12

[Akkana Peck]

r=akkana

Comment 13

[Joe Francis]

ok, patch landed.  speed improvements should be noticeable on sufficiently large 
selections, though it's only a factor of 3 or so, so if you have a case that used 
to take minutes, it will still be a long time.

Comment 14

[rubydoo123]

moving to 1.0

Comment 15

[Joe Francis]

should this be closed?  If not, should I still own it?

Comment 16

[Joe Francis]

closing this out because no one has complained about selection speed in a long 
time, and if they did we would have to start at the top and reprofile, which is a 
job for selection folks.