6 ms·

Interesting, but I’m not sure the algorithm aged well. Memory is a block device now. DDR delivers 8 bytes per transaction per channel, e.g. 16 bytes per transa

Interesting, but I’m not sure the algorithm aged well. Memory is a block device now. DDR delivers 8 bytes per transaction per channel, e.g. 16 bytes per transaction for dual-channel memory configuration. Skipping bytes delivers little profit in terms of memory bandwidth (but it saves other things, CPUs have very small limit how many memory load instructions can run per cycle). SIMD instructions can compare vectors for about the same cost as scalars, e.g. _mm_cmpeq_epi8 (SSE2) and vceqq_u8 (NEON) compare 16 bytes with another 16 bytes. If I wanted a super-fast substring search, I would try to leverage these things.

beagle3 6y ago
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.
- lofi_lory 6y ago
  Harder to argue about character frequency in DNA/RNA sequences.
  - pmiller2 6y ago
    Naively, I'd expect all letters to occur equally frequently. Do you know if this is the case?
    - thamer 6y ago
      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 https://en.wikipedia.org/wiki/GC-content [2] https://en.wikipedia.org/wiki/DNA_and_RNA_codon_tables https://en.wikipedia.org/wiki/DNA_and_RNA_codon_tables
      - lofi_lory 6y ago
        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.
tankenmate 6y ago
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.
- tankenmate 6y ago
  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);
- lofi_lory 6y ago
  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.
MaxBarraclough 6y ago
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#issuecomment-304847996 https://github.com/BurntSushi/ripgrep/issues/493#issuecommen...
- burntsushi 6y ago
  It does actually! But only in some cases. See https://github.com/BurntSushi/ripgrep/issues/617#issuecomment-354568111 https://github.com/BurntSushi/ripgrep/issues/617#issuecommen... and https://github.com/rust-lang/regex/issues/408 https://github.com/rust-lang/regex/issues/408 and https://github.com/rust-lang/regex/pull/419 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-generic-simd 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.
  - MaxBarraclough 6y ago
    It's interesting that we're still seeing such interesting progress in such a fundamental problem. What kind of performance boost do you expect?
    - burntsushi 6y ago
      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/3db8722d0b204a85380fe2a65e13d7065d7dd968/src/literal/imp.rs#L370-L501 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
burntsushi 6y ago
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?
      - 6y ago

beagle3 6y ago

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.

lofi_lory 6y ago
Harder to argue about character frequency in DNA/RNA sequences.
- pmiller2 6y ago
  Naively, I'd expect all letters to occur equally frequently. Do you know if this is the case?
  - thamer 6y ago
    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 https://en.wikipedia.org/wiki/GC-content [2] https://en.wikipedia.org/wiki/DNA_and_RNA_codon_tables https://en.wikipedia.org/wiki/DNA_and_RNA_codon_tables
    - lofi_lory 6y ago
      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.

tankenmate 6y ago

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.

tankenmate 6y ago
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);
lofi_lory 6y ago
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.

MaxBarraclough 6y ago

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#issuecomment-304847996 https://github.com/BurntSushi/ripgrep/issues/493#issuecommen...

burntsushi 6y ago
It does actually! But only in some cases. See https://github.com/BurntSushi/ripgrep/issues/617#issuecomment-354568111 https://github.com/BurntSushi/ripgrep/issues/617#issuecommen... and https://github.com/rust-lang/regex/issues/408 https://github.com/rust-lang/regex/issues/408 and https://github.com/rust-lang/regex/pull/419 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-generic-simd 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.
- MaxBarraclough 6y ago
  It's interesting that we're still seeing such interesting progress in such a fundamental problem. What kind of performance boost do you expect?
  - burntsushi 6y ago
    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/3db8722d0b204a85380fe2a65e13d7065d7dd968/src/literal/imp.rs#L370-L501 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

burntsushi 6y ago

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?
    - 6y ago