Bug 146338 - Make the NFA transitions range-based
Summary: Make the NFA transitions range-based
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-26 00:13 PDT by Benjamin Poulain
Modified: 2015-06-29 14:03 PDT (History)
3 users (show)

See Also:


Attachments
Patch (86.32 KB, patch)
2015-06-26 00:20 PDT, Benjamin Poulain
no flags Details | Formatted Diff | Diff
Patch (137.56 KB, patch)
2015-06-28 23:17 PDT, Benjamin Poulain
no flags Details | Formatted Diff | Diff
Patch (136.09 KB, patch)
2015-06-29 10:36 PDT, Alex Christensen
no flags 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-26 00:13:51 PDT
Make the NFA transitions range-based
Comment 1 Benjamin Poulain 2015-06-26 00:20:03 PDT
Created attachment 255619 [details]
Patch
Comment 2 Alex Christensen 2015-06-26 14:16:21 PDT
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
Comment 3 Benjamin Poulain 2015-06-28 23:17:39 PDT
Created attachment 255737 [details]
Patch
Comment 4 Alex Christensen 2015-06-29 10:29:28 PDT
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.
Comment 5 Alex Christensen 2015-06-29 10:36:08 PDT
Created attachment 255759 [details]
Patch
Comment 6 Alex Christensen 2015-06-29 11:31:04 PDT
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.
Comment 7 WebKit Commit Bot 2015-06-29 12:41:08 PDT
Comment on attachment 255759 [details]
Patch

Clearing flags on attachment: 255759

Committed r186079: <http://trac.webkit.org/changeset/186079>
Comment 8 WebKit Commit Bot 2015-06-29 12:41:12 PDT
All reviewed patches have been landed.  Closing bug.
Comment 9 Alex Christensen 2015-06-29 14:03:08 PDT
(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!