Bug 1355540, use SegmentedVector for pending links to avoid slow hashtable lookups in hot codepaths, r=bz
authorOlli Pettay <Olli.Pettay@helsinki.fi>
Sat, 15 Apr 2017 18:55:05 +0300
changeset 353278 3f319382720cc8fa8257b25b7513546e6113791e
parent 353277 cd981920d0ef8adf66e504b718a4208dc03c7a4c
child 353279 7c9e059fe6da793ec1f20f1cf7ba1d45cb8ab4a8
push id89231
push useropettay@mozilla.com
push dateSat, 15 Apr 2017 16:15:46 +0000
treeherdermozilla-inbound@3f319382720c [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbz
bugs1355540
milestone55.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 1355540, use SegmentedVector for pending links to avoid slow hashtable lookups in hot codepaths, r=bz
dom/base/Element.h
dom/base/Link.cpp
dom/base/Link.h
dom/base/nsDocument.cpp
dom/base/nsIDocument.h
dom/html/HTMLAnchorElement.cpp
dom/html/HTMLAnchorElement.h
dom/html/HTMLAreaElement.cpp
dom/html/HTMLAreaElement.h
dom/html/HTMLLinkElement.cpp
dom/html/HTMLLinkElement.h
dom/mathml/nsMathMLElement.cpp
dom/mathml/nsMathMLElement.h
dom/svg/SVGAElement.cpp
dom/svg/SVGAElement.h
dom/svg/nsSVGElement.h
toolkit/components/places/tests/gtest/mock_Link.h
--- a/dom/base/Element.h
+++ b/dom/base/Element.h
@@ -1157,16 +1157,18 @@ public:
   /**
    * Called when we have been adopted, and the information of the
    * node has been changed.
    *
    * The new document can be reached via OwnerDoc().
    *
    * If you override this method,
    * please call up to the parent NodeInfoChanged.
+   *
+   * If you change this, change also the similar method in Link.
    */
   virtual void NodeInfoChanged(nsIDocument* aOldDoc) {}
 
   /**
    * Parse a string into an nsAttrValue for a CORS attribute.  This
    * never fails.  The resulting value is an enumerated value whose
    * GetEnumValue() returns one of the above constants.
    */
--- a/dom/base/Link.cpp
+++ b/dom/base/Link.cpp
@@ -28,26 +28,28 @@ namespace mozilla {
 namespace dom {
 
 Link::Link(Element *aElement)
   : mElement(aElement)
   , mHistory(services::GetHistoryService())
   , mLinkState(eLinkState_NotLink)
   , mNeedsRegistration(false)
   , mRegistered(false)
+  , mHasPendingLinkUpdate(false)
 {
   MOZ_ASSERT(mElement, "Must have an element");
 }
 
 Link::Link()
   : mElement(nullptr)
   , mHistory(nullptr)
   , mLinkState(eLinkState_NotLink)
   , mNeedsRegistration(false)
   , mRegistered(false)
+  , mHasPendingLinkUpdate(false)
 {
 }
 
 Link::~Link()
 {
   UnregisterFromHistory();
 }
 
--- a/dom/base/Link.h
+++ b/dom/base/Link.h
@@ -121,16 +121,26 @@ public:
   void TryDNSPrefetch();
   void CancelDNSPrefetch(nsWrapperCache::FlagsType aDeferredFlag,
                          nsWrapperCache::FlagsType aRequestedFlag);
 
   // This is called by HTMLLinkElement.
   void TryDNSPrefetchPreconnectOrPrefetchOrPrerender();
   void CancelPrefetch();
 
+  bool HasPendingLinkUpdate() { return mHasPendingLinkUpdate; }
+  void SetHasPendingLinkUpdate() { mHasPendingLinkUpdate = true; }
+  void ClearHasPendingLinkUpdate() { mHasPendingLinkUpdate = false; }
+
+  // To ensure correct mHasPendingLinkUpdate handling, we have this method
+  // similar to the one in Element. Overriders must call
+  // ClearHasPendingLinkUpdate().
+  // If you change this, change also the method in Element.
+  virtual void NodeInfoChanged(nsIDocument* aOldDoc) = 0;
+
 protected:
   virtual ~Link();
 
   /**
    * Return true if the link has associated URI.
    */
   bool HasURI() const
   {
@@ -159,19 +169,21 @@ private:
   Element * const mElement;
 
   // Strong reference to History.  The link has to unregister before History
   // can disappear.
   nsCOMPtr<IHistory> mHistory;
 
   uint16_t mLinkState;
 
-  bool mNeedsRegistration;
+  bool mNeedsRegistration : 1;
 
-  bool mRegistered;
+  bool mRegistered : 1;
+
+  bool mHasPendingLinkUpdate : 1;
 };
 
 NS_DEFINE_STATIC_IID_ACCESSOR(Link, MOZILLA_DOM_LINK_IMPLEMENTATION_IID)
 
 } // namespace dom
 } // namespace mozilla
 
 #endif // mozilla_dom_Link_h__
--- a/dom/base/nsDocument.cpp
+++ b/dom/base/nsDocument.cpp
@@ -1312,16 +1312,17 @@ nsIDocument::nsIDocument()
     mAllowDNSPrefetch(true),
     mIsStaticDocument(false),
     mCreatingStaticClone(false),
     mInUnlinkOrDeletion(false),
     mHasHadScriptHandlingObject(false),
     mIsBeingUsedAsImage(false),
     mIsSyntheticDocument(false),
     mHasLinksToUpdate(false),
+    mHasLinksToUpdateRunnable(false),
     mMayHaveDOMMutationObservers(false),
     mMayHaveAnimationObservers(false),
     mHasMixedActiveContentLoaded(false),
     mHasMixedActiveContentBlocked(false),
     mHasMixedDisplayContentLoaded(false),
     mHasMixedDisplayContentBlocked(false),
     mHasMixedContentObjectSubrequest(false),
     mHasCSP(false),
@@ -10000,44 +10001,69 @@ nsIDocument::EnumerateActivityObservers(
     aEnumerator(iter.Get()->GetKey(), aData);
   }
 }
 
 void
 nsIDocument::RegisterPendingLinkUpdate(Link* aLink)
 {
   MOZ_ASSERT(!mIsLinkUpdateRegistrationsForbidden);
-  mLinksToUpdate.PutEntry(aLink);
+
+  if (aLink->HasPendingLinkUpdate()) {
+    return;
+  }
+
+  aLink->SetHasPendingLinkUpdate();
+
+  if (!mHasLinksToUpdateRunnable) {
+    nsCOMPtr<nsIRunnable> event =
+      NewRunnableMethod(this, &nsIDocument::FlushPendingLinkUpdatesFromRunnable);
+    nsresult rv =
+      Dispatch("nsIDocument::FlushPendingLinkUpdatesFromRunnable",
+               TaskCategory::Other, event.forget());
+    if (NS_FAILED(rv)) {
+      // If during shutdown posting a runnable doesn't succeed, we probably
+      // don't need to update link states.
+      return;
+    }
+    mHasLinksToUpdateRunnable = true;
+  }
+
+  mLinksToUpdate.InfallibleAppend(aLink);
   mHasLinksToUpdate = true;
 }
 
 void
