Bug 145572 – Combine tiny DFAs into slightly larger ones

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

[Benjamin Poulain]

Combine tiny DFAs into slightly larger ones

[Benjamin Poulain]

Created attachment 254109 [details]
Patch

[WebKit Commit Bot]

Attachment 254109 [details] did not pass style-queue:


ERROR: Tools/TestWebKitAPI/Tests/WebCore/DFAHelpers.h:31:  Do not use 'using namespace WebCore;'.  [build/using_namespace] [4]
ERROR: Source/WebCore/contentextensions/DFACombiner.cpp:86:  enum members should use InterCaps with an initial capital letter.  [readability/enum_casing] [4]
ERROR: Source/WebCore/contentextensions/DFACombiner.cpp:87:  enum members should use InterCaps with an initial capital letter.  [readability/enum_casing] [4]
Total errors found: 3 in 16 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Alex Christensen]

Comment on attachment 254109 [details]
Patch

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

This seems good.  I'll have to look closer later.

> Source/WebCore/contentextensions/DFA.cpp:130
> +unsigned DFA::graphSize() const

I think there are places where we use nodes.size().  Put a FIXME: make nodes private

> Source/WebCore/contentextensions/DFACombiner.cpp:53
> +            memset(m_transitionTargets, 0xff, sizeof(m_transitionTargets));

0xFF

> Source/WebCore/contentextensions/DFACombiner.cpp:83
> +    uint32_t invalidNodeIndex = 0xffffffff;

const, capital F's here and elsewhere.

> Source/WebCore/contentextensions/DFACombiner.cpp:87
> +    enum class WhichDFA {
> +        A,
> +        B

Are there really not better names than this?

> Source/WebCore/contentextensions/DFACombiner.cpp:253
> +            // Minimizing is somewhat expensive. We only do it in bulk when we reach the threshold
> +            // to reduce the load.

I think we should always minimize combined DFAs unless it is catastrophic.

[Benjamin Poulain]

Comment on attachment 254109 [details]
Patch

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

>> Source/WebCore/contentextensions/DFACombiner.cpp:253
>> +            // to reduce the load.
> 
> I think we should always minimize combined DFAs unless it is catastrophic.

We do minimize them systematically, but only after they got big.

If we do it at every step, it doubles compile time for no additional gain.

[Alex Christensen]

Comment on attachment 254109 [details]
Patch

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

I'm not entirely convinced that fewer DFAs is worth the additional memory used for the byte code size.  I think this patch might hurt overall performance.

> Source/WebCore/contentextensions/ContentExtensionCompiler.cpp:252
> +    auto lowerFiltersWithoutDomainsDFAToBytecode = [&](DFA&& dfa)

This should probably be refactored even more.  This is almost identical to lowerFiltersWithDomainsDFAToBytecode

[Alex Christensen]

Comment on attachment 254109 [details]
Patch

Let's land this.  We can always disable or tweak when we combine small DFAs to help performance.

[Benjamin Poulain]

Committed r185230: <http://trac.webkit.org/changeset/185230>