It has not aged well for ascii characters, especially for texts like English where the letter “e” is abundant enough to make it likely that your average jump would be 6, less than the 64-bit fetch.

It can still be used to find a substring of 100 64-bit values in a much longer 64-bit string, but ... it’s a problem I never encountered (and only encountered a 16-bit version of it once in my life). Then again, if you use 32-bit for each Unicode character and have a lot of emojis, it might still be somewhat competitive with brute force.

Harder to argue about character frequency in DNA/RNA sequences.

Naively, I'd expect all letters to occur equally frequently. Do you know if this is the case?

It's not the case.

There are consequences to the proportion of some nucleotides, the most well-known being the GC-content[1], or proportion in a sequence of bases being G or C (G pairs with C and A pairs with T). There are benefits to a higher GC-content, like the sequence being more stable.

From this the obvious question would be why this matters, since you obviously can't replace an A-T pair with a G-C pair just to increase this proportion. Except that there are ways to do it… kind of. If you look at the codon table[2], you'll see that there are multiple ways to represent each protein encoded by a triplet of nucleotides.

[1] https://en.wikipedia.org/wiki/GC-content

[2] https://en.wikipedia.org/wiki/DNA_and_RNA_codon_tables

Thanks for jumping in with way more info than I could provide.

I love how the DNA language, much unlike spoke words, is in close relation to physical properties of the world.

There really is some exciting magic in the interception of biology and computation.

Most BM implementations do this implicitly by using `memchr` in their skip loops. A lot of folks attribute the "skipping bytes" aspect of BM as its main reason for being fast. But nowadays, it's really just because most implementations run memchr on the last byte. At least for common cases and fairly short needles. (I'm sure there are inputs where the byte skipping plays a larger role.)

I tried to argue once that longer needles were better for searching; but I didn't find any literature to back that up. And I suspect most searches are done with line endings being tracked, such that most have an implicit tiny needle they are tracking.

To a first approximation, I would agree with the statement that "longer needles are better for searching." They just tend to have more useful properties: better chance of containing a rarer byte (or bytes), better chance of skipping characters, less of a chance of occurring at all, and so on. Of course, longer needles can sometimes result in a much slower search for pathological cases, depending on the substring algorithm you use.

The grep tools do track line endings, yes. ripgrep does it by default where as GNU grep does not. Line endings are only tracked to print line numbers. If you don't need to print line numbers, then you don't need to track all line endings.

The thing with tiny needles is that they aren't all created equal. If your tiny needle is a single byte and that byte doesn't occur too frequently, then it's going to be very fast to find occurrences of that byte.

I'm curious how you can speed up finding a single byte? Don't you have to touch all bytes at that point? Leaning heavily on simd instructions?

And I realize newlines is only to track line counts. Am I wrong that that slows things down?

> I'm curious how you can speed up finding a single byte? Don't you have to touch all bytes at that point? Leaning heavily on simd instructions?

Yes. That's what memchr does: https://github.com/BurntSushi/rust-memchr/blob/427fdc384007d...

> And I realize newlines is only to track line counts. Am I wrong that that slows things down?

It does, but only a little if it's implemented using vector instructions. You can try with ripgrep using -N/-n. GNU grep's line counting isn't vectorized IIRC, so you might notice bigger differences there.

On a typical input, where there's probably a newline every 30–80 characters on average [1], it seems like many of the bytes are not in that algorithm's happy 64-bytes-at-a-time 16-bytes-aligned main loop because each line would be a separate memchr call which has to redo the unaligned prefix bit, and/or are processed twice because they're in the 64 bytes but after the first newline. Have you ever considered an alternate interface which returns all the newline positions in a single call on a whole buffer? [edit: or next N with N>1.] Is it worth pursuing?

[1] bytes/lines on "wc -l *.[ch]" in the ffmpeg/libavformat directory I happened to have open says there's a newline every ~34 bytes.

edit: I suppose if ripgrep -N and ripgrep -n aren't that far apart, it's fast enough already. But I have to think it's not getting much mileage out of that 64-bytes-at-a-time loop.

> each line would be a separate memchr call which has to redo the unaligned prefix bit

I'm not sure what GNU grep/wc does, but assuming you're getting line numbers for relatively rare matches, you probably shouldn't use memchr. Instead, load chunks of bytes into a SIMD/vector register, compare each one for equality to 0A, take the popcnt, and add it to a line number counter. You don't actually care where (most of) the newlines are located, just how many of them there are.

Yes, that's what ripgrep does, or similarish. In my initial implementation, I did what you suggested on a standard u64. But bytecount adds SIMD to it (which I did not write): https://docs.rs/bytecount

I believe GNU grep just uses memchr for this. But I might be mis-remembering.

For line counting specifically, memchr isn't used, but rather, bytecount is: https://docs.rs/bytecount/0.6.2/bytecount/

However, memchr is still used for finding the bounds of a line when a match occurs. memchr still does pretty well on shorter haystacks too. The main loop is indeed quite large, but before that, it does unaligned loads of 32 bytes: https://github.com/BurntSushi/rust-memchr/blob/427fdc384007d...

I think in the general case, random strings, long patterns do not improve average performance.

Or rather nothing will change, once the pattern length exceeded the expected value for the alphabet used. E.g. for a simplified DNA alphabet, extended BC shifts on average 4 characters. On the fly I can't do the stochastics on GS, but I assume substring match length and chance of reoccurrence run against each other in a similar manner.

On the other hand long patterns increase preprocessing/access time: Extended BC and GS have O(m) for preprocessing, and BC may have non-constant access, depending on space tradeoff.

That is all true. You can however increase the effective alphabet size by working with n-grams of the needle rather than bytes. Even a 2 byte n-gram gives you an alphabet of 65536. You wouldn't get all of that as the hash table would probably be smaller, but you can increase the shifts a lot for longer patterns in this manner.

My gut is that "long string" just isn't that long nowadays. Even searching for a full UUID in a log doesn't do much to change the size of the needle relative to cache sizes. Though, maybe it is enough to help with some of the wide instruction choices?

(I am no expert at all!)

I mean yes of course in specific scenarios certain assumptions can be made. E.g. for UUIDs you probably better off exploiting the fixed length pattern too.

But for the general/theoretical case these intuitions do not pan out usually. I mean even "memory hacks" make assumptions about the data indirectly by common hardware architecture.

That is, most data isn't random strings of course XD

However when BM is used in e.g. bioinformatics on DNA and you are still stuck with firstly finding data against evolutionary noise, when your algorithms must adapt to your hypotheses, theory becomes more relevant I assume.

I think DNA focused "string search problems" are really inspiring and have a lot of potential for mingling with philosophical fundamentals of informatics. There is something about the evolutionary emergence of "data" AFAIK no other field offers. E.g. the overlapping, extending, or contextualizing information meta-layers upon meta-layers in DNA translation and structure "specified" to no more than merely exist. Throwing Boyer-Moore at ASCII encoded sequences in FASTA files almost feels blasphemous, or the arrogantly fallacious human essence.

I think using an alphabet of length 4 is probably a specialized enough use case that it deserves its own analysis from whole cloth if your goal is maximal performance.

I work on text search where the alphabet size is 256. If someone told me to work on text search where the alphabet size is 4, a lot of what I'd do would change, starting with my benchmark inputs.

So I kind of think responding to general claims about substring performance with, "well in DNA searching..." is kind of reframing the discussion to a specialized use case with very different priors. That is, I'm not sure anyone ever said running BM on DNA was a good idea. But maybe it's convenient, so that's what folks do. :-)

I don't think your comment your comment is a fitting response as I clearly stated this is about the general, theoretical stance, where you can't make assumptions about either the alphabet, nor the text.

As I recognized, introducing assumptions of course opens possibilities for doing things differently.

I was using the DNA example, because bioinformatics is where a lot of people learn about BMA, because the math is easy there and we are not tempted to make assumptions about the text, even tho it's not random. For most bioinfo applications the alphabet is not four letters, but e.g. the amino acid alphabet, or having additional sequence information included.

In bioinfo practice the naive algorithm often performs competitive against BMA if you optimize for hardware assumptions. Branch prediction is a bitch for BMA.

If you know the maximum width of the sub string you are searching for you can easily calculate the maximal forward jump, and hence you'll know when to issue a pre-fetch.

Having had a quick look at the AMD 17h processor family optimization guide, it would seem that the PREFETCHNTA opcode is the one you are looking for; it hints to the processor to pull the memory pointer close to the processor while avoiding polluting the cache.

For GCC it would seem that using this built in pseudo function call does the trick;

__builtin_prefetch((void *)p,0,0);

Yes ofc. I was making a theoretical argument. Assumptions about the data or hardware matter in practice, but they are not relevant for the theoretical exploration.

I imagine Boyer-More might still make sense for some applications, where the searched-for string is very long, such that whole blocks can be skipped.

Related TIL: ripgrep ̶d̶o̶e̶s̶n̶'̶t̶ edit mostly doesn't use Boyer-Moore. [0]

[0] https://github.com/BurntSushi/ripgrep/issues/493#issuecommen...

It does actually! But only in some cases. See https://github.com/BurntSushi/ripgrep/issues/617#issuecommen... and https://github.com/rust-lang/regex/issues/408 and https://github.com/rust-lang/regex/pull/419

Note though that it is going away soon. It's going to be replaced with a combination of Two-Way, Rabin-Karp and a fast vectorized prefilter based on this: http://0x80.pl/articles/simd-strfind.html#algorithm-1-generi...

The "secret sauce" is that in the vectorized prefilter, we don't just choose the first and last bytes. Instead, we pick bytes that we think will be rare based on a priori assumption of relative byte frequencies.

It's interesting that we're still seeing such interesting progress in such a fundamental problem. What kind of performance boost do you expect?

For queries that are already fast, I expect them to remain similarly fast. Or hope that they do. :-)

But there are many queries that are not so fast today. For example:

    $ time rg-master -Nc 'strengths' OpenSubtitles2018.raw.sample.en
    242

    real    0.255
    user    0.204
    sys     0.050
    maxmem  903 MB
    faults  0

    $ time rg -Nc 'strengths' OpenSubtitles2018.raw.sample.en
    242

    real    0.092
    user    0.068
    sys     0.024
    maxmem  904 MB
    faults  0

Where the second command has the new substring algorithm. Nothing earth shattering to be honest. ripgrep already did a good job of dealing with common cases.

This is ripgrep's current work-horse: https://github.com/rust-lang/regex/blob/3db8722d0b204a85380f...

The revised algorithm is based on the same principles (heuristics derived from an a priori frequency distribution), but shouldn't be as easy to get into cases where it runs very slowly. Here's another more poignant example (where the needle is two ASCII space characters):

    $ time rg-master -Nc '  ' OpenSubtitles2018.raw.sample.en

    real    0.887
    user    0.859
    sys     0.027
    maxmem  903 MB
    faults  0

    $ time rg -Nc '  ' OpenSubtitles2018.raw.sample.en

    real    0.084
    user    0.043
    sys     0.040
    maxmem  903 MB
    faults  0

> heuristics derived from an a priori frequency distribution

How did you come up with the frequency distribution? English text? Code samples? Languages other than English?

Yes, yes and yes. :-)

https://github.com/rust-lang/regex/blob/3db8722d0b204a85380f...

Wow, cool!

Since rg (which is awesome) understands which programming languages map to which file suffixes, could it make sense to do per-language frequency analysis? {}[] are common in C-style languages, but much less so in lisp, python, etc.

It could. But there's a lot of code complexity there because ripgrep is made from de-coupled components. Implementing your idea would require making that frequency distribution available as an overridable element all the way down into where substring search is actually implemented (a transitive dependency of ripgrep).

On top of that, it's unlikely to make much of a difference. Not only would the frequency distributions between languages look pretty similar, but it's still just a guess at the end of the day. There is such a thing as overfitting too. :-)