Optimize string comparison by using memcmp

llvm seems to be having some trouble optimizing the iterator-based
string comparsion method into some equivalent to memcmp. This
explicitly calls out to the memcmp intrinisic in order to allow
llvm to generate better code. In some manual benchmarking, this
memcmp-based approach is 20 times faster than the iterator approach.

1 files changed, 20 insertions, 15 deletions

diff --git a/src/libcore/str/mod.rs b/src/libcore/str/mod.rs
index 694d93b75ca..139f589e6c5 100644
--- a/src/libcore/str/mod.rs
+++ b/src/libcore/str/mod.rs
@@ -896,14 +896,18 @@ Section: Comparing strings
 #[lang = "str_eq"]
 #[inline]
 fn eq_slice(a: &str, b: &str) -> bool {
+    a.len() == b.len() && unsafe { cmp_slice(a, b, a.len()) == 0 }
+}
+
+/// Bytewise slice comparison.
+/// NOTE: This uses the system's memcmp, which is currently dramatically
+/// faster than comparing each byte in a loop.
+#[inline]
+unsafe fn cmp_slice(a: &str, b: &str, len: usize) -> i32 {
     // NOTE: In theory n should be libc::size_t and not usize, but libc is not available here
     #[allow(improper_ctypes)]
     extern { fn memcmp(s1: *const i8, s2: *const i8, n: usize) -> i32; }
-    a.len() == b.len() && unsafe {
-        memcmp(a.as_ptr() as *const i8,
-               b.as_ptr() as *const i8,
-               a.len()) == 0
-    }
+    memcmp(a.as_ptr() as *const i8, b.as_ptr() as *const i8, len)
 }
 
 /*
@@ -1039,8 +1043,8 @@ Section: Trait implementations
 */
 
 mod traits {
-    use cmp::{Ordering, Ord, PartialEq, PartialOrd, Eq};
-    use cmp::Ordering::{Less, Equal, Greater};
+    use cmp::{self, Ordering, Ord, PartialEq, PartialOrd, Eq};
+    use cmp::Ordering::{Less, Greater};
     use iter::Iterator;
     use option::Option;
     use option::Option::Some;
@@ -1051,15 +1055,16 @@ mod traits {
     impl Ord for str {
         #[inline]
         fn cmp(&self, other: &str) -> Ordering {
-            for (s_b, o_b) in self.bytes().zip(other.bytes()) {
-                match s_b.cmp(&o_b) {
-                    Greater => return Greater,
-                    Less => return Less,
-                    Equal => ()
-                }
+            let cmp = unsafe {
+                super::cmp_slice(self, other, cmp::min(self.len(), other.len()))
+            };
+            if cmp == 0 {
+                self.len().cmp(&other.len())
+            } else if cmp < 0 {
+                Less
+            } else {
+                Greater
             }
-
-            self.len().cmp(&other.len())
         }
     }