Bug 140873 – Optimize matchesLangPseudoClass() of :lang()

• Component: New Bugs
• Status: RESOLVED FIXED

[Dhi Aurrahman]

Optimize matchesLangPseudoClass of :lang()

[Dhi Aurrahman]

Created attachment 245310 [details]
Patch

[Build Bot]

Comment on attachment 245310 [details]
Patch

Attachment 245310 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.appspot.com/results/6575596767281152

New failing tests:
fast/selectors/lang-valid-extended-filtering.html
fast/selectors/lang-extended-filtering.html
fast/selectors/lang-vs-xml-lang.html
fast/selectors/lang-vs-xml-lang-xhtml.xhtml
fast/selectors/lang-inheritance2.html
fast/selectors/lang-inheritance.html

[Build Bot]

Created attachment 245311 [details]
Archive of layout-test-results from ews100 for mac-mavericks

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: ews100  Port: mac-mavericks  Platform: Mac OS X 10.9.5

[Build Bot]

Comment on attachment 245310 [details]
Patch

Attachment 245310 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.appspot.com/results/4613462432940032

New failing tests:
fast/selectors/lang-valid-extended-filtering.html
fast/selectors/lang-extended-filtering.html
fast/selectors/lang-vs-xml-lang.html
fast/selectors/lang-vs-xml-lang-xhtml.xhtml
fast/selectors/lang-inheritance2.html
fast/selectors/lang-inheritance.html

[Build Bot]

Created attachment 245312 [details]
Archive of layout-test-results from ews104 for mac-mavericks-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: ews104  Port: mac-mavericks-wk2  Platform: Mac OS X 10.9.5

[Dhi Aurrahman]

Created attachment 245313 [details]
Patch

[Benjamin Poulain]

Comment on attachment 245313 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=245313&action=review

That looks like a good start. Something is fishy with the length handling though.

Did you measure the before-after this patch on the microbenchmark?

> Source/WebCore/css/SelectorCheckerTestFunctions.h:185
> +    if (languageString[languageLength - 1] == '-')
> +        languageLength += 1;

This looks very very fishy.

A length for a buffer should never exceed the buffer size.

> Source/WebCore/css/SelectorCheckerTestFunctions.h:206
> +        if (rangeString[rangeLength - 1] == '-')
> +            rangeLength += 1;

Very fishy again.

[Dhi Aurrahman]

Created attachment 245429 [details]
Patch

[Dhi Aurrahman]

