Poor performance of Rejections::into_response()

[alexeiakimov]

Version

0.3.3

Platform

Linux xxx 5.15.0-52-generic #58-Ubuntu SMP Thu Oct 13 08:03:55 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux

Description

warp::reject::Rejections::into_response has poor performance if the Rejections instance is a large combination of
known or custom rejections.

I tried this code:

#[test]
    fn convert_rejection_into_response() {
        let mut rejections = Rejections::Custom(Box::new(std::io::Error::from_raw_os_error(100)));
        for _ in 0..50 {
            rejections = Rejections::Combined(
                Box::new(Rejections::Known(Known::MethodNotAllowed(
                    MethodNotAllowed { _p: () },
                ))),
                Box::new(rejections),
            );
        }
        let reason = Reason::Other(Box::new(rejections));
        let rejection = Rejection { reason };
        println!("{:?}", rejection);
        // The next line is the problem
        println!("{:?}", rejection.into_response());
    }

I expected to see this happen: rejection.into_response() returns within 1 second

Instead, this happened: rejection.into_response() cannot return within 1,5 minutes

[seanmonstar]

1.5 minutes? Wow. That with --release?

[alexeiakimov]

I would like to add that the test above is not artificial, in the real application I have

1. A composite filter like f1 or f2 or f3 or ... fn where each fk is a simple combination of path and HTTP method.
2. A request has a correct path and method, but invalid JSON body which fails to be parsed.

In such a case the rejection is a combination of many MethodNotAllowed and one parsing error.

[alexeiakimov]

I would like also to add some analysis of how into_response is implemented.
Let n be the number of simple (i.e. known or custom) rejections in a simple linear combination. Then let

1. R(n) be the time to convert the rejection into response
2. P(n) be the time to compute the preferred rejection in worst case
3. S(n) be the time to compute the rejection status

Then we have

S(n) = P(n) + S(n-1) + C
P(n) = S(n-1) + C = P(n-1) + P(n-2) +...
R(n) = P(n) + R(n-1) = P(n) + P(n-1) + ... = 2*(P(n-1) + P(n-2) +...) = 2*R(n-1)

So it seems that R(n) has exponential growth, so I doubt if the --release can improve the situation significantly.

[alexeiakimov]

A possible patch:

diff --git a/src/reject.rs b/src/reject.rs
index fd09188..3311267 100644
--- a/src/reject.rs
+++ b/src/reject.rs
@@ -436,7 +436,7 @@ impl Rejections {
                 | Known::BodyConsumedMultipleTimes(_) => StatusCode::INTERNAL_SERVER_ERROR,
             },
             Rejections::Custom(..) => StatusCode::INTERNAL_SERVER_ERROR,
-            Rejections::Combined(ref a, ref b) => preferred(a, b).status(),
+            Rejections::Combined(..) => self.reduce().status(),
         }
     }
 
@@ -465,7 +465,7 @@ impl Rejections {
                 );
                 res
             }
-            Rejections::Combined(ref a, ref b) => preferred(a, b).into_response(),
+            Rejections::Combined(..) => self.reduce().into_response(),
         }
     }
 
@@ -491,21 +491,29 @@ impl Rejections {
             }
         }
     }
-}
 
-fn preferred<'a>(a: &'a Rejections, b: &'a Rejections) -> &'a Rejections {
-    // Compare status codes, with this priority:
-    // - NOT_FOUND is lowest
-    // - METHOD_NOT_ALLOWED is second
-    // - if one status code is greater than the other
-    // - otherwise, prefer A...
-    match (a.status(), b.status()) {
-        (_, StatusCode::NOT_FOUND) => a,
-        (StatusCode::NOT_FOUND, _) => b,
-        (_, StatusCode::METHOD_NOT_ALLOWED) => a,
-        (StatusCode::METHOD_NOT_ALLOWED, _) => b,
-        (sa, sb) if sa < sb => b,
-        _ => a,
+    fn reduce(&self) -> &Rejections {
+        match self {
+            Rejections::Known(_) | Rejections::Custom(_) => self,
+            Rejections::Combined(first, second) => {
+                let first = first.reduce();
+                let second = second.reduce();
+                // After reduction it is safe to call status
+                // Compare status codes, with this priority:
+                // - NOT_FOUND is lowest
+                // - METHOD_NOT_ALLOWED is second
+                // - if one status code is greater than the other
+                // - otherwise, prefer A...
+                match (first.status(), second.status()) {
+                    (_, StatusCode::NOT_FOUND) => first,
+                    (StatusCode::NOT_FOUND, _) => second,
+                    (_, StatusCode::METHOD_NOT_ALLOWED) => first,
+                    (StatusCode::METHOD_NOT_ALLOWED, _) => second,
+                    (s1, s2) if s1 < s2 => second,
+                    _ => first,
+                }
+            }
+        }
     }
 }
 
@@ -841,4 +849,21 @@ mod tests {
         let s = format!("{:?}", rej);
         assert_eq!(s, "Rejection([X(0), X(1), X(2)])");
     }
+
+    #[test]
+    fn convert_big_rejection_into_response() {
+        let mut rejections = Rejections::Custom(Box::new(std::io::Error::from_raw_os_error(100)));
+        for _ in 0..50 {
+            rejections = Rejections::Combined(
+                Box::new(Rejections::Known(Known::MethodNotAllowed(
+                    MethodNotAllowed { _p: () },
+                ))),
+                Box::new(rejections),
+            );
+        }
+        let reason = Reason::Other(Box::new(rejections));
+        let rejection = Rejection { reason };
+        let response = rejection.into_response();
+        assert_eq!(StatusCode::INTERNAL_SERVER_ERROR, response.status());
+    }
 }

[alexeiakimov]

Here is the PR: #1005