-
Notifications
You must be signed in to change notification settings - Fork 1.6k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Slow compilation because of deep inheritance hierarchy. #48011
Comments
Such deep hierarchies are unusual outside of language tests. |
I am trying to use autogenerated DSLs, one of which is generated from a specification for Ansi Escape Codes. Importing it adds a second of overhead to each execution of I'm experiencing the same overhead with multiple other DSLs which prevents me from using them without having to worry about compilation time overhead.
Yes, I believe you're right. This is just one example that seems to reproduce one of my bottlenecks, but I'm not entirely sure. Do you know of any other flags that would provide more detail for these two measurements?
|
Running C on earlier dart releases: 6.40s user 0.18s system 103% cpu 6.361 total 0.93s user 0.18s system 168% cpu 0.656 total 0.14s user 0.04s system 116% cpu 0.153 total |
Some algorithms in the CFE might have quadratic complexity (with respect to the depth of the hierarchy) /cc @johnniwinther IIRC Dart 1 VM was very lazy at parsing and finalising classes so unless you actually instantiate the class you are paying very little for the declaration itself.
I'd say ever since Dart 2 we landed in a very unfortunately spot with fidelity of the Sadly we have never found time to sit down and address this somehow. (e.g. building persistent modular / incremental compilation into the CLI) |
We recently discovered (and removed) a quadratic implementation for checking the class hierarchy for cycles (https://dart-review.googlesource.com/c/sdk/+/221820). I believe that |
...for many implements. #48011 Change-Id: Id654864a2929981f5771fe491fa811d123daabcd Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/226684 Reviewed-by: Johnni Winther <johnniwinther@google.com> Commit-Queue: Jens Johansen <jensj@google.com>
This should be fixed in the CFE. I don't know if there's anything to be done on the dart2js side? |
dart2js still has a slow phase:
|
I'm happy to confirm that with
I'm also seeing a consistent ~10% improvement in compilation time (for the vm) on some other code that motivated this issue. Thank you @jensjoha & @johnniwinther! |
The sdk/pkg/front_end/lib/src/api_unstable/dart2js.dart Lines 164 to 172 in 90542c2
A verbose flag must be set, it defaults to false. Here's what will be reported with verbose set to true: generateKernelInternal metrics for big_deep.dart
|
I'm closing this issue because it is stale. The issue presented here was fixed for the DartVM target. Note: incremental compilation using either the -r flag or packages like fire helps here. |
This issue is about the compiler being slow when given a program with a deep inheritance hierarchy.
A: 1000 classes with a single parent
dart big_wide.dart 0.60s user 0.19s system 146% cpu 0.536 total
big_wide.dart
B: 1000 classes with no parent
dart big_disconnected.dart 0.51s user 0.17s system 141% cpu 0.480 total
big_disconnected.dart
C: 1000 classes linked-list-style
dart big_deep.dart 6.21s user 0.21s system 104% cpu 6.156 total
big_deep.dart
D: big_deep.dart via dart2js
dart2js big_deep.dart --verbose 14.97s user 0.55s system 107% cpu 14.387 total
The text was updated successfully, but these errors were encountered: