Are iterator functions amortizing vector operations when needles are close by?

[Yomguithereal]

Hello @BurntSushi, sorry if this is obvious but I could not find an answer on this and was not able to answer it myself by reading the source code of the lib: basically are iterator versions of the lib functions to be considered as fancy trench coats over a loop that execute memchr starting from last match onwards at each iteration? Or are they able to amortize something when next match would be in the same vector slice processed by SIMD than previous match?

[BurntSushi]

For memmem, they are definitely amortizing construction.

For memchr, I believe they do as well, includes cpuid check. But I'm not sure if it's optimal. There is likely an even smarter amortization strategy (I believe some have posted about it on this repo).

[Yomguithereal]

So this means:

for offset in memchr_iter(needle, haystack) {
  // ..
}

remains faster than mere:

while let Some(offset) = memchr(needle, haystack[some_maintained_start_point..]) {
  // ..
}

right? But that it is not as fast as not recomputing same SIMD operations when next match is in same window as last time because it would involve some nasty bookkeeping?

[BurntSushi]

That sounds about right with two caveats:

1. The iterator being faster is a claim about it probably being faster. I'd be surprised if there was a meaningful difference to be honest.
2. It's not just about the book-keeping being subjectively nasty, but any book-keeping you add is likely something that increases the initial cost of the first search, which has downsides. Maybe there is a clever way to mitigate this, or the added cost is insignificant. I'm not sure. I haven't spent much time investigating this direction.

[Yomguithereal]

Thanks for the clarification @BurntSushi. I will benchmark for my use-case and see whether it makes an actual difference.

I think I found the conversation you were hinting about earlier over there: #88

[Yomguithereal]

I had time to benchmark my use-cases and I can report the *_iter function are very slightly more performant than hand-crafting the loop.

I will try to tinker around to find a way to get all matches found in a single pass of your loop unrolling to see whether it can yield improvements when splitting by a combination of bytes that are sometimes very close of each other.

[Yomguithereal]

I have a toy prototype of an iterator splitting a binary string using three different possible characters using the wide library here. It guarantees that no SIMD call will happen on overlapping slices as the moving mask is preserved between iterations. My early benchmark seems to indicate (using avx2) it does a good job even when needles are close to one another. I used it to improve my quasi-zero-copy csv parser and found it competitive when you only need to access a tiny subset of fields when reading the file. I also tried a correct approach by copying bytes whenever needed (thus unquoting the fields properly) and it was on par with the csv crate for files with tiny field values and seems better as soon as the field values are longer. This is very preliminary and I would not trust my work very much. I just report things here so it can be of use to anyone if required.

My weird inkling here is that if you are able to scan the whole data only once and avoid vectorizing the same bytes multiple times it is possible to actually create a faster, vectorized, correct and copying csv parser without relying on the complicated simd-json tricks?

Should I spend some time industrializing a scanning iterator for the memchr crate? Or do you know since you obvsiouly have a tremendously superior experience than myself on those subjects if this is a useless endeavor?