REP SCASB on 1994 (same year as the incident in the article) Intel Pentium would have taken 9 + 4 * n clock cycles [0][1] to go through a string. So scanning 4 chars long string takes 25 clock cycles.
[0]: Agner's instruction tables page 123: https://www.agner.org/optimize/instruction_tables.pdf
[1]: Plus one extra cycle to decode REP prefix, if previous instruction took 1 cycle.
As even nowadays, it would likely depend on the particular algorithm and data set. I'd be surprised if you can't do better than 4 cycles per char for sufficiently long strings. Most likely for short strings, REP SCASB wins due to setup costs. (Actually that article's skipto method would have of course used REP CMPSB, but that's just splitting hairs.)
Remember that even original Pentium could execute up to two instructions per clock. Unless you messed up with those damn U & V pipes. :-)
The hypothetical faster-than-rep solution would need to process data in 32-bit chunks, faux vector style.
Or with real vector style with vectorized instructions?
It makes sense to delegate some of the microoptims to the hardware.
But regular scalar instructions are also optimized like crazy. Write a small loop, and your state of the art microarch might sort of unroll it by using register renaming and speculative execution, so sometimes basically multiple iterations are executed at the same time (and on top of that you sometimes get uOP cache locking, which then improves energy and hyperthreading efficiency).
Yes, REP MOVSB is fast at least on Intel CPUs nowadays.