Bug 146338 – Make the NFA transitions range-based

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

[Benjamin Poulain]

Make the NFA transitions range-based

[Benjamin Poulain]

Created attachment 255619 [details]
Patch

[Alex Christensen]

Initial performance analysis indicates this patch is a huge time and memory improvement.  Here's data from compiling a large content blocker:

                        Without Patch   With Patch
Compiling Time          11.46 Seconds   5.39 Seconds
Memory Used for NFAs    ~20MB           ~16MB
Compiled Bytecode Size  14887063 Bytes  14311716 Bytes

[Benjamin Poulain]

Created attachment 255737 [details]
Patch

[Alex Christensen]

Comment on attachment 255737 [details]
Patch

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

> Source/WebCore/contentextensions/ImmutableNFA.h:127
> +        void debugPrint() const

This and the other print functions should be in #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING

> Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h:99
> +        struct FakeRangeIterator {

This needs to be outside the scope of addTransition to compile successfully on Mavericks.

[Alex Christensen]

Created attachment 255759 [details]
Patch

[Alex Christensen]

After applying this patch and running a large test case, we are spending 5580ms total in compileRuleList.  Of that, 2253ms are spent in NFAtoDFA::convert and 2114ms are spent in DFAMinimizer::minimize.

[WebKit Commit Bot]

Comment on attachment 255759 [details]
Patch

Clearing flags on attachment: 255759

Committed r186079: <http://trac.webkit.org/changeset/186079>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Alex Christensen]

(In reply to comment #2)
> Memory Used for NFAs    ~20MB           ~16MB
Correction: This reduced memory from ~20MB to ~1.6MB. A factor of 10 better than I thought!