diff options
| -rw-r--r-- | src/librustc/traits/select.rs | 21 |
1 files changed, 18 insertions, 3 deletions
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs index bd7ec4a12b0..da9ac85639f 100644 --- a/src/librustc/traits/select.rs +++ b/src/librustc/traits/select.rs @@ -3356,13 +3356,28 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> { predicate: predicate.value })) }).collect(); + // We are performing deduplication here to avoid exponential blowups // (#38528) from happening, but the real cause of the duplication is // unknown. What we know is that the deduplication avoids exponential - // amount of predicates being propogated when processing deeply nested + // amount of predicates being propagated when processing deeply nested // types. - let mut seen = FxHashSet(); - predicates.retain(|i| seen.insert(i.clone())); + // + // This code is hot enough that it's worth avoiding the allocation + // required for the FxHashSet when possible. Special-casing lengths 0, + // 1 and 2 covers roughly 75--80% of the cases. + if predicates.len() <= 1 { + // No possibility of duplicates. + } else if predicates.len() == 2 { + // Only two elements. Drop the second if they are equal. + if predicates[0] == predicates[1] { + predicates.truncate(1); + } + } else { + // Three or more elements. Use a general deduplication process. + let mut seen = FxHashSet(); + predicates.retain(|i| seen.insert(i.clone())); + } self.infcx().plug_leaks(skol_map, snapshot, predicates) } } |