Closed Bug 1359556 Opened 4 years ago Closed 4 years ago

cloneNode should preallocate nsAttrAndChildArray


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

Not set



Tracking Status
firefox55 --- fixed


(Reporter: bytesized, Assigned: bytesized)




(3 files)

Currently, nsAttrAndChildArray allocates no space when it is created. It then increases the array size by 8 children until reaching enough space for 32 children. After that, it expands to the next power of 2.

When (deep) cloning however, we know how big that array should be in advance since it will match the parent's array. We should preallocate it to that size rather than reallocating it as children are added in order to increase performance.
Because this benchmark clones elements with less than 8 children, it should correctly allocate enough space for each child without further optimization. This should allow us to observe the performance impact of the optimization in usages that do not benefit from the optimization to make sure the optimization is not significantly slowing down those cases.
This micro benchmark should allow us to observe the performance increase provided by this optimization because some items being cloned have more than 8 children.
I see a small performance decrease on *both* benchmarks. I am currently looking into why this might be.
This version of the patch seems much better:

Pre-patch benchmark results (build 62a2d3693579):
Micro benchmark 1: 347ms
Micro benchmark 2: 819ms

Patched benchmark results:
Micro benchmark 1: 342ms
Micro benchmark 2: 748ms
Attachment #8861578 - Flags: review?(bzbarsky)
Another test would be to clone elements with lots of attributes.
Comment on attachment 8861578 [details]
Bug 1359556 - Optimize cloneNode by preinitializing attribute and child arrays

r=me with the comment nits below.

::: commit-message-62a2d:5
(Diff revision 2)
> +Bug 1359556 - Optimize cloneNode by preinitializing attribute and child arrays
> +
> +Currently, attribute and child arrays (implemented in dom/base/nsAttrAndChildArray.h) start out empty. When cloning, the array ends up being resized multiple times in order to add the attributes and children that are being cloned from the original node. This would be quicker if the array was initialized to the correct size in the first place so that resizes are not necessary.
> +
> +However, this is only necessary when performing a deep clone. Therefore, an additional parameter is being added to Clone methods to indicate whether this preallocation of children should happen. Attributes are copied either way, so that part of the array is preallocated in both cases.

s/this/preallocating space for children/, right?

::: dom/base/nsAttrAndChildArray.cpp:812
(Diff revision 2)
> +
> +  if (attrCount == 0 && childCount == 0) {
> +    return NS_OK;
> +  }
> +
> +  uint32_t size = attrCount;

Might be worth a comment about how we know none of the calculations here will overflow because we already have a thing allocated to this size.

::: dom/base/nsAttrAndChildArray.cpp:823
(Diff revision 2)
> +  mImpl = static_cast<Impl*>(malloc(totalSize * sizeof(void*)));
> +
> +  mImpl->mMappedAttrs = nullptr;
> +  mImpl->mBufferSize = size;
> +  memset(static_cast<void*>(mImpl->mBuffer), 0, sizeof(InternalAttr) * attrCount);

This could use a comment explaining why we're not just doing SetAttrSlotAndChildCount(0, 0).  Presumably because we don't want the kids to start getting put into the attr slots unnecessarily, etc.
Attachment #8861578 - Flags: review?(bzbarsky) → review+
And thank you for doing this!
Pushed by
Optimize cloneNode by preinitializing attribute and child arrays r=bz
Closed: 4 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
Component: DOM → DOM: Core & HTML
You need to log in before you can comment on or make changes to this bug.