Bug 1395701 part 2. Use a linked list, not a hashtable, for registering selection ranges on a node, so the registration will be faster. r=ehsan
authorBoris Zbarsky <bzbarsky@mit.edu>
Fri, 01 Sep 2017 11:13:47 -0400
changeset 430348 c1522ab270db8e96b8bae2a97715fde3cfd65574
parent 430347 584fa2c09356e6b5d1b6c048f2c41b8152139951
child 430349 298699310b26131dbb5f8c8e341bace5a995278c
push id1567
push userjlorenzo@mozilla.com
push dateThu, 02 Nov 2017 12:36:05 +0000
treeherdermozilla-release@e512c14a0406 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersehsan
bugs1395701
milestone57.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1395701 part 2. Use a linked list, not a hashtable, for registering selection ranges on a node, so the registration will be faster. r=ehsan Inserting/removing things into a doubly-linked list is much faster than doing the same with a hashtable. Selection ranges register themselves on their common ancestor, but all we do with that in non-debug code is iterate all the ranges registered. A doubly-linked list works fine for that. This adds three words to every range for the LinkedListItem members, but that should be OK.
dom/base/Element.cpp
dom/base/nsINode.h
dom/base/nsRange.cpp
dom/base/nsRange.h
dom/base/nsTextNode.cpp
--- a/dom/base/Element.cpp
+++ b/dom/base/Element.cpp
@@ -3039,19 +3039,25 @@ Element::List(FILE* out, int32_t aIndent
   fprintf(out, "@%p", (void *)this);
 
   ListAttributes(out);
 
   fprintf(out, " state=[%llx]",
           static_cast<unsigned long long>(State().GetInternalValue()));
   fprintf(out, " flags=[%08x]", static_cast<unsigned int>(GetFlags()));
   if (IsCommonAncestorForRangeInSelection()) {
-    const nsTHashtable<nsPtrHashKey<nsRange>>* ranges =
-      GetExistingCommonAncestorRanges();
-    fprintf(out, " ranges:%d", ranges ? ranges->Count() : 0);
+    const LinkedList<nsRange>* ranges = GetExistingCommonAncestorRanges();
+    int32_t count = 0;
+    if (ranges) {
+      // Can't use range-based iteration on a const LinkedList, unfortunately.
+      for (const nsRange* r = ranges->getFirst(); r; r = r->getNext()) {
+        ++count;
+      }
+    }
+    fprintf(out, " ranges:%d", count);
   }
   fprintf(out, " primaryframe=%p", static_cast<void*>(GetPrimaryFrame()));
   fprintf(out, " refcount=%" PRIuPTR "<", mRefCnt.get());
 
   nsIContent* child = GetFirstChild();
   if (child) {
     fputs("\n", out);
 
--- a/dom/base/nsINode.h
+++ b/dom/base/nsINode.h
@@ -14,16 +14,17 @@
 #include "nsIDOMNode.h"
 #include "mozilla/dom/NodeInfo.h"            // member (in nsCOMPtr)
 #include "nsIVariant.h"             // for use in GetUserData()
 #include "nsNodeInfoManager.h"      // for use in NodePrincipal()
 #include "nsPropertyTable.h"        // for typedefs
 #include "nsTObserverArray.h"       // for member
 #include "nsWindowSizes.h"          // for nsStyleSizes
 #include "mozilla/ErrorResult.h"
+#include "mozilla/LinkedList.h"
 #include "mozilla/MemoryReporting.h"
 #include "mozilla/dom/EventTarget.h" // for base class
 #include "js/TypeDecls.h"     // for Handle, Value, JSObject, JSContext
 #include "mozilla/dom/DOMString.h"
 #include "mozilla/dom/BindingDeclarations.h"
 #include "nsTHashtable.h"
 #include <iosfwd>
 
@@ -1127,20 +1128,22 @@ public:
 
     /**
      * Weak reference to this node.  This is cleared by the destructor of
      * nsNodeWeakReference.
      */
     nsNodeWeakReference* MOZ_NON_OWNING_REF mWeakReference;
 
     /**
-     * A set of ranges in the common ancestor for the selection to which
-     * this node belongs to.
+     * A set of ranges which are in the selection and which have this node as
+     * their endpoints' common ancestor.  This is a UniquePtr instead of just a
+     * LinkedList, because that prevents us from pushing DOMSlots up to the next
+     * allocation bucket size, at the cost of some complexity.
      */
-    mozilla::UniquePtr<nsTHashtable<nsPtrHashKey<nsRange>>> mCommonAncestorRanges;
+    mozilla::UniquePtr<mozilla::LinkedList<nsRange>> mCommonAncestorRanges;
 
     /**
      * Number of descendant nodes in the uncomposed document that have been
      * explicitly set as editable.
      */
     uint32_t mEditableDescendantCount;
   };
 
@@ -1938,33 +1941,33 @@ public:
                                                 CallerType aCallerType,
                                                 ErrorResult& aRv);
   already_AddRefed<DOMPoint> ConvertPointFromNode(const DOMPointInit& aPoint,
                                                   const TextOrElementOrDocument& aFrom,
                                                   const ConvertCoordinateOptions& aOptions,
                                                   CallerType aCallerType,
                                                   ErrorResult& aRv);
 
