1384661 - Implement a separate cache for node.childNodes

Status: RESOLVED FIXED

(Core :: DOM: Core & HTML, enhancement, P1)

Description

[Cătălin Badea (:catalinb)]

Dropping the child array in bug 651120 means we will break performance in node.childNodes. We should fix that by having a separate cache.

Comment 1

[(no longer active)]

The idea here is to extend nsChildContentList to have a cached array of child nodes that it can use for fast indexing into.

In nsINode::ChildNodes(), when we are about to create this object for the first time, we will scan the linked list of the children for the node, and gather a cached array of the pointers to all of the children in the mentioned array.

Obviously, we also need to invalidate this cache when the list of children changes. Since we have a pointer to nsChildContentList in our slots, it's easy to know when we need to do this work.  The right place to do the invalidation is probably in nsINode::doInsertChildAt() or thereabouts.  It's probably OK to just invalidate the cache and reconstruct it lazily the next time that a method or property off of nsChildContentList gets accessed.

Take extra care that nsINode::ChildNodes() can be called on attribute nodes also, and since the storage of attribute nodes won't change in bug 651120, it may make sense to not change the existing implementation strategy for that case.  Therefore, we may want to rename nsChildContentList to nsAttrChildContentList, and have an nsElementChildContentList that implements the cached array explained above.

Comment 2

[Hsin-Yi Tsai (she/her) [:hsinyi]]

Hi Ben, please help this. :)

Comment 3

[Ben Tian (inactive)]

Attachment: [final] Patch 1: Rename class nsChildContentList to nsAttrChildContentList, r=smaug

Comment 4

[Ben Tian (inactive)]

Attachment: Patch 2 (v1): Add class nsElementAttrChildContentList

Comment 5

[Ben Tian (inactive)]

Attachment: Patch 3 (v1): Invalidate cached child array when list of children changes

Comment 6

[Ben Tian (inactive)]

Attachment: Patch 2 (v2): Add class nsElementAttrChildContentList

Change
- fix bug that cache validation doesn't clear cached array first

Comment 7

[Ben Tian (inactive)]

Attachment: Test patch: remove-child-array

Test patch that removes |GetChildArray| method. The patch is rebased on m-c from patch in bug 651120 comment 18.

Comment 8

[Ben Tian (inactive)]

Attachment: Patch 2 (v3): Add class nsElementAttrChildContentList

Change:
- fix nit

Comment 9

[Ben Tian (inactive)]

Comment on attachment 8896087 [details] [diff] [review]
[final] Patch 1: Rename class nsChildContentList to nsAttrChildContentList, r=smaug

Ehsan, can you review my patches based on your comment 1 suggestion?

Three patches in total:
1) rename nsChildContentList to nsAttrChildContentList
2) add nsElementChildContentList that implements cached array
3) invalidate child array when list of children changes

Verified on try with comment 7 patch that removes |GetChildArray| method.
https://treeherder.mozilla.org/#/jobs?repo=try&revision=49c9426c8d88f230c4cbab26549a6b587642cc47

Comment 10

[Ben Tian (inactive)]

Comment on attachment 8896087 [details] [diff] [review]
[final] Patch 1: Rename class nsChildContentList to nsAttrChildContentList, r=smaug

Will verify further on performance. Cancel review first.

Comment 11

[Ben Tian (inactive)]

Attachment: Test patch: remove-index-argument

Test patch that removes index argument from content removed/appended/inserted notifications. The patch is rebased on m-c from patch in bug 651120 comment 26.

Comment 12

[Ben Tian (inactive)]

