Bug 132546 – CSS JIT: reduce cost of computing backtracking height

• Status: RESOLVED
• Resolution: FIXED
• Component: CSS

[Yusuke Suzuki]

Because compiler previously compute backtracking height for previous child fragment,
by leveraging this, we can limit the `maxPrefixSize` for `computeBacktrackingHeightFromDescendant`.

For example, consider selector "A>B>C>D>E>F G"'s descendant chain, "A>B>C>D>E>F".

In the case of <B>, we calculate the backtracking height such as,

pattern:    [B, C, D, E, F]
candidate0: [C, D, E, F]      => not matched
candidate1: [D, E, F]         => not matched
candidate2: [E, F]            => matched

At this time, first candidate (0)'s pattern size is `pattern.size() - 1`.
And get backtracking height from descendant 3 `pattern.size() - candidate.size()`.

And next, in the case of <A>, we re-calcucate the backtracking height such as,

pattern:    [A, B, C, D, E, F]
candidate0: [B, C, D, E, F]      => not matched
candidate1: [C, D, E, F]         => not matched
candidate2: [D, E, F]            => not matched
candidate3: [E, F]               => matched

But we should known that candidate0 ~ candidate1 always fail because part of these patterns are already calculated in <B>'s case and we know that doesn't match.

So in the case of <A>, we should start this computation from candidate2, such as,

pattern:    [A, B, C, D, E, F]
candidate2: [D, E, F]            => not matched
candidate3: [E, F]               => matched

We can start computation with candidate size = `currentPattern.size() - previousChildFragmentBacktrackingHeightFromDescendant`. In this example, `currentPattern.size()` is 6 and `previousChildFragmentBacktrackingHeightFromDescendant` is 3, so candidate size is `3`.

[Yusuke Suzuki]

Created attachment 230789 [details]
Patch

[Benjamin Poulain]

Comment on attachment 230789 [details]
Patch

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

Sorry, I only had a quick look, I had two crazy days.

I see what you are going for here, but I am a little puzzled by the change log. Can you explain from the comment bellow?

One little thing that would be nice in the changelog is explaining that your reasoning also applies for tagNameNotMatchedBacktrackingStartHeightFromDescendant because the subset before the "not matched" must have matched.

> Source/WebCore/ChangeLog:13
> +        For example, consider selector "A>B>C>D>E>F G"'s descendant chain,
> +        "A>B>C>D>E>F".

I am somewhat confused by the example...

> Source/WebCore/ChangeLog:17
> +        pattern:    [B, C, D, E, F]

Shouldn't the pattern be [F, E, D, C, B, A]?

> Source/WebCore/ChangeLog:20
> +        candidate2: [E, F]            => matched

You lost me here, why is [E, F] a matching "prefix"?

> Source/WebCore/cssjit/SelectorCompiler.cpp:719
> +    for (unsigned largestPrefixSize = maxPrefixSize; largestPrefixSize > 0; largestPrefixSize--) {

Traditionally, in Webkit we prefer the prefix increment/decrement instead of suffix operations (because of iterators).

It really does not matter here, this is just for info.

> Source/WebCore/cssjit/SelectorCompiler.cpp:757
> +            RELEASE_ASSERT(tagNames.size() >= previousChildFragmentInDescendantBacktrackingChain->tagNameMatchedBacktrackingStartHeightFromDescendant);

Ensuring there is no overflow here is a great use of RELEASE_ASSERT :)

[Yusuke Suzuki]

Comment on attachment 230789 [details]
Patch

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

>> Source/WebCore/ChangeLog:17
>> +        pattern:    [B, C, D, E, F]
> 
> Shouldn't the pattern be [F, E, D, C, B, A]?

Since we now considers about <B>'s backtracking. <A> is not included in tagNames pattern vector.
In the implementation detail, this vector is [F, E, D, C, B], but to follow the fragment's order in the selector, we describe it as [B, C, D, E, F] now.

>> Source/WebCore/ChangeLog:20
>> +        candidate2: [E, F]            => matched
> 
> You lost me here, why is [E, F] a matching "prefix"?

In this example, "A" doesn't represent actual tag "A". "A" is an identifier for this fragment. Actually, "A" may be "div".
In this time, we assume that prefix [E, F] matches to the [B, C] in this example to show the subsequent matching example.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:719
>> +    for (unsigned largestPrefixSize = maxPrefixSize; largestPrefixSize > 0; largestPrefixSize--) {
> 
> Traditionally, in Webkit we prefer the prefix increment/decrement instead of suffix operations (because of iterators).
> 
> It really does not matter here, this is just for info.

Thank you! I also prefer the prefix inc/dec because of C++ iterators, I don't know WebKit also prefer it!
I'll change it.

[Yusuke Suzuki]

/I don't know/I didn't know/s
Oops, mistyped. Sorry for my poor English.

[Yusuke Suzuki]

Created attachment 231146 [details]
Patch

[Darin Adler]

Can we produce a performance test for this that shows the benefit?

[Benjamin Poulain]

Comment on attachment 231146 [details]
Patch

Looks good to me.

[WebKit Commit Bot]

Comment on attachment 231146 [details]
Patch

Clearing flags on attachment: 231146

Committed r168606: <http://trac.webkit.org/changeset/168606>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.