Mounir Lamouri (:mounir) Reporter
	Description • 14 years ago

Kind of a follow-up from bug 564432.
We need to be sure it's not used too.

	Mounir Lamouri (:mounir) Reporter
	Comment 2 • 14 years ago

More explanation about the goal of this bug, quoting jst's comment in bug 661064:
Since bug 564432 got fixed we now carry a duplication of the storage for the children in the DOM. This extra storage costs memory, and more importantly, it costs time and code complexity to maintain both ways of storing child nodes.

The storage model we want long term is what was implemented in bug 564432 (first child and next/previous sibling), so the array of children is not necessary any more. But we do still have consumers of the old storage, and we need to find those and convert the remaining ones to not rely on the index of the child etc or fast access to the n:th child etc. This bug is about removing the remaining code that depends on the array storage, and also removing the array storage.

	Andrew Overholt [:overholt]
	Comment 3 • 9 years ago

Elsewhere, Olli said: "Relevant discussion also in bug 533892 and Bug 513169".

	James Andreou
	Comment 5 • 8 years ago

There is more work to be done before this patch is ready.

mChildCount can be integrated into mNextSibling on the last child to save memory on nsINode.

Similarly mNodeIndexCache can be reworked a bit to save memory by removing the bool isValid and moving into the slots used by ChildNodes()

Currently nsAttrAndChildArray children code is dead with this patch but not deleted.

There are many optimizations that can be made to calls of IndexOf that is now much slower, such as adding a capped static cache and refactoring code to not use IndexOf(child);

Also parts 1/2/3 are dependent on one another.

	(no longer active)
	Comment 8 • 8 years ago

Comment on attachment 8780689 [details] [diff] [review]
P2.patch

Sorry, I reviewed this in Splinter and for some reason it is refusing to let me upload my review comments, so I'm copy and pasting them here, ruining all formatting.  I'm formatting this manually in the hopes of making the comments more useful.


dom/base/StructuredCloneHolder.cpp
----------------------------------
#include "mozilla/dom/SubtleCryptoBinding.h"
#include "mozilla/dom/ToJSValue.h"
#include "mozilla/dom/URLSearchParams.h"
#include "mozilla/dom/URLSearchParamsBinding.h"
	
Why is this needed?  Looks like an unintentional change?


dom/base/nsDOMMutationObserver.cpp
----------------------------------
    if (aPreviousSibling) {
      m->mNextSibling = aPreviousSibling->GetNextSibling();
    } else {
      m->mNextSibling = nullptr;
    }
	
This seems to be wrong, since mNextSibling is supposed to return the next sibling of the node that has been removed, and in the case where aPreviousSibling is null, you'll set mNextSibling to null as well.
 
If this doesn't break any existing tests on the try server, can you please add a test for this case where you remove an element's first child and verify that the nextSibling on the resulting MutationRecord is the new first child?  Please make sure the test fails with your existing code.


dom/events/IMEContentObserver.cpp
---------------------------------
 
  uint32_t offset = 0;
  nsresult rv = NS_OK;
  nsINode* container = NODE_FROM(aContainer, aDocument);
	
containerNode is the same thing here, you don't need to define container here again.


