Re^3: counting the number of 16384 pattern matches in a large DNA sequence

[BrowserUk]

Just as a matter of curiosity, have you ever come across a case in which there was a benefit from studying a string even once?

Yes. But it was

• a while ago on much slower hardware than I now run.

  Boyer-Moore worked best in the days before the chip manufacturers had built string search algorithms into microcode; and before the advent of deeply pipelined architectures with branch predictions, when branching had a proportionally significantly greater impact on throughput than with modern hardware.

• the needle being search for contained a character that was very rare in the haystack being searched.

  This allows the algorithm to trade intelligence for brute force.

  With modern processors that overlap fetches and branching stalls with other parts of the opcodes, the benefits are greatly curtailed.

I tried to look up a old post of mine that benchmarked study having a beneficial effect, but couldn't find it.

I also tried to replicate my memory of what I was doing back then, but cannot reproduce it. Whether that's because my memory is bad, or my modern processor negates the benefits I'm not totally sure, but I suspect the latter.