(In reply to Ben Tian [:btian] from comment #10)
> Will verify further on performance. Cancel review first.

The bottleneck remains (https://goo.gl/JcDd1g) as bug 651120 comment 27. Need to improve the caching.
Note the patched build includes my 3 patches and rebased patches in comment 7 and comment 11.

Comment 13

[Ben Tian (inactive)]

(In reply to Ben Tian [:btian] from comment #12)
> (In reply to Ben Tian [:btian] from comment #10)
> > Will verify further on performance. Cancel review first.
> 
> The bottleneck remains (https://goo.gl/JcDd1g) as bug 651120 comment 27.
> Need to improve the caching.
> Note the patched build includes my 3 patches and rebased patches in comment
> 7 and comment 11.

Hmm... not sure whether the bottleneck is the same problem as this bug. Will confirm.

Comment 14

[Ben Tian (inactive)]

Attachment: Patch 3 (v2): Invalidate cached child array when list of children changes

Changes:
- do not create new slots for cache invalidation if they don't exist
- replace NS_PRECONDITION with MOZ_ASSERT

Comment 15

[Ben Tian (inactive)]

Attachment: Test patch 1: remove-child-array

Rebase to solve conflict.

Comment 16

[Ben Tian (inactive)]

Attachment: Test patch 2: remove-index-argument

Remove unused variable to avoid compiler warning.

Comment 17

[Ben Tian (inactive)]

(In reply to Ben Tian [:btian] from comment #13)
> Hmm... not sure whether the bottleneck is the same problem as this bug. Will
> confirm.

The cached array impacts only on read performance via node.childNodes, not on write (append/insert/remove) performance of underlying child array (bug 651120 comment 27).

Comment 18

[Ben Tian (inactive)]

Comment on attachment 8896087 [details] [diff] [review]
[final] Patch 1: Rename class nsChildContentList to nsAttrChildContentList, r=smaug

(Resend review)

Ehsan, can you review my patches based on your comment 1 suggestion?

Three patches in total:
1) rename nsChildContentList to nsAttrChildContentList
2) add nsElementChildContentList that implements cached array
3) invalidate child array when list of children changes

Comment 19

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

Comment on attachment 8896087 [details] [diff] [review]
[final] Patch 1: Rename class nsChildContentList to nsAttrChildContentList, r=smaug

You should also rename nsChildContentList.h

Comment 20

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

(In reply to Olli Pettay [:smaug] from comment #19)

> You should also rename nsChildContentList.h
Ah, no need, since you add more stuff there.

Comment 21

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

Comment on attachment 8896821 [details] [diff] [review]
Patch 2 (v3): Add class nsElementAttrChildContentList

>+  void InvalidateCache()
>+  {
>+    mIsCacheValid = false;
>+  }
I think InvalidateCache should clear the array. We don't want the array to have pointers to possibly deleted objects.
And DropReference() needs to invalidate the cache too, so need to override the method from parent class.

>+  // Cached array of child nodes
>+  nsTArray<nsIContent*> mCachedChildArray;
It would be good to test a bit what is the average size for this, and possibly use AutoTArray<nsIContent*, {some_reasonable_value}>.
That would reduce malloc/free calls, but use more memory in some cases.
Maybe running Speedometer (http://speedometer2.benj.me/) for example could give reasonable values, assuming it uses childlist.

Comment 22

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

Comment on attachment 8897367 [details] [diff] [review]
Patch 3 (v2): Invalidate cached child array when list of children changes

> {
>   nsSlots* slots = Slots();
>   if (!slots->mChildNodes) {
>-    slots->mChildNodes = new nsAttrChildContentList(this);
>+    slots->mChildNodes =
>+      IsNodeOfType(nsINode::eATTRIBUTE) ? new nsAttrChildContentList(this)
Just to avoid virtual call in common case, could this be
!IsElement() && IsNodeOfType(nsINode::eATTRIBUTE). Add a comment too that !IsElement() should catch the common case without virtual call.

>+                                        : new nsElementChildContentList(this);
Ahaa, nsElementChildContentList is wrong name, since the list is used also with Document and DocumentFragment.
Perhaps nsParentNodeChildContentList
https://dom.spec.whatwg.org/#parentnode
So make the change in the other patch

Comment 23

[Ben Tian (inactive)]

Attachment: [final] Patch 3: Invalidate cached child array when list of children changes, r=smaug

Update patch 3 per reviewer's comment 22.

Comment 24

[Ben Tian (inactive)]

Attachment: Plot - array size occurrence

(In reply to Olli Pettay [:smaug] from comment #21)
> >+  // Cached array of child nodes
> >+  nsTArray<nsIContent*> mCachedChildArray;
> It would be good to test a bit what is the average size for this, and
> possibly use AutoTArray<nsIContent*, {some_reasonable_value}>.
> That would reduce malloc/free calls, but use more memory in some cases.
> Maybe running Speedometer (http://speedometer2.benj.me/) for example could
> give reasonable values, assuming it uses childlist.

Set some_reasonable_value=8 after running Speedometer, as
1) the average array size is 8.08, and
2) 8 covers 89.6% occurrences.

Attach plot showing occurrences of array size.

Comment 25

[Ben Tian (inactive)]

Attachment: [final] Patch 2: Add class nsParentNodeChildContentList, r=smaug

Changes:
- clear array while cache invalidation
- invalidate cache in DropReference()
- replace nsTArray with AutoTArray<, 8> (comment 24)
- rename nsElementChildContentList to nsParentNodeChildContentList

Comment 26

[Ben Tian (inactive)]

Try result:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=57018194287b756ed48de114f4255ca16128bce2

Comment 27

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/b679806ce7e3
Part 1: Rename class nsChildContentList to nsAttrChildContentList. r=smaug
https://hg.mozilla.org/integration/mozilla-inbound/rev/8f77d260780d
Part 2: Add class nsParentNodeChildContentList. r=smaug
https://hg.mozilla.org/integration/mozilla-inbound/rev/7df868e0e356
Part 3: Invalidate cached child array when list of children changes. r=smaug

Comment 28

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/mozilla-central/rev/b679806ce7e3
https://hg.mozilla.org/mozilla-central/rev/8f77d260780d
https://hg.mozilla.org/mozilla-central/rev/7df868e0e356

Comment 29

[Ryan VanderMeulen [:RyanVM]]

Backed out for causing bug 1406395.

Comment 30

[Ben Tian (inactive)]

Catalin,

FYI, this bug results in bug 1406395 that causes use-after-free of node. So I decide to backout this bug for 57 and revise patch to re-land.

Comment 31

[Ben Tian (inactive)]

Attachment: [final] Patch 3: Invalidate cached child array when list of children changes, r=smaug

The patch invalidates cached child array when nsAttrAndChildArray::InsertChildAt, RemoveChildAt, or TakeChildAt is called.

- InsertChildAt [1]: 2 callers.
  1 is invalidated in |nsINode::doInsertChildAt|;
  1 in unused method |nsAttrAndChildArray::AppendChild| is removed in this patch.

- RemoveChildAt [2]: 4 callers.
  1 is invalidated in |nsINode::doInsertChildAt|;
  1 is invalidated in |nsINode::doRemoveChildAt|;
  1 is invalidated in |nsDocument::ResetToURI|;
  1 is invalidated in |nsDocument::~nsDocument|.

- TakeChildAt [3]: 4 callers.
  2 are in CC unlink method and invalidated by prior |nsINode::Unlink|;
  1 is called by |nsAttrAndChildArray::RemoveChildAt|;
  1 is invalidated in |ContentUnbinder::UnbindSubtree|.


[1] http://searchfox.org/mozilla-central/search?q=symbol:_ZN19nsAttrAndChildArray13InsertChildAtEP10nsIContentj&redirect=false
[2] http://searchfox.org/mozilla-central/search?q=symbol:_ZN19nsAttrAndChildArray13RemoveChildAtEj&redirect=false
[3] http://searchfox.org/mozilla-central/search?q=symbol:_ZN19nsAttrAndChildArray11TakeChildAtEj&redirect=false

Comment 32

[Ben Tian (inactive)]

Attachment: Patch 4 (v1): Test for invalidation of cached child array

The test case is based on bug 1406395.

Comment 33

[Ben Tian (inactive)]

Attachment: Patch 4 (v2): Test for invalidation of cached child array

Change:
- correct title bug number

Comment 34

[Ben Tian (inactive)]

Attachment: Patch 4 (v3): Test for invalidation of cached child array

Changes:
- rename function name
- fix indention

Comment 35

[Ben Tian (inactive)]

Attachment: [final] Patch 4: Test for invalidation of cached child array, r=smaug

Change:
- correct bug number

Comment 36

[Ben Tian (inactive)]

Comment on attachment 8920978 [details] [diff] [review]
[final] Patch 3: Invalidate cached child array when list of children changes, r=smaug

Olli, can you review my patches for cached child array invalidation and  corresponding test?

Patch 3 invalidates cached child array as comment 31, and patch 4 adds corresponding test based on bug 1406395.

Try result is in
https://treeherder.mozilla.org/#/jobs?repo=try&revision=7aa56cc73a471684b0e0fd14569efb85eca93aa7

Comment 37

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

bug 651120 didn't land for FF57

Comment 38

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

I need to think this a bit. Would there be some less error prone approach to invalidate the list?
Something which doesn't require one to remember to call InvalidateChildNodes in various places.

Comment 39

[Ben Tian (inactive)]

(In reply to Olli Pettay [:smaug] from comment #38)
> I need to think this a bit. Would there be some less error prone approach to
> invalidate the list?
> Something which doesn't require one to remember to call InvalidateChildNodes
> in various places.

One alternative is to invalidate in new nsINode methods [1] added by bug 651120 comment 32's WIP patch. But maybe in a follow-up bug to not block bug 651120 by this bug.

[1] |nsINode::AppendChild|, |nsINode::InsertBefore|, and |nsINode::UnlinkChild|
https://bugzilla.mozilla.org/attachment.cgi?id=8903569&action=diff#a/dom/base/nsINode.cpp_sec10

Comment 40

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

btw, please use -p -U 8 when creating patches.
I have
[defaults]
diff = -p -U 8
in my .hgrc

Comment 41

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

(In reply to Ben Tian [:btian] from comment #39)
> (In reply to Olli Pettay [:smaug] from comment #38)
> > I need to think this a bit. Would there be some less error prone approach to
> > invalidate the list?
> > Something which doesn't require one to remember to call InvalidateChildNodes
> > in various places.
> 
> One alternative is to invalidate in new nsINode methods [1] added by bug
> 651120 comment 32's WIP patch. But maybe in a follow-up bug to not block bug
> 651120 by this bug.
> 
Yeah, that sounds reasonable.

Comment 42

[Ben Tian (inactive)]

(In reply to Olli Pettay [:smaug] from comment #40)
> btw, please use -p -U 8 when creating patches.
> I have
> [defaults]
> diff = -p -U 8
> in my .hgrc

Revised my .hgrc accordingly.

(In reply to Olli Pettay [:smaug] from comment #41)
> > One alternative is to invalidate in new nsINode methods [1] added by bug
> > 651120 comment 32's WIP patch. But maybe in a follow-up bug to not block bug
> > 651120 by this bug.
> > 
> Yeah, that sounds reasonable.

Opened follow-up bug 1412165 to track.

Comment 43

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/11be1a494ce0
Part 1: Rename class nsChildContentList to nsAttrChildContentList. r=smaug
https://hg.mozilla.org/integration/mozilla-inbound/rev/25d99455a3bd
Part 2: Add class nsParentNodeChildContentList. r=smaug
https://hg.mozilla.org/integration/mozilla-inbound/rev/7c6b44c85d8b
Part 3: Invalidate cached child array when list of children changes. r=smaug
https://hg.mozilla.org/integration/mozilla-inbound/rev/a1a3fa8038e0
Part 4: Test for invalidation of cached child array. r=smaug

Comment 44

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/mozilla-central/rev/11be1a494ce0
https://hg.mozilla.org/mozilla-central/rev/25d99455a3bd
https://hg.mozilla.org/mozilla-central/rev/7c6b44c85d8b
https://hg.mozilla.org/mozilla-central/rev/a1a3fa8038e0