[ES6 modules] UninstantiatedInclusiveDescendants: skip recursion for instantiated sub-trees.

[ES6 modules] UninstantiatedInclusiveDescendants: skip recursion for instantiated sub-trees.

Before this CL, UninstantiatedInclusiveDescendants enumerated all descendants
of the given module, even for instantiated sub trees.

This CL speeds up computation of UninstantiatedInclusiveDescendants by skipping
instantiated sub trees, where we can guarantee that all its descendants state
are already "instantiated", and would never end up in the "uninstantiated
descendants set".

BUG=594639, 722728

[kouhei (in TOK), 2017-05-16 20:04:23]

kouhei@chromium.org changed reviewers:
+ domenic@chromium.org, hiroshige@chromium.org, module-dev@chromium.org,
neis@chromium.org

[kouhei (in TOK), 2017-05-16 20:04:47]

The CQ bit was checked by kouhei@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-05-16 20:06:37]

Dry run: CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-05-17 04:34:05]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-05-17 04:34:06]

Dry run: Try jobs failed on following builders:
  win_chromium_rel_ng on master.tryserver.chromium.win (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_rel_...)

[neis, 2017-05-17 09:41:13]

I doubt this change is correct. It looks to me like you're short-cutting the
very code that is responsible for
establishing the invariant in the first place.

[kouhei (in TOK), 2017-05-17 23:40:08]

On 2017/05/17 09:41:13, neis wrote:
> I doubt this change is correct. It looks to me like you're short-cutting the
> very code that is responsible for
> establishing the invariant in the first place.

While I agree that this change is scary, we do need to cut down the number of
module graph nodes we visit while instantiate, otherwise we are stuck at O(n^2).
If you could help me with a failure case and/or alternate optimization, I'd
really appreciate it.

[blink-reviews, 2017-05-18 13:13:38]

I believe this part of the algorithm will simply disappear with the
upcoming specification changes, so maybe it's best to wait for that.

On Thu, May 18, 2017 at 1:40 AM,  <kouhei@chromium.org> wrote:
> On 2017/05/17 09:41:13, neis wrote:
>> I doubt this change is correct. It looks to me like you're short-cutting
>> the
>> very code that is responsible for
>> establishing the invariant in the first place.
>
> While I agree that this change is scary, we do need to cut down the number
> of
> module graph nodes we visit while instantiate, otherwise we are stuck at
> O(n^2).
> If you could help me with a failure case and/or alternate optimization, I'd
> really appreciate it.
>
> https://codereview.chromium.org/2890593002/

-- 
You received this message because you are subscribed to the Google Groups "Blink
Reviews" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to blink-reviews+unsubscribe@chromium.org.

[chromium-reviews, 2017-05-18 13:13:38]

I believe this part of the algorithm will simply disappear with the
upcoming specification changes, so maybe it's best to wait for that.

On Thu, May 18, 2017 at 1:40 AM,  <kouhei@chromium.org> wrote:
> On 2017/05/17 09:41:13, neis wrote:
>> I doubt this change is correct. It looks to me like you're short-cutting
>> the
>> very code that is responsible for
>> establishing the invariant in the first place.
>
> While I agree that this change is scary, we do need to cut down the number
> of
> module graph nodes we visit while instantiate, otherwise we are stuck at
> O(n^2).
> If you could help me with a failure case and/or alternate optimization, I'd
> really appreciate it.
>
> https://codereview.chromium.org/2890593002/

-- 
You received this message because you are subscribed to the Google Groups
"Chromium-reviews" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to chromium-reviews+unsubscribe@chromium.org.