A perf regression between 2018-12-20 and 2018-12-21

[ljedrz]

Instructions and wall-time took a noticeable hit due to one of these changes.

instructions:

style-servo-check
	avg: 43.0%	min: 23.4%	max: 55.9%
style-servo-opt
	avg: 14.4%	min: 2.9%	max: 49.5%
style-servo-debug
	avg: 20.5%	min: 7.1%	max: 44.0%
sentry-cli-check
	avg: 29.6%	min: 14.9%	max: 41.4%
inflate-check
	avg: 10.6%	min: 3.4%	max: 33.6%
syn-check
	avg: 23.9%	min: 13.3%	max: 28.6%
inflate-opt
	avg: 7.3%?	min: 0.8%?	max: 26.0%?
inflate-debug
	avg: 9.2%	min: 3.5%	max: 25.6%
syn-debug
	avg: 12.7%	min: 6.9%	max: 20.4%
syn-opt
	avg: 6.6%?	min: 1.9%?	max: 20.3%?
sentry-cli-opt
	avg: 5.4%	min: 1.1%	max: 18.4%
ripgrep-check
	avg: 12.0%	min: 6.4%	max: 16.1%

wall-time:

style-servo-check
	avg: 21.8%	min: 12.3%	max: 29.1%
style-servo-opt
	avg: 11.5%	min: 5.3%	max: 22.2%
sentry-cli-check
	avg: 15.9%	min: 7.9%	max: 21.3%
syn-check
	avg: 13.6%	min: 7.6%	max: 18.6%
style-servo-debug
	avg: 14.2%	min: 7.8%	max: 18.4%
inflate-check
	avg: 10.1%	min: 7.2%	max: 17.0%
inflate-opt
	avg: 4.3%?	min: 0.3%?	max: 14.4%?
inflate-debug
	avg: 7.3%	min: 4.9%	max: 12.7%
syn-opt
	avg: 5.5%?	min: 3.4%?	max: 10.2%?

Cc @varkor (I narrowed it down)

[nikic]

This is likely due to #51085 (comment). The inhabitedness code is now used in a lot more places, and it's extremely slow.

[ljedrz]

It was an improvement, but it doesn't look like the issue is solved.

I'd reopen, but I can't override bors.

[nikic]

Yeah, clearly that wasn't (all of) it. I remember another perf issue in this code (set intersections are not lazy -- they continue even if the intersection is already empty), but will have to profile to make sure this is really the right issue this time...

[nikic]

With the second fix the really large regression is gone, but we're still not at parity: https://perf.rust-lang.org/compare.html?start=2018-12-20&end=fa922ab876cb3140de2ead9c8ad88a75982c167c&stat=instructions%3Au

This code will need some more optimization, or possibly needs to be turned into a query so it can be cached.