Re:The Boyer-Moore Fast String Searching Algorithm
by burntsushi on Friday April 23, 2021 @05:23PM
(#26919352)
Yes, that's what ripgrep does, or similarish. In my initial implementation, I did what you suggested on a standard u64. But bytecount adds SIMD to it (which I did not write): https://docs.rs/bytecount
I believe GNU grep just uses memchr for this. But I might be mis-remembering.
I'm not sure what GNU grep/wc does, but assuming you're getting line numbers for relatively rare matches, you probably shouldn't use memchr. Instead, load chunks of bytes into a SIMD/vector register, compare each one for equality to 0A, take the popcnt, and add it to a line number counter. You don't actually care where (most of) the newlines are located, just how many of them there are.