1373654 - Create alternative Range class for simpler use

Status: RESOLVED FIXED

(Core :: DOM: Editor, enhancement, P3)

Description

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

When I check some profiles when I do something, I often see nsRange in them.

nsRange is always allocated in heap. And it observe mutation of the document. Additionally, it checks the point relation between start and end. All of them are too expensive especially when the range is in temporary use.

So, I've investigated (experimented) how to fix this issue. Then, current my idea is, we should redesign around nsRange.

* nsRange should keep representing DOM Range and it should be used for long life object since it observers mutation and keeps itself valid.
* mozilla::RangeData should represent similar to DOM Range but doesn't observe mutation and can be created in stack, and should be able to skip to check the relation between start point and end point (i.e., can be reversed).
* mozilla::RawRangeData should be simple struct to represent two DOM points and RangeData should inherit this class.

Then, nsRange should *not* inherit RangeData because it causes increasing the instance size. Looks like that we shouldn't increase nsRange instance size as far as possible. And if I create a static class like mozilla::RangeImpl, nsRange and RangeData can share the implementation.

Any ideas?

# Although I don't want to fix this issue in this bug, I *guess* that Selection can store RangeData instead of nsRange because Selection should observe mutation instead of nsRange. See bug 1370756.

Comment 1

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

How often is it ok to not observe mutations?

Where are we creating temporary Range objects which don't need to observe mutations? We should just stop doing that.


For the cases when we have several range objects pointing to same values I was thinking we could add
some shared object which observes mutations and range objects would then  get values from it.

Comment 2

[Mats Palmgren (inactive)]

> When I check some profiles when I do something, I often see nsRange in them.

That's pretty vague as a problem description, so it's hard to understand
which use case you're trying to optimize.

> nsRange is always allocated in heap.

We could use arena allocation to optimize that.

> And it observe mutation of the document.

Only nsRanges that are in a Selection do that.  They observe the common
ancestor of the range IIRC, so for a page with thousands of <input>s
none of them should be notified of DOM changes that isn't inside any
<input> data.  So is the problem that just having that many Observers
is making some code slow?

One idea would be to not create a Range/Selection for <input> unless
it's needed.  I think we used to create the editor lazily at some
point (create it on focus, destroy it on blur), but that was fragile
IIRC. (I haven't checked if we have resurrected that though.)

> Then, nsRange should *not* inherit RangeData because it causes increasing the instance size.

nsRange doesn't inherit RangeData.
http://searchfox.org/mozilla-central/rev/20d16dadd336e0c6b97e3e19dc4ff907744b5734/dom/base/nsRange.h#37
http://searchfox.org/mozilla-central/rev/20d16dadd336e0c6b97e3e19dc4ff907744b5734/layout/generic/Selection.h#42

I think you need to describe *in detail* which problem you intend
to optimize in this bug, and probably limit it to just one specific
problem.  Bugs are cheap, if there are multiple problems then just
file new bugs.  Thanks.

Comment 3

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

(In reply to Olli Pettay [:smaug] from comment #1)
> Where are we creating temporary Range objects which don't need to observe
> mutations? We should just stop doing that.

I saw a lot of unnecessary cost of nsRange use in ContentEventHandler first. It's used often, but it creates nsRange when it converts offset and length in plaintext to DOM points. Then, it uses the range just for other methods which computes something queried. So, it's not necessary to expensive handling in nsRange (observing mutation nor checking relation between start point and end point).

And as I filed this bug as blocking bug 1367744, Selection::Extend() creates two nsRange instances and they are modified with checking relation between start point and end point even if the caller know if it's safe.
https://searchfox.org/mozilla-central/rev/b2d072aa5847996b8276bd8d7b150e0ea6bf6283/layout/generic/nsSelection.cpp#5643,5682,5685,5690-5691,5706,5719-5720,5726,5736,5742,5749,5754-5755,5784-5785,5791,5802,5807,5810,5816-5817,5841,5846-5848
Relation check uses |nsContentUtils::ComparePoints()| that is expensive in most cases because it creates an array and uses nsINode::IndexOf(). So, if caller can guarantee that a call of SetStart*(), SetEnd*() or SetStartAndEnd() doesn't create reversed range, nsRange can skip this cost.

And I see some methods taking nsRange pointer with their argument usually use only GetStartParent(), GetEndParent(), StartOffset() and EndOffset() (and sometimes GetRoot() and GetCommonAncestor()). E.g., ContentIterators:
https://searchfox.org/mozilla-central/rev/b2d072aa5847996b8276bd8d7b150e0ea6bf6283/dom/base/nsContentIterator.cpp#294,299,304,310,312,318,320
https://searchfox.org/mozilla-central/rev/b2d072aa5847996b8276bd8d7b150e0ea6bf6283/dom/base/nsContentIterator.cpp#1276,1282,1285-1289
(nsContentSubtreeIterator also stores the range as its member. However, looks like that it doesn't need the mutation observer since its lifetime is short and no users causes DOM tree change during using it.)

nsFind uses nsRange only for initializing content iterator:
https://searchfox.org/mozilla-central/rev/b2d072aa5847996b8276bd8d7b150e0ea6bf6283/toolkit/components/find/nsFind.cpp#264,291-294
https://searchfox.org/mozilla-central/rev/b2d072aa5847996b8276bd8d7b150e0ea6bf6283/toolkit/components/find/nsFind.cpp#364,392-393,402,407,410,413,421-422,425-426,431,438
(Although, this is not so many times unless there is a lot of <input type="text"> and/or <textarea>.)

And I've not investigated under editor/, there could be similar cases.

> How often is it ok to not observe mutations?

I think that it's a lot in short time usage. And if Selection has mutation observer, the number may be decreased a lot.

> For the cases when we have several range objects pointing to same values I
> was thinking we could add
> some shared object which observes mutations and range objects would then 
> get values from it.

Hmm, I have no idea how to implement such stuff. Sounds like needs a hashtable. But I see adding to/removing from mutation observer in nsRange::DoSetRange(). So, looks like using hashtable in hot path may appear in profiles. (Although if there is no way, it must be the best idea.)

(In reply to Mats Palmgren (:mats) from comment #2)
> > When I check some profiles when I do something, I often see nsRange in them.
> 
> That's pretty vague as a problem description, so it's hard to understand
> which use case you're trying to optimize.

Sorry, see first block of this comment.

> > nsRange is always allocated in heap.
> 
> We could use arena allocation to optimize that.

Ah, that's a good idea. Do you know some bug#s which implemented arena?

> > And it observe mutation of the document.
> 
> Only nsRanges that are in a Selection do that.

No, unless the range is not positioned, nsRange observes mutation of the *root*.
https://searchfox.org/mozilla-central/rev/b2d072aa5847996b8276bd8d7b150e0ea6bf6283/dom/base/nsRange.cpp#893,897-898,921-923,925-926

> They observe the common
> ancestor of the range IIRC, so for a page with thousands of <input>s
> none of them should be notified of DOM changes that isn't inside any
> <input> data.  So is the problem that just having that many Observers
> is making some code slow?

The root is computed by nsRange::IsValidBoundary():
https://searchfox.org/mozilla-central/rev/b2d072aa5847996b8276bd8d7b150e0ea6bf6283/dom/base/nsRange.cpp#1150,1163,1165-1167,1172-1174,1181-1183,1186,1192
If it's not allowed to span subtrees (in most cases) and it's not in subtree, it observers all nodes in the document, it's in a subtree, then, it observers all of the subtree. Otherwise, it's used by nsFind, it observes all parent tree (I'm not sure if it's nested subtree).

> One idea would be to not create a Range/Selection for <input> unless
> it's needed.  I think we used to create the editor lazily at some
> point (create it on focus, destroy it on blur), but that was fragile
> IIRC. (I haven't checked if we have resurrected that though.)

Yeah. I think I should investigate it. However, editor depends on Selection. Therefore, it's modified Selection a lot during editing and then, set Selection to as is. If editor doesn't depend on Selection, it could reduce the runtime cost.

> > Then, nsRange should *not* inherit RangeData because it causes increasing the instance size.
> 
> nsRange doesn't inherit RangeData.
> http://searchfox.org/mozilla-central/rev/
> 20d16dadd336e0c6b97e3e19dc4ff907744b5734/dom/base/nsRange.h#37
> http://searchfox.org/mozilla-central/rev/
> 20d16dadd336e0c6b97e3e19dc4ff907744b5734/layout/generic/Selection.h#42

Ah, sorry. I should mention it. Current "RangeData" isn't good name. So, I think that it should be renamed to RangeAndStyle or StyledRange. (I'll file a bug for it.)

The RangeData which I mentioned in comment 0 is *new* class.  In my experimental patch, it needs to store root, start parent, end parent, start offset, end offset and "allowed to span subtrees" as bool.  The last bool causes increasing nsRange's instance size unfortunately.

> I think you need to describe *in detail* which problem you intend
> to optimize in this bug, and probably limit it to just one specific
> problem.  Bugs are cheap, if there are multiple problems then just
> file new bugs.  Thanks.

Yeah, I tried to look for generic resolution. However, if we can fix the performance issue with smaller changes, I'd like to take them.

On the other hand, if owners of nsRange can stop/use mutation observers and/or comparing start and end points during initializing, it means that nsRange instance will have additional state and methods may be stateful with it. That sounds bad because it may be difficult to check the state only from the code if the range comes from its argument.

Comment 4

[Mats Palmgren (inactive)]

(In reply to Masayuki Nakano [:masayuki] (JST, +0900) from comment #3)
> No, unless the range is not positioned, nsRange observes mutation of the
> *root*.

Ah right, thanks for reminding me.  Yeah, that seems unnecessary for
temporary nsRanges that we just throw away.

> The RangeData which I mentioned in comment 0 is *new* class.

OK, now your comments makes more sense, I thought you meant the existing
RangeData class.  Yeah, I think it's probably a good idea to avoid using
nsRange for short-lived internal uses and instead use something simpler
that isn't an observer.  Looking at "new nsRange" the problem doesn't
appear to be that widespread though:
https://searchfox.org/mozilla-central/search?q=new+nsRange&case=false&regexp=false&path=
I suspect most of those ranges are probably added to a Selection and
needs to continue to be nsRange.  The one that stands out is
dom/events/ContentEventHandler.cpp
Perhaps we should start by fixing that one first?  I mean, just declare
a class locally there for now, without making changes to nsRange.
It seems to me all that is needed there is to propagate a couple of
node/offset boundary points around, and from the looks of it can
just be a temporary stack allocated object.  If that works and if we
see that it's needed also in other places, then we can think about
how to integrate it better with nsRange.  WDYT?

Comment 5

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

(In reply to Mats Palmgren (:mats) from comment #4)
> I suspect most of those ranges are probably added to a Selection and
> needs to continue to be nsRange.

I wonder, cannot ranges in Selection be new range class instances? If Selection observes the mutation, then, each range doesn't need to observe mutation. Then, only when GetRangeAt() is called, Selection can create nsRange instance and it should be used in Selection instead of new class instance until it's removed from Selection.

I guess that ranges of non-normal selection are never used by JS. If so, we can reduce a lot of runtime cost, especially for spellchecker and find.

Comment 6

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

I met Maybe template class implementation that has storage and use it for an instance of given class. So, I guess that we can create arena with Maybe, but I still don't have a good idea, where is a good owner of the arena? nsRange is created by nsDocument::CreateRange(). However, the instance may be grabbed by other documents and can live longer than the document.

Comment 7

[Sylvestre Ledru [:Sylvestre]]

Moving to p3 because no activity for at least 1 year(s).
See https://github.com/mozilla/bug-handling/blob/master/policy/triage-bugzilla.md#how-do-you-triage for more information

Comment 8

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

Now, we have EditorDOMRange for editor module.