memchr: `x86` performance regression `2.5.0` -> `2.6.0`

The following disgusting patch gets rid of the extra mov for me. Perhaps it can inspire a non-disgusting patch. The idea is rather than keeping {cur, index1, index2} all live at once, pre-compute (cur1, cur2) = (cur.add(index1), cur.add(index2)) and then you can forget about the indices.

diff --git a/src/arch/generic/packedpair.rs b/src/arch/generic/packedpair.rs
index 8d97cf2..2667cc8 100644
--- a/src/arch/generic/packedpair.rs
+++ b/src/arch/generic/packedpair.rs
@@ -93,7 +93,6 @@ impl<V: Vector> Finder<V> {
         let start = haystack.as_ptr();
         let end = start.add(haystack.len());
         let max = end.sub(self.min_haystack_len);
-        let mut cur = start;
 
         // N.B. I did experiment with unrolling the loop to deal with size(V)
         // bytes at a time and 2*size(V) bytes at a time. The double unroll
@@ -101,14 +100,21 @@ impl<V: Vector> Finder<V> {
         // slower. In the end, I decided the complexity from unrolling wasn't
         // worth it. I used the memmem/krate/prebuilt/huge-en/ benchmarks to
         // compare.
-        while cur <= max {
-            if let Some(chunki) = self.find_in_chunk(needle, cur, end, all) {
-                return Some(matched(start, cur, chunki));
+        let index1 = usize::from(self.pair.index1());
+        let index2 = usize::from(self.pair.index2());
+        let mut cur1 = start.add(index1);
+        let mut cur2 = start.add(index2);
+        let end1 = end.add(index1);
+        let max1 = max.add(index1);
+        while cur1 <= max1 {
+            if let Some(chunki) = self.find_in_chunk(needle, cur1, cur2, end1, all) {
+                return Some(matched(start, cur1.sub(index1), chunki));
             }
-            cur = cur.add(V::BYTES);
+            cur1 = cur1.add(V::BYTES);
+            cur2 = cur2.add(V::BYTES);
         }
-        if cur < end {
-            let remaining = end.distance(cur);
+        if cur1 < end1 {
+            let remaining = end1.distance(cur1);
             debug_assert!(
                 remaining < self.min_haystack_len,
                 "remaining bytes should be smaller than the minimum haystack \
@@ -120,10 +126,10 @@ impl<V: Vector> Finder<V> {
                 return None;
             }
             debug_assert!(
-                max < cur,
+                max1 < cur1,
                 "after main loop, cur should have exceeded max",
             );
-            let overlap = cur.distance(max);
+            let overlap = cur1.distance(max1);
             debug_assert!(
                 overlap > 0,
                 "overlap ({}) must always be non-zero",
@@ -140,10 +146,11 @@ impl<V: Vector> Finder<V> {
             // occur in find_in_chunk within the overlap are automatically
             // ignored.
             let mask = V::Mask::all_zeros_except_least_significant(overlap);
-            cur = max;
-            let m = self.find_in_chunk(needle, cur, end, mask);
+            cur1 = max1;
+            cur2 = max1.sub(index1).add(index2);
+            let m = self.find_in_chunk(needle, cur1, cur2, end1, mask);
             if let Some(chunki) = m {
-                return Some(matched(start, cur, chunki));
+                return Some(matched(start, cur1.sub(index1), chunki));
             }
         }
         None
@@ -229,25 +236,24 @@ impl<V: Vector> Finder<V> {
     unsafe fn find_in_chunk(
         &self,
         needle: &[u8],
-        cur: *const u8,
-        end: *const u8,
+        cur1: *const u8,
+        cur2: *const u8,
+        end1: *const u8,
         mask: V::Mask,
     ) -> Option<usize> {
-        let index1 = usize::from(self.pair.index1());
-        let index2 = usize::from(self.pair.index2());
-        let chunk1 = V::load_unaligned(cur.add(index1));
-        let chunk2 = V::load_unaligned(cur.add(index2));
+        let chunk1 = V::load_unaligned(cur1);
+        let chunk2 = V::load_unaligned(cur2);
         let eq1 = chunk1.cmpeq(self.v1);
         let eq2 = chunk2.cmpeq(self.v2);
 
         let mut offsets = eq1.and(eq2).movemask().and(mask);
         while offsets.has_non_zero() {
             let offset = offsets.first_offset();
-            let cur = cur.add(offset);
-            if end.sub(needle.len()) < cur {
+            let cur1 = cur1.add(offset);
+            if end1.sub(needle.len()) < cur1 {
                 return None;
             }
-            if is_equal_raw(needle.as_ptr(), cur, needle.len()) {
+            if is_equal_raw(needle.as_ptr(), cur1.sub(self.pair.index1() as usize), needle.len()) {
                 return Some(offset);
             }
             offsets = offsets.clear_least_significant_bit();

For anyone who might be willing to help, I’ve created a bit more of a refined reproduction of the issue that shows the codegen problem here: https://github.com/BurntSushi/memchr-2.6-mov-regression

Any help would be appreciated!

This seems to be a register pressure issue. For me, LLVM has hoisted this load of index2, but spills it to the stack as 0x10(%rsp) instead of keeping it in a register: https://github.com/BurntSushi/memchr/blob/2.6.4/src/arch/generic/packedpair.rs#L237

Thanks! I’ll take a look later.

For Assembly, the best way in my experience is to use perf on Linux. It should be pretty clear where the hotspot is in functions like memchr::arch::x86_64::avx2::packedpair::Finder::find_impl. Look for the SIMD instructions starting with v. That should be where most of the time is being spent. Then compare those with the instructions used in memchr 2.5.0.

But I’ll take a look now that I have a repro. Just not sure when. Thank you!