Tweaks to improve performance of type-inference.

Tweaks to improve performance of type-inference.
- short-circuit cases where join yields dynamic
- improve performance of some queries like `hasOnlySubclasses` and how `contains` is implemented in `flatten`. We could also add caching for `length`, but not sure if we want to just have a static map or precompute the data in the class-hierarchy nodes.

On my experiments this reduces inference times more than 50% on a large customer app, while small apps have almost no change.

R=johnniwinther@google.com, sra@google.com

Committed: https://github.com/dart-lang/sdk/commit/913ca6683412d4e770bf9c1132b721a59f7e3e34

[Siggi Cherem (dart-lang), 2015-12-16 04:29:10]

Description was changed from

==========
Tweaks to improve performance of type-inference.
- short-circuit cases where join yield dynamic
- improve performance of some queries to the world used in flatten including
`contains`, `hasOnlySubclasses`, and possibly `length` (compare patchset 1 and
patchset 2 and let me know what you think).

On my experiments this reduces inference times by 40% on large apps, small apps
have almost no change.
==========

to

==========
Tweaks to improve performance of type-inference.
- short-circuit cases where join yields dynamic
- improve performance of some queries like `hasOnlySubclasses` and how
`contains` is implemented in `flatten`. We could also add caching for `length`,
but not sure if we want to just have a static map or precompute the data in the
class-hierarchy nodes.

On my experiments this reduces inference times more than 50% on a large customer
app, while small apps have almost no change.
==========

[Siggi Cherem (dart-lang), 2015-12-16 04:31:21]

sigmund@google.com changed reviewers:
+ johnniwinther@google.com, sra@google.com

[sra1, 2015-12-16 05:06:17]

lgtm

https://codereview.chromium.org/1528953002/diff/40001/pkg/compiler/lib/src/in...
File pkg/compiler/lib/src/inferrer/type_graph_inferrer.dart (right):

https://codereview.chromium.org/1528953002/diff/40001/pkg/compiler/lib/src/in...
pkg/compiler/lib/src/inferrer/type_graph_inferrer.dart:546: for (TypeMask mask
in masks) {
what is the input iterable?
If its is mapped, this could be made cheaper by collecting values in the first
scan.

[Johnni Winther, 2015-12-16 09:07:08]

lgtm

https://codereview.chromium.org/1528953002/diff/40001/pkg/compiler/lib/src/in...
File pkg/compiler/lib/src/inferrer/type_graph_inferrer.dart (right):

https://codereview.chromium.org/1528953002/diff/40001/pkg/compiler/lib/src/in...
pkg/compiler/lib/src/inferrer/type_graph_inferrer.dart:547: newType =
newType.union(mask, classWorld);
How about:

TypeMask newType;
for (TypeMask mask in masks) {
  if (newType == null) {
    newType = mask;
  } else {
    newType = newType.union(mask, classWorld);
  }
  ...
}
return newType ?? const TypeMask.nonNullEmpty();

to avoid union of empty and the first mask.

Maybe also avoid unions where [newType] is empty.

https://codereview.chromium.org/1528953002/diff/40001/pkg/compiler/lib/src/ty...
File pkg/compiler/lib/src/types/union_type_mask.dart (right):

https://codereview.chromium.org/1528953002/diff/40001/pkg/compiler/lib/src/ty...
pkg/compiler/lib/src/types/union_type_mask.dart:121: size =
classWorld.strictSubclassesOf(candidate).length;
This is easily cachable in ClassHierarchyNode. Will make a CL.

https://codereview.chromium.org/1528953002/diff/40001/pkg/compiler/lib/src/wo...
File pkg/compiler/lib/src/world.dart (right):

https://codereview.chromium.org/1528953002/diff/40001/pkg/compiler/lib/src/wo...
pkg/compiler/lib/src/world.dart:312: bool hasOnlySubclasses(ClassElement cls) {
Add a TODO for me to move this to [ClassSet].

[Siggi Cherem (dart-lang), 2015-12-17 00:46:18]

Patchset #4 (id:60001) has been deleted

[Siggi Cherem (dart-lang), 2015-12-17 00:50:20]

Patchset #4 (id:80001) has been deleted

[Siggi Cherem (dart-lang), 2015-12-17 01:02:57]

thanks!

https://codereview.chromium.org/1528953002/diff/40001/pkg/compiler/lib/src/in...
File pkg/compiler/lib/src/inferrer/type_graph_inferrer.dart (right):

https://codereview.chromium.org/1528953002/diff/40001/pkg/compiler/lib/src/in...
pkg/compiler/lib/src/inferrer/type_graph_inferrer.dart:546: for (TypeMask mask
in masks) {
On 2015/12/16 05:06:17, sra1 wrote:
> what is the input iterable?
> If its is mapped, this could be made cheaper by collecting values in the first
> scan.

Done. It's mapped, although I couldn't observe any extra savings here since the
operation was just reading a field (see call in line 537).

https://codereview.chromium.org/1528953002/diff/40001/pkg/compiler/lib/src/in...
pkg/compiler/lib/src/inferrer/type_graph_inferrer.dart:547: newType =
newType.union(mask, classWorld);
On 2015/12/16 09:07:08, Johnni Winther wrote:
> How about:
> 
> TypeMask newType;
> for (TypeMask mask in masks) {
>   if (newType == null) {
>     newType = mask;
>   } else {
>     newType = newType.union(mask, classWorld);
>   }
>   ...
> }
> return newType ?? const TypeMask.nonNullEmpty();
> 
> to avoid union of empty and the first mask.
> 
> Maybe also avoid unions where [newType] is empty.

Done. Also not much savings from this: empty is handled efficiently already
(e.g. FlatTypeMask.empty knows to return the other mask, and the union operation
skips empty masks too).

https://codereview.chromium.org/1528953002/diff/40001/pkg/compiler/lib/src/ty...
File pkg/compiler/lib/src/types/union_type_mask.dart (right):

https://codereview.chromium.org/1528953002/diff/40001/pkg/compiler/lib/src/ty...
pkg/compiler/lib/src/types/union_type_mask.dart:121: size =
classWorld.strictSubclassesOf(candidate).length;
On 2015/12/16 09:07:08, Johnni Winther wrote:
> This is easily cachable in ClassHierarchyNode. Will make a CL.

Nice.

https://codereview.chromium.org/1528953002/diff/40001/pkg/compiler/lib/src/wo...
File pkg/compiler/lib/src/world.dart (right):

https://codereview.chromium.org/1528953002/diff/40001/pkg/compiler/lib/src/wo...
pkg/compiler/lib/src/world.dart:312: bool hasOnlySubclasses(ClassElement cls) {
On 2015/12/16 09:07:08, Johnni Winther wrote:
> Add a TODO for me to move this to [ClassSet].

Done.

https://codereview.chromium.org/1528953002/diff/120001/pkg/compiler/lib/src/i...
File pkg/compiler/lib/src/inferrer/type_graph_inferrer.dart (right):

https://codereview.chromium.org/1528953002/diff/120001/pkg/compiler/lib/src/i...
pkg/compiler/lib/src/inferrer/type_graph_inferrer.dart:551: if
(mask.containsAll(classWorld)) return dynamicType;
note: i reverted a change I did here: instead of `mask == dynamicType` I'm
checking `mask.containsAll(world)`. Turns out that doing == dyanmicType is more
precise (we can preserve non-null on joins).

I switched back to remain consistent with the previous semantics and keep this
CL just about optimizations. I added a TODO for now. I might send out a separate
CL changing that.

[Siggi Cherem (dart-lang), 2015-12-17 01:03:49]

Description was changed from

==========
Tweaks to improve performance of type-inference.
- short-circuit cases where join yields dynamic
- improve performance of some queries like `hasOnlySubclasses` and how
`contains` is implemented in `flatten`. We could also add caching for `length`,
but not sure if we want to just have a static map or precompute the data in the
class-hierarchy nodes.

On my experiments this reduces inference times more than 50% on a large customer
app, while small apps have almost no change.
==========

to

==========
Tweaks to improve performance of type-inference.
- short-circuit cases where join yields dynamic
- improve performance of some queries like `hasOnlySubclasses` and how
`contains` is implemented in `flatten`. We could also add caching for `length`,
but not sure if we want to just have a static map or precompute the data in the
class-hierarchy nodes.

On my experiments this reduces inference times more than 50% on a large customer
app, while small apps have almost no change.

R=johnniwinther@google.com, sra@google.com

Committed:
https://github.com/dart-lang/sdk/commit/913ca6683412d4e770bf9c1132b721a59f7e3e34
==========

[Siggi Cherem (dart-lang), 2015-12-17 01:03:50]

Committed patchset #5 (id:120001) manually as
913ca6683412d4e770bf9c1132b721a59f7e3e34 (presubmit successful).