> The skipto method is a single x86 machine instruction.
That’s not always a good thing, especially on modern hardware. And obviously, the “single instruction” doesn’t mean it’ll take bounded time to execute…
That’s not always a good thing, especially on modern hardware. And obviously, the “single instruction” doesn’t mean it’ll take bounded time to execute…
So to reiterate one aspect of your point, there might be lots of work, written in C, that occurs in response to the page fault in the middle of your "hardware-backed" single instruction. On top of all the other complexities of cache vs memory access etc. that make scanning and copying memory complicated no matter which way you do it.
But probably in the heyday of Visual Basic, and especially the DOS-based BASICs that preceded it which wouldn't have had virtual memory at all, all of this is less of a concern. The story takes place in a simpler time which serves as a plot device to better illustrate the point.
When did I dispute this?
> Besides, the page in question would very likely be already present.
Really? How are you so sure? I guess you can just abandon all notion of virtual memory and mmap then. 'Cause it ain't gonna happen.
> Really? How are you so sure?
It was in a BASIC interpreter. Most of the time string needle in a haystack search is done, haystack is relatively fresh, almost certainly on a page that is present. Might not be in CPU dcache, but that's another matter.
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.