-  const nsTHashtable<nsPtrHashKey<nsRange>>* GetExistingCommonAncestorRanges() const
+  const mozilla::LinkedList<nsRange>* GetExistingCommonAncestorRanges() const
   {
     if (!HasSlots()) {
       return nullptr;
     }
-    mozilla::UniquePtr<nsTHashtable<nsPtrHashKey<nsRange>>>& ranges =
-      GetExistingSlots()->mCommonAncestorRanges;
-    return ranges.get();
+    return GetExistingSlots()->mCommonAncestorRanges.get();
   }
 
-  nsTHashtable<nsPtrHashKey<nsRange>>* GetExistingCommonAncestorRanges()
+  mozilla::LinkedList<nsRange>* GetExistingCommonAncestorRanges()
   {
-    nsINode::nsSlots* slots = GetExistingSlots();
-    return slots ? slots->mCommonAncestorRanges.get() : nullptr;
+    if (!HasSlots()) {
+      return nullptr;
+    }
+    return GetExistingSlots()->mCommonAncestorRanges.get();
   }
 
-  mozilla::UniquePtr<nsTHashtable<nsPtrHashKey<nsRange>>>& GetCommonAncestorRangesPtr()
+  mozilla::UniquePtr<mozilla::LinkedList<nsRange>>& GetCommonAncestorRangesPtr()
   {
     return Slots()->mCommonAncestorRanges;
   }
 
 protected:
 
   // Override this function to create a custom slots class.
   // Must not return null.
