Bug 146575 – [Content Extensions] Make the DFA transitions ranges instead of characters

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

[Benjamin Poulain]

[Content Extensions] Make the DFA transitions ranges instead of characters

[Benjamin Poulain]

Created attachment 256075 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/WebCore/contentextensions/DFACombiner.cpp:41:  enum members should use InterCaps with an initial capital letter.  [readability/enum_casing] [4]
ERROR: Source/WebCore/contentextensions/DFACombiner.cpp:42:  enum members should use InterCaps with an initial capital letter.  [readability/enum_casing] [4]
Total errors found: 2 in 16 files


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

[Benjamin Poulain]

Created attachment 256078 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/WebCore/contentextensions/DFACombiner.cpp:41:  enum members should use InterCaps with an initial capital letter.  [readability/enum_casing] [4]
ERROR: Source/WebCore/contentextensions/DFACombiner.cpp:42:  enum members should use InterCaps with an initial capital letter.  [readability/enum_casing] [4]
Total errors found: 2 in 16 files


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

[Alex Christensen]

Comment on attachment 256078 [details]
Patch

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

> Source/WebCore/contentextensions/DFABytecodeCompiler.cpp:208
> +    uint32 fallbackTransitionTarget = std::numeric_limits<uint32>::max();

uint32_t

[Alex Christensen]

This reduces compile time from 22.4 to 6.9 seconds in a large test, reduces byte code size from 26.8MB to 25.3MB, and reduces DFA memory usage from ~32MB to ~6MB. Win Win Win!

[Alex Christensen]

In another large test case, this reduces the compiling time from 5.8 to 4.4 seconds, but increases the byte code size from 14 to 19 MB.

[Benjamin Poulain]

(In reply to comment #7)
> In another large test case, this reduces the compiling time from 5.8 to 4.4
> seconds, but increases the byte code size from 14 to 19 MB.

When comparing the final size, don't forget the previous minimizer was accidentally destroying information. The resulting DFA was not always correct.

The new minimizer always find the smallest DFA and does not fuck up the fallback transition :)

I have an idea to get back some of the size increase in the bytecode.

[Benjamin Poulain]

Created attachment 256125 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/WebCore/contentextensions/DFACombiner.cpp:41:  enum members should use InterCaps with an initial capital letter.  [readability/enum_casing] [4]
ERROR: Source/WebCore/contentextensions/DFACombiner.cpp:42:  enum members should use InterCaps with an initial capital letter.  [readability/enum_casing] [4]
Total errors found: 2 in 16 files


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

[Alex Christensen]

Created attachment 256227 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/WebCore/contentextensions/DFACombiner.cpp:41:  enum members should use InterCaps with an initial capital letter.  [readability/enum_casing] [4]
ERROR: Source/WebCore/contentextensions/DFACombiner.cpp:42:  enum members should use InterCaps with an initial capital letter.  [readability/enum_casing] [4]
Total errors found: 2 in 16 files


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

[Alex Christensen]

Comment on attachment 256227 [details]
Patch

New patch for ews.  Still reviewing minimizer.

[Alex Christensen]

Comment on attachment 256227 [details]
Patch

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

> Source/WebCore/contentextensions/DFAMinimizer.cpp:103
> +        m_sets.append(SetDescriptor { start, size, 0 });

appendUnchecked?

> Source/WebCore/contentextensions/DFAMinimizer.cpp:373
> +            return 1;

This seems a little strange.

> Source/WebCore/contentextensions/DFANode.cpp:80
> +    // Transitions can contains "0" if the expression has a end-of-line marker.

"0" -> '\0'

[Alex Christensen]

http://trac.webkit.org/changeset/186374

[Alex Christensen]

*** Bug 146429 has been marked as a duplicate of this bug. ***