Bug 199959 - [JSC] Remove quadratic complexity algorithm in AI structure transition tracking
Summary: [JSC] Remove quadratic complexity algorithm in AI structure transition tracking
Status: NEW
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Yusuke Suzuki
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2019-07-19 14:02 PDT by Yusuke Suzuki
Modified: 2019-07-20 10:09 PDT (History)
2 users (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Yusuke Suzuki 2019-07-19 14:02:48 PDT
Keith pointed one good idea, converting O(N^2) to O(2N) where N is # of DFG nodes in a basic block.
It's worth trying!
Comment 1 Yusuke Suzuki 2019-07-19 14:14:17 PDT
I believe this improves compile time of JetStream2/octane-zlib.
I'm pretty sure that one of JetStream2/octane-zlib function takes very long time to be compiled and it blocks DFG compilation pipeline and effectively blocks the following compile requests for small hot functions.
Comment 2 Yusuke Suzuki 2019-07-19 14:20:02 PDT
When I added AI mitigation to my working copy, CNN page is improved, but still it was laggy.
So, fixing AI algorithm does not offer much for CNN page. CNN page's script is huge, and anyway we should not handle it in DFG.
I think reducing the threshold is the right way to fix CNN page.

On the other hand, we have another compile time problem in JetStream2/octane-zlib.
I know that one of JetStream2/octane-zlib function takes very long time to be compiled and it blocks subsequent DFG compilation requests for small hot functions.
Interestingly, according to the A/B test, the above AI mitigation has performance problem in JetStream2/octane-zlib.
This fact means that JetStream2/octane-zlib has very large basic block which has PutStructure etc., but if we do conservative analysis onto that, it largely regressed the performance of JetStream2/octane-zlib.
So, if we want to improve compile time in JetStream2/octane-zlib, fixing AI algorithm is the right choice.