Arithmetic operations with inferred variables take quadratic time to type-check

[huonw]

This takes ~2 seconds to type check (according to -Z time-passes):

fn main() {
    macro_rules! f {
        () => { 0 + 0 }
    }
    // 16 per line
    f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();
    f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();
    f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();
    f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();

    f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();
    f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();
    f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();
    f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();

    f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();
    f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();
    f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();
    f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();

    f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();
    f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();
    f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();
    f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();f!();
}

Doubling (respectively, halving) the number of f!() invocations multiplies (resp. divides) the time by 4.

It applies to arithmetic in consts/statics too which is, I imagine, where this will occur most often in practice (it's how I found it).

Observations:

• for +, -, * and /, annotating either side (e.g. 0 + 0u8) or both sides makes it take only 0.03s and behave linearly (AFAICT)
• for << and >>:
  • annotating the LHS (0u8 >> 0) reduces the time to ~1.5s,
  • annotating the RHS (0 >> 0u8) reduces it to ~1.1s but both are still quadratic,
  • annotating both takes it to 0.04s and linear
• it seems to only be dependent on the number of operations in a single function/item, separating the 4 big chunks above across 4 functions reduces the time to ~0.5s.
• there's no significant difference between using the macro or writing the operations inline (I only use f! to allow easier experimentation)

cc @rust-lang/compiler

[eddyb]

This must be what's making my old macro-abusing inflate implementation take almost 300 seconds in typeck.
It almost sounds like type-checking a function is quadratic over the number of inference variables.

Having ran callgrind on the sample and also half of it, I'm seeing the following trace:

Function	Calls (N=128)	Calls (N=256)	Calls (N)
check::op::check_binop	128	256	N
check::FnCtxt::resolve_type_vars_if_possible	512	1024	4N
check::FnCtxt::select_obligations_where_possible	512 + 12	1024 + 12	4N + 12
traits::FulfillmentContext::select_where_possible	512 + 27	1024 + 27	4N + 27
traits::FulfillmentContext::select	1024 + 155	2048 + 183	8N + M
infer::InferCtxt::commit_if_ok	83072	329984	5N² + 9N

An unrefined conclusion is that either check_binop shouldn't call fcx.resolve_type_vars_if_possible() or FulfillmentContext::select should be constant-time.

[bluss]

Is this the same issue as #23977?

[eddyb]

@nikomatsakis I'm not too familiar with fulfill and infer, but couldn't select_where_possible track the latest InferCtxt snapshot it processed and look at the new information there?

[arielb1]

@eddyb

We have select_new_obligations exactly for this reason. It doesn't work for some reason tho.

[arielb1]

This is the same issue as
#25069
#23977

This is a different issue from #22204 (I think I will fix that one separately).