Guard more thoroughly against stack overflows in the backtracking version solver.

Guard more thoroughly against stack overflows in the backtracking version solver.

R=rnystrom@google.com

Committed: https://code.google.com/p/dart/source/detail?r=22200

[Bob Nystrom, 2013-04-30 20:27:54]

I'm personally not too crazy about this. This can end up doing a lot of
thrashing on the event loop which might have negative perf. I also find
reasoning about the code that calls resetStack() really difficult.

Is this really better than just having the backtracking solver use an explicit
completer?

https://codereview.chromium.org/14673004/diff/1/sdk/lib/_internal/pub/lib/src...
File sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/14673004/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:179:
.catchError((error) => new Future.error(error));
Given the above resetStack, why are these needed?

https://codereview.chromium.org/14673004/diff/1/sdk/lib/_internal/pub/lib/src...
File sdk/lib/_internal/pub/lib/src/utils.dart (right):

https://codereview.chromium.org/14673004/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/utils.dart:405: runAsync(() =>
completer.complete(val));
If we're using new Future(), is runAsync still needed?

[nweiz, 2013-04-30 20:46:00]

> I'm personally not too crazy about this. This can end up doing a lot of
thrashing on the event loop which might have negative perf.

If the solver doesn't go exponential, any perf hit here will be dwarfed by our
HTTP requests. If it does go exponential, perf is already shot, and a small
additional constant factor won't make much of a difference.

Also, keep in mind that we're doing way more event loop thrashing than this in
our scheduled tests, and those are reasonably performant as long as we don't
capture stack traces.

> I also find reasoning about the code that calls resetStack() really difficult.

The external semantics are exactly the same as [new Future].

> Is this really better than just having the backtracking solver use an explicit
completer?

Oh goodness yes.

https://codereview.chromium.org/14673004/diff/1/sdk/lib/_internal/pub/lib/src...
File sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/14673004/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:179:
.catchError((error) => new Future.error(error));
On 2013/04/30 20:27:54, Bob Nystrom wrote:
> Given the above resetStack, why are these needed?

Left over from trying an alternative solution.

https://codereview.chromium.org/14673004/diff/1/sdk/lib/_internal/pub/lib/src...
File sdk/lib/_internal/pub/lib/src/utils.dart (right):

https://codereview.chromium.org/14673004/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/utils.dart:405: runAsync(() =>
completer.complete(val));
On 2013/04/30 20:27:54, Bob Nystrom wrote:
> If we're using new Future(), is runAsync still needed?

Yes. [new Future] only breaks the stack when entering into the function; we also
need to break the stack when leaving it to satisfy case 3. Since
[Completer.complete] is not asynchronous on its own, we need to add asynchrony
ourselves.

[Bob Nystrom, 2013-04-30 21:13:05]

On 2013/04/30 20:46:00, nweiz wrote:
> > I'm personally not too crazy about this. This can end up doing a lot of
> thrashing on the event loop which might have negative perf.
> 
> If the solver doesn't go exponential, any perf hit here will be dwarfed by our
> HTTP requests. If it does go exponential, perf is already shot, and a small
> additional constant factor won't make much of a difference.

No, this isn't true. Everything we request over HTTP is cached in memory. So,
consider a case where there are 10 versions each of 5 packages and for whatever
reason the solver goes exponential.

In that case, it will just do 50 HTTP requests which is a chore but not too bad.
Then the solver will crank through 100,000 possible solutions. While that's
certainly not ideal, it *can* find a solution to that pretty quickly if we don't
exhaust the heap with huge future chains or lots of event loop thrashing.

This algorithm can be CPU bound, I believe.

But LGTM. I personally don't mind reading the Completer-based code, but if it
bothers you, I don't mind this way either. It's more important for this to be
readable to both of us. :)

[nweiz, 2013-04-30 21:18:04]

Committed patchset #2 manually as r22200 (presubmit successful).