[arrow-rs] branch master updated: Faster prefix match in object_store path handling (#4164)

[tustvold]

This is an automated email from the ASF dual-hosted git repository.

tustvold pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git


The following commit(s) were added to refs/heads/master by this push:
     new 6280a709c Faster prefix match in object_store path handling (#4164)
6280a709c is described below

commit 6280a709c025e5585ada7fcc27431ca9314bb403
Author: Raphael Taylor-Davies <1781103+tustv...@users.noreply.github.com>
AuthorDate: Tue May 9 17:43:23 2023 +0100

    Faster prefix match in object_store path handling (#4164)
    
    * Faster prefix match
    
    * Simplify parts
---
 object_store/src/path/mod.rs | 33 ++++++++++++---------------------
 1 file changed, 12 insertions(+), 21 deletions(-)

diff --git a/object_store/src/path/mod.rs b/object_store/src/path/mod.rs
index a15f7ca0f..29b134176 100644
--- a/object_store/src/path/mod.rs
+++ b/object_store/src/path/mod.rs
@@ -227,14 +227,9 @@ impl Path {
 
     /// Returns the [`PathPart`] of this [`Path`]
     pub fn parts(&self) -> impl Iterator<Item = PathPart<'_>> {
-        match self.raw.is_empty() {
-            true => itertools::Either::Left(std::iter::empty()),
-            false => itertools::Either::Right(
-                self.raw
-                    .split(DELIMITER)
-                    .map(|s| PathPart { raw: s.into() }),
-            ),
-        }
+        self.raw
+            .split_terminator(DELIMITER)
+            .map(|s| PathPart { raw: s.into() })
     }
 
     /// Returns the last path segment containing the filename stored in this 
[`Path`]
@@ -265,20 +260,14 @@ impl Path {
         &self,
         prefix: &Self,
     ) -> Option<impl Iterator<Item = PathPart<'_>> + '_> {
-        let diff = itertools::diff_with(self.parts(), prefix.parts(), |a, b| a 
== b);
-
-        match diff {
-            // Both were equal
-            None => Some(itertools::Either::Left(std::iter::empty())),
-            // Mismatch or prefix was longer => None
-            Some(
-                itertools::Diff::FirstMismatch(_, _, _) | 
itertools::Diff::Longer(_, _),
-            ) => None,
-            // Match with remaining
-            Some(itertools::Diff::Shorter(_, back)) => {
-                Some(itertools::Either::Right(back))
-            }
+        let mut stripped = self.raw.strip_prefix(&prefix.raw)?;
+        if !stripped.is_empty() && !prefix.raw.is_empty() {
+            stripped = stripped.strip_prefix(DELIMITER)?;
         }
+        let iter = stripped
+            .split_terminator(DELIMITER)
+            .map(|x| PathPart { raw: x.into() });
+        Some(iter)
     }
 
     /// Returns true if this [`Path`] starts with `prefix`
@@ -453,6 +442,8 @@ mod tests {
 
         let prefix = existing_path.clone();
         assert_eq!(existing_path.prefix_match(&prefix).unwrap().count(), 0);
+
+        assert_eq!(Path::default().parts().count(), 0);
     }
 
     #[test]