如何优化小型固定大小数组中的搜索？

Question

我想找到 16 字节数组中第一次出现的字节。如果我编写一个简单的版本（使用迭代器或手动循环），rustc 似乎不会矢量化（https://godbolt.org/z/fbKfvxTdv）。

我对优化解决方案的模糊想法是这样的

• 广播

  x

  到某个向量寄存器中
• 立即将其与

  y

  的每个元素进行比较
• 将 16 个结果布尔值收集到 u16 中
• 使用 count_leading_zeros 执行某些操作来查找匹配的那个。

相反，对于手动循环，它只是通过 16 次比较和跳转完全展开，而对于基于迭代器的版本，它似乎根本没有利用已知的固定长度（正好是 16）

pub fn find_first(x: u8, y: &[u8;16]) -> Option<usize> {
    y.iter().position(|w| *w == x)
}

pub fn find_first_manual(x: u8, y: &[u8;16]) -> Option<usize> {
    for i in 0..16 {
        if y[i] == x {
            return Some(i);
        }
    }
    None
}

Answer 1

问题中提到的想法很有道理。

或者，也可以使用

_mm_cmpestrc

/

_mm_cmpestri

来完成。

如果编译器没有为您执行此操作，即使有提示，如

find_first_manual

所示，您可以使用 SSE / AVX 内在函数手动执行此操作。

像 C 标准

memchr

这样的库函数通常已经过优化，尽管如果它们保留在库中并且没有由编译器内联到您的代码中，则它们无法利用已知的上下文，在您的情况下，假设长度为 16 。不知道Rust有没有

memchr

。