dart-lang / dart_style

An opinionated formatter/linter for Dart code
https://pub.dev/packages/dart_style
BSD 3-Clause "New" or "Revised" License
645 stars 117 forks source link

Bind pieces based on page width during formatting. #1455

Closed munificent closed 3 months ago

munificent commented 3 months ago

One important optimization to avoid trying a bunch of dead end solutions is to see if we can eagerly determine that a piece will always end up in some state based on just the size of its contents and the page width. In order to apply that optimization, we walk the piece tree when constructing the solution and ask each piece if it can be eagerly bound.

Unfortunately, that traversal itself has significant overhead:

Times (ms)
AstNodeVisitor build Piece tree               =    777.852
AstNodeVisitor.run()                          =   4166.931
CodeWriter.format() write separate piece text =     46.461
PieceWriter.finish() format piece tree        =   3383.440
Solution bind by page width                   =    442.435
Solution.mergeSubtree()                       =    110.427
Solver dequeue                                =     74.833
Solver enqueue                                =     58.036
Whole enchilada                               =   5147.055

That's the "Solution bind by page width" step here.

This PR gets rid of the separate eager traversal. Instead, when we reach a piece during formatting, if it isn't already bound, we try the eager binding optimization then. That yields:

Times (ms)
AstNodeVisitor build Piece tree               =    790.935
AstNodeVisitor.run()                          =   3944.811
CodeWriter try to bind by page width          =    145.603
CodeWriter.format() write separate piece text =     45.283
PieceWriter.finish() format piece tree        =   3151.060
Solution.mergeSubtree()                       =    119.708
Solver dequeue                                =     74.775
Solver enqueue                                =     56.464
Whole enchilada                               =   4813.870

The binding step is now "CodeWriter try to bind by page width" and is much faster.

This improves the overall performance when formatting the Flutter repo from 3.575s to 3.325s, or 7.5% faster. Some of the benchmarks show a more significant improvement:

Benchmark (tall)                fastest   median  slowest  average  baseline
-----------------------------  --------  -------  -------  -------  --------
block                             0.076    0.079    0.151    0.083    119.1%
chain                             2.505    2.536    2.616    2.538     99.0%
collection                        0.161    0.169    0.316    0.175    115.3%
collection_large                  0.910    0.955    1.033    0.954    131.0%
flutter_popup_menu_test           0.466    0.483    0.774    0.494    117.3%
flutter_scrollbar_test            0.149    0.154    0.184    0.156    155.3%
function_call                     1.497    1.534    1.678    1.537    132.9%
infix_large                       1.525    1.552    1.624    1.555    111.4%
infix_small                       0.315    0.327    0.356    0.329    116.7%
interpolation                     0.107    0.113    0.239    0.121    113.6%
large                             4.648    4.750    5.032    4.755    121.2%
top_level                         0.256    0.264    0.340    0.269    104.7%

Not bad for a small code change.