1386480 - Make RangeItem a non-cycle-collectable type

Status: RESOLVED WONTFIX

(Core :: DOM: Editor, enhancement)

Description

[(no longer active)]

RangeItem right now is a heap allocated cycle collected object, which introduces both malloc and CC overhead, I have a patch to make it a normal value type.

It of course has to nsCOMPtr members that need to be introduced to the CC, but that can be done by the container classes, and by implementing ImplCycleCollectionUnlink() and ImplCycleCollectionTraverse() for the object.

Comment 1

[(no longer active)]

Attachment: Make RangeItem a value type

This removes the malloc and cycle collection overhead of this object.

Comment 2

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

Comment on attachment 8892716 [details] [diff] [review]
Make RangeItem a value type

>diff --git a/editor/libeditor/HTMLEditRules.h b/editor/libeditor/HTMLEditRules.h
>@@ -435,17 +435,17 @@ protected:
>   bool mReturnInEmptyLIKillsList;
>   bool mDidDeleteSelection;
>   bool mDidRangedDelete;
>   bool mRestoreContentEditableCount;
>   RefPtr<nsRange> mUtilRange;
>   // Need to remember an int across willJoin/didJoin...
>   uint32_t mJoinOffset;
>   nsCOMPtr<Element> mNewBlock;
>-  RefPtr<RangeItem> mRangeItem;
>+  RangeItem mRangeItem;

Hmm, this class members needs to be sorted for memory alignment... (not in the scope of this bug)

