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

RESOLVED FIXED in mozilla1.0

Status

()

Core
Selection
P1
critical
RESOLVED FIXED
18 years ago
17 years ago

People

(Reporter: buster, Assigned: Joe Francis)

Tracking

({perf})

Trunk
mozilla1.0
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [nav+perf])

Attachments

(3 attachments)

(Reporter)

Description

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

Comment 1

18 years ago
Created attachment 21310 [details]
quantify output, copied into a text file an annotated
(Reporter)

Comment 2

18 years ago
Created attachment 21311 [details]
test case used to generate the data I just attached

Comment 3

18 years ago
Mind posting your patch for 56432 so I can try it out?
Blocks: 62971
Keywords: perf
OS: Windows NT → All
Hardware: PC → All
(Reporter)

Comment 4

18 years ago
cc-ing Kin - this is the bug you and I were just talking about.
(Assignee)

Comment 5

18 years ago
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.
Assignee: mjudge → jfrancis
Priority: -- → P1
Target Milestone: --- → mozilla0.9
(Assignee)

Comment 6

18 years ago
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.
Status: NEW → ASSIGNED
(Assignee)

Comment 7

18 years ago
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.
Target Milestone: mozilla0.9 → mozilla0.9.1
(Assignee)

Comment 8

18 years ago
Created attachment 25231 [details] [diff] [review]
patch to layout/base/src/nsContentIterator.cpp
(Assignee)

Comment 9

18 years ago
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?
Whiteboard: patch, need review
(Assignee)

Comment 10

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

Comment 11

18 years ago
sr=sfraser

Comment 12

18 years ago
r=akkana
(Assignee)

Comment 13

18 years ago
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.
Whiteboard: patch, need review
(Assignee)

Updated

18 years ago
Target Milestone: mozilla0.9.1 → mozilla0.9.2

Comment 14

17 years ago
moving to 1.0
Target Milestone: mozilla0.9.2 → mozilla1.0

Updated

17 years ago
Whiteboard: [nav+perf]
(Assignee)

Comment 15

17 years ago
should this be closed?  If not, should I still own it?
(Assignee)

Comment 16

17 years ago
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.
Status: ASSIGNED → RESOLVED
Last Resolved: 17 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.