4 ms·
But is any of them using `_mm256_sad_epu8` for small, literal strings?
by stabbles 3y ago
But is any of them using `_mm256_sad_epu8` for small, literal strings?
- lifthrasiir 3y agoNot exactly but yes, it ultimately uses the `memchr` crate [1] which provides SIMD-optimized character and string search routines. But it uses `_mm256_cmpeq_epi8` instead of `_mm256_sad_epu8`. [1] https://docs.rs/memchr/latest/memchr/ https://docs.rs/memchr/latest/memchr/
- burntsushi 3y agoAnd also the SIMD in aho-corasick, which is used whenever a small number of literals are searched for. For example, `foo|bar` or `(?i)foo`. https://github.com/BurntSushi/aho-corasick/blob/f227162f7c56b3f28e9dd69a655316af0107b29b/src/packed/vector.rs https://github.com/BurntSushi/aho-corasick/blob/f227162f7c56... But no `_mm256_sad_epu8`. What an oddly specific question..?
- stabbles 3y agoWhat is really oddly specific is this instruction :p but I believe it is a common trick to quickly scan for short string matches. It computes `sum(|x[i] - y[i]|)` for consecutive `i` at different offsets, so it should be zero at substring matches. For context: https://epubs.siam.org/doi/pdf/10.1137/1.9781611972931.10 https://epubs.siam.org/doi/pdf/10.1137/1.9781611972931.10 I was slightly mistaken, the instruction of interest is _mm256_mpsadbw_epu8
- burntsushi 3y agoOh I see. Yes, that's what is commonly used in academic publications. But I've yet to see it used in the wild. I mentioned exactly that paper (I believe) in my write-up on Teddy: https://github.com/BurntSushi/aho-corasick/tree/master/src/packed/teddy https://github.com/BurntSushi/aho-corasick/tree/master/src/p...
- lifthrasiir 3y agoI think Wojciech Muła, who devised the original SIMD-oriented Rabin Karp algorithm, also did measure MPSADBW approaches and found that it is not a good fit for general string-in-string searches [1]. Maybe not today though. [1] http://0x80.pl/articles/simd-strfind.html#id7 http://0x80.pl/articles/simd-strfind.html#id7
- saagarjha 3y ago_mm256_:(_epu8