>diff --git a/editor/libeditor/SelectionState.cpp b/editor/libeditor/SelectionState.cpp
>+// This is used for mArray.Contains() below.
>+template<>
>+class nsDefaultComparator<mozilla::RangeItem, mozilla::RangeItem*> {

nit: put the |{| to the next line and remove the trailing white space (it's before |{|).

>+public:
>+  bool Equals(const mozilla::RangeItem& aLHS,
>+              mozilla::RangeItem* aRHS) const {

nit: same.

>@@ -224,24 +236,23 @@ RangeUpdater::SelAdjCreateNode(nsINode* aParent,
>   }
>   NS_ENSURE_TRUE(aParent, NS_ERROR_NULL_POINTER);
>   size_t count = mArray.Length();
>   if (!count) {
>     return NS_OK;
>   }
> 
>   for (size_t i = 0; i < count; i++) {
>-    RangeItem* item = mArray[i];
>-    NS_ENSURE_TRUE(item, NS_ERROR_NULL_POINTER);
>+    RangeItem& item = mArray[i];

How about to use |for (RangeItem& item : mArray) {|? (Up to you because of not your new code.)

>@@ -262,49 +273,48 @@ RangeUpdater::SelAdjDeleteNode(nsINode* aNode)
>     return;
>   }
> 
>   nsCOMPtr<nsINode> parent = aNode->GetParentNode();
>   int32_t offset = parent ? parent->IndexOf(aNode) : -1;
> 
>   // check for range endpoints that are after aNode and in the same parent
>   for (size_t i = 0; i < count; i++) {
>-    RangeItem* item = mArray[i];
>-    MOZ_ASSERT(item);
>+    RangeItem& item = mArray[i];

Same.

>@@ -323,31 +333,30 @@ RangeUpdater::SelAdjSplitNode(nsIContent& aOldRightNode,
>   int32_t offset = parent ? parent->IndexOf(&aOldRightNode) : -1;
> 
>   // first part is same as inserting aNewLeftnode
>   nsresult rv = SelAdjInsertNode(parent, offset - 1);
>   NS_ENSURE_SUCCESS(rv, rv);
> 
>   // next step is to check for range enpoints inside aOldRightNode
>   for (size_t i = 0; i < count; i++) {
>-    RangeItem* item = mArray[i];
>-    NS_ENSURE_TRUE(item, NS_ERROR_NULL_POINTER);
>+    RangeItem& item = mArray[i];

Same.

>@@ -361,51 +370,50 @@ RangeUpdater::SelAdjJoinNodes(nsINode& aLeftNode,
>     return NS_OK;
>   }
>   size_t count = mArray.Length();
>   if (!count) {
>     return NS_OK;
>   }
> 
>   for (size_t i = 0; i < count; i++) {
>-    RangeItem* item = mArray[i];
>-    NS_ENSURE_TRUE(item, NS_ERROR_NULL_POINTER);
>+    RangeItem& item = mArray[i];

Same.

>@@ -419,24 +427,23 @@ RangeUpdater::SelAdjInsertText(Text& aTextNode,
> 
>   size_t count = mArray.Length();
>   if (!count) {
>     return;
>   }
> 
>   size_t len = aString.Length();
>   for (size_t i = 0; i < count; i++) {
>-    RangeItem* item = mArray[i];
>-    MOZ_ASSERT(item);
>+    RangeItem& item = mArray[i];

Same.

>@@ -448,29 +455,28 @@ RangeUpdater::SelAdjDeleteText(nsIContent* aTextNode,
> 
>   size_t count = mArray.Length();
>   if (!count) {
>     return NS_OK;
>   }
>   NS_ENSURE_TRUE(aTextNode, NS_ERROR_NULL_POINTER);
> 
>   for (size_t i = 0; i < count; i++) {
>-    RangeItem* item = mArray[i];
>-    NS_ENSURE_TRUE(item, NS_ERROR_NULL_POINTER);
>+    RangeItem& item = mArray[i];

Same.

>@@ -500,24 +506,23 @@ RangeUpdater::DidReplaceContainer(Element* aOriginalNode,
> 
>   NS_ENSURE_TRUE(aOriginalNode && aNewNode, NS_ERROR_NULL_POINTER);
>   size_t count = mArray.Length();
>   if (!count) {
>     return NS_OK;
>   }
> 
>   for (size_t i = 0; i < count; i++) {
>-    RangeItem* item = mArray[i];
>-    NS_ENSURE_TRUE(item, NS_ERROR_NULL_POINTER);
>+    RangeItem& item = mArray[i];

Same.

>@@ -539,32 +544,31 @@ RangeUpdater::DidRemoveContainer(nsINode* aNode,
>   size_t count = mArray.Length();
>   if (!count) {
>     return NS_OK;
>   }
> 
>   for (size_t i = 0; i < count; i++) {
>-    RangeItem* item = mArray[i];
>-    NS_ENSURE_TRUE(item, NS_ERROR_NULL_POINTER);
>+    RangeItem& item = mArray[i];

Same.

>+void
>+RangeItem::Traverse(nsCycleCollectionTraversalCallback& aCallback, uint32_t aFlags)

Too long line, please wrap it after |aCallback,|.

>+{
>+  CycleCollectionNoteChild(aCallback, mStartContainer.get(), "mStartContainer", aFlags);

Too long line, please wrap it after |mStartContainer.get(),|.

>+  CycleCollectionNoteChild(aCallback, mEndContainer.get(), "mEndContainer", aFlags);

Too long line, please wrap it after |mEndContainer.get(),|.

>diff --git a/editor/libeditor/SelectionState.h b/editor/libeditor/SelectionState.h
>+inline void
>+ImplCycleCollectionUnlink(RangeItem& aItem)
>+{
>+  aItem.Unlink();
>+}
>+
>+inline void
>+ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback,
>+                            RangeItem& aItem,
>+                            const char* aName,
>+                            uint32_t aFlags = 0)
>+{
>+  aItem.Traverse(aCallback, aFlags);
>+}

Hmm, these inline method names are too generic and SelectionState.h is exposed. So, the method names may conflict with future patches.

Why don't you declare these methods in RangeItem class? Or use more specific name?

Comment 3

[(no longer active)]

Sorry, this patch turned out to be completely broken!

There are the following issues in it:

  * RangeUpdater needs to update the RangeItem objects alive elsewhere, so mArray there needs to store pointers, not value objects!
  * Therefore, RegisterRangeItem() and DropRangeItem() also need to change.  Since they are used in a stack order, we can make the register function return the index of the registered element, and for the drop method to take that index as an argument.

I'd like to address these, and get a green try run before posting the next version.  A lot of the previous review comments are unfortunately invalidated because the code changes went away...

(In reply to Masayuki Nakano [:masayuki] (JST, +0900) from comment #2)
> >diff --git a/editor/libeditor/SelectionState.h b/editor/libeditor/SelectionState.h
> >+inline void
> >+ImplCycleCollectionUnlink(RangeItem& aItem)
> >+{
> >+  aItem.Unlink();
> >+}
> >+
> >+inline void
> >+ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback,
> >+                            RangeItem& aItem,
> >+                            const char* aName,
> >+                            uint32_t aFlags = 0)
> >+{
> >+  aItem.Traverse(aCallback, aFlags);
> >+}
> 
> Hmm, these inline method names are too generic and SelectionState.h is
> exposed. So, the method names may conflict with future patches.
> 
> Why don't you declare these methods in RangeItem class? Or use more specific
> name?

These are cycle collector API names, I didn't invent them.  :-)  They need to be in the headers so that all code that sees these types has access to them...  Although in reality I think only code in SelectionState.cpp uses RangeItem inside CC macros, I'll see if I can move them to the cpp file.

Comment 4

[(no longer active)]

Status update: Today I got this down to 1 remaining test failure! https://treeherder.mozilla.org/#/jobs?repo=try&revision=d58ab5af85fa38e74e707b76d69cd3edafbb1ab6  Once I figure out why this is happening I'll clean things up and submit a patch for review.

Comment 5

[(no longer active)]

After spending a few days trying to get this to work, I no longer think this is viable, or at least I can't disentangle the current code in a way that fills me with confidence about the correctness of the patch.  The fundamental issue is that we pass RangeItem objects around using pointers, and in general my previous approach made it so that we didn't really have anything that ensured the pointers point to valid objects, so it seems like we can't easily avoid refcounting this object.  :-(

At the lack of that, I'm going to morph this bug to the much more simple case of just removing the CC overhead from this type.

Comment 6

[(no longer active)]

Attachment: Make RangeItem a non-cycle-collectable type

Comment 7

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

Comment on attachment 8896619 [details] [diff] [review]
Make RangeItem a non-cycle-collectable type

Okay, but I'm not familiar with CC. So, if you're not familiar with it too, please ask additional review to another person.

Comment 8

[(no longer active)]

I'm fairly familiar with it.  To explain what the patch is doing, it is basically shifting the responsibility of traversing and unlinking the RangeItem objects from themselves to their containers.

The way that CC usually works is you have a bunch of objects called CC participants (the ones which typically have NS_DECL_CYCLE_COLLECTION_CLASS macros in them) which provide Travese and Unlink methods that tell the cycle collector how the object traverses other cycle collectable members and unlinks them when the object ends up becoming disconnected from all external non-cycling references.  The way that these methods work, you either delegate to each type using custom overloads of ImplCycleCollectionTraverse and ImplCycleCollectionUnlink and let those custom overloads do something custom, or you use the generic macros, as the RangeItem class used to do.

After this patch, for example, when SelectionState::mArray needs to be traversed in https://searchfox.org/mozilla-central/rev/6482c8a5fa5c7446e82ef187d1a1faff49e3379e/editor/libeditor/SelectionState.h#86, since there is a custom ImplCycleCollectionTraverse overload that accepts a RefPtr<RangeItem>& argument, that one gets called, and that knows how to call RangeItem::Traverse() which knows how to tell the cycle collector about the cycle collectible members of RangeItem.  Without this, you'd need to rely on our generic macro-based machinery which involves a bit higher overhead.

Comment 9

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/22e03ad3b371
Make RangeItem a non-cycle-collectable type; r=masayuki

Comment 10

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

(In reply to :Ehsan Akhgari (needinfo please, extremely long backlog) from comment #8)
> I'm fairly familiar with it.  To explain what the patch is doing, it is
> basically shifting the responsibility of traversing and unlinking the
> RangeItem objects from themselves to their containers.

Yeah, I understood it from your patch.

> The way that CC usually works is you have a bunch of objects called CC
> participants (the ones which typically have NS_DECL_CYCLE_COLLECTION_CLASS
> macros in them) which provide Travese and Unlink methods that tell the cycle
> collector how the object traverses other cycle collectable members and
> unlinks them when the object ends up becoming disconnected from all external
> non-cycling references.

I read http://blog.kylehuey.com/post/27564411715/cycle-collection again with your this comment. However, there still be some mysterious macros like NS_IMPL_CYCLE_COLLECTION_ROOT_NATIVE without documents. So, now I got the overview of CC now more, but still don't understand your patch fully.

> The way that these methods work, you either
> delegate to each type using custom overloads of ImplCycleCollectionTraverse
> and ImplCycleCollectionUnlink and let those custom overloads do something
> custom, or you use the generic macros, as the RangeItem class used to do.
> 
> After this patch, for example, when SelectionState::mArray needs to be
> traversed in
> https://searchfox.org/mozilla-central/rev/
> 6482c8a5fa5c7446e82ef187d1a1faff49e3379e/editor/libeditor/SelectionState.
> h#86, since there is a custom ImplCycleCollectionTraverse overload that
> accepts a RefPtr<RangeItem>& argument, that one gets called, and that knows
> how to call RangeItem::Traverse() which knows how to tell the cycle
> collector about the cycle collectible members of RangeItem.  Without this,
> you'd need to rely on our generic macro-based machinery which involves a bit
> higher overhead.

I still have a question, why the change makes the performance better? Is it just expensive if there are a lot of cycle collectable objects? Instead, is it reasonable to reduce cycle collectable objects but managed by their containers if the number of containers is enough smaller than the number of items?

Comment 11

[(no longer active)]

It is the cost of the separate participant object that I am trying to save on here.  For example, <https://searchfox.org/mozilla-central/rev/e5b13e6224dbe3182050cf442608c4cb6a8c5c55/xpcom/base/nsCycleCollector.cpp#2658> is a virtual call.  Similarly there's other participant APIs that are implemented as virtual calls: <https://searchfox.org/mozilla-central/rev/e5b13e6224dbe3182050cf442608c4cb6a8c5c55/xpcom/base/nsCycleCollectionParticipant.h#113>.  There are also features such as skipping <https://searchfox.org/mozilla-central/rev/e5b13e6224dbe3182050cf442608c4cb6a8c5c55/xpcom/base/nsCycleCollector.cpp#2520> which do incur a bit of a cost which we don't need here.  And then there is the fact that the Release() function for cycle collectible classes is a bit more expensive that non-cycle collectible classes due to it calling NS_CycleCollectorSuspect3().  I hope I'm covering all of the overhead involved.  Sorry I don't have a profile link handy.  :-)

Oh, and BTW note that all of the above is well into the micro-optimization territory.  The most important motivation factor here was really NS_CycleCollectorSuspect3() showing up in profiles IIRC given how frequently we AddRef/Release this object...

Comment 12

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/22e03ad3b371

Comment 13

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

(In reply to :Ehsan Akhgari (needinfo please, extremely long backlog) from comment #11)
> It is the cost of the separate participant object that I am trying to save
> on here.  For example,
> <https://searchfox.org/mozilla-central/rev/
> e5b13e6224dbe3182050cf442608c4cb6a8c5c55/xpcom/base/nsCycleCollector.
> cpp#2658> is a virtual call.  Similarly there's other participant APIs that
> are implemented as virtual calls:
> <https://searchfox.org/mozilla-central/rev/
> e5b13e6224dbe3182050cf442608c4cb6a8c5c55/xpcom/base/
> nsCycleCollectionParticipant.h#113>.  There are also features such as
> skipping
> <https://searchfox.org/mozilla-central/rev/
> e5b13e6224dbe3182050cf442608c4cb6a8c5c55/xpcom/base/nsCycleCollector.
> cpp#2520> which do incur a bit of a cost which we don't need here.  And then
> there is the fact that the Release() function for cycle collectible classes
> is a bit more expensive that non-cycle collectible classes due to it calling
> NS_CycleCollectorSuspect3().  I hope I'm covering all of the overhead
> involved.  Sorry I don't have a profile link handy.  :-)

Thank you for your explanation. I'll also read the comment of nsCycleCollector.cpp. I didn't know they are implemented with such a lot of virtual calls.

> Oh, and BTW note that all of the above is well into the micro-optimization
> territory.  The most important motivation factor here was really
> NS_CycleCollectorSuspect3() showing up in profiles IIRC given how frequently
> we AddRef/Release this object...

Thanks, that's very useful information to me. I'll keep in mind what should be cycle collectable and shouldn't.

I'd like to say, thank you very much again!

Comment 14

[(no longer active)]

I'm going to back this out for bug 1391410 and mark this as WONTFIX.  I still think we can redo RangeItem a lot more efficiently in editor but this requires a lot of deep surgery in the editor code, which I honestly have no desire to do.  :-/

Comment 15

[Pulsebot]

Backout by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/85490b718699
Backout for causing bug 1391410

Comment 16

[Andrew McCreight [:mccr8]]

Olli filed bug 1391423 about possibly reducing the overhead for the purple buffer for these and other mainthread only objects.

Comment 17

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

Merged backout: https://hg.mozilla.org/mozilla-central/rev/85490b718699

Comment 18

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

FWIW, I'm having trouble to see RangeItem in profiles.