From 7cce618d18c8203369d605d1ccedcfda09d58acc Mon Sep 17 00:00:00 2001
From: The 8472 <git@infinite-source.de>
Date: Mon, 6 Mar 2023 15:07:02 +0100
Subject: Fast path that skips over unchanged obligations in
 process_obligations

- only borrow the refcell once per loop
- avoid complex matches to reduce branch paths in the hot loop
- use a by-ref fast path that avoids mutations at the expense of having false negatives
---
 compiler/rustc_data_structures/Cargo.toml             |  2 +-
 .../src/obligation_forest/mod.rs                      | 19 ++++++++++++++++---
 2 files changed, 17 insertions(+), 4 deletions(-)

(limited to 'compiler/rustc_data_structures')

diff --git a/compiler/rustc_data_structures/Cargo.toml b/compiler/rustc_data_structures/Cargo.toml
index 29cb2c0a33e..f2a904a6654 100644
--- a/compiler/rustc_data_structures/Cargo.toml
+++ b/compiler/rustc_data_structures/Cargo.toml
@@ -9,7 +9,7 @@ edition = "2021"
 arrayvec = { version = "0.7", default-features = false }
 bitflags = "1.2.1"
 cfg-if = "1.0"
-ena = "0.14.1"
+ena = "0.14.2"
 indexmap = { version = "1.9.1" }
 jobserver_crate = { version = "0.1.13", package = "jobserver" }
 libc = "0.2"
diff --git a/compiler/rustc_data_structures/src/obligation_forest/mod.rs b/compiler/rustc_data_structures/src/obligation_forest/mod.rs
index 91abdaadabd..27a869eb7cd 100644
--- a/compiler/rustc_data_structures/src/obligation_forest/mod.rs
+++ b/compiler/rustc_data_structures/src/obligation_forest/mod.rs
@@ -97,7 +97,17 @@ pub trait ObligationProcessor {
     type Error: Debug;
     type OUT: OutcomeTrait<Obligation = Self::Obligation, Error = Error<Self::Obligation, Self::Error>>;
 
-    fn needs_process_obligation(&self, obligation: &Self::Obligation) -> bool;
+    /// Implementations can provide a fast-path to obligation-processing
+    /// by counting the prefix of the passed iterator for which
+    /// `needs_process_obligation` would return false.
+    fn skippable_obligations<'a>(
+        &'a self,
+        _it: impl Iterator<Item = &'a Self::Obligation>,
+    ) -> usize {
+        0
+    }
+
+    fn needs_process_obligation(&self, _obligation: &Self::Obligation) -> bool;
 
     fn process_obligation(
         &mut self,
@@ -416,6 +426,10 @@ impl<O: ForestObligation> ObligationForest<O> {
         loop {
             let mut has_changed = false;
 
+            // This is the super fast path for cheap-to-check conditions.
+            let mut index =
+                processor.skippable_obligations(self.nodes.iter().map(|n| &n.obligation));
+
             // Note that the loop body can append new nodes, and those new nodes
             // will then be processed by subsequent iterations of the loop.
             //
@@ -424,9 +438,8 @@ impl<O: ForestObligation> ObligationForest<O> {
             // `for index in 0..self.nodes.len() { ... }` because the range would
             // be computed with the initial length, and we would miss the appended
             // nodes. Therefore we use a `while` loop.
-            let mut index = 0;
             while let Some(node) = self.nodes.get_mut(index) {
-                // This test is extremely hot.
+                // This is the moderately fast path when the prefix skipping above didn't work out.
                 if node.state.get() != NodeState::Pending
                     || !processor.needs_process_obligation(&node.obligation)
                 {
-- 
cgit 1.4.1-3-g733a5