Merge into larger interval set

This reduces the work done while merging rows. In at least one case
(issue 50450), we have thousands of union([range], [20,000 ranges]),
which previously inserted each of the 20,000 ranges one by one. Now we
only insert one range into the right hand set after copying the set
over.

1 files changed, 6 insertions, 0 deletions

diff --git a/compiler/rustc_index/src/interval.rs b/compiler/rustc_index/src/interval.rs
index d3cf267dc9d..0c1180b3e98 100644
--- a/compiler/rustc_index/src/interval.rs
+++ b/compiler/rustc_index/src/interval.rs
@@ -236,6 +236,12 @@ impl<I: Idx> IntervalSet<I> {
         I: Step,
     {
         assert_eq!(self.domain, other.domain);
+        if self.map.len() < other.map.len() {
+            let backup = self.clone();
+            self.map.clone_from(&other.map);
+            return self.union(&backup);
+        }
+
         let mut did_insert = false;
         for range in other.iter_intervals() {
             did_insert |= self.insert_range(range);