Bug 146961 – [Content extensions] Combine suffixes when generating NFAs

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Benjamin Poulain]

[Content extensions] Combine suffixes when generating NFAs

[Benjamin Poulain]

Created attachment 256827 [details]
Patch

[Alex Christensen]

Comment on attachment 256827 [details]
Patch

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

> Source/WebCore/ChangeLog:14
> +        have the same trailing NFA nodes for both side of the disjunction.

sides

> Source/WebCore/ChangeLog:46
> +        Overall, I get the following gains:

Awesome.  Where are these gains coming from?  Is the DFA minimization faster, or NFA to DFA faster, or both?

> Source/WebCore/ChangeLog:50
> +        -Armand's test cse:

case

> Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:70
> -    EXPECT_EQ(static_cast<size_t>(13), countLiveNodes(dfa));
> +    EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
>      dfa.minimize();
>      EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));

A lot of these minimization tests don't do anything now.  Could you add some cases where the minimizer still does a lot of the work?

[Benjamin Poulain]

Comment on attachment 256827 [details]
Patch

(In reply to comment #2)
> > Source/WebCore/ChangeLog:46
> > +        Overall, I get the following gains:
> 
> Awesome.  Where are these gains coming from?  Is the DFA minimization
> faster, or NFA to DFA faster, or both?

The compile time is improved because the DFA have less redundancy. This makes NFA-to-DFA and Minimization simpler.

The memory gains are due to combining more patterns into NFAs.

> > Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:70
> > -    EXPECT_EQ(static_cast<size_t>(13), countLiveNodes(dfa));
> > +    EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
> >      dfa.minimize();
> >      EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
> 
> A lot of these minimization tests don't do anything now.  Could you add some
> cases where the minimizer still does a lot of the work?

That's a good point. I'll add new test cases.

[Benjamin Poulain]

Created attachment 256859 [details]
Patch

[Benjamin Poulain]

Created attachment 256869 [details]
Patch

[Alex Christensen]

I measured a large test case on a device and this cut the compiling time in half, and the max memory usage stayed almost exactly the same.

[Alex Christensen]

Comment on attachment 256869 [details]
Patch

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

> Source/WebCore/contentextensions/Term.h:646
> -        for (unsigned i = 1; i < m_atomData.group.terms.size(); ++i) {
> +        for (unsigned i = 1; i < m_atomData.group.terms.size() - 1; ++i) {

Why is the last one a special case?

[Benjamin Poulain]

Comment on attachment 256869 [details]
Patch

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

>> Source/WebCore/contentextensions/Term.h:646
>> +        for (unsigned i = 1; i < m_atomData.group.terms.size() - 1; ++i) {
> 
> Why is the last one a special case?

The generateGraph() for the last one is not one that generate a new node, it is one that generate transitions to an existing node.

[Radar WebKit Bug Importer]

<rdar://problem/21863296>

[Benjamin Poulain]

Committed r186910: <http://trac.webkit.org/changeset/186910>