Implementing strcmp, strlen, and strstr using SSE 4.2 instructions (2008)

> The following strcmp and strlen functions were written and published when the processors with SSE 4.2 support were not available yet. Later they were tested on real hardware and found to be correct.

Too many programmers often think of programming as an online operation - online with stackoverflow, the manual, npm install, and so on -- and in a world of always-online it's hard to justify "wasting" precious mental-space preserving the ability to program in a wifi-free zone like an airplane or on the underground, but you need the ability to think about your software to program on the chip that doesn't exist yet, so this may be interesting to meditate over from time to time.

For short needle + haystack that fits in a vector reg, use SSE/AVX2 string search.

For short needle and long haystack, use SSE to find the first byte of the needle jumping a whole vector-register width at a time, then compare. If that produces too many false positives, fall back to SSE/AVX2 search for the whole needle.

For long needle, use a Rabin-Karp rolling hash to find a likely match, then verify.

The string search optimization rabbit hole can go pretty deep, especially because different implementations might win for different values passed to the function. Like, I'm guessing Go tries that search for just the first byte because, empirically, it helps pretty often, but it's not inherently faster for every possible needle and haystack (think needle ab haystack aaaaaaaaaaaaaa...ab), hence the escape hatch after too many false matches.

It's kind of wild what clever machinery gets invoked when you try to do simple things.

Another set of benchmarks comparing simple strcmp to SSE 4.2: https://www.linkedin.com/pulse/simple-fast-string-comparison...

I did a quick skim (disclaimer it's sometimes hard to rule out that an SSE optimized version is in there somewhere).

* musl 1.1.16: no

* glibc 2.26: yes (also an avx2 optimized one)

* Apple Libc 1158.50.2: optimized (non-SSE2) versions of several str* funcs exist but strcpy() has an >=SSE impl

It's supposed to be a comparison, but it doesn't set the flags with comparison results. Instead it uses them to signal if it's found an unequal byte, or hit the end of the strings. The latter is equality, which is one condition we want, but it doesn't say where in the 16 bytes it found the terminator. In fact it sets the register (ecx) which otherwise would be the offset to compare bytes, to 16.

That's all fine if you just want to return string comparison, but if you're trying to find their longest common prefix it's a whole new comparison to find the 0x00's.