Long compile time due to privacy checking private alias of public type

[iliekturtles]

Private type aliases of public types (e.g. type V = f32;) cause long compile times in the privacy checking phase. Making the type alias public resolves the issue. See iliekturtles/uom#52 where the issue was originally identified and the work-around was found. See privacy_checking.rs for a simple example to reproduce the problem.

The following command can be used to reproduce the problem with a private type alias.

time rustc +nightly --crate-type lib privacy_checking.rs -Ztime-passes --cfg 'feature="priv"' --cfg 'feature="T6"' --cfg 'feature="I5"'

Replacing the priv feature with pub shows that the issue is corrected when using a public type alias.

time rustc +nightly --crate-type lib privacy_checking.rs -Ztime-passes --cfg 'feature="pub"' --cfg 'feature="T6"' --cfg 'feature="I5"'

Varying the T_ (number of types) and I_ (number of trait impls) features shows how compile times change. See the below test data from my machine. It looks like privacy checking of a private type alias of a public type is exponential with the number of types and becomes linear with a very slight slope when checking public aliases.

Types	Impls	Ty x Impl	Time	Privacy checking	Time (pub)	Privacy checking (pub)
1	5	5	1.324	0.206	1.123	0.023
2	5	10	2.816	0.823	1.999	0.061
3	5	15	4.641	1.853	2.827	0.080
4	5	20	6.968	3.243	3.714	0.103
5	5	25	9.219	4.700	4.686	0.129
6	5	30	12.721	7.371	5.598	0.163

[ishitatsuyuki]

Track down:

rust/src/librustc_privacy/lib.rs

Lines 1471 to 1490 in acd3871

	// Slow path taken only if there any errors in the crate.
	for &id in self.old_error_set {
	// Walk up the nodes until we find `item_id` (or we hit a root).
	let mut id = id;
	loop {
	if id == item_id {
	has_old_errors = true;
	break;
	}
	let parent = self.tcx.hir.get_parent_node(id);
	if parent == id {
	break;
	}
	id = parent;
	}
	if has_old_errors {
	break;
	}
	}

Git blame: @eddyb

[eddyb]

Does this only happen with errors, or can compilation succeed?
In the former case, we tend to prefer trading efficiency for accuracy in error reporting.
cc @petrochenkov (this code has changed since)

[ishitatsuyuki]

From my understanding, what the comment says is false and it seems private items are unconditionally pushed onto the list. The program compiles successfully.

[iliekturtles]

I'm reviewing uom performance again in iliekturtles/uom#222 and re-ran benchmarks with privacy_checking.rs. There is still a dramatic slowdown but the time is now under the -Ztime-passes misc_checking_3 category:

Private alias of public type:

time: 27.479; rss: 167MB	misc_checking_3
...
time: 33.143; rss: 37MB		total

Public alias of public type

time: 0.271; rss: 168MB	misc_checking_3
...
time: 5.950; rss: 37MB		total

[memoryruins]

@tmiasko is there anything left to do now that #81574 has merged?

[iliekturtles]

By coincidence I just happened to already have nightly-2021-02-19 installed which was the first version including @tmiasko's fix.

$ rustc +nightly-2021-02-18 --version
rustc 1.52.0-nightly (152f66092 2021-02-17)
...
time:  62.964; rss:  158MB ->  170MB (  +11MB)  misc_checking_3

$ rustc +nightly --version
rustc 1.52.0-nightly (0148b971c 2021-02-18)
...
time:   0.457; rss:  157MB ->  169MB (  +12MB)  misc_checking_3

A non-scientific 10,000 % speed up with privacy_checking.rs! I think we're good to mark this complete. That's for the great work, @tmiasko!

[iliekturtles]

Actually closing the issue now! I verified one more time that compile times are consistent with the public and private type aliases.

Pub:

time:   2.301; rss:   46MB ->  106MB (  +60MB)  total

Priv:

time:   2.279; rss:   46MB ->  102MB (  +57MB)  total