Exponential slow down in compilation speed (because of visiblity checking?) #145741
Description
See the playground as I didn't try to make it as small as humanly possibly. This comes from a real usage. Its a form of type level bit mask. Though im going to have to rethink this considering how bad the performance is.
https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=e71881dcc42a013c31d81e6defae2180
The playground takes about 5-6s to complete a build. However, if Fn3 is introduced then the playground times out. The build time for it should be roughly 25s.
I would expect this to be hard on the trait solver, but not the roughly 5^n (where n is number of generics on the FnX types). Looking at a self profile it appears most of the time isn't even from the trait solver. Its from visibility checking?
Meta
rustc --version --verbose:
rustc 1.89.0 (29483883e 2025-08-04)
binary: rustc
commit-hash: 29483883eed69d5fb4db01964cdf2af4d86e9cb2
commit-date: 2025-08-04
host: x86_64-unknown-linux-gnu
release: 1.89.0
LLVM version: 20.1.7
Also happens on recent nightly.
The following is from a self profile doing a clean build with the Fn3 type.
+------------------------------------------------------+-----------+-----------------+----------+------------+---------------------------------+
| Item | Self time | % of total time | Time | Item count | Incremental result hashing time |
+------------------------------------------------------+-----------+-----------------+----------+------------+---------------------------------+
| effective_visibilities | 21.44s | 47.630 | 21.44s | 1 | 5.10µs |
+------------------------------------------------------+-----------+-----------------+----------+------------+---------------------------------+
| check_private_in_public | 9.90s | 21.987 | 9.90s | 1 | 2.46µs |
+------------------------------------------------------+-----------+-----------------+----------+------------+---------------------------------+
| check_mod_privacy | 6.03s | 13.399 | 6.03s | 1 | 2.65µs |
+------------------------------------------------------+-----------+-----------------+----------+------------+---------------------------------+
| check_well_formed | 3.86s | 8.569 | 7.64s | 67 | 13.43µs |
+------------------------------------------------------+-----------+-----------------+----------+------------+---------------------------------+
| compare_impl_item | 3.78s | 8.387 | 3.78s | 19 | 3.13µs |
+------------------------------------------------------+-----------+-----------------+----------+------------+---------------------------------+
| type_of | 1.39ms | 0.003 | 1.71ms | 79 | 18.16µs |
+------------------------------------------------------+-----------+-----------------+----------+------------+---------------------------------+
| generate_crate_metadata | 577.99µs | 0.001 | 1.08ms | 1 | 0.00ns |
+------------------------------------------------------+-----------+-----------------+----------+------------+---------------------------------+
| metadata_register_crate | 564.79µs | 0.001 | 939.63µs | 19 | 0.00ns |
+------------------------------------------------------+-----------+-----------------+----------+------------+---------------------------------+
| expand_crate | 441.79µs | 0.001 | 1.51ms | 1 | 0.00ns |
+------------------------------------------------------+-----------+-----------------+----------+------------+---------------------------------+
| incr_comp_encode_dep_graph | 400.03µs | 0.001 | 400.03µs | 3969 | 0.00ns |
+------------------------------------------------------+-----------+-----------------+----------+------------+---------------------------------+
| metadata_decode_entry_module_children | 359.31µs | 0.001 | 359.31µs | 5 | 0.00ns |
+------------------------------------------------------+-----------+-----------------+----------+------------+---------------------------------+
| parse_crate | 357.66µs | 0.001 | 357.66µs | 1 | 0.00ns |
+------------------------------------------------------+-----------+-----------------+----------+------------+---------------------------------+