dom/xbl/nsBindingManager.cpp
----------------------------
                                  int32_t     aNewIndexInContainer)
{
  if (aNewIndexInContainer == -1) {
    return;
  }
	
Hmm.  Is there any reason why this code does this check in the case of ContentInserted and ContentAppended?


editor/libeditor/HTMLEditor.cpp
-------------------------------
 
  nsCOMPtr<nsIHTMLEditor> kungFuDeathGrip(this);
 
  nsINode* container = NODE_FROM(aContainer, aDocument);
	
Now that you have this line, a few lines below there is this code: |else if (!mAction && (aContainer ? aContainer->IsEditable() : aDocument->IsEditable())) {|.  You can rewrite that too in order to use the container variable.

    // Update spellcheck for only the newly-inserted node (bug 743819)
    if (mInlineSpellChecker) {
      RefPtr<nsRange> range = new nsRange(aChild);
      int32_t endIndex = index + 1;
	
Given that we *only* need the index in this branch, computing it in all cases is wasteful. Please move the definition of |index| to before this line.

layout/base/nsPresShell.cpp
---------------------------
  if (aPreviousSibling) {
    oldNextSibling = aPreviousSibling->GetNextSibling();
  } else if (aContainer) {
    oldNextSibling = aContainer->GetFirstChild();
  }
	
What if you have a document like this:
 
<html><body>...</body></html>
<!-- comment -->
 
And you remove the <html> element?
 
I think you should use a NODE_FROM here similar to other similar call sites.
 
(FWIW I tried following along what happens to oldNextSibling after this point, and I couldn't come up with a case where this problem is going to be noticeable to a web page, but I could be wrong.)

	(no longer active)
	Comment 9 • 8 years ago

Comment on attachment 8780690 [details] [diff] [review]
P3.patch

Review of attachment 8780690 [details] [diff] [review]:
-----------------------------------------------------------------

(testing, please ignore me)

	Olli Pettay [:smaug][bugs@pettay.fi] Assignee
	Comment 10 • 8 years ago

Comment on attachment 8780688 [details] [diff] [review]
Part 1 - Core Changes P1.patch

>-FragmentOrElement::InsertChildAt(nsIContent* aKid,
>-                                uint32_t aIndex,
>-                                bool aNotify)
>+FragmentOrElement::InsertChildAt(nsIContent* aKid, uint32_t aIndex, bool aNotify)
> {
>-  NS_PRECONDITION(aKid, "null ptr");
>+  MOZ_ASSERT(aKid, "Trying to insert a null child.");
> 
>-  return doInsertChildAt(aKid, aIndex, aNotify, mAttrsAndChildren);
>+  nsIContent* childToInsertBefore = doChildAt(aIndex);
>+  return doInsertChild(aKid, childToInsertBefore, aNotify);

Ok, so InsertChildAt...

> void
> FragmentOrElement::RemoveChildAt(uint32_t aIndex, bool aNotify)
> {
>-  nsCOMPtr<nsIContent> oldKid = mAttrsAndChildren.GetSafeChildAt(aIndex);
>-  NS_ASSERTION(oldKid == GetChildAt(aIndex), "Unexpected child in RemoveChildAt");
>+  nsCOMPtr<nsIContent> oldKid = doChildAt(aIndex);
>+  MOZ_ASSERT(oldKid == GetChildAt(aIndex), "Unexpected child in RemoveChildAt");
> 
>   if (oldKid) {
>-    doRemoveChildAt(aIndex, aNotify, oldKid, mAttrsAndChildren);
>+    doRemoveChild(oldKid, aNotify);
>   }
> }
And RemoveChildAt become O(n) methods, when they used to be O(1).
Does this or the followup patches remove all or most of their use?



> 
>-  // Unlink child content (and unbind our subtree).
>-  if (tmp->UnoptimizableCCNode() || !nsCCUncollectableMarker::sGeneration) {
>-    uint32_t childCount = tmp->mAttrsAndChildren.ChildCount();
>-    if (childCount) {
>-      // Don't allow script to run while we're unbinding everything.
>-      nsAutoScriptBlocker scriptBlocker;
>-      while (childCount-- > 0) {
>-        // Hold a strong ref to the node when we remove it, because we may be
>-        // the last reference to it.  We need to call TakeChildAt() and
>-        // update mFirstChild before calling UnbindFromTree, since this last
>-        // can notify various observers and they should really see consistent
>-        // tree state.
>-        nsCOMPtr<nsIContent> child = tmp->mAttrsAndChildren.TakeChildAt(childCount);
>-        if (childCount == 0) {
>-          tmp->mFirstChild = nullptr;
>-        }
>-        child->UnbindFromTree();
>-      }
>-    }
>-  } else if (!tmp->GetParent() && tmp->mAttrsAndChildren.ChildCount()) {
>+  if (!tmp->GetParent() && tmp->GetChildCount()) {
Why you remove the if() ? We need to unbind those elements (anonymous content and such) explicitly here and not rely on ContentUnbinder -
or at least this would be rather major change and should be done separately.

>+++ b/dom/base/NodeIndexCache.cpp
This file uses odd indentation. Should be two spaces.


>+nsIContent*
>+NodeIndexCache::IterateToChildFrom(uint32_t aIndex,
>+								   nsIContent* aIterChild,
>+								   uint32_t aStartIndex)
You have some tabs used for indentation. Only use spaces.


>+{
>+	uint32_t iterDirection = (aIndex >= aStartIndex) ? 1 : -1;
Why iterDirection is 


>+
>+	while (aIndex != aStartIndex && aIterChild) {
>+		if (iterDirection == 1) {
>+			aIterChild = aIterChild->GetNextSibling();
>+		} else {
>+			aIterChild = aIterChild->GetPreviousSibling();
>+		}
>+		aStartIndex += iterDirection;
>+	}
>+
>+	MOZ_ASSERT(aIterChild, "Something went wrong.");
>+	mCachedIndex = aIndex;
Hmm, I don't quite understand what this method does. It updates cached index but not mCachedChild.



>+NodeIndexCache::IterateToChild(uint32_t aIndex, const nsINode* aOwningNode)
>+{
>+	uint32_t lastIndex = aOwningNode->GetChildCount() - 1;
>+	MOZ_ASSERT(aIndex <= lastIndex);
>+
>+	uint32_t startFromFirst = aIndex;
I don't understand the naming. startFromFirst? Would startIndex work here?

>+	uint32_t startFromCache = mozilla::Abs(int32_t(mCachedIndex - aIndex));
>+	uint32_t startFromLast = mozilla::Abs(int32_t(lastIndex - aIndex));
>+
>+	uint32_t minDifference = std::min(startFromFirst,
>+								      std::min(startFromCache, startFromLast));
What is minDifference about?

>+
>+	if (minDifference == startFromLast) {
>+		return IterateToChildFrom(aIndex, aOwningNode->GetLastChild(), lastIndex);
>+	} else if (minDifference == startFromCache) {
>+		return IterateToChildFrom(aIndex, mCachedChild, mCachedIndex);
>+	} else {
>+		return IterateToChildFrom(aIndex, aOwningNode->GetFirstChild(), 0);
>+	}
>+}
This method really needs some comments.






>+++ b/dom/base/NodeIndexCache.h
This file uses odd indentation. Should be two spaces.






>+#ifdef MOZILLA_INTERNAL_API
>+  nsINode::nsINode(already_AddRefed<mozilla::dom::NodeInfo>& aNodeInfo)
>+  : mNodeInfo(aNodeInfo)
>+  , mParent(nullptr)
>+  , mBoolFlags(0)
>+  , mChildCount(0)
>+  , mPreviousSibling(nullptr)
>+  , mSubtreeRoot(this)
>+  , mSlots(nullptr)
>+#ifdef MOZ_STYLO
>+  , mServoNodeData(nullptr)
>+#endif
>+  {
>+    mNodeIndexCache = mozilla::MakeUnique<NodeIndexCache>();
Why is mNodeIndexCache UniquePtr, when it is always allocated anyhow?
It could be just NodeIndexCache mNodeIndexCache; in the class definition.


>@@ -563,16 +581,12 @@ nsINode::RemoveChild(nsINode& aOldChild, ErrorResult& aError)
> 
>   if (aOldChild.GetParentNode() == this) {
>     nsContentUtils::MaybeFireNodeRemoved(&aOldChild, this, OwnerDoc());
>-  }
>-
>-  int32_t index = IndexOf(&aOldChild);
>-  if (index == -1) {
>-    // aOldChild isn't one of our children.
>+  } else if (IndexOf(&aOldChild) == -1) {
>     aError.Throw(NS_ERROR_DOM_NOT_FOUND_ERR);
>     return nullptr;
>   }
> 
>-  RemoveChildAt(index, true);
>+  doRemoveChild(static_cast<nsIContent*> (&aOldChild), true);
Use ->AsContent() 


>+  if (aChildToInsertBefore == mFirstChild) {
>     mFirstChild = aKid;
>   }
> 
>+  mChildCount ++;
extra space before ++

>+nsINode::GetPreviousSibling() const
>+{
>+  // Do not expose circular linked list
>+  if (mPreviousSibling && !mPreviousSibling->mNextSibling) {
>+    return nullptr;
>+  }
>+  return mPreviousSibling;
>+}
So given that mPreviousSibling has two meanings now, I think it should be somehow renamed.
Perhaps mPrevOrLastSibling or some such. Otherwise it will be misused.



>@@ -2095,15 +2093,19 @@ private:
>   // Boolean flags.
>   uint32_t mBoolFlags;
> 
>+  // Number of children in the list
>+  uint32_t mChildCount;
>+
>+  // Cache used to make IndexOf fast
>+  mozilla::UniquePtr<mozilla::dom::NodeIndexCache> mNodeIndexCache;

Hmm, so you add uint32_t and NodeIndexCache to nsINode. How much is the sizeof nsINode increased with these changes on 32bit opt builds, and what about 64bit opt builds,
in case an Element doesn't have any children nor attributes.

You do save by not storing children in nsAttrAndChildArray, so when there are children or attributes, this is ok.

However, textnodes are common, often with just \n or so, and would be annoying to increase too much their size.
So, please provide some sizeof numbers 


(We could possibly have mChildCount and mNodeIndexCache in some struct which is allocated from heap and then member variable pointing to that, defaulting to null.
 Effectively emulating what nsAttrAndChildArray does when there are no children nor attributes.)


Looking pretty good, but some fixes and explanations needed.

	(no longer active)
	Comment 11 • 8 years ago

Comment on attachment 8780690 [details] [diff] [review]
P3.patch

Review of attachment 8780690 [details] [diff] [review]:
-----------------------------------------------------------------

I think all of the issues below are relatively minor, but since there's a number of them, I'd prefer to look at an updated version of the patch.

::: dom/base/FragmentOrElement.cpp
@@ -1156,3 @@
>  {
> -  nsCOMPtr<nsIContent> oldKid = doChildAt(aIndex);
> -  MOZ_ASSERT(oldKid == GetChildAt(aIndex), "Unexpected child in RemoveChildAt");

I'm assuming that you're going back to having this code in another part of your patch series.

::: dom/base/nsContentUtils.cpp
@@ +4710,4 @@
>          removeIndex = 1;
>        }
>        else {
> +        aContent->RemoveChildAt(aContent->GetChildAt(removeIndex), true);

I think here it's much better to rewrite the outer loop to iterate over the linked list directly rather than using indices.

@@ +4725,1 @@
>      }

It would be better to rewrite this as |while (aContent->GetFirstChild()) aContent->RemoveChildAt(aContent->GetFirstChild(), true)|.

::: dom/base/nsDocument.cpp
@@ -4042,2 @@
>  {
> -  nsCOMPtr<nsIContent> oldKid = GetChildAt(aIndex);

Again, I'm assuming this is coming back in another part.

@@ +7789,4 @@
>        // Remove from parent.
>        nsCOMPtr<nsINode> parent = adoptedNode->GetParentNode();
>        if (parent) {
> +        parent->RemoveChildAt(static_cast<nsIContent*>(adoptedNode), true);

Instead of the case, please do: adoptedNode->AsElement().

::: dom/base/nsGenericDOMDataNode.cpp
@@ +899,4 @@
>      if (aCloneAfterOriginal) {
>        ++insertionIndex;
>      }
> +    parent->InsertChild(newContent, parent->GetChildAt(insertionIndex), true);

This code is doing an IndexOf() and then using that index to insert a child.  Please rewrite it to not use indices.

::: dom/base/nsINode.cpp
@@ +2026,4 @@
>  nsINode::doRemoveChild(nsIContent* aKid, bool aNotify)
>  {
>    MOZ_ASSERT(aKid && aKid->GetParentNode() == this, "Bogus aKid");
> +  MOZ_ASSERT(IndexOf(aKid) >= 0, "Trying to remove child that has no index?");

Nit: "... that's not ours"

I think that would make the assertion comment more readable.

@@ +2346,4 @@
>        mozAutoDocUpdate batch(newContent->GetComposedDoc(),
>                               UPDATE_CONTENT_MODEL, true);
>        nsAutoMutationBatch mb(oldParent, true, true);
> +      oldParent->RemoveChildAt(oldParent->GetChildAt(removeIndex), true);

Is there any reason why you're continuing to use indices in this function?  I think we should be able to rewrite ReplaceOrInsertBefore to avoid using indices...

::: dom/html/nsGenericHTMLElement.cpp
@@ +3167,4 @@
>  
>    mb.Init(this, true, false);
>    for (uint32_t i = 0; i < childCount; ++i) {
> +    RemoveChildAt(GetChildAt(0), true);

Please rewrite this loop on top of GetFirstChild() also.

::: dom/svg/SVGUseElement.cpp
@@ +311,5 @@
>      }
>  
>      // move the children over
> +    nsCOMPtr<nsIContent> child = newcontent->GetFirstChild();
> +    while (child) {

Nit: You can make this a bit shorter if you do:

  |while (nsCOMPtr<nsIContent> child = ...) {...}|

::: dom/xul/nsXULElement.cpp
@@ -912,2 @@
>  {
> -    nsCOMPtr<nsIContent> oldKid = GetChildAt(aIndex);

Same as the other two cases.

::: layout/forms/nsTextControlFrame.cpp
@@ +1329,4 @@
>    }
>  
>    if (aBeforeEditorInit && value.IsEmpty()) {
> +    rootNode->RemoveChildAt(rootNode->GetChildAt(0), true);

Nit: GetFirstChild

::: parser/html/nsHtml5TreeOperation.cpp
@@ +260,4 @@
>    bool didAppend = false;
>    while (aNode->HasChildren()) {
>      nsCOMPtr<nsIContent> child = aNode->GetFirstChild();
> +    aNode->RemoveChildAt(aNode->GetChildAt(0), true);

Nit: GetFirstChild

	Cătălin Badea (:catalinb)
	Comment 15 • 8 years ago

Stealing this bug (with permission from :overholt).

	Cătălin Badea (:catalinb)
	Comment 16 • 8 years ago

Something interesting to note:
While testing on https://github.com/jamesandreou/Do-You-Even-DOM I noticed that the cleanup function that's being used in between tests removeAllChildren is a lot slower on Firefox than it is on Chrome or Safari.
nsAttrAndChildArray::RemoveChildAt will do a memmove to shrink the vector every time we remove a element.

For 100000 elements, Firefox will take ~1300 ms, while Chrome takes around 40ms and Safari 20ms.

	Olli Pettay [:smaug][bugs@pettay.fi] Assignee
	Comment 17 • 8 years ago

Yes, that is what removing child array is largely about, to get rid of memmoves around the array usage.
The move happens particularly often when inserting new nodes before any existing node, and with removeChild when used the way the testcase does. If one would remove lastChild, it should be ok in the current setup.

	Cătălin Badea (:catalinb)
	Comment 19 • 8 years ago

Original patch author: James Andreou jandreou25@gmail.com

	Boris Zbarsky [:bzbarsky]
	Comment 20 • 8 years ago

What sort of performance testing has been done on the nsRange::ContentInserted/Removed bits?  Of the IndexOf() calls in this patch, those are the most obviously worrisome....

I strongly recommend making the nsRange changes in a separate commit (ideally on a separate day, for easy bisection) so that performance regressions will be easier to hunt down.

	(no longer active)
	Comment 21 • 8 years ago

Thanks a lot for working on this, Catalin!

But I'm afraid I'm not a good reviewer for this.  James was my intern and parts of this patch may have been heavily influenced by me, so I'd really prefer a fresh pair of eyes.  Peter, I think you could be a good reviewer for this.  Do you have cycles?

(In reply to Boris Zbarsky [:bz] (still a bit busy) (if a patch has no decent message, automatic r-) from comment #20)
> What sort of performance testing has been done on the
> nsRange::ContentInserted/Removed bits?  Of the IndexOf() calls in this
> patch, those are the most obviously worrisome....

The plan was to write some microbenchmarks and profile using them to see what the performance looks like, and if we need to improve...  I don't remember if we got to doing that before James' internship ended.  Have you measured that Catalin?

	(no longer active)
	Comment 22 • 8 years ago

No response from Peter.  But I really am the worst choice for the reviewer of these patches.  :-(

Andrew any chance you can roll the dice here?  These are core DOM tree changes and require pretty careful review by the usual suspects who are all very busy and all..  Thanks!

	Olli Pettay [:smaug][bugs@pettay.fi] Assignee
	Comment 23 • 8 years ago

Before reviewing (whoever does that) it would be good to know what kinds of microbenchmarks have been run, and if some cases, like the one mentioned in comment 20, are missing, better to write some.
Need to think about worst case scenarios and write testcases for those.

	Andrew Overholt [:overholt]
	Comment 24 • 8 years ago

Andrew, would you be able to take a look at these patches?

	Peter Van der Beken [:peterv]
	Comment 25 • 8 years ago

I can take a look, but I'd like to echo comment 20 and 23.

	Cătălin Badea (:catalinb)
	Comment 26 • 7 years ago

Original patch author: James Andreou jandreou25@gmail.com

	Cătălin Badea (:catalinb)
	Comment 27 • 7 years ago

I've written some tests that use document.createRange() to measure the impact of IndexOf in nsRange::ContentInserted and nsRange::ContentRemoved.

The last patch contains a small fix which saves from doing an unnecessary IndexOf(aPreviousSibling) (which iterates through all children) if aPreviousSibling is null.

Note:
nsINode::RemoveChild and nsINode::ReplaceOrInsertBefore already call IndexOf before dispatching the notifications.

The only case I found to be slower due to the changes in nsRange is when we alternate removing the first child and the last child. This is a bit unexpected. While, alternating back and front should yield the worst case for the caching mechanism we use in nsAttrAndChildArray::IndexOf - I expected the call at 
http://searchfox.org/mozilla-central/rev/484d2b7f51b7aed035147bbb4a565061659d9278/dom/base/nsINode.cpp#593 to cache the index and not see nsRange::ContentRemoved::IndexOf in the profiler.

Results: https://docs.google.com/spreadsheets/d/1wnmdn_er9ZRcooG0uvCUJIrTDYv3QlFlwgA1N-URzUk/edit?usp=sharing
benchmark: https://github.com/catalinb/Do-You-Even-DOM

	Peter Van der Beken [:peterv]
	Comment 28 • 7 years ago

(In reply to Cătălin Badea (:catalinb) from comment #27)
> The only case I found to be slower due to the changes in nsRange is when we
> alternate removing the first child and the last child. This is a bit
> unexpected. While, alternating back and front should yield the worst case
> for the caching mechanism we use in nsAttrAndChildArray::IndexOf - I
> expected the call at 
> http://searchfox.org/mozilla-central/rev/
> 484d2b7f51b7aed035147bbb4a565061659d9278/dom/base/nsINode.cpp#593 to cache
> the index and not see nsRange::ContentRemoved::IndexOf in the profiler.

But you're looking for the index of the previous sibling after the node has been removed, right? Could it be that you're hitting the case at http://searchfox.org/mozilla-central/rev/a14524a72de6f4ff738a5e784970f0730cea03d8/dom/base/nsAttrAndChildArray.cpp#237 ? We could try to set |cursor| to |count - 1| if |cursor == count|, not sure how much that'd help and if it'd make sense in general.

	Andrew Overholt [:overholt]
	Comment 29 • 7 years ago

This blocks a qf:p1 bug so it should be qf:p1 as well.

	Cătălin Badea (:catalinb)
	Comment 31 • 7 years ago

Comment on attachment 8903564 [details] [diff] [review]
Remove index argument from content removed/appended/inserted notifications.

I think this patch can be reviewed at this time.
The IMEContentObserver case is being handled in bug 1384915.

	Jean Gong :jgong
	Comment 33 • 7 years ago

This bug won't make it for 57; I am moving P2 for post 57 work.

	Peter Van der Beken [:peterv]
	Comment 34 • 7 years ago

Comment on attachment 8903564 [details] [diff] [review]
Remove index argument from content removed/appended/inserted notifications.

Review of attachment 8903564 [details] [diff] [review]:
-----------------------------------------------------------------

ContentInserted/ContentRemoved can have a null container when the node is inserted/removed from the document. Need to use aDocument in that case. We really should fix that API to take nsINode instead :-/.

::: dom/base/nsDOMMutationObserver.cpp
@@ +367,5 @@
>      if (m->mTarget) {
>        // Already handled case.
>        return;
>      }
> +    MOZ_ASSERT(aContainer);

Shouldn't this assert parent?

@@ +374,5 @@
>      m->mRemovedNodes = new nsSimpleContentList(parent);
>      m->mRemovedNodes->AppendElement(aChild);
>      m->mPreviousSibling = aPreviousSibling;
> +    m->mNextSibling = aPreviousSibling ?
> +      aPreviousSibling->GetNextSibling() : aContainer->GetFirstChild();

Shouldn't this use parent instead of aContainer?

::: dom/events/IMEContentObserver.cpp
@@ +1105,2 @@
>  {
> +  MOZ_ASSERT(aContainer);

NODE_FROM(aContainer, aDocument) instead of aContainer?

@@ +1124,5 @@
>    MaybeNotifyIMEOfAddedTextDuringDocumentChange();
>  
>    nsINode* containerNode = NODE_FROM(aContainer, aDocument);
>  
> +  MOZ_ASSERT(aContainer);

containerNode?

::: layout/base/PresShell.cpp
@@ +4484,5 @@
>    // Call this here so it only happens for real content mutations and
>    // not cases when the frame constructor calls its own methods to force
>    // frame reconstruction.
> +  nsIContent* oldNextSibling = nullptr;
> +  if (container->GetChildCount()) {

Why do we need to check this first? GetNextSibling()/GetFirstChild() will return null anyway for that case, no?

::: widget/cocoa/nsMenuBarX.mm
@@ +315,2 @@
>  {
> +  int32_t index = aContainer->IndexOf(aPreviousSibling) + 1;

NODE_FROM(aContainer, aDocument) instead of aContainer?

	Cătălin Badea (:catalinb)
	Comment 36 • 7 years ago

https://treeherder.mozilla.org/#/jobs?repo=try&revision=f6e88fad24100bf9729116b78b2479af52348a6e&selectedJob=134431168

	Pulsebot
	Comment 37 • 7 years ago

Pushed by catalin.badea392@gmail.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/4a8294c6b8e3
Remove index argument from content removed/appended/inserted notifications. r=peterv

	Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)
	Comment 38 • 7 years ago
bugherder

https://hg.mozilla.org/mozilla-central/rev/4a8294c6b8e3

	Naveed Ihsanullah [:naveed]
	Comment 39 • 7 years ago

Andrew can you please re-evaluate this bug in terms of [perf]? Also we may need a DOM rep at our triage mtgs. Thanks.

	Olli Pettay [:smaug][bugs@pettay.fi] Assignee
	Comment 40 • 7 years ago

FWIW, this is probably the biggest architectural perf issue we have in DOM.

	Andrew Overholt [:overholt]
	Comment 41 • 7 years ago

(In reply to Naveed Ihsanullah [:naveed] from comment #39)
> Andrew can you please re-evaluate this bug in terms of [perf]? Also we may
> need a DOM rep at our triage mtgs. Thanks.

This is Catalin's #1 priority.

	Cătălin Badea (:catalinb)
	Comment 43 • 7 years ago

Fixed some rebase errors.

	Olli Pettay [:smaug][bugs@pettay.fi] Assignee
	Comment 44 • 7 years ago

This really should be p1, per comment 40.

	Cătălin Badea (:catalinb)
	Comment 48 • 7 years ago

https://treeherder.mozilla.org/#/jobs?repo=try&revision=11cd82e894a57af05e4f7ed90152efd16fb4d821

Try looks good.

	Andrea Marchesini [:baku]
	Comment 49 • 7 years ago

Comment on attachment 8945481 [details] [diff] [review]
Remove nsAttrAndChildArray in nsInode.

Review of attachment 8945481 [details] [diff] [review]:
-----------------------------------------------------------------

::: dom/base/nsGenericDOMDataNode.cpp
@@ +717,5 @@
>    }
>  
>    nsCOMPtr<nsINode> parent = GetParentNode();
>    if (parent) {
> +    nsIContent* insertBefore = aCloneAfterOriginal ?  GetNextSibling() : this;

double space after "?"

::: dom/base/nsINode.cpp
@@ +1699,5 @@
> +{
> +  MOZ_ASSERT(aKid);
> +  //MOZ_ASSERT(!aKid->GetNextSibling());
> +  // Why can't I assert these?
> +  //MOZ_ASSERT(!aKid->GetPreviousSibling());

remove these comments.

@@ +1725,5 @@
> +  MOZ_ASSERT(aChildBefore);
> +
> +  // Why can't I assert these?
> +  //MOZ_ASSERT(!aKid->GetNextSibling());
> +  //MOZ_ASSERT(!aKid->GetPreviousSibling());

same here

@@ +1786,5 @@
> +  return mSlotsOrChildrenCount.ChildCount();
> +}
> +
> +nsIContent*
> +nsINode::GetChildAt_Deprecated(uint32_t aIndex) const

Maybe after this patch we can rename GetchildAt_Deprecated to ComputeChildAt()

::: dom/html/HTMLOptGroupElement.cpp
@@ +81,5 @@
>  {
> +  int32_t index = aChildToInsertBefore ?
> +    ComputeIndexOf(aChildToInsertBefore) : GetChildCount();
> +  SafeOptionListMutation safeMutation(GetSelect(), this, aKid, index, aNotify);
> +  nsresult rv = nsGenericHTMLElement::InsertChildBefore(aKid, aChildToInsertBefore, aNotify);

I have a patch to clean up this. I'll land after this patch.

::: dom/xul/XULDocument.cpp
@@ +2160,5 @@
>      } else if (aProtoPI->mTarget.EqualsLiteral("xul-overlay")) {
>          rv = InsertXULOverlayPI(aProtoPI, aParent, aIndex, node);
>      } else {
>          // No special processing, just add the PI to the document.
> +        rv = aParent->InsertChildBefore(node, aParent->GetChildAt_Deprecated(aIndex), false);

This is already gone.

	Cătălin Badea (:catalinb)
	Comment 51 • 7 years ago

Comment on attachment 8947094 [details] [diff] [review]
Remove nsAttrAndChildArray in nsInode.

Boris, could you please take a look at this?

This patch changes the storage for children from nsAttrAndChildArray to just a linked list stored in nsINode. This change will make operations like InsertBefore and RemoveChild a lot faster. The downside is that GetChildAt becomes more expensive (O(1) -> O(n)) and IndexOf won't have a cache anymore.

In the past couple of months, we removed a lot of the GetChildAt and IndexOf calls throughout the code base and we've reached a point where it might be feasible to land this.

Talos results look mostly good:
https://treeherder.mozilla.org/perf.html#/compare?originalProject=mozilla-central&newProject=try&newRevision=5ce99fc373ee1b7ee9b976b2b6eb497661ceee5d&framework=1&showOnlyImportant=1&selectedTimeRange=172800

:baku put together a list of the remaining call sites that need to be fixed and has pending patches for some of them:
https://docs.google.com/spreadsheets/d/1V7zso2voMFPy-MghE9h0ZnGjIcU-eMLiA_xfPYwV-3o/edit#gid=0

	Cătălin Badea (:catalinb)
	Comment 52 • 7 years ago

Note: I'll change the commit message to a summary of #comment 51.

	Boris Zbarsky [:bzbarsky]
	Comment 53 • 7 years ago

I don't trust Talos to catch performance regressions very much, unless they're pretty sweepingly cross-cutting.

The two main performance questions I have are:

1)  How do we handle childNodes[n] access now?
2)  Have we done any measurement with lots of live ranges (e.g. complicated selections
    a la spellcheck, or just manually creating a bunch of ranges).

	Boris Zbarsky [:bzbarsky]
	Comment 54 • 7 years ago

So looking at the patch, a bunch of this can be landed without the full removal, right?  For example the Element::UnbindFromTree changes.

We should get those landed, with individual reviews for them, because some of them may have non-obvious performance implications.  For example, the change to OwnedOnlyByTheDOMTree changes cycle collection CanSkip for a node from O(1) to O(N), which is probably not OK, but definitely needs review from someone familiar with cycle collection performance.

	Boris Zbarsky [:bzbarsky]
	Comment 55 • 7 years ago

Comment on attachment 8947094 [details] [diff] [review]
Remove nsAttrAndChildArray in nsInode.

r-; this needs to land in pieces.

	Boris Zbarsky [:bzbarsky]
	Comment 56 • 7 years ago

Oh, and the stylo bits need to keep doing inline stuff for the nextSibling walk, not FFI.  That part can't land until the conversion of mNextSibling to nsCOMPtr lands.  But _that_ can land in a separate changeset from the child array removal, even if they land in the same push.

	Cătălin Badea (:catalinb)
	Comment 57 • 7 years ago

(In reply to Boris Zbarsky [:bz] (no decent commit message means r-) from comment #53)
> I don't trust Talos to catch performance regressions very much, unless
> they're pretty sweepingly cross-cutting.
> 
> The two main performance questions I have are:
> 
> 1)  How do we handle childNodes[n] access now?
We have a separate array cache for childNodes which we create when you first access .childNodes.

> 2)  Have we done any measurement with lots of live ranges (e.g. complicated
> selections
>     a la spellcheck, or just manually creating a bunch of ranges).

Compared to other browsers our range implementation is really strong. Both safari and chrome perform poorly when there's a range receiving mutation notifications because they need to recompute indices for the boundaries. In firefox, we avoid doing that
by keeping the actual first/last node, as opposed to just a parent, index pair.

Tests: https://github.com/catalinb/Do-You-Even-DOM

Regarding the spellchecker, I didn't test that until now and it seems we do regress for input elements with a lot of text. One reason is nsContentSubIterator which performs some unnecessary ComputeIndex calls. Working on a fix.

	Cătălin Badea (:catalinb)
	Comment 58 • 7 years ago

(In reply to Boris Zbarsky [:bz] (no decent commit message means r-) from comment #54)
> So looking at the patch, a bunch of this can be landed without the full
> removal, right?  For example the Element::UnbindFromTree changes.
I'll try to split it as much as possible.

> We should get those landed, with individual reviews for them, because some
> of them may have non-obvious performance implications.  For example, the
> change to OwnedOnlyByTheDOMTree changes cycle collection CanSkip for a node
> from O(1) to O(N), which is probably not OK, but definitely needs review
> from someone familiar with cycle collection performance.

OwnedOnlyByTheDOMTree is still O(1), we still maintain a counter for GetChildCount().

	Andrew Overholt [:overholt]
	Comment 59 • 7 years ago

Given competing priorities and staffing, this is unlikely to be completed in 61, Jean.

	Cătălin Badea (:catalinb)
	Comment 60 • 7 years ago

This removes nsAttrAndChildArray usage from ::UnbindFromTree, ::DestroyContent
and ::SaveSubtreeState.

	Cătălin Badea (:catalinb)
	Comment 63 • 7 years ago

This patch touches the code responsible for unbinding elements from the
dom tree and couple of other places which rely on the children array.

	Cătălin Badea (:catalinb)
	Comment 66 • 7 years ago

Comment on attachment 8966589 [details] [diff] [review]
Remove InsertChildAt_Deprecated and RemoveChildAt_Deprecated.

Review of attachment 8966589 [details] [diff] [review]:
-----------------------------------------------------------------

The important part to review are the changes in nsINode.cpp. Eveything else should be straightforward.

	Cătălin Badea (:catalinb)
	Comment 67 • 7 years ago

Comment on attachment 8966588 [details] [diff] [review]
Remove some nsAttrAndChildArray usage.

Some changes that I could peel off from the rest. This can be landed right separately.

	Boris Zbarsky [:bzbarsky]
	Comment 68 • 7 years ago

Comment on attachment 8966589 [details] [diff] [review]
Remove InsertChildAt_Deprecated and RemoveChildAt_Deprecated.

>+++ b/dom/base/nsINode.cpp
>@@ -533,24 +533,25 @@ nsINode::RemoveChild(nsINode& aOldChild, ErrorResult& aError)
>-  int32_t index = ComputeIndexOf(&aOldChild);
>-  if (index == -1) {
...
>+  if (aOldChild.GetParentNode() != this) {

That's not an equivalent check.  In particular, if aOldChild is an anonymous kid of "this", then the old check would have errored out but the new check won't, we'll call RemoveChildNode(), potentially land in FragmentOrElement::RemoveChildNode, call doRemoveChildAt with uint32_t(-1) as first arg, fail some asserts at the beginning, and then end up writing to whatever memory is pointed to by whatever value is at that offset past the end of the array.

All of which is to say, we should probably check aOldChild.IsRootOfAnonymousSubtree() somewhere here.

On the other hand, the existing IsNodeOfType(eDATA_NODE) check can go away, since if it's false we will bail out on this "is this one of our kids?" check anyway.

>@@ -2027,59 +2028,53 @@ nsINode::ReplaceOrInsertBefore(bool aReplace, nsINode* aNewChild,
>+    nodeToInsertBefore = aRefChild ? aRefChild->AsContent() : nullptr;

I assume this is safe because in that case we checked aRefChild->GetParentNode() != this and only nodes that are nsIContent can have parents?  Might be worth documenting that.

>+      nsIContent* previous = aNewChild->GetPreviousSibling();
>+      nsIContent* next = aNewChild->GetNextSibling();

Please document why these can be weak refs (e.g. because we're under a scritblocker between when we grab them and when we take a strong ref to them in the automutationbatch?).

r=me with the above fixed.  Thank you for doing this in sanely reviewable pieces!

	Marion Daly [:mdaly]
	Comment 69 • 7 years ago

:baku can you take this over?

	Andrea Marchesini [:baku]
	Comment 70 • 7 years ago

This is the interdiff of patch Remove InsertChildAt_Deprecated and RemoveChildAt_Deprecated.

I see there are other patches with r=bz in the commit message, but I don't know  if you have actually reviewed them. Can you confirm that? I'm going to rebase them all, see if they compile and if they are green on try.

	Andrea Marchesini [:baku]
	Comment 71 • 7 years ago

Comment on attachment 8969603 [details] [diff] [review]
Remove InsertChildAt_Deprecated and RemoveChildAt_Deprecated - InterDiff

Review of attachment 8969603 [details] [diff] [review]:
-----------------------------------------------------------------

::: dom/base/nsINode.cpp
@@ +540,5 @@
>    }
>  
>    // Check again, we may not be the child's parent anymore.
>    // Can be triggered by dom/base/crashtests/293388-1.html
> +  if (!aOldChild.IsRootOfAnonymousSubtree() ||

Actually, the method would be aOldChild.IsInAnonymousSubtree()

	Boris Zbarsky [:bzbarsky]
	Comment 72 • 7 years ago

Comment on attachment 8969603 [details] [diff] [review]
Remove InsertChildAt_Deprecated and RemoveChildAt_Deprecated - InterDiff

>+  if (!aOldChild.IsRootOfAnonymousSubtree() ||
>+      aOldChild.GetParentNode() != this) {

This isn't right.  The right check is more like:

  if (aOldChild.IsRootOfAnonymousSubtree() ||
      aOldChild.GetParentNode() != this) {

because the whole point is that the old code would have bailed out if aOldChild was one of our anonymous kids (because indexof would return -1).

> Actually, the method would be aOldChild.IsInAnonymousSubtree()

No, it should be a root of anon subtree check.  Removing things that are just somewhere in an anon subtree but not anonymous from their parent's point of view is fine.

Why did the review comment about IsNodeOfType(eDATA_NODE) not get applied?

Why did the review comment about documenting the safety of nodeToInsertBefore being set to AsContent() stuff without checking IsContent() not get applied?

>+      nsCOMPtr<nsIContent> previous = aNewChild->GetPreviousSibling();
>+      nsCOMPtr<nsIContent> next = aNewChild->GetNextSibling();

Well.  _Is_ using weak refs there safe?  This is somwhat hot code; the extra refcount traffic may not be desirable...

> I see there are other patches with r=bz in the commit message

Anything that doesn't have an actual review flag set by me I did not review.  It was all part of that big patch that I marked "r-, please break this up" and did not read the details of.

	Andrea Marchesini [:baku]
	Comment 73 • 6 years ago

I'm not working on this at the moment.

	Olli Pettay [:smaug][bugs@pettay.fi] Assignee
	Comment 74 • 6 years ago

Comment on attachment 8966588 [details] [diff] [review]
Remove some nsAttrAndChildArray usage.

># HG changeset patch
># User Catalin Badea <catalin.badea392@gmail.com>
>
>Bug 651120 - Remove some nsAttrAndChildArray usage. r=baku
>
>This removes nsAttrAndChildArray usage from ::UnbindFromTree, ::DestroyContent
>and ::SaveSubtreeState.
>
>diff --git a/dom/base/Element.cpp b/dom/base/Element.cpp
>index fd63d72bb12d..d3e692bc0d11 100644
>--- a/dom/base/Element.cpp
>+++ b/dom/base/Element.cpp
>@@ -2039,23 +2039,23 @@ Element::UnbindFromTree(bool aDeep, bool aNullParent)
>   if (IsHTMLElement()) {
>     ResetDir(this);
>   }
> 
>   if (aDeep) {
>     // Do the kids. Don't call GetChildCount() here since that'll force
>     // XUL to generate template children, which there is no need for since
>     // all we're going to do is unbind them anyway.
>-    uint32_t i, n = mAttrsAndChildren.ChildCount();
>-
>-    for (i = 0; i < n; ++i) {
>+    nsIContent* child = GetFirstChild();
>+    while (child) {
>       // Note that we pass false for aNullParent here, since we don't want
>       // the kids to forget us.  We _do_ want them to forget their binding
>       // parent, though, since this only walks non-anonymous kids.
>-      mAttrsAndChildren.ChildAt(i)->UnbindFromTree(true, false);
>+      child->UnbindFromTree(true, false);
>+      child = child->GetNextSibling();
>     }
>   }
> 
>   nsNodeUtils::ParentChainChanged(this);
> 
>   // Unbind children of shadow root.
>   if (ShadowRoot* shadowRoot = GetShadowRoot()) {
>     for (nsIContent* child = shadowRoot->GetFirstChild(); child;
>diff --git a/dom/base/FragmentOrElement.cpp b/dom/base/FragmentOrElement.cpp
>index cc3456caedd0..12922adfc618 100644
>--- a/dom/base/FragmentOrElement.cpp
>+++ b/dom/base/FragmentOrElement.cpp
>@@ -1256,33 +1256,35 @@ FragmentOrElement::DestroyContent()
>   if (IsElement() && document->IsStyledByServo()) {
>     AsElement()->ClearServoData();
>   }
> 
>   document->BindingManager()->RemovedFromDocument(this, document,
>                                                   nsBindingManager::eRunDtor);
>   document->ClearBoxObjectFor(this);
> 
>-  uint32_t i, count = mAttrsAndChildren.ChildCount();
>-  for (i = 0; i < count; ++i) {
>+  for (nsIContent* child = GetFirstChild(); child;) {
>     // The child can remove itself from the parent in BindToTree.
>-    mAttrsAndChildren.ChildAt(i)->DestroyContent();
>+    nsIContent* current = child;
>+    child = child->GetNextSibling();
>+
>+    current->DestroyContent();
>   }
>   ShadowRoot* shadowRoot = GetShadowRoot();
>   if (shadowRoot) {
>     shadowRoot->DestroyContent();
>   }
> }
> 
> void
> FragmentOrElement::SaveSubtreeState()
> {
>-  uint32_t i, count = mAttrsAndChildren.ChildCount();
>-  for (i = 0; i < count; ++i) {
>-    mAttrsAndChildren.ChildAt(i)->SaveSubtreeState();
>+  for (nsIContent* child = GetFirstChild(); child;
>+       child = child->GetNextSibling()) {
>+    child->SaveSubtreeState();
>   }
> }
> 
> //----------------------------------------------------------------------
> 
> // Generic DOMNode implementations
> 
> void
>@@ -1467,17 +1469,17 @@ NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN(FragmentOrElement)
>         // unlink impl and ContentUnbinder::UnbindSubtree.
>         nsCOMPtr<nsIContent> child = tmp->mAttrsAndChildren.TakeChildAt(childCount);
>         if (childCount == 0) {
>           tmp->mFirstChild = nullptr;
>         }
>         child->UnbindFromTree();
>       }
>     }
>-  } else if (!tmp->GetParent() && tmp->mAttrsAndChildren.ChildCount()) {
>+  } else if (!tmp->GetParent() && tmp->HasChildren()) {
>     ContentUnbinder::Append(tmp);
>   } /* else {
>     The subtree root will end up to a ContentUnbinder, and that will
>     unbind the child nodes.
>   } */
> 
>   // Clear flag here because unlinking slots will clear the
>   // containing shadow root pointer.
>diff --git a/dom/base/nsDocument.cpp b/dom/base/nsDocument.cpp
>index 6d5b5944e460..1ccb14567a8a 100644
>--- a/dom/base/nsDocument.cpp
>+++ b/dom/base/nsDocument.cpp
>@@ -4195,19 +4195,18 @@ Element*
> nsIDocument::GetRootElementInternal() const
> {
>   // We invoke GetRootElement() immediately before the servo traversal, so we
>   // should always have a cache hit from Servo.
>   MOZ_ASSERT(NS_IsMainThread());
> 
>   // Loop backwards because any non-elements, such as doctypes and PIs
>   // are likely to appear before the root element.
>-  uint32_t i;
>-  for (i = mChildren.ChildCount(); i > 0; --i) {
>-    nsIContent* child = mChildren.ChildAt(i - 1);
>+  for (nsIContent* child = nsINode::GetLastChild(); child;
>+       child = child->GetPreviousSibling()) {
>     if (child->IsElement()) {
>       const_cast<nsIDocument*>(this)->mCachedRootElement = child->AsElement();
>       return child->AsElement();
>     }
>   }
> 
>   const_cast<nsIDocument*>(this)->mCachedRootElement = nullptr;
>   return nullptr;
>@@ -8265,19 +8264,19 @@ nsDocument::Destroy()
>   mIsGoingAway = true;
> 
>   ScriptLoader()->Destroy();
>   SetScriptGlobalObject(nullptr);
>   RemovedFromDocShell();
> 
>   bool oldVal = mInUnlinkOrDeletion;
>   mInUnlinkOrDeletion = true;
>-  uint32_t i, count = mChildren.ChildCount();
>-  for (i = 0; i < count; ++i) {
>-    mChildren.ChildAt(i)->DestroyContent();
>+  for (nsIContent* child = nsINode::GetFirstChild(); child;
>+       child = child->GetNextSibling()) {
>+    child->DestroyContent();
>   }
>   mInUnlinkOrDeletion = oldVal;
> 
>   mLayoutHistoryState = nullptr;
> 
>   // Shut down our external resource map.  We might not need this for
>   // leak-fixing if we fix nsDocumentViewer to do cycle-collection, but
>   // tearing down all those frame trees right now is the right thing to do.
>@@ -8288,19 +8287,19 @@ void
> nsDocument::RemovedFromDocShell()
> {
>   if (mRemovedFromDocShell)
>     return;
> 
>   mRemovedFromDocShell = true;
>   EnumerateActivityObservers(NotifyActivityChanged, nullptr);
> 
>-  uint32_t i, count = mChildren.ChildCount();
>-  for (i = 0; i < count; ++i) {
>-    mChildren.ChildAt(i)->SaveSubtreeState();
>+  for (nsIContent* child = nsINode::GetFirstChild(); child;
>+       child = child->GetNextSibling()) {
>+    child->SaveSubtreeState();
>   }
> }
> 
> already_AddRefed<nsILayoutHistoryState>
> nsIDocument::GetLayoutHistoryState() const
> {
>   nsCOMPtr<nsILayoutHistoryState> state;
>   if (!mScriptGlobalObject) {
>

	Olli Pettay [:smaug][bugs@pettay.fi] Assignee
	Comment 75 • 6 years ago

Comment on attachment 8966589 [details] [diff] [review]
Remove InsertChildAt_Deprecated and RemoveChildAt_Deprecated.

this was moved to bug 1469385

	Olli Pettay [:smaug][bugs@pettay.fi] Assignee
	Comment 76 • 6 years ago

Comment on attachment 8966593 [details] [diff] [review]
Share storage between slots pointer and children count in nsINode.

Given that sizeof HTMLElement is now smaller than it used to be, we may not want this.
This would cause weirdly sized slot structures anyhow.

	Olli Pettay [:smaug][bugs@pettay.fi] Assignee
	Comment 77 • 6 years ago

Comment on attachment 8966591 [details] [diff] [review]
Stop using nsAttrAndChildArray in FragmentOrElement and nsDocument.

this is now tracked in bug 1469382

	Olli Pettay [:smaug][bugs@pettay.fi] Assignee
	Comment 78 • 6 years ago

Tracking what was happening with this bug was hard, because some patch landed already last autumn, and then there were plenty of unreviewed patches and a reviewed patch...
So, this is now a meta bug. See 'depends on' what all needs to be done to get this fixed.

	Olli Pettay [:smaug][bugs@pettay.fi] Assignee
	Comment 79 • 6 years ago

As of now, this is fixed. There is more clean up work to do and removal of some _deprecated calls is in process.