3 ms·

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

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.)

taeric 6y ago
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.
- burntsushi 6y ago
  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.
  - taeric 6y ago
    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?
    - burntsushi 6y ago
      > 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/427fdc384007d0a5b00b190e8313b3c8d3694a67/src/x86/sse2.rs#L18 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.
      - scottlamb 6y ago
        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.
        a1369209993 6y ago
        > 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.
        6y ago
- lofi_lory 6y ago
  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.
  - taeric 6y ago
    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?
    - lofi_lory 6y ago
      (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.
      - 6y ago

taeric 6y ago

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.

burntsushi 6y ago
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.
- taeric 6y ago
  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?
  - burntsushi 6y ago
    > 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/427fdc384007d0a5b00b190e8313b3c8d3694a67/src/x86/sse2.rs#L18 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.
    - scottlamb 6y ago
      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.
      - a1369209993 6y ago
        > 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.
        6y ago
lofi_lory 6y ago
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.
- taeric 6y ago
  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?
  - lofi_lory 6y ago
    (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.
    - 6y ago