Now this is what I wanted to see: no behavior changes and colour brought down to 27 minutes from 50 - almost halved!

This is not ready for code review, removing draft status to get some feedback on the idea itself. I do not particularly like using id(expr) as a cache key, but it should be OK? TempNode is excluded, and everything else should not be subject to ID rot because objects actually remain in the parsed tree for the whole lifetime of checker, their IDs cannot get reused, and we should not construct any nodes other than TempNode while checking function calls.

That's why I only added caching to infer_args_in_empty_context. It's a nice place to do that: diagnostics from this call are never silenced and do not affect current overload resolution. We reject incompatible signatures later, accepting all arguments again anyway. Furthermore, it is only called when checking overload calls and Any calls, so I can safely remove overload stack check from it and replace it with a boolean flag. So I don't think that the generated errors can become relevant later. This might change overload resolution in presence of a globally invalid argument (foo(1 + 'a') where foo is overloaded), but any behavior is reasonable in such case IMO: we still emit an error that the argument is invalid itself. To prevent this, it is enough to record whether any errors were encountered, and skip the cache in such case.

Binder is indeed an implicit dependency, but it's still OK within a parent overload: re-accepting an AssignmentExpr should not change anything? Anyway, we can poison the cache in visit_assignment_expr to be extra sure, and that's probably a reasonable thing to do.

I'll add the changes mentioned above in a few hrs, but frankly my main "wtf" here is using IDs as cache keys.

According to mypy_primer, this change doesn't affect type check results on a corpus of open source code. ✅

Still quite nice in a single sample:

/tmp/mypy_primer/mypy_new/venv/bin/mypy on colour took 1988.16s
/tmp/mypy_primer/mypy_old/venv/bin/mypy on colour took 2953.89s

FWIW I am trying a (much) higher-level caching, like caching check_call() or maybe even accept() itself. Hopefully I will have time to finish a PR this weekend.

Superseded by #19505 which implements a superset of this functionality (but only for some expressions), further attempts should add other expressions there instead of rolling out another cache on top.