|
/// Compares short slices for equality. |
|
/// |
|
/// It avoids a call to libc's memcmp which is faster on long slices |
|
/// due to SIMD optimizations but it incurs a function call overhead. |
|
/// |
|
/// # Safety |
|
/// |
|
/// Both slices must have the same length. |
|
#[cfg(any( |
|
all(target_arch = "x86_64", target_feature = "sse2"), |
|
all(target_arch = "loongarch64", target_feature = "lsx"), |
|
all(target_arch = "aarch64", target_feature = "neon") |
|
))] |
|
#[inline] |
|
unsafe fn small_slice_eq(x: &[u8], y: &[u8]) -> bool { |
|
debug_assert_eq!(x.len(), y.len()); |
|
// This function is adapted from |
|
// https://github.com/BurntSushi/memchr/blob/8037d11b4357b0f07be2bb66dc2659d9cf28ad32/src/memmem/util.rs#L32 |
|
|
|
// If we don't have enough bytes to do 4-byte at a time loads, then |
|
// fall back to the naive slow version. |
|
// |
|
// Potential alternative: We could do a copy_nonoverlapping combined with a mask instead |
|
// of a loop. Benchmark it. |
|
if x.len() < 4 { |
|
for (&b1, &b2) in x.iter().zip(y) { |
|
if b1 != b2 { |
|
return false; |
|
} |
|
} |
|
return true; |
|
} |
|
// When we have 4 or more bytes to compare, then proceed in chunks of 4 at |
|
// a time using unaligned loads. |
|
// |
|
// Also, why do 4 byte loads instead of, say, 8 byte loads? The reason is |
|
// that this particular version of memcmp is likely to be called with tiny |
|
// needles. That means that if we do 8 byte loads, then a higher proportion |
|
// of memcmp calls will use the slower variant above. With that said, this |
|
// is a hypothesis and is only loosely supported by benchmarks. There's |
|
// likely some improvement that could be made here. The main thing here |
|
// though is to optimize for latency, not throughput. |
|
|
|
// SAFETY: Via the conditional above, we know that both `px` and `py` |
|
// have the same length, so `px < pxend` implies that `py < pyend`. |
|
// Thus, dereferencing both `px` and `py` in the loop below is safe. |
|
// |
|
// Moreover, we set `pxend` and `pyend` to be 4 bytes before the actual |
|
// end of `px` and `py`. Thus, the final dereference outside of the |
|
// loop is guaranteed to be valid. (The final comparison will overlap with |
|
// the last comparison done in the loop for lengths that aren't multiples |
|
// of four.) |
|
// |
|
// Finally, we needn't worry about alignment here, since we do unaligned |
|
// loads. |
|
unsafe { |
|
let (mut px, mut py) = (x.as_ptr(), y.as_ptr()); |
|
let (pxend, pyend) = (px.add(x.len() - 4), py.add(y.len() - 4)); |
|
while px < pxend { |
|
let vx = (px as *const u32).read_unaligned(); |
|
let vy = (py as *const u32).read_unaligned(); |
|
if vx != vy { |
|
return false; |
|
} |
|
px = px.add(4); |
|
py = py.add(4); |
|
} |
|
let vx = (pxend as *const u32).read_unaligned(); |
|
let vy = (pyend as *const u32).read_unaligned(); |
|
vx == vy |
|
} |
|
} |
I noticed that the candidate check for SIMD substring search
rust/library/core/src/str/pattern.rs
Lines 1843 to 1855 in 029c9e1
is using
small_slice_eqrust/library/core/src/str/pattern.rs
Lines 1914 to 1985 in 029c9e1
This was pulled from
memchra while back. Butmemchrgot an improvement here a few years ago:BurntSushi/memchr@e77f0bf
std might consider adopting this. Note that
memchr's infrastructure uses raw pointers everywhere for $reasons, so I'm unsure if that will matter since compilers are weird.