--- a/dom/base/nsRange.cpp
+++ b/dom/base/nsRange.cpp
@@ -200,24 +200,24 @@ nsRange::IsNodeSelected(nsINode* aNode, 
   NS_ASSERTION(n || !aNode->IsSelectionDescendant(),
                "orphan selection descendant");
 
   // Collect the potential ranges and their selection objects.
   RangeHashTable ancestorSelectionRanges;
   nsTHashtable<nsPtrHashKey<Selection>> ancestorSelections;
   uint32_t maxRangeCount = 0;
   for (; n; n = GetNextRangeCommonAncestor(n->GetParentNode())) {
-    nsTHashtable<nsPtrHashKey<nsRange>>* ranges =
-      n->GetExistingCommonAncestorRanges();
+    LinkedList<nsRange>* ranges = n->GetExistingCommonAncestorRanges();
     if (!ranges) {
       continue;
     }
-    for (auto iter = ranges->ConstIter(); !iter.Done(); iter.Next()) {
-      nsRange* range = iter.Get()->GetKey();
-      if (range->IsInSelection() && !range->Collapsed()) {
+    for (nsRange* range : *ranges) {
+      MOZ_ASSERT(range->IsInSelection(),
+                 "Why is this range registeed with a node?");
+      if (!range->Collapsed()) {
         ancestorSelectionRanges.PutEntry(range);
         Selection* selection = range->mSelection;
         ancestorSelections.PutEntry(selection);
         maxRangeCount = std::max(maxRangeCount, selection->RangeCount());
       }
     }
   }
 
@@ -332,16 +332,24 @@ NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(
   NS_INTERFACE_MAP_ENTRY_AMBIGUOUS(nsISupports, nsIDOMRange)
 NS_INTERFACE_MAP_END
 
 NS_IMPL_CYCLE_COLLECTION_CLASS(nsRange)
 
 NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN(nsRange)
   NS_IMPL_CYCLE_COLLECTION_UNLINK_PRESERVED_WRAPPER
   NS_IMPL_CYCLE_COLLECTION_UNLINK(mOwner);
+
+  // We _could_ just rely on Reset() to UnregisterCommonAncestor(),
+  // but it wouldn't know we're calling it from Unlink and so would do
+  // more work than it really needs to.
+  if (tmp->mRegisteredCommonAncestor) {
+    tmp->UnregisterCommonAncestor(tmp->mRegisteredCommonAncestor, true);
+  }
+
   tmp->Reset();
 
   // This needs to be unlinked after Reset() is called, as it controls
   // the result of IsInSelection() which is used by tmp->Reset().
   NS_IMPL_CYCLE_COLLECTION_UNLINK(mSelection);
 NS_IMPL_CYCLE_COLLECTION_UNLINK_END
 
 NS_IMPL_CYCLE_COLLECTION_TRAVERSE_BEGIN(nsRange)
@@ -405,56 +413,55 @@ nsRange::RegisterCommonAncestor(nsINode*
 {
   NS_PRECONDITION(aNode, "bad arg");
   NS_ASSERTION(IsInSelection(), "registering range not in selection");
 
   mRegisteredCommonAncestor = aNode;
 
   MarkDescendants(aNode);
 
-  UniquePtr<nsTHashtable<nsPtrHashKey<nsRange>>>& ranges =
-    aNode->GetCommonAncestorRangesPtr();
+  UniquePtr<LinkedList<nsRange>>& ranges = aNode->GetCommonAncestorRangesPtr();
   if (!ranges) {
-    ranges = MakeUnique<nsRange::RangeHashTable>();
+    ranges = MakeUnique<LinkedList<nsRange>>();
   }
-  ranges->PutEntry(this);
+  ranges->insertBack(this);
   aNode->SetCommonAncestorForRangeInSelection();
 }
 
 void
-nsRange::UnregisterCommonAncestor(nsINode* aNode)
+nsRange::UnregisterCommonAncestor(nsINode* aNode, bool aIsUnlinking)
 {
   NS_PRECONDITION(aNode, "bad arg");
   NS_ASSERTION(aNode->IsCommonAncestorForRangeInSelection(), "wrong node");
   MOZ_DIAGNOSTIC_ASSERT(aNode == mRegisteredCommonAncestor, "wrong node");
-  nsTHashtable<nsPtrHashKey<nsRange>>* ranges =
-    aNode->GetExistingCommonAncestorRanges();
+  LinkedList<nsRange>* ranges = aNode->GetExistingCommonAncestorRanges();
   MOZ_ASSERT(ranges);
-  NS_ASSERTION(ranges->GetEntry(this), "unknown range");
 
   mRegisteredCommonAncestor = nullptr;
 
-  bool isNativeAnon = aNode->IsInNativeAnonymousSubtree();
-  bool removed = false;
-
-  if (ranges->Count() == 1) {
+#ifdef DEBUG
+  bool found = false;
+  for (nsRange* range : *ranges) {
+    if (range == this) {
+      found = true;
+      break;
+    }
+  }
+  MOZ_ASSERT(found,
+             "We should be in the list on our registered common ancestor");
+#endif // DEBUG
+
+  remove();
+
+  // We don't want to waste time unmarking flags on nodes that are
+  // being unlinked anyway.
+  if (!aIsUnlinking && ranges->isEmpty()) {
     aNode->ClearCommonAncestorForRangeInSelection();
-    if (!isNativeAnon) {
-      // For nodes which are in native anonymous subtrees, we optimize away the
-      // cost of deallocating the hashtable here because we may need to create
-      // it again shortly afterward.  We don't do this for all nodes in order
-      // to avoid the additional memory usage unconditionally.
-      aNode->GetCommonAncestorRangesPtr().reset();
-      removed = true;
-    }
     UnmarkDescendants(aNode);
   }
-  if (!removed) {
-    ranges->RemoveEntry(this);
-  }
 }
 
 /******************************************************
  * nsIMutationObserver implementation
  ******************************************************/
 void
 nsRange::CharacterDataChanged(nsIDocument* aDocument,
                               nsIContent* aContent,
@@ -507,17 +514,17 @@ nsRange::CharacterDataChanged(nsIDocumen
       newStart.Set(aInfo->mDetails->mNextSibling, newStartOffset);
       if (MOZ_UNLIKELY(aContent == mRoot)) {
         newRoot = IsValidBoundary(newStart.Container());
       }
 
       bool isCommonAncestor =
         IsInSelection() && mStart.Container() == mEnd.Container();
       if (isCommonAncestor) {
-        UnregisterCommonAncestor(mStart.Container());
+        UnregisterCommonAncestor(mStart.Container(), false);
         RegisterCommonAncestor(newStart.Container());
       }
       if (mStart.Container()->IsDescendantOfCommonAncestorForRangeInSelection()) {
         newStart.Container()->SetDescendantOfCommonAncestorForRangeInSelection();
       }
     } else {
       // If boundary is inside changed text, position it before change
       // else adjust start offset for the change in length.
@@ -541,17 +548,17 @@ nsRange::CharacterDataChanged(nsIDocumen
       NS_ASSERTION(mEnd.Offset() <= aInfo->mChangeEnd + 1,
                    "mEnd.Offset() is beyond the end of this node");
       newEnd.Set(aInfo->mDetails->mNextSibling, mEnd.Offset() - aInfo->mChangeStart);
 
       bool isCommonAncestor =
         IsInSelection() && mStart.Container() == mEnd.Container();
       if (isCommonAncestor && !newStart.Container()) {
         // The split occurs inside the range.
-        UnregisterCommonAncestor(mStart.Container());
+        UnregisterCommonAncestor(mStart.Container(), false);
         RegisterCommonAncestor(mStart.Container()->GetParentNode());
         newEnd.Container()->SetDescendantOfCommonAncestorForRangeInSelection();
       } else if (mEnd.Container()->
                    IsDescendantOfCommonAncestorForRangeInSelection()) {
         newEnd.Container()->SetDescendantOfCommonAncestorForRangeInSelection();
       }
     } else {
       int32_t newEndOffset = mEnd.Offset() <= aInfo->mChangeEnd ?
@@ -969,25 +976,29 @@ nsRange::DoSetRange(const RawRangeBounda
     }
     if (aRoot) {
       aRoot->AddMutationObserver(this);
     }
   }
   bool checkCommonAncestor =
     (mStart.Container() != aStart.Container() || mEnd.Container() != aEnd.Container()) &&
     IsInSelection() && !aNotInsertedYet;
-  nsINode* oldCommonAncestor = checkCommonAncestor ? GetCommonAncestor() : nullptr;
+
+  // GetCommonAncestor is unreliable while we're unlinking (could
+  // return null if our start/end have already been unlinked), so make
+  // sure to not use it here to determine our "old" current ancestor.
   mStart = aStart;
   mEnd = aEnd;
   mIsPositioned = !!mStart.Container();
   if (checkCommonAncestor) {
+    nsINode* oldCommonAncestor = mRegisteredCommonAncestor;
     nsINode* newCommonAncestor = GetCommonAncestor();
     if (newCommonAncestor != oldCommonAncestor) {
       if (oldCommonAncestor) {
-        UnregisterCommonAncestor(oldCommonAncestor);
+        UnregisterCommonAncestor(oldCommonAncestor, false);
       }
       if (newCommonAncestor) {
         RegisterCommonAncestor(newCommonAncestor);
       } else {
         NS_ASSERTION(!mIsPositioned, "unexpected disconnected nodes");
         mSelection = nullptr;
       }
     }
@@ -1029,22 +1040,22 @@ nsRange::SetSelection(mozilla::dom::Sele
   }
   // At least one of aSelection and mSelection must be null
   // aSelection will be null when we are removing from a selection
   // and a range can't be in more than one selection at a time,
   // thus mSelection must be null too.
   MOZ_ASSERT(!aSelection || !mSelection);
 
   mSelection = aSelection;
-  nsINode* commonAncestor = GetCommonAncestor();
-  NS_ASSERTION(commonAncestor, "unexpected disconnected nodes");
   if (mSelection) {
+    nsINode* commonAncestor = GetCommonAncestor();
+    NS_ASSERTION(commonAncestor, "unexpected disconnected nodes");
     RegisterCommonAncestor(commonAncestor);
   } else {
-    UnregisterCommonAncestor(commonAncestor);
+    UnregisterCommonAncestor(mRegisteredCommonAncestor, false);
   }
 }
 
 nsINode*
 nsRange::GetCommonAncestor() const
 {
   return mIsPositioned ?
     nsContentUtils::GetCommonAncestor(mStart.Container(), mEnd.Container()) :
--- a/dom/base/nsRange.h
+++ b/dom/base/nsRange.h
@@ -17,31 +17,34 @@
 #include "nsIDocument.h"
 #include "nsIDOMNode.h"
 #include "nsLayoutUtils.h"
 #include "prmon.h"
 #include "nsStubMutationObserver.h"
 #include "nsWrapperCache.h"
 #include "mozilla/Attributes.h"
 #include "mozilla/GuardObjects.h"
+#include "mozilla/LinkedList.h"
 
 namespace mozilla {
 class ErrorResult;
 namespace dom {
 struct ClientRectsAndTexts;
 class DocumentFragment;
 class DOMRect;
 class DOMRectList;
 class Selection;
 } // namespace dom
 } // namespace mozilla
 
 class nsRange final : public nsIDOMRange,
                       public nsStubMutationObserver,
-                      public nsWrapperCache
+                      public nsWrapperCache,
+                      // For linking together selection-associated ranges.
+                      public mozilla::LinkedListElement<nsRange>
 {
   typedef mozilla::ErrorResult ErrorResult;
   typedef mozilla::dom::DOMRect DOMRect;
   typedef mozilla::dom::DOMRectList DOMRectList;
 
   virtual ~nsRange();
 
 public:
@@ -585,17 +588,17 @@ protected:
 
     mutable mozilla::Maybe<uint32_t> mOffset;
   };
 
   typedef RangeBoundaryBase<nsCOMPtr<nsINode>, nsCOMPtr<nsIContent>> RangeBoundary;
   typedef RangeBoundaryBase<nsINode*, nsIContent*> RawRangeBoundary;
 
   void RegisterCommonAncestor(nsINode* aNode);
-  void UnregisterCommonAncestor(nsINode* aNode);
+  void UnregisterCommonAncestor(nsINode* aNode, bool aIsUnlinking);
   nsINode* IsValidBoundary(nsINode* aNode) const
   {
     return ComputeRootNode(aNode, mMaySpanAnonymousSubtrees);
   }
 
   /**
    * XXX nsRange should accept 0 - UINT32_MAX as offset.  However, users of
    *     nsRange treat offset as int32_t.  Additionally, some other internal
--- a/dom/base/nsTextNode.cpp
+++ b/dom/base/nsTextNode.cpp
@@ -160,19 +160,25 @@ void
 nsTextNode::List(FILE* out, int32_t aIndent) const
 {
   int32_t index;
   for (index = aIndent; --index >= 0; ) fputs("  ", out);
 
   fprintf(out, "Text@%p", static_cast<const void*>(this));
   fprintf(out, " flags=[%08x]", static_cast<unsigned int>(GetFlags()));
   if (IsCommonAncestorForRangeInSelection()) {
-    const nsTHashtable<nsPtrHashKey<nsRange>>* ranges =
-      GetExistingCommonAncestorRanges();
-    fprintf(out, " ranges:%d", ranges ? ranges->Count() : 0);
+    const LinkedList<nsRange>* ranges = GetExistingCommonAncestorRanges();
+    int32_t count = 0;
+    if (ranges) {
+      // Can't use range-based iteration on a const LinkedList, unfortunately.
+      for (const nsRange* r = ranges->getFirst(); r; r = r->getNext()) {
+        ++count;
+      }
+    }
+    fprintf(out, " ranges:%d", count);
   }
   fprintf(out, " primaryframe=%p", static_cast<void*>(GetPrimaryFrame()));
   fprintf(out, " refcount=%" PRIuPTR "<", mRefCnt.get());
 
   nsAutoString tmp;
   ToCString(tmp, 0, mText.GetLength());
   fputs(NS_LossyConvertUTF16toASCII(tmp).get(), out);