(In reply to comment #7)
> Comment on attachment 245313 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=245313&action=review
> 
> That looks like a good start. Something is fishy with the length handling
> though.

That was a cheap trick on handling '-' at the end of language or range. I have managed it to be removed in next patch.

> 
> Did you measure the before-after this patch on the microbenchmark?

Before: https://cloudup.com/ckxm_SuTIiO
After: https://cloudup.com/ct6MMBNCSTv

> 
> > Source/WebCore/css/SelectorCheckerTestFunctions.h:185
> > +    if (languageString[languageLength - 1] == '-')
> > +        languageLength += 1;
> 
> This looks very very fishy.
> 
> A length for a buffer should never exceed the buffer size.
> 
> > Source/WebCore/css/SelectorCheckerTestFunctions.h:206
> > +        if (rangeString[rangeLength - 1] == '-')
> > +            rangeLength += 1;
> 
> Very fishy again.

[Darin Adler]

Comment on attachment 245429 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=245429&action=review

This is a fantastic project to do! I will say review+ but I would prefer that this use even more StringView and even less String, although that will require filling out more operations that we can do with StringView.

> Source/WebCore/css/SelectorCheckerTestFunctions.h:135
> +ALWAYS_INLINE bool containslanguageSubtagMatchingRange(const StringView& language, const size_t& languageLength, const StringView& range, size_t& position)

We should always use StringView, not const StringView&.

> Source/WebCore/css/SelectorCheckerTestFunctions.h:139
> +    const String& rangeString = range.toStringWithoutCopying();

We shouldn’t need to make a String here at all. If we define the right set of operations on StringView, then we can avoid the memory allocation entirely. And it helps us fill out the StringView class as needed for future use.

> Source/WebCore/css/SelectorCheckerTestFunctions.h:180
> +    const StringView& languageStringView = language.string();

Just StringView here, not const StringView&.

> Source/WebCore/css/SelectorCheckerTestFunctions.h:181
> +    const size_t& languageLength = languageStringView.length();

Just unsigned here, not const size_t&.

> Source/WebCore/css/SelectorCheckerTestFunctions.h:190
> +        const StringView& rangeStringView = range.string();

Just StringView, not const StringView&.

> Source/WebCore/css/SelectorCheckerTestFunctions.h:194
> +        size_t rangeSubtagsStartIndex = 0;
> +        size_t rangeSubtagsEndIndex = notFound;
> +        size_t lastMatchedLanguageSubtagIndex = 0;
> +        size_t rangeLength = rangeStringView.length();

These should all be unsigned, not size_t.

> Source/WebCore/css/SelectorCheckerTestFunctions.h:204
> +            const StringView& rangeSubtag = rangeStringView.substring(rangeSubtagsStartIndex, rangeSubtagsEndIndex - rangeSubtagsStartIndex);

Just StringView, not const StringView&.

[Benjamin Poulain]

(In reply to comment #9) 
> > Did you measure the before-after this patch on the microbenchmark?
> 
> Before: https://cloudup.com/ckxm_SuTIiO
> After: https://cloudup.com/ct6MMBNCSTv

Nice!

[Dhi Aurrahman]

Created attachment 245816 [details]
Patch

[Dhi Aurrahman]

Created attachment 245833 [details]
Patch

[Dhi Aurrahman]

Created attachment 245834 [details]
Patch

[Dhi Aurrahman]

Comment on attachment 245834 [details]
Patch

I hope it will be fine to add some basic equality comparisons for StringVIew.

[Darin Adler]

Comment on attachment 245834 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=245834&action=review

> Source/WTF/wtf/text/StringView.h:145
> +inline bool equal(StringView, StringView);
> +inline bool equal(StringView, const LChar*);
> +inline bool equal(StringView, const char*);
> +inline bool equalIgnoringASCIICase(StringView, StringView);

The inline keyword should be omitted here. It has no effect.

[Dhi Aurrahman]

Created attachment 245910 [details]
Patch

[WebKit Commit Bot]

Comment on attachment 245910 [details]
Patch

Clearing flags on attachment: 245910

Committed r179532: <http://trac.webkit.org/changeset/179532>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Alexey Proskuryakov]

ASan detected out of bounds access on multiple lang tests today, I suspect this change.

fast/css-generated-content/quotes-lang.html
fast/canvas/imagedata-contains-uint8clampedarray.html
fast/selectors/lang-multiple.html
fast/selectors/lang-inheritance2.html
fast/selectors/lang-specificity-xml.xhtml
fast/selectors/lang-extended-filtering.html
fast/selectors/lang-valid-extended-filtering.html
fast/selectors/lang-extended-filtering-with-string-arguments.html

    #1 0x10d798aa0 in unsigned int WTF::loadUnaligned<unsigned int>(char const*)
    #2 0x10d798981 in WTF::equal(WTF::StringView, unsigned char const*)
    #3 0x10d798861 in WTF::operator==(WTF::StringView, char const*)
    #4 0x10d795166 in WebCore::SelectorChecker::checkOne(WebCore::SelectorChecker::CheckingContextWithStatus const&, WebCore::PseudoIdSet&, WebCore::SelectorChecker::MatchType&, unsigned int&) const
    #5 0x10d791220 in WebCore::SelectorChecker::matchRecursively(WebCore::SelectorChecker::CheckingContextWithStatus const&, WebCore::PseudoIdSet&, unsigned int&) const

[Alexey Proskuryakov]

I don't think that this is an issue with the patch. Filed bug 141258 and bug 141259 for two aspects of the problem.