NLL: dropck_vec_cycle_checked.rs very slow to compile

[pnkfelix]

As noted on #49900 (comment) it appears that dropck_vec_cycle_checked.rs under -Znll requires more than an hour to compile (not yet clear how much time is actually required.)

Here is a reduced version of that test case that exhibits a 50x slowdown under -Znll. (Namely, it takes 0.163s to compile without -Znll, and takes 8.424s to compile with -Znll

// Reduced version of compile-fail/dropck_vec_cycle_checked.rs that
// still exhibits unacceptable time blow-up (but not to the point of
// being unrunnable).

use std::cell::Cell;

trait HasId { }
struct CheckId<T:HasId> { v: T }
impl<T:HasId> Drop for CheckId<T> { fn drop(&mut self) { } }
struct C<'a> { v: Vec<CheckId<Cell<Option<&'a C<'a>>>>> }
impl<'a> HasId for Cell<Option<&'a C<'a>>> { }
impl<'a> C<'a> { fn new() -> C<'a> { C { v: Vec::new() } } }

fn main() {
    let (mut c1, mut c2);
    c1 = C::new();
    c2 = C::new();

    c1.v[0].v.set(Some(&c2));
    //~^ ERROR `c2` does not live long enough

    c1.v[0].v.set(Some(&c2));
    //~^ ERROR `c2` does not live long enough
}

[pnkfelix]

It seems the problem, at least in this case, is this line of code

 if cause < **old_cause {

After some inspection with gdb and perf, my guess is that these region_infer::Causes can build up into (very?) long linked-list chains. I would think that the automatically-derived PartialOrd implementation would only fall into bad performance if those long chains have matching prefixes, but I haven't actually confirmed that (i.e., is it possible that the derived PartialOrd does not short cut when an early point in the linked list is different? Does it need to reach the end for some reason?)

Anyway, from what I can tell this code is just trying to reduce the cause to something simpler, but maybe once we are looking at two instances of Cause::Outlives we should not be wasting time trying to figure out which one is "less" ?

So some experiments to try:

1. Find out how long these chains actually are. Perhaps even store the length in the Outlives variant and use that as a way to eagerly exit the comparison when the two lengths are not the same. I haven't done this yet because I was more interested in trying the next experiment.
   • Update: adding the length field and assuming it would short-cut traversal did not seem to work. (I.e. the running time is still bad). The length for the error being reported is 14; I have not yet gathered data on the lengths during the various comparison operations that are taking place.
2. Make a variant comparison method that does not recur, and instead just always returns false when comparing two Cause::Outlives. I have implemented this and it seems to address the slow-down for this test case. (Of course this approach does not preserve the prior behavior. My theory though is that wasting a lot of time to find the minimal cause is not going to pay off in these cases.)

[pnkfelix]

Based on some rough debug! instrumentation, the maximum length is 25, the average is about 5, and that cause < **old_cause expression is being evaluated 5,194 times. To be honest I'm a little surprised that the time is blowing up that badly if it really is due solely to the comparison operation alone. (Maybe the perf data is misleading me.)

• When I use a filter that skips considering the comparison and the replacement when both sides are Cause::Outlives (i.e. experiment 2 written in previous comment), then add_internal only adds new elements 3,738 times. I briefly skimmed the code to see where the returned boolean here flows to, and it didn't seem like it was affecting anything (i.e. it seemed like it ended up being discarded without affecting control flow) but I certainly could have overlooked something.

Another reasonable theory is that the reason that it speeds things up to always return false when comparing two Cause::Outlives is that then we will spend far less time replacing the entry (a linked list structure) held in the cause map. It should be relatively cheap to move the new cause (which we already have constructed regardless of the outcome of the comparison operation) into a newly allocated Rc, but we also must deallocate the old cause (and/or the causes it links to) if there are no other owners sharing it?

[pnkfelix]

A variation on outright skipping comparison when given two Outlives: always reduce the two inputs to root_cause() before comparing them. In my initial experiments, this seems like it yields a similar performance boost in error reporting to what I reported above, while I think it has a smaller (though still non-zero) impact on the actual errors we currently produce on the ui test suite.

[ishitatsuyuki]

Please revisit the status of this issue, as the PartialOrd bug is fixed.

[nikomatsakis]

Testing with nightly now, I see no difference at all between them.