Bug 145572 - Combine tiny DFAs into slightly larger ones
Summary: Combine tiny DFAs into slightly larger ones
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: New Bugs (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Benjamin Poulain
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2015-06-02 15:08 PDT by Benjamin Poulain
Modified: 2015-06-04 18:02 PDT (History)
2 users (show)

See Also:


Attachments
Patch (51.48 KB, patch)
2015-06-02 15:16 PDT, Benjamin Poulain
achristensen: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
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>