997428 - off the main parser is very malloc heavy, nsTArray::AppendElement taking up to 25% time

Status: RESOLVED FIXED

(Core :: DOM: HTML Parser, defect)

Description

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

...this is when profiling html spec (one page version) loading.
Of the total page load, parser thread isn't too much, <10%.

I wonder if mOpQueue shouldn't be nsTArray but LinkedList. That would make
append O(1) vs the current worst case O(n). Even better might be some sort of segmented array.

Comment 1

[Henri Sivonen (:hsivonen)]

If we make it a linked list, the ops themselves should probably have next op pointers to avoid the overhead of a generic linked list around them.

Comment 2

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

That is how LinkedList is implemented
http://mxr.mozilla.org/mozilla-central/source/mfbt/LinkedList.h

http://mxr.mozilla.org/mozilla-central/source/xpcom/base/nsCycleCollector.cpp#2239 combines
nsTArray and LinkedList to reduce malloc/free and doesn't require each entry to have prev/next pointers.

Comment 3

[william bradshaw]

nsTArray uses array size doubling expand procedure and thus append cost is an amortized O(1) for arrays smaller than page size. If the arrays are smaller than 1024 bytes than copy semantics for the types contained in the array is poor causing the performance issue. I would look into improving copy semantics of contained objects or changing the array to use type* as opposed to type.  If type* is a problem outside of parse I would recommend using type* during parse then copying to a type array and than stripping back array.

If arrays get larger than page size this is an issue with the implementation of nsTArray. Regardless the nsTArray issue should be fixed and I am going to look into that.

Comment 4

[william bradshaw]

nsTArray growth issue has been resolved via Bug 1048044. I suggest retesting to see if this issue still exists after application of patch.

Comment 5

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

Thanks for reminding about that. I'll reprofile this.

It is still possible we should use SegmentedArray here.

Comment 6

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

I don't see nsTArray::AppendElement, but nsTArray::EnsureCapacity in the profile, and for the
parser thread it is now only 1.8%.

stateLoop and createElement dominate now.

Marking this fixed.