-nsIDocument::UnregisterPendingLinkUpdate(Link* aLink)
-{
-  MOZ_ASSERT(!mIsLinkUpdateRegistrationsForbidden);
-  if (!mHasLinksToUpdate)
-    return;
-
-  mLinksToUpdate.RemoveEntry(aLink);
+nsIDocument::FlushPendingLinkUpdatesFromRunnable()
+{
+  MOZ_ASSERT(mHasLinksToUpdateRunnable);
+  mHasLinksToUpdateRunnable = false;
+  FlushPendingLinkUpdates();
 }
 
 void
 nsIDocument::FlushPendingLinkUpdates()
 {
   MOZ_ASSERT(!mIsLinkUpdateRegistrationsForbidden);
   if (!mHasLinksToUpdate)
     return;
 
 #ifdef DEBUG
   AutoRestore<bool> saved(mIsLinkUpdateRegistrationsForbidden);
   mIsLinkUpdateRegistrationsForbidden = true;
 #endif
-  for (auto iter = mLinksToUpdate.ConstIter(); !iter.Done(); iter.Next()) {
-    Link* link = iter.Get()->GetKey();
-    link->GetElement()->UpdateLinkState(link->LinkState());
+  for (auto iter = mLinksToUpdate.Iter(); !iter.Done(); iter.Next()) {
+    Link* link = iter.Get();
+    Element* element = link->GetElement();
+    if (element->OwnerDoc() == this) {
+      link->ClearHasPendingLinkUpdate();
+      if (element->IsInComposedDoc()) {
+        element->UpdateLinkState(link->LinkState());
+      }
+    }
   }
   mLinksToUpdate.Clear();
   mHasLinksToUpdate = false;
 }
 
 already_AddRefed<nsIDocument>
 nsIDocument::CreateStaticClone(nsIDocShell* aCloneContainer)
 {
--- a/dom/base/nsIDocument.h
+++ b/dom/base/nsIDocument.h
@@ -30,16 +30,17 @@
 #include "Units.h"
 #include "nsContentListDeclarations.h"
 #include "nsExpirationTracker.h"
 #include "nsClassHashtable.h"
 #include "prclist.h"
 #include "mozilla/CORSMode.h"
 #include "mozilla/dom/DispatcherTrait.h"
 #include "mozilla/LinkedList.h"
+#include "mozilla/SegmentedVector.h"
 #include "mozilla/StyleBackendType.h"
 #include "mozilla/StyleSheet.h"
 #include "mozilla/TimeStamp.h"
 #include "mozilla/UniquePtr.h"
 #include <bitset>                        // for member
 
 #ifdef MOZILLA_INTERNAL_API
 #include "mozilla/dom/DocumentBinding.h"
@@ -2457,24 +2458,22 @@ public:
 
   virtual nsresult SetNavigationTiming(nsDOMNavigationTiming* aTiming) = 0;
 
   virtual Element* FindImageMap(const nsAString& aNormalizedMapName) = 0;
 
   // Add aLink to the set of links that need their status resolved.
   void RegisterPendingLinkUpdate(mozilla::dom::Link* aLink);
 
-  // Remove aLink from the set of links that need their status resolved.
-  // This function must be called when links are removed from the document.
-  void UnregisterPendingLinkUpdate(mozilla::dom::Link* aElement);
-
   // Update state on links in mLinksToUpdate.  This function must
   // be called prior to selector matching.
   void FlushPendingLinkUpdates();
 
+  void FlushPendingLinkUpdatesFromRunnable();
+
 #define DEPRECATED_OPERATION(_op) e##_op,
   enum DeprecatedOperations {
 #include "nsDeprecatedOperationList.h"
     eDeprecatedOperationCount
   };
 #undef DEPRECATED_OPERATION
   bool HasWarnedAbout(DeprecatedOperations aOperation) const;
   void WarnOnceAbout(DeprecatedOperations aOperation,
@@ -3038,20 +3037,23 @@ protected:
 
   // The set of all object, embed, applet, video/audio elements or
   // nsIObjectLoadingContent or nsIDocumentActivity for which this is the
   // owner document. (They might not be in the document.)
   // These are non-owning pointers, the elements are responsible for removing
   // themselves when they go away.
   nsAutoPtr<nsTHashtable<nsPtrHashKey<nsISupports> > > mActivityObservers;
 
-  // The set of all links that need their status resolved.  Links must add themselves
-  // to this set by calling RegisterPendingLinkUpdate when added to a document and must
-  // remove themselves by calling UnregisterPendingLinkUpdate when removed from a document.
-  nsTHashtable<nsPtrHashKey<mozilla::dom::Link> > mLinksToUpdate;
+  // The array of all links that need their status resolved.  Links must add themselves
+  // to this set by calling RegisterPendingLinkUpdate when added to a document.
+  static const size_t kSegmentSize = 128;
+  mozilla::SegmentedVector<nsCOMPtr<mozilla::dom::Link>,
+                           kSegmentSize,
+                           InfallibleAllocPolicy>
+    mLinksToUpdate;
 
   // SMIL Animation Controller, lazily-initialized in GetAnimationController
   RefPtr<nsSMILAnimationController> mAnimationController;
 
   // Table of element properties for this document.
   nsPropertyTable mPropertyTable;
   nsTArray<nsAutoPtr<nsPropertyTable> > mExtraPropertyTables;
 
@@ -3134,16 +3136,19 @@ protected:
 
   // True is this document is synthetic : stand alone image, video, audio
   // file, etc.
   bool mIsSyntheticDocument : 1;
 
   // True if this document has links whose state needs updating
   bool mHasLinksToUpdate : 1;
 
+  // True is there is a pending runnable which will call FlushPendingLinkUpdates().
+  bool mHasLinksToUpdateRunnable : 1;
+
   // True if a DOMMutationObserver is perhaps attached to a node in the document.
   bool mMayHaveDOMMutationObservers : 1;
 
   // True if an nsIAnimationObserver is perhaps attached to a node in the document.
   bool mMayHaveAnimationObservers : 1;
 
   // True if a document has loaded Mixed Active Script (see nsMixedContentBlocker.cpp)
   bool mHasMixedActiveContentLoaded : 1;
--- a/dom/html/HTMLAnchorElement.cpp
+++ b/dom/html/HTMLAnchorElement.cpp
@@ -167,23 +167,16 @@ HTMLAnchorElement::UnbindFromTree(bool a
   // mCachedURI based on data that is invalid - due to a call to GetHostname.
   CancelDNSPrefetch(HTML_ANCHOR_DNS_PREFETCH_DEFERRED,
                     HTML_ANCHOR_DNS_PREFETCH_REQUESTED);
 
   // If this link is ever reinserted into a document, it might
   // be under a different xml:base, so forget the cached state now.
   Link::ResetLinkState(false, Link::ElementHasHref());
 
-  // Note, we need to use OwnerDoc() here, since GetComposedDoc() might
-  // return null.
-  nsIDocument* doc = OwnerDoc();
-  if (doc) {
-    doc->UnregisterPendingLinkUpdate(this);
-  }
-
   nsGenericHTMLElement::UnbindFromTree(aDeep, aNullParent);
 }
 
 static bool
 IsNodeInEditableRegion(nsINode* aNode)
 {
   while (aNode) {
     if (aNode->IsEditable()) {
--- a/dom/html/HTMLAnchorElement.h
+++ b/dom/html/HTMLAnchorElement.h
@@ -223,16 +223,22 @@ public:
   {
     SetHTMLAttr(nsGkAtoms::shape, aValue, rv);
   }
   void Stringify(nsAString& aResult)
   {
     GetHref(aResult);
   }
 
+  virtual void NodeInfoChanged(nsIDocument* aOldDoc) final override
+  {
+    ClearHasPendingLinkUpdate();
+    nsGenericHTMLElement::NodeInfoChanged(aOldDoc);
+  }
+
   static DOMTokenListSupportedToken sSupportedRelValues[];
 
 protected:
   virtual ~HTMLAnchorElement();
 
   virtual JSObject* WrapNode(JSContext *aCx, JS::Handle<JSObject*> aGivenProto) override;
   RefPtr<nsDOMTokenList > mRelList;
 };
--- a/dom/html/HTMLAreaElement.cpp
+++ b/dom/html/HTMLAreaElement.cpp
@@ -137,23 +137,16 @@ HTMLAreaElement::BindToTree(nsIDocument*
 
 void
 HTMLAreaElement::UnbindFromTree(bool aDeep, bool aNullParent)
 {
   // If this link is ever reinserted into a document, it might
   // be under a different xml:base, so forget the cached state now.
   Link::ResetLinkState(false, Link::ElementHasHref());
 
-  // Note, we need to use OwnerDoc() here, since GetComposedDoc() might
-  // return null.
-  nsIDocument* doc = OwnerDoc();
-  if (doc) {
-    doc->UnregisterPendingLinkUpdate(this);
-  }
-
   nsGenericHTMLElement::UnbindFromTree(aDeep, aNullParent);
 }
 
 nsresult
 HTMLAreaElement::SetAttr(int32_t aNameSpaceID, nsIAtom* aName,
                          nsIAtom* aPrefix, const nsAString& aValue,
                          bool aNotify)
 {
--- a/dom/html/HTMLAreaElement.h
+++ b/dom/html/HTMLAreaElement.h
@@ -176,16 +176,22 @@ public:
     SetHTMLBoolAttr(nsGkAtoms::nohref, aValue, aError);
   }
 
   void Stringify(nsAString& aResult)
   {
     GetHref(aResult);
   }
 
+  virtual void NodeInfoChanged(nsIDocument* aOldDoc) final override
+  {
+    ClearHasPendingLinkUpdate();
+    nsGenericHTMLElement::NodeInfoChanged(aOldDoc);
+  }
+
 protected:
   virtual ~HTMLAreaElement();
 
   virtual JSObject* WrapNode(JSContext* aCx, JS::Handle<JSObject*> aGivenProto) override;
 
   RefPtr<nsDOMTokenList > mRelList;
 };
 
--- a/dom/html/HTMLLinkElement.cpp
+++ b/dom/html/HTMLLinkElement.cpp
@@ -213,18 +213,16 @@ HTMLLinkElement::UnbindFromTree(bool aDe
   // from the parser.
   nsCOMPtr<nsIDocument> oldDoc = GetUncomposedDoc();
 
   // Check for a ShadowRoot because link elements are inert in a
   // ShadowRoot.
   ShadowRoot* oldShadowRoot = GetBindingParent() ?
     GetBindingParent()->GetShadowRoot() : nullptr;
 
-  OwnerDoc()->UnregisterPendingLinkUpdate(this);
-
   CreateAndDispatchEvent(oldDoc, NS_LITERAL_STRING("DOMLinkRemoved"));
   nsGenericHTMLElement::UnbindFromTree(aDeep, aNullParent);
 
   UpdateStyleSheetInternal(oldDoc, oldShadowRoot);
   UpdateImport();
 }
 
 bool
--- a/dom/html/HTMLLinkElement.h
+++ b/dom/html/HTMLLinkElement.h
@@ -166,16 +166,23 @@ public:
 
   already_AddRefed<nsIDocument> GetImport();
   already_AddRefed<ImportLoader> GetImportLoader()
   {
     return RefPtr<ImportLoader>(mImportLoader).forget();
   }
 
   virtual CORSMode GetCORSMode() const override;
+
+  virtual void NodeInfoChanged(nsIDocument* aOldDoc) final override
+  {
+    ClearHasPendingLinkUpdate();
+    nsGenericHTMLElement::NodeInfoChanged(aOldDoc);
+  }
+
 protected:
   virtual ~HTMLLinkElement();
 
   // nsStyleLinkElement
   virtual already_AddRefed<nsIURI> GetStyleSheetURL(bool* aIsInline) override;
   virtual void GetStyleSheetInfo(nsAString& aTitle,
                                  nsAString& aType,
                                  nsAString& aMedia,
--- a/dom/mathml/nsMathMLElement.cpp
+++ b/dom/mathml/nsMathMLElement.cpp
@@ -131,21 +131,16 @@ nsMathMLElement::BindToTree(nsIDocument*
 }
 
 void
 nsMathMLElement::UnbindFromTree(bool aDeep, bool aNullParent)
 {
   // If this link is ever reinserted into a document, it might
   // be under a different xml:base, so forget the cached state now.
   Link::ResetLinkState(false, Link::ElementHasHref());
-  
-  nsIDocument* doc = GetUncomposedDoc();
-  if (doc) {
-    doc->UnregisterPendingLinkUpdate(this);
-  }
 
   nsMathMLElementBase::UnbindFromTree(aDeep, aNullParent);
 }
 
 bool
 nsMathMLElement::ParseAttribute(int32_t aNamespaceID,
                                 nsIAtom* aAttribute,
                                 const nsAString& aValue,
--- a/dom/mathml/nsMathMLElement.h
+++ b/dom/mathml/nsMathMLElement.h
@@ -101,16 +101,22 @@ public:
   virtual nsresult SetAttr(int32_t aNameSpaceID, nsIAtom* aName,
                            nsIAtom* aPrefix, const nsAString& aValue,
                            bool aNotify) override;
   virtual nsresult UnsetAttr(int32_t aNameSpaceID, nsIAtom* aAttribute,
                              bool aNotify) override;
 
   virtual nsIDOMNode* AsDOMNode() override { return this; }
 
+  virtual void NodeInfoChanged(nsIDocument* aOldDoc) override
+  {
+    ClearHasPendingLinkUpdate();
+    nsMathMLElementBase::NodeInfoChanged(aOldDoc);
+  }
+
 protected:
   virtual ~nsMathMLElement() {}
 
   virtual JSObject* WrapNode(JSContext *aCx, JS::Handle<JSObject*> aGivenProto) override;
 
 private:
   bool mIncrementScriptLevel;
 };
--- a/dom/svg/SVGAElement.cpp
+++ b/dom/svg/SVGAElement.cpp
@@ -146,23 +146,16 @@ SVGAElement::BindToTree(nsIDocument *aDo
 
 void
 SVGAElement::UnbindFromTree(bool aDeep, bool aNullParent)
 {
   // If this link is ever reinserted into a document, it might
   // be under a different xml:base, so forget the cached state now.
   Link::ResetLinkState(false, Link::ElementHasHref());
 
-  // Note, we need to use OwnerDoc() here since GetComposedDoc() may
-  // return null already at this point.
-  nsIDocument* doc = OwnerDoc();
-  if (doc) {
-    doc->UnregisterPendingLinkUpdate(this);
-  }
-
   SVGAElementBase::UnbindFromTree(aDeep, aNullParent);
 }
 
 already_AddRefed<nsIURI>
 SVGAElement::GetHrefURI() const
 {
   nsCOMPtr<nsIURI> hrefURI;
   return IsLink(getter_AddRefs(hrefURI)) ? hrefURI.forget() : nullptr;
--- a/dom/svg/SVGAElement.h
+++ b/dom/svg/SVGAElement.h
@@ -68,16 +68,22 @@ public:
                              bool aNotify) override;
 
   // WebIDL
   already_AddRefed<SVGAnimatedString> Href();
   already_AddRefed<SVGAnimatedString> Target();
   void GetDownload(nsAString & aDownload);
   void SetDownload(const nsAString & aDownload, ErrorResult& rv);
 
+  virtual void NodeInfoChanged(nsIDocument* aOldDoc) final override
+  {
+    ClearHasPendingLinkUpdate();
+    SVGAElementBase::NodeInfoChanged(aOldDoc);
+  }
+
 protected:
   virtual ~SVGAElement();
 
   virtual StringAttributesInfo GetStringInfo() override;
 
   enum { HREF, XLINK_HREF, TARGET };
   nsSVGString mStringAttributes[3];
   static StringInfo sStringInfo[3];
--- a/dom/svg/nsSVGElement.h
+++ b/dom/svg/nsSVGElement.h
@@ -113,17 +113,17 @@ public:
                                               int32_t aModType) const override;
 
   virtual bool IsNodeOfType(uint32_t aFlags) const override;
 
   /**
    * We override the default to unschedule computation of Servo declaration blocks
    * when adopted across documents.
    */
-  virtual void NodeInfoChanged(nsIDocument* aOldDoc) final;
+  virtual void NodeInfoChanged(nsIDocument* aOldDoc) override;
 
   NS_IMETHOD WalkContentStyleRules(nsRuleWalker* aRuleWalker) override;
   void WalkAnimatedContentStyleRules(nsRuleWalker* aRuleWalker);
 
   NS_IMETHOD_(bool) IsAttributeMapped(const nsIAtom* aAttribute) const override;
 
   static const MappedAttributeEntry sFillStrokeMap[];
   static const MappedAttributeEntry sGraphicsMap[];
--- a/toolkit/components/places/tests/gtest/mock_Link.h
+++ b/toolkit/components/places/tests/gtest/mock_Link.h
@@ -42,16 +42,18 @@ public:
     mDeathGrip = nullptr;
   }
 
   virtual size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const override
   {
     return 0;   // the value shouldn't matter
   }
 
+  virtual void NodeInfoChanged(nsIDocument* aOldDoc) final override {}
+
 protected:
   ~mock_Link() {
     // Run the next test if we are supposed to.
     if (mRunNextTest) {
       run_next_test();
     }
   }