519657 - Selecting text across many DOM elements is slow

Status: NEW

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

Description

[Olli Pettay [:smaug][[e-mail]]]

Attachment: testcase

Set cursor somewhere in the first line, then scroll to the last line and
shift-click somewhere there.
ComparePoints is a problem here. It can be made a lot faster in this case
even without having a float/double location marker in the nodes.

Comment 1

[Olli Pettay [:smaug][[e-mail]]]

Attachment: Add CompareChildNodes to nsINode

If/when we add the float/double location marker to nsINode, the implementation
for CompareChildNodes could be changed. But this might be safe enough even for
1.9.2.

And even select all is slow with the test case (without this patch).

Comment 2

[Boris Zbarsky [:bzbarsky]]

We could probably avoid changing all the nsINode implementations if we just implemented this as a non-virtual nsINode method (possibly even inline if we care about it being callable cross-module; there's only one consumer anyway) on top of GetChildArray.

That said, I guess this makes it faster to compare two nodes if one is near the beginning of the list (e.g. when doing "select all") and slower to compare them if they're closer to each other (e.g. when making a small selection in the middle of a large document).  In fact, it makes the latter case require walking half the nodes whereas right now it might or might not involve that depending on the state of the indexof cache....

If we're pretty sure that won't cause problems, I guess we can take this.  For 1.9.3 I think peter's working on the other approach.

Comment 3

[Olli Pettay [:smaug][[e-mail]]]

(In reply to comment #2)
> We could probably avoid changing all the nsINode implementations if we just
> implemented this as a non-virtual nsINode method (possibly even inline if we
> care about it being callable cross-module; there's only one consumer anyway) on
> top of GetChildArray.
Could do this. (Would be nicer if GetChildArray returned nsINodes and not nsIContents.)


> That said, I guess this makes it faster to compare two nodes if one is near the
> beginning of the list (e.g. when doing "select all") and slower to compare them
> if they're closer to each other (e.g. when making a small selection in the
> middle of a large document).  In fact, it makes the latter case require walking
> half the nodes whereas right now it might or might not involve that depending
> on the state of the indexof cache....
Right. Currently it is sort of random how fast the comparison is; it depends on
the current state of the indexof cache.
The change to the testcase handling is pretty dramatic though.

> For
> 1.9.3 I think peter's working on the other approach.
Bug#?

Comment 4

[Boris Zbarsky [:bzbarsky]]

> The change to the testcase handling is pretty dramatic though.

Sure.  The question is whether there are realistic testcases where the change is just as dramatic in the other direction.

> Bug#?

Bug 513169.  I added you to the cc list.

Comment 5

[Olli Pettay [:smaug][[e-mail]]]

Attachment: testcase 2

Another testcase. Still not too bad with the patch.
There should be some bad case for the patch, but somehow I haven't found anything
which behaves worse than trunk.

Comment 6

[Olli Pettay [:smaug][[e-mail]]]

Attachment: Simple patch

Comment 7

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

Sucks to have to do those two virtual IsNodeOfType calls. Can we move that function up to nsINode? Alternatively, I suspect that it's fine if nsContentUtils::ComparePoints treats anonymous children as being after the real children (which would be the case if you just skipped those checks). However we'd need to check that. And maybe just do *that* for trunk I guess.

You should also assert that the two passed in nodes are in fact children of the node.

Also, why do the casting? Comparing a const nsIContent* to a non-const nsINode* should work fine.

Comment 8

[Olli Pettay [:smaug][[e-mail]]]

Attachment: testcase for comparepoints

This very artificial testcase shows 10% regression with the patch (after quickstubbing nsIDOMRange).
If setStart uses the comment out code, the patch makes the testcase to run twice as fast as trunk.

Comment 9

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

Oh, and can you give the same treatment to nsContentUtils::ComparePosition

Comment 10

[Olli Pettay [:smaug][[e-mail]]]

> Sucks to have to do those two virtual IsNodeOfType calls.
Doesn't show up badly in profiles. 0.0% IIRC with the testcase.

> Can we move that
> function up to nsINode?
Well, that wouldn't be quite right, IMO, since we don't currently track down
whether attribute nodes are in anonymous content. 

> Alternatively, I suspect that it's fine if
> nsContentUtils::ComparePoints treats anonymous children as being after the real
> children
Yeah, maybe. I was just hoping to improve the performance for 1.9.2, which is
why I did choose the least regression-risky approach.

> You should also assert that the two passed in nodes are in fact children of 
> the node.
Could do.

Comment 11

[Olli Pettay [:smaug][[e-mail]]]

Not sure how important ::ComparePosition is. Would have to write some testcases.

Comment 12

[Boris Zbarsky [:bzbarsky]]

I really wish we had fewer position-comparison functions (we have ones for nodes in both nsLayoutUtils and nsContentUtils, and more than one in nsContentUtils, right?)

Comment 13

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

(In reply to comment #10)
> > Sucks to have to do those two virtual IsNodeOfType calls.
> Doesn't show up badly in profiles. 0.0% IIRC with the testcase.

I think the virtual call overhead is attributed to the caller, since IsNodeOfType isn't yet on the stack.

> > Can we move that
> > function up to nsINode?
> Well, that wouldn't be quite right, IMO, since we don't currently track down
> whether attribute nodes are in anonymous content. 

We really should make attributes not be nsINodes, that was my bad :(
(I'd really like to remove attribute nodes altogether, but that's a separate discussion).

> > Alternatively, I suspect that it's fine if
> > nsContentUtils::ComparePoints treats anonymous children as being after the real
> > children
> Yeah, maybe. I was just hoping to improve the performance for 1.9.2, which is
> why I did choose the least regression-risky approach.

Yes, I was suggesting to use the approach in the patch for 1.9.2, but do the even faster thing on trunk.

(In reply to comment #11)
> Not sure how important ::ComparePosition is. Would have to write some
> testcases.

What's the downside to using it in in ComparePosition? I don't quite understand in which situations the new approach could be slower?

(In reply to comment #12)
> I really wish we had fewer position-comparison functions (we have ones for
> nodes in both nsLayoutUtils and nsContentUtils, and more than one in
> nsContentUtils, right?)

Agreed. The two in nsContentUtils do different things, so we definitely need both of them. The ones in layout looks like they could be implemented on top of the nsContentUtils one though. With only a couple of extra conditional branches as overhead. Filed bug 519787 on this.

Comment 14

[Boris Zbarsky [:bzbarsky]]

> Agreed. The two in nsContentUtils do different things

How so?  I'm looking at ComparePoints vs ComparePosition.  They do do different things when attr nodes are involved, but after that they have shared code and then only differ in return values.  And both do stuff that I think most callers don't care about much in terms of disconnected nodes...

Comment 15

[Olli Pettay [:smaug][[e-mail]]]

(In reply to comment #13)
> We really should make attributes not be nsINodes,
No! (Unless also DOM Core changes)

> What's the downside to using it in in ComparePosition? I don't quite understand
> in which situations the new approach could be slower?
If the two nodes are very close to each other but close to the last child of
their parent.
I'm not sure how often DOM 3 compareDocumentPosition is used, and when usually.

Comment 16

[Olli Pettay [:smaug][[e-mail]]]

Attachment: patch

Anyway, this is the patch for nsContentUtils::ComparePoints.

Comment 17

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

> > What's the downside to using it in in ComparePosition? I don't quite
> > understand in which situations the new approach could be slower?
> If the two nodes are very close to each other but close to the last child of
> their parent.
> I'm not sure how often DOM 3 compareDocumentPosition is used, and when
> usually.

How so? In the current code we first get the index of the first child, then of the second. If they are close, we benefit from the IndexOf cache when getting the second childs index, but that's still on top of  the time spent on getting the first childs index.

So it seems to me that the only advantage to the current code is when we can find both children using the IndexOf cache faster than finding the first child by scanning.

I guess in the case of selecting there's a good chance that the IndexOf cache is primed from when the selection started. But wouldn't that mean that the patch is using a bad approach?

Comment 18

[Olli Pettay [:smaug][[e-mail]]]

(In reply to comment #17)
> How so? In the current code we first get the index of the first child, then of
> the second. 
I mean I don't know what is the common use case for compareDocumentPosition.
I do know what it does ;)

> I guess in the case of selecting there's a good chance that the IndexOf cache
> is primed from when the selection started. But wouldn't that mean that the
> patch is using a bad approach?
Well, select all case can't really work well with current IndexOf cache.

Comment 19

[Alex Vincent [:WeirdAl]]

(In reply to comment #18)
> I mean I don't know what is the common use case for compareDocumentPosition.
> I do know what it does ;)

I can't speak for what others use it for, but usually I use it to find out if one node is a descendant of another.

Comment 20

[Boris Zbarsky [:bzbarsky]]

In core code you'd never do that.

Comment 21

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

Comment on attachment 403835 [details] [diff] [review]
patch

Please make CompareDocumentPosition use this new code too.

Also I'd say be bold and remove the code to deal with anonymous children. I really doubt that it'll affect anyone.

Comment 22

[(no longer active)]

The textarea part of this bug is solved by my patches in bug 240933.  I'm morphing this bug to include the general case.

Comment 23

[RNicoletto]

Cannot reproduce with Mozilla/5.0 (Windows NT 5.1; rv:15.0) Gecko/15.0 Firefox/15.0a1