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.

[memoryruins]

[privacy_checking.rs](https://gist.githubusercontent.com/iliekturtles/1ca45b239c7133cdc259d5089535bc87/raw/4e26f32c038070542b1d7cd40cecd62b79c6a5ca/privacy_checking.rs) continues to have a notable difference in ``rustc 1.30.0-nightly (d41f21f 2018-08-24)``

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

real 0m53.449s
user 0m49.484s
sys 0m3.563s

---

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

real 0m21.467s
user 0m18.000s
sys 0m3.328s

edit: the machine I tried it on had problems of its own at the time (throttled to roughly 800MHz), so the seconds taken are not normal results.

[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