Bug 145572

Summary: Combine tiny DFAs into slightly larger ones
Product: WebKit Reporter: Benjamin Poulain <benjamin>
Component: New BugsAssignee: Benjamin Poulain <benjamin>
Status: RESOLVED FIXED    
Severity: Normal CC: achristensen, commit-queue
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Attachments:
Description Flags
Patch achristensen: review+

Description Benjamin Poulain 2015-06-02 15:08:53 PDT
Combine tiny DFAs into slightly larger ones
Comment 1 Benjamin Poulain 2015-06-02 15:16:05 PDT
Created attachment 254109 [details]
Patch
Comment 2 WebKit Commit Bot 2015-06-02 15:19:17 PDT
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.
Comment 3 Alex Christensen 2015-06-02 20:03:48 PDT
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.
Comment 4 Benjamin Poulain 2015-06-02 20:33:35 PDT
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.
Comment 5 Alex Christensen 2015-06-02 23:31:17 PDT
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
Comment 6 Alex Christensen 2015-06-03 14:25:26 PDT
Comment on attachment 254109 [details]
Patch

Let's land this.  We can always disable or tweak when we combine small DFAs to help performance.
Comment 7 Benjamin Poulain 2015-06-04 18:02:24 PDT
Committed r185230: <http://trac.webkit.org/changeset/185230>