3 ms·

For many situations the more complex substring search algorithms gave way to raw, brute force some time ago, I believe. For example, if you are looking for a gi

For many situations the more complex substring search algorithms gave way to raw, brute force some time ago, I believe. For example, if you are looking for a given relatively short string, you can just take a prefix of say four bytes and then make parallel comparisons within a vector; this simple technique gets you already down to the general area of 1 cpb. The SSE 4.2 PCMPSTR family of instructions is basically the same thing but microcoded, and is a bit faster. For short patterns, which are imho by far the most common use, any algorithm that tries to be smart and skip a couple bytes wastes cycles on being smart where a simpler brute force algorithm has already fetched the next 16 bytes and started to compare them while the prefetcher already went off to get the next line from L2.

glangdale 8y ago
When did you measure SSE4.2 against straightforward vector usage and find it faster? In my experience this was true more or less never. There's almost nothing in SSE4.2 that can't be done better with SSSE3. Intel has slowly deprecated SSE4.2 by not promoting it to wider vectors (it is still 128b when most other instructions are 512b) and letting the throughput/latency stagnate. 1 cycle per byte is not a good result for single string search; you can practically do a shift-and comparison of your input in that speed using general purpose registers.
- blattimwind 8y ago
  That work was all in the context of searching for a binary string with a mask. I didn't try too long to optimize it, since performance was quickly satisfactory, so it's not just possible, but rather very likely that my implementation isn't particularly good. I'll keep your advice about SSE 4.2 in mind should I revisit that code. https://github.com/rust-lang/regex/blob/master/src/literal/teddy_ssse3/imp.rs https://github.com/rust-lang/regex/blob/master/src/literal/t... might be of interest to casual readers (not necessarily you, considering you were probably very involved in developing that algorithm ;)
  - glangdale 8y ago
    I wouldn't use "Teddy" to look for single strings, at least not without heavy modification. The boring approach of hunting for a predicate or two with PCMPEQB or equivalent then shift-and'ing things together has worked well in practice for that sort of thing, although it can be a bit brittle if you get the predicate(s) wrong.

glangdale 8y ago

When did you measure SSE4.2 against straightforward vector usage and find it faster? In my experience this was true more or less never. There's almost nothing in SSE4.2 that can't be done better with SSSE3. Intel has slowly deprecated SSE4.2 by not promoting it to wider vectors (it is still 128b when most other instructions are 512b) and letting the throughput/latency stagnate. 1 cycle per byte is not a good result for single string search; you can practically do a shift-and comparison of your input in that speed using general purpose registers.

blattimwind 8y ago
That work was all in the context of searching for a binary string with a mask. I didn't try too long to optimize it, since performance was quickly satisfactory, so it's not just possible, but rather very likely that my implementation isn't particularly good. I'll keep your advice about SSE 4.2 in mind should I revisit that code. https://github.com/rust-lang/regex/blob/master/src/literal/teddy_ssse3/imp.rs https://github.com/rust-lang/regex/blob/master/src/literal/t... might be of interest to casual readers (not necessarily you, considering you were probably very involved in developing that algorithm ;)
- glangdale 8y ago
  I wouldn't use "Teddy" to look for single strings, at least not without heavy modification. The boring approach of hunting for a predicate or two with PCMPEQB or equivalent then shift-and'ing things together has worked well in practice for that sort of thing, although it can be a bit brittle if you get the predicate(s) wrong.