62971 - Sluggish selection performance at certain page

Status: RESOLVED FIXED

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

Description

[Blake Ross]

Build ID: 12/15 trunk (tip)

Selection is considerably slower at 
http://www.autsch.de/bitsteller/linux_penguin.html in my latest build than in 
Netscape 4.x / IE 5.5.

Comment 1

[Blake Ross]

I'll try to get some timing data soon.

Comment 2

[Blake Ross]

`Select All' all but freezes on my PIII 930 mHZ w/ 256 MB SDRAM.  It takes at 
least 25-30 seconds, during which time all instances of Mozilla are completely 
unresponsive.  This would be a nice win for beta1...Can anyone profile this?

Comment 3

[rubydoo123]

setting to moz0.9

Comment 4

[rubydoo123]

moz0.9.1

Comment 5

[mjudge]

404 error. please find a new page that locks up selection and reopen...

Comment 6

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

Reopening.  Selection is quite slow on:
http://lxr.mozilla.org/seamonkey/source/layout/html/style/src/nsCSSFrameConstructor.cpp

...especially extending an existing selection while near the end of the page (
in certain cases a lot more than others... I can get things to lock up for 30
seconds or more by extending the selection a few times).

Comment 7

[mjudge]

is that on unix with that autocopying going on? or all platforms have a 30sec 
lockup

Comment 8

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

I was seeing it on Linux.  I can't test on any other platforms.

Comment 9

[kinmoz]

It's slow on windows too.

Comment 10

[mjudge]

Got patch?  I do.  

the first will speed up selection direction toggling. it has to do with turning 
off the selection bit on a frame and that frame not bothering to check the 
anchor-focus range.  good win for small number of cases. nsSelection.cpp

the second has to do with selecting into a block frame. the block frame for the 
"pre" in this case has 13000 lines.  before EACH line is checked sequencialy to 
see if IT is the line that owns a particular event point. once it found the 
right one it "snaps" the selection to the frame that should get it.  I made the 
new "seeking" for the correct line do a binary search until it has about 20 
lines left then it does those sequencialy.  

(for 13000 line block frame)
worst case before = 13K compares
best case before = 1
worst case now =29
best case now  = 11 (POSSIBLE 1 but very unlikely hitting it exactly on a 
division)

Comment 11

[mjudge]

Attachment: dif for the selection change talked about before

Comment 12

[mjudge]

Attachment: put this in layout\html\base\src

Comment 13

[mjudge]

kin has reviewed it i think i need a layout person to SR it though. i think... I 
am ccing waterson. he usually has constructive stuff to say.

Comment 14

[kinmoz]

Can we add a comment at the top describing how the search works?

Is there a way to do the binary search loop and avoid precalculating division?

+ while(shifted > MAGIC_LINENUM)
+ {
+ ++divisions;
+ shifted>>=1;
+ }


Let's remove the commented out code:

+ // if (y < 0 ) //we need to look upwards leave start alone
+ if (y > 0) //advance start shifted amount


Can we propogate the error returned by GetClosestLine() instead of returning
NS_ERROR_FAILURE?

+ if (NS_FAILED(GetClosestLine(it,origin,aEvent->point,closestLine)))
+ return NS_ERROR_FAILURE;

Comment 15

[kinmoz]

By the way mike, this makes a big difference in that lxr page!! Nice job.

Comment 16

[mjudge]

sure i will propogate. and yes i think we can not precalculate the loop amount. 
I am going to make it just binary search till it finds it.  I will make a new 
patch tomorrow. waterson also has an idea on how to stop the chunk of time it 
takes to make the line iterator in the first place.

Comment 17

[Brendan Eich [:brendan]]

The layout propAgate misspelling meme lives, but must die!

/be

Comment 18

[mjudge]

Richard Dawkins eat your heart out..
ok new patch.  Made the find only use binary search. cleaned up code more. more 
comments. Oh, also, I just finished propogating the propogated result ;).  
asking for another round of r and sr from kin and waterson.

Comment 19

[mjudge]

Attachment: layout\html\base\src\ v2.0

Comment 20

[David Hyatt]

sr=hyatt

Comment 21

[mjudge]

the slugishness thats still here may be fixed with what waterson is kicking 
around with making the blockframes have an array of lines not a linked list of 
lines. but thats a different story..