Closed Bug 1384661 Opened 2 years ago Closed 2 years ago

Implement a separate cache for node.childNodes

Categories

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

enhancement

Tracking

()

RESOLVED FIXED
mozilla58
Tracking Status
firefox57 --- unaffected
firefox58 --- fixed

People

(Reporter: catalinb, Assigned: ben.tian)

References

(Blocks 1 open bug)

Details

Attachments

(5 files, 13 obsolete files)

5.82 KB, patch
smaug
: review+
Details | Diff | Splinter Review
45.57 KB, image/png
Details
4.27 KB, patch
smaug
: review+
Details | Diff | Splinter Review
5.55 KB, patch
smaug
: review+
Details | Diff | Splinter Review
2.13 KB, patch
smaug
: review+
Details | Diff | Splinter Review
Dropping the child array in bug 651120 means we will break performance in node.childNodes. We should fix that by having a separate cache.
Priority: -- → P1
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.
Hi Ben, please help this. :)
Assignee: nobody → btian
Change
- fix bug that cache validation doesn't clear cached array first
Attachment #8896088 - Attachment is obsolete: true
Attached patch Test patch: remove-child-array (obsolete) — Splinter Review
Test patch that removes |GetChildArray| method. The patch is rebased on m-c from patch in bug 651120 comment 18.
Attachment #8896163 - Attachment description: remove-child-array.patch → Test patch: remove-child-array
Change:
- fix nit
Attachment #8896159 - Attachment is obsolete: true
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
Attachment #8896087 - Flags: review?(ehsan)
Attachment #8896821 - Flags: review?(ehsan)
Attachment #8896089 - Flags: review?(ehsan)
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.
Attachment #8896087 - Flags: review?(ehsan)
Attachment #8896089 - Flags: review?(ehsan)
Attachment #8896821 - Flags: review?(ehsan)
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.
(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.
(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.
Changes:
- do not create new slots for cache invalidation if they don't exist
- replace NS_PRECONDITION with MOZ_ASSERT
Attachment #8896089 - Attachment is obsolete: true
Attached patch Test patch 1: remove-child-array (obsolete) — Splinter Review
Rebase to solve conflict.
Attachment #8896163 - Attachment is obsolete: true
Remove unused variable to avoid compiler warning.
Attachment #8897337 - Attachment is obsolete: true
(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 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
Attachment #8896087 - Flags: review?(ehsan)
Attachment #8896821 - Flags: review?(ehsan)
Attachment #8897367 - Flags: review?(ehsan)
Comment on attachment 8896087 [details] [diff] [review]
[final] Patch 1: Rename class nsChildContentList to nsAttrChildContentList, r=smaug

You should also rename nsChildContentList.h
Attachment #8896087 - Flags: review?(ehsan) → review+
(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 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.
Attachment #8896821 - Flags: review?(ehsan) → review-
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
Attachment #8897367 - Flags: review?(ehsan) → review+
Update patch 3 per reviewer's comment 22.
Attachment #8897367 - Attachment is obsolete: true
(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.
Changes:
- clear array while cache invalidation
- invalidate cache in DropReference()
- replace nsTArray with AutoTArray<, 8> (comment 24)
- rename nsElementChildContentList to nsParentNodeChildContentList
Attachment #8896821 - Attachment is obsolete: true
Attachment #8899392 - Flags: review?(bugs)
Attachment #8896087 - Attachment description: Patch 1 (v1): Rename class nsChildContentList to nsAttrChildContentList → [final] Patch 1: Rename class nsChildContentList to nsAttrChildContentList, r=smaug
Attachment #8899392 - Flags: review?(bugs) → review+
Attachment #8898600 - Attachment description: Patch 3 (v3): Invalidate cached child array when list of children changes, r=smaug → [final] Patch 3: Invalidate cached child array when list of children changes, r=smaug
Attachment #8899392 - Attachment description: Patch 2 (v4): Add class nsParentNodeChildContentList → [final] Patch 2: Add class nsParentNodeChildContentList, r=smaug
Attachment #8897681 - Attachment is obsolete: true
Attachment #8897682 - Attachment is obsolete: true
Pushed by ryanvm@gmail.com:
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
Keywords: checkin-needed
Depends on: 1406395
Backed out for causing bug 1406395.
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Target Milestone: mozilla57 → ---
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.
Depends on: 1408114
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
Attachment #8898600 - Attachment is obsolete: true
The test case is based on bug 1406395.
Change:
- correct title bug number
Attachment #8920982 - Attachment is obsolete: true
Changes:
- rename function name
- fix indention
Attachment #8920986 - Attachment is obsolete: true
Change:
- correct bug number
Attachment #8921362 - Attachment is obsolete: true
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
Attachment #8920978 - Flags: review?(bugs)
Attachment #8921380 - Flags: review?(bugs)
bug 651120 didn't land for FF57
Attachment #8921380 - Flags: review?(bugs) → review+
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.
(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
btw, please use -p -U 8 when creating patches.
I have
[defaults]
diff = -p -U 8
in my .hgrc
(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.
Attachment #8920978 - Flags: review?(bugs) → review+
Blocks: 1412165
Attachment #8920978 - Attachment description: Patch 3 (v4): Invalidate cached child array when list of children changes → [final] Patch 3: Invalidate cached child array when list of children changes, r=smaug
Attachment #8921380 - Attachment description: Patch 4 (v4): Test for invalidation of cached child array → [final] Patch 4: Test for invalidation of cached child array, r=smaug
(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.
Keywords: checkin-needed
Pushed by ryanvm@gmail.com:
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
Keywords: checkin-needed
Component: DOM → DOM: Core & HTML
You need to log in before you can comment on or make changes to this bug.