Optimize splitting lines with many rules.

Optimize splitting lines with many rules.

The constraint checking was quadratic in the number of rules in the
line which is bad on pathologically long lines like #456.

This gets it back down to linear. It takes that bug from 7 minutes to
about 20 seconds on my machine. The benchmark, which is closer to real
code, gets about 20% faster.

I'm still leaving #456 open because I think there's more work to be
done there, but this is a solid improvement overall.

R=kevmoo@google.com

Committed: https://github.com/dart-lang/dart_style/commit/10ad66e2915f8760aa0c07fac47f2fd7474b2b88

[Bob Nystrom, 2015-11-09 23:03:16]

rnystrom@google.com changed reviewers:
+ kevmoo@google.com

[kevmoo, 2015-11-09 23:40:47]

LGTM w/ a question

Also: self-format – I saw a weird update to lib/src/dart_formatter.dart – check
it out

https://codereview.chromium.org/1418483008/diff/1/lib/src/line_splitting/solv...
File lib/src/line_splitting/solve_state.dart (right):

https://codereview.chromium.org/1418483008/diff/1/lib/src/line_splitting/solv...
lib/src/line_splitting/solve_state.dart:504: _constraints = {};
QQ: does order matter here? Would using HashMap from dart:collection improve
perf?

https://codereview.chromium.org/1418483008/diff/1/lib/src/line_splitting/solv...
lib/src/line_splitting/solve_state.dart:531: _unboundConstraints = {};
ditto RE HashMap

[Bob Nystrom, 2015-11-10 20:08:05]

Committed patchset #1 (id:1) manually as
10ad66e2915f8760aa0c07fac47f2fd7474b2b88 (presubmit successful).

[Bob Nystrom, 2015-11-10 20:08:24]

https://codereview.chromium.org/1418483008/diff/1/lib/src/line_splitting/solv...
File lib/src/line_splitting/solve_state.dart (right):

https://codereview.chromium.org/1418483008/diff/1/lib/src/line_splitting/solv...
lib/src/line_splitting/solve_state.dart:504: _constraints = {};
On 2015/11/09 23:40:46, kevmoo wrote:
> QQ: does order matter here? Would using HashMap from dart:collection improve
> perf?

Nope. No measurable improvement.

https://codereview.chromium.org/1418483008/diff/1/lib/src/line_splitting/solv...
lib/src/line_splitting/solve_state.dart:531: _unboundConstraints = {};
On 2015/11/09 23:40:46, kevmoo wrote:
> ditto RE HashMap

Acknowledged.