1366241 - Use of BinarySearch is slow in nsHtml5ElementName::elementNameByBuffer and nsHTML5AttributeName::nameByBuffer

Status: RESOLVED FIXED

(Core :: DOM: HTML Parser, defect, P2)

Description

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

See https://bugzilla.mozilla.org/show_bug.cgi?id=1351857#c16 and comments onward.

qf:p1 is perhaps a bit too high priority, but this shouldn't be too difficult to fix and could make us faster than Chrome.

Comment 1

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

... in Bug 1347525

Comment 2

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

Henri, would you be able to take this?

Comment 3

[Henri Sivonen (:hsivonen)]

(In reply to Hsin-Yi Tsai [:hsinyi] from comment #2)
> Henri, would you be able to take this?

Yes, but it's unclear to me what should be done here.

The right thing to do would be to come up with a perfect hash function, but I'm unaware of suitable code generators.

The alternative is to have a cache for making particular benchmarks look good.

I guess I'll try to find a suitable code generator.

Comment 4

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

It is not just that particular benchmark. It should catch common cases usually.
We use similar caches in many places (and have used for a long time) and they tend to work rather well.
Perfect hash would be of course the best option.

Comment 5

[Henri Sivonen (:hsivonen)]

Let's see if StackOverflow yields the needed code generator:
https://stackoverflow.com/questions/44133839/minimal-perfect-hash-function-code-generator-for-java

Comment 6

[Andrew Overholt [:overholt]]

Seems like Henri's working on this.

Comment 7

[(no longer active)]

If I'm not mistaken, the ELEMENT_HASHES table has 204 entries which means that it won't fit in a cache line.  Doing a binary search over it in the usual way is pretty cache hostile.

Over the weekend I did some research over what cache friendly binary search algorithms are available, and it turns out that with a bit smarter arrangement of the entries in the array instead of just sorting them, you can achieve much better cache efficiency rates while performing the binary search, by mutating the access patterns in order to transform them into linear advances into the array instead of randomly jumping around over the array which a normal binary search over the array would achieve.  Furthermore, it makes it so that the first few accesses into the array for the first few steps of the binary search happen close to each other, increasing the likelihood that after the first access, the next few will be in the fetched cache line.  This blog post does a great job at explaining the concept with some helpful graphs: http://bannalia.blogspot.ca/2015/06/cache-friendly-binary-search.html

This recent survey looks very interesting: https://arxiv.org/abs/1509.05053  Based on this, and given that this data is sorted statically, perhaps we should consider switching it to Eytzinger sorting order?

Comment 8

[William Chen [:wchen]]

I changed the memory layout of the hashes for both element names and attribute names and profiled against the testcases in bug 1347525. Without the patch, the time spent in nsHtml5ElementName::elementNameByBuffer and nsHTML5AttributeName::nameByBuffer is approximately 8% of FragmentOrElement::SetInnerHTMLInternal. After the patch, it's approximately 4%.

Comment 9

[William Chen [:wchen]]

Attachment: Java changes - Change memory layout of element name and attribute name hashes in HTML parser from sorted to level order BST in order to take advantage of cache during lookup.

Comment 10

[William Chen [:wchen]]

Attachment: cpp changes - Change memory layout of element name and attribute name hashes in HTML parser from sorted to level order BST in order to take advantage of cache during lookup

Comment 11

[Henri Sivonen (:hsivonen)]

Comment on attachment 8880241 [details] [diff] [review]
cpp changes - Change memory layout of element name and attribute name hashes in HTML parser from sorted to level order BST in order to take advantage of cache during lookup

I looks like this is not the intended attachment.

Comment 12

[Henri Sivonen (:hsivonen)]

Comment on attachment 8880240 [details] [diff] [review]
Java changes - Change memory layout of element name and attribute name hashes in HTML parser from sorted to level order BST in order to take advantage of cache during lookup.

Review of attachment 8880240 [details] [diff] [review]:
-----------------------------------------------------------------

Thank you. r+ even if the nit isn't fixed, but I'd prefer the nit to be fixed unless there's a translation reason not to.

::: src/nu/validator/htmlparser/impl/AttributeName.java
@@ +297,5 @@
>          // XXX deal with offset
>          @Unsigned int hash = AttributeName.bufToHash(buf, length);
> +        int[] hashes;
> +        hashes = AttributeName.ATTRIBUTE_HASHES;
> +        int index = levelOrderBinarySearch(hashes, hash);

Why isn't AttributeName.ATTRIBUTE_HASHES passed directly to levelOrderBinarySearch? Why is int[] hashes declared alone on a separate line? If these oddities are needed for translator quirks, they are OK. Otherwise, it would be nicer to pass AttributeName.ATTRIBUTE_HASHES to levelOrderBinarySearch directly.

Comment 13

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/b40afe5dca11
Change memory layout of element name and attribute name hashes in HTML parser from sorted to level order BST in order to take advantage of cache during lookup. r=hsivonen

Comment 14

[William Chen [:wchen]]

(In reply to Henri Sivonen (:hsivonen) from comment #12)
> Comment on attachment 8880240 [details] [diff] [review]
> Java changes - Change memory layout of element name and attribute name
> hashes in HTML parser from sorted to level order BST in order to take
> advantage of cache during lookup.
> 
> Review of attachment 8880240 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Thank you. r+ even if the nit isn't fixed, but I'd prefer the nit to be
> fixed unless there's a translation reason not to.
> 
> ::: src/nu/validator/htmlparser/impl/AttributeName.java
> @@ +297,5 @@
> >          // XXX deal with offset
> >          @Unsigned int hash = AttributeName.bufToHash(buf, length);
> > +        int[] hashes;
> > +        hashes = AttributeName.ATTRIBUTE_HASHES;
> > +        int index = levelOrderBinarySearch(hashes, hash);
> 
> Why isn't AttributeName.ATTRIBUTE_HASHES passed directly to
> levelOrderBinarySearch? Why is int[] hashes declared alone on a separate
> line? If these oddities are needed for translator quirks, they are OK.
> Otherwise, it would be nicer to pass AttributeName.ATTRIBUTE_HASHES to
> levelOrderBinarySearch directly.

Yeah, it's due to a translator quirk.

Comment 15

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/b40afe5dca11