Sneller Regex vs Ripgrep
Thanks for responding!<p>&gt; but considering that regex handling is a common task, it would be a missed opportunity not to consider AVX-512.<p>Just to be really clear here, it&#x27;s less about &quot;not considering it&quot; and more about &quot;not prioritizing it.&quot; I don&#x27;t have any telemetry on where ripgrep is running, but I would guess that 99% of its uses are on consumer hardware. And consumer hardware is heading in a direction that doesn&#x27;t include AVX-512. That lowers the priority for using it, especially when AVX-2 is available nearly everywhere. And indeed, ripgrep uses AVX-2.<p>&gt; While ripgrep delegates compression to other tools, I&#x27;m curious about your approach to decompression if you really needed it. I&#x27;m interested in exploring ways in which people do use ripgrep with compression. Do you use transparent disk compression?<p>I don&#x27;t really have an approach. ripgrep&#x27;s decompression support isn&#x27;t really about performance or improving throughput. It&#x27;s just about the user experience. It&#x27;s about making it easier to search stuff without having to decompress it explicitly first. You have a `foo.txt.gz` on your system? Great, ripgrep can search it using the standard tools available to you.<p>The separate question of making that faster (`gzip -d` is usually not the fastest way to decompress gzipped data for example) is something I&#x27;d like to explore in the future.<p>The <i>other</i> separate question of how to integrate compression and searching such that the holistic result unlocks interesting use cases and potentially even makes the overall search faster is not a use case that ripgrep really cares about. The important thing with ripgrep is about being able to search <i>existing</i> compressed data using standard tools.<p>What I&#x27;m trying to say here is that Sneller has a much more specialized and interesting target audience than ripgrep. :-)<p>&gt; Can you explain how you calculated that. In our calculation we accounted for the time needed to do the decompression.<p>I&#x27;m looking at `Regex1` in your table. ripgrep has a reported timing of 3.899s and Sneller with one thread has a reported timing of 10.024s.<p>&gt; Could you give some of those questions?<p>I tried to include those scattered around in my original comment. Otherwise I don&#x27;t know what was on my mind when I wrote that. It was a while ago.<p>&gt; That is unfortunate, because in Go `\w` is the Perl word character class `[0-9A-Za-z_]` (<a href="https:&#x2F;&#x2F;pkg.go.dev&#x2F;regexp&#x2F;syntax" rel="nofollow">https:&#x2F;&#x2F;pkg.go.dev&#x2F;regexp&#x2F;syntax</a>) and not what you use, which I assume is `\p{L}`. The state of the DFA with `\p{L}` has 12 states and 1291 edges, compared to 12 states and 132 edges with `\w`. When would you call a DFA enormous or impractical?<p>How are you getting 12 states for \pL?<p>DFAs with Unicode aware \w are about a couple orders of magnitude bigger than DFAs with an ASCII-only \w:<p><pre><code>    $ regex-cli debug dense dfa -p &#x27;\w&#x27; -q --minimize --start-kind unanchored
          parse time:  28.222µs
      translate time:  28.317µs
    compile nfa time:  915.99µs
    compile dfa time:  12.150283ms
              memory:  159296
         pattern len:  1
          start kind:  Unanchored
        alphabet len:  113
              stride:  128
          has empty?:  false
            is utf8?:  true
    $ regex-cli debug dense dfa -p &#x27;(?-u)\w&#x27; -q --minimize --start-kind unanchored
          parse time:  35.948µs
      translate time:  32.843µs
    compile nfa time:  67.048µs
    compile dfa time:  102.022µs
              memory:  384
         pattern len:  1
          start kind:  Unanchored
        alphabet len:  10
              stride:  16
          has empty?:  false
            is utf8?:  true
</code></pre>
That&#x27;s with DFA minimization. Also, &#x27;\w&#x27; has 311 states while &#x27;(?-u)\w&#x27; has 5 states.<p>I don&#x27;t have a precise definition of enormous or impractical. Does it matter? I suppose one obvious one is when DFA construction time starts having a significant impact on total search times.<p>&gt; Additionally, the results are not the same: the number of matches is not equal to 7882. How could I make `\w` conform to other regex implementations in ripgrep?<p>By following UTS#18: <a href="https:&#x2F;&#x2F;unicode.org&#x2F;reports&#x2F;tr18&#x2F;#word" rel="nofollow">https:&#x2F;&#x2F;unicode.org&#x2F;reports&#x2F;tr18&#x2F;#word</a><p>Most regex engines make \w be ASCII-only by default. But most also have a way to opt into Unicode-aware mode. RE2, Go&#x27;s regexp and ECMAScript are popular regex engines that have no way to change the interpretation of \w.<p>&gt; Fair question how regex compilers handle nefarious regexes. Go does not handle NFA with more than 1000 states, and, as you observed, we added some more restrictions when processing the NFA. It can be an interesting academic exercise to find monstrous regexes, but we haven&#x27;t encountered useful regexes that hit these limits. But I guess you know some...<p>It&#x27;s definitely not academic. People use regexes for lexers. People use big regexes to recognize certain things like email addresses and dates. Here&#x27;s a real regex used in real software to identify dates in unstructured text for example: <a href="https:&#x2F;&#x2F;github.com&#x2F;akoumjian&#x2F;datefinder&#x2F;blob&#x2F;5376ece0a522c44762b1ab656fc80737b427ed16&#x2F;datefinder&#x2F;constants.py#L112-L124">https:&#x2F;&#x2F;github.com&#x2F;akoumjian&#x2F;datefinder&#x2F;blob&#x2F;5376ece0a522c44...</a><p>Otherwise, as I hinted at above, the thing that can make regexes very large very quickly is when you mix Unicode classes with counted repetitions. It doesn&#x27;t take a lot to make them &quot;big.&quot;