HTML Parser should avoid dynamic allocations for storing attributes in the case where it knows how many attributes are going to be allocated

RESOLVED WONTFIX

Status

()

enhancement
P2
normal
RESOLVED WONTFIX
2 years ago
10 months ago

People

(Reporter: Ehsan, Assigned: allstars.chh)

Tracking

(Blocks 1 bug)

Firefox Tracking Flags

(Not tracked)

Details

Reporter

Description

2 years ago
This is motivated by this profile from a partial Speedometer run: http://bit.ly/2t0hzGZ

Note that the HTML Parser here is creating the node, and immediately setting a bunch of attrs on it, for example <http://searchfox.org/mozilla-central/rev/ae94cfb36d804727dfb38f2750bfcaab4621df6e/parser/html/nsHtml5TreeOperation.cpp#380>.  However since each node's nsAttrAndChildArray starts off with an empty array, we end up having to do a dynamic allocation here where we could in theory know in advance how many attributes we would need and somehow avoid having to do a separate malloc for it.

That however is easier said than done given the way that nsAttrAndChildArray is implemented (by putting the array elements after the object in memory and using C-style allocation functions.)  I haven't thought about a good way to do it yet.
Priority: -- → P2
Assignee: nobody → allstars.chh
(In reply to :Ehsan Akhgari (needinfo please, extremely long backlog) from comment #0)
> Note that the HTML Parser here is creating the node, and immediately setting
> a bunch of attrs on it, for example
> <http://searchfox.org/mozilla-central/rev/
> ae94cfb36d804727dfb38f2750bfcaab4621df6e/parser/html/nsHtml5TreeOperation.
> cpp#380>. 

Ehsan, the line you pointed out is for keygen, but keygen should not be a common case
Are you referring 
http://searchfox.org/mozilla-central/rev/ae94cfb36d804727dfb38f2750bfcaab4621df6e/parser/html/nsHtml5TreeOperation.cpp#431

In that case, we did set a bunch of attributes base on the value of aAttributes->getLength()
http://searchfox.org/mozilla-central/rev/ae94cfb36d804727dfb38f2750bfcaab4621df6e/parse/html/nsHtml5TreeOperation.cpp#408

But each call to GrowBy, in most cases, it actually increases the buffer size by 6, got from ATTRCHILD_ARRAY_GROWSIZE(which is 8) - NS_IMPL_EXTRA_SIZE (which is 2)
http://searchfox.org/mozilla-central/rev/ae94cfb36d804727dfb38f2750bfcaab4621df6e/dom/base/nsAttrAndChildArray.cpp#866
http://searchfox.org/mozilla-central/rev/ae94cfb36d804727dfb38f2750bfcaab4621df6e/dom/base/nsAttrAndChildArray.cpp#899,

and each attribute takes 2 byte (ATTRSIZE)
so the call to SetAttr will only trigger GrowBy() if it has more than 4 attributes (take 8 bytes)

So we could pre-allocate the size base on the attributes we have, but in most cases, normal node has only less than 4 attributes, so doing this might only have small improvements.

Is this what you have in mind?

Thanks
Flags: needinfo?(ehsan)
Reporter

Comment 2

2 years ago
(In reply to Yoshi Huang [:allstars.chh] from comment #1)
> (In reply to :Ehsan Akhgari (needinfo please, extremely long backlog) from
> comment #0)
> > Note that the HTML Parser here is creating the node, and immediately setting
> > a bunch of attrs on it, for example
> > <http://searchfox.org/mozilla-central/rev/
> > ae94cfb36d804727dfb38f2750bfcaab4621df6e/parser/html/nsHtml5TreeOperation.
> > cpp#380>. 
> 
> Ehsan, the line you pointed out is for keygen, but keygen should not be a
> common case
> Are you referring 
> http://searchfox.org/mozilla-central/rev/
> ae94cfb36d804727dfb38f2750bfcaab4621df6e/parser/html/nsHtml5TreeOperation.
> cpp#431

Yes probably, keygen isn't important at all as you noted.  :-)

> In that case, we did set a bunch of attributes base on the value of
> aAttributes->getLength()
> http://searchfox.org/mozilla-central/rev/
> ae94cfb36d804727dfb38f2750bfcaab4621df6e/parse/html/nsHtml5TreeOperation.
> cpp#408
> 
> But each call to GrowBy, in most cases, it actually increases the buffer
> size by 6, got from ATTRCHILD_ARRAY_GROWSIZE(which is 8) -
> NS_IMPL_EXTRA_SIZE (which is 2)
> http://searchfox.org/mozilla-central/rev/
> ae94cfb36d804727dfb38f2750bfcaab4621df6e/dom/base/nsAttrAndChildArray.cpp#866
> http://searchfox.org/mozilla-central/rev/
> ae94cfb36d804727dfb38f2750bfcaab4621df6e/dom/base/nsAttrAndChildArray.
> cpp#899,
> 
> and each attribute takes 2 byte (ATTRSIZE)
> so the call to SetAttr will only trigger GrowBy() if it has more than 4
> attributes (take 8 bytes)
> 
> So we could pre-allocate the size base on the attributes we have, but in
> most cases, normal node has only less than 4 attributes, so doing this might
> only have small improvements.
> 
> Is this what you have in mind?

I haven't looked into the details here yet.  I think we shouldn't invest time into this before bug 651120 is fixed, because that bug will remove child nodes from nsAttrAndChildArray, and may have an impact on when we should consider growing this array (and how many attributes will fit into it).

The ultimate goal here is to avoid the cost of an allocation if we can, but this is definitely in the area of micro-optimizations, so we shouldn't expect a huge improvement as a result of it.
Depends on: 651120
Flags: needinfo?(ehsan)

Comment 3

10 months ago
Difficult thing here is that some attributes are mapped. We don't want to increase AttrArray if we have such attribute. And checking whether attribute is mapped is a virtual call.

We could, if this was showing really badly in profile, check mapped-ness in parser, and based on that
preallocate storage for non-mapped attribute and then pass information whether something is mapped to SetAttr. But given that we anyhow allocate just once per 4 attributes, that should be quite ok normally.

And we do need to do separate allocation and not allocate from the same bucket as Element, since Element (and common subtypes like HTMLDivElement and HTMLSpanElement) take currently perfectly 128 bytes (on 64bit. We have static assert about that), which is a mozjemalloc bucket size. And 128 happens to fit in to 2 cache lines.

So, I think this is wontfix. Please reopen, if you disagree.
Status: NEW → RESOLVED
Closed: 10 months ago
Resolution: --- → WONTFIX
You need to log in before you can comment on or make changes to this bug.