18 ms·

Why GNU grep is fast (2010)

• xiphias2 8y ago
  Ripgrep uses SSE3 parallelization instead of skipping input bytes to get faster on current architectures.
  • taeric 8y ago
    I'm assuming it still does both. Parallel is nice. Never touching a byte is tough to beat, though. I've often thought of making sure my IDs are uncommon characters to exploit the ability to skip a lot.
    • burntsushi 8y ago
      It does not. ripgrep does not use Boyer-Moore in most searches. In particular, the advice in the OP is generally out of date. The "secret" sauce to ripgrep's speed in simple literal searches is a simple heuristic: choose the rarest byte in the needle and feed that to memchr. (The "heuristic" is that you can't actually know the optimal choice, but it turns out that a guess works pretty well most of time since most things you search have a similar frequency distribution.) The SSSE3 optimizations come from Hyperscan, and are only applicable when searching a small number of small patterns. e.g., `Holmes|Watson|Moriarty|Adler`. In other words, for common searches (which are short strings), it is much better to spend more time in a vectorized routine than to try to skip bytes.
      • blattimwind 8y ago
        > In other words, for common searches (which are short strings), it is much better to spend more time in a vectorized routine than to try to skip bytes. Complexity analysis of substring search focuses on the number of comparisons – at least those I saw –, much like sorting, and of course that's not an accurate model at all.
      • taeric 8y ago
        This makes sense. Surprises me, but makes sense. I typically search for the largest string I can nowadays. Though, I suspect even those are not large enough to tip the needle, since I'm usually just talking about a uuid.
      • ComplexSystems 8y ago
        Interesting. Could this perform even faster if you (for large files) took a random sample of bytes before doing the search, to get the best distribution? Or just update the distribution as the search progresses.
        • burntsushi 8y ago
          It's probably more terrible than its worth, and you'd need to figure out how to take the sample in a way that doesn't kill performance. It would be an interesting experiment, but the usual heuristic is just to give up on fast skipping if it's ineffective.
      • adrianratnapala 8y ago
        >... but it turns out that a guess works pretty well most of time since most things you search have a similar frequency distribution.) This kind of thing is an pattern unless the benefit over Boyer-Moore huge. A small performance gain in the common-case is not worth the pain of introducing pathological cases that only bite you once you are deeply committed. Presumably this is not too bad for ripgrep itself, as long as it falls back to something sensible when the assumption fails.
        • TheCoelacanth 8y ago
          What pathological case are you referring to? The worst case I can think of is a completely random haystack in which case it is approximately equivalent to a naive search. Even Boyer-Moore is not superior to a naive search in literally every case, e.g. short needle or large alphabet.
        • burntsushi 8y ago
          This is wrong. Boyer-Moore does the same thing. It just always selects the last byte to feed into memchr. If that byte happens to be rare, then it works great. But if it happens to be common, then it gets into the weeds pretty quickly. My suggested heuristic does the same thing, but increases the chances that it selects a rare byte. And yes, the performance difference can be very large. Here's an example on a ~9.3GB file: $ time rg --no-mmap 'Sherlock ' OpenSubtitles2016.raw.en | wc -l 6698 real 3.006 user 1.658 sys 1.345 maxmem 8 MB faults 0 $ time grep 'Sherlock ' OpenSubtitles2016.raw.en | wc -l 6698 real 9.023 user 7.921 sys 1.092 maxmem 8 MB faults 0 Notice that the pattern is `Sherlock `. The last byte is an ASCII space character, which is incredibly common. Boyer-Moore blindly picks this as the skip byte, but ripgrep uses a simple pre-computed frequency table to select a better byte as the skip byte. > Presumably this is not too bad for ripgrep itself, as long as it falls back to something sensible when the assumption fails. It does. That's why I said, "ripgrep does not use Boyer-Moore in most searches."
• prolepunk 8y ago
  I've been using ack (https://beyondgrep.com/ https://beyondgrep.com/) for a while and it seems to be better suited for my specific purpose -- looking into source files and avoiding things like data dumps and VCS. It may be slower than grep, but it faster in the sense that I don't spend time remembering all the parameter combinations when I search for something. Here are a few aliases I use: alias ack="ack --color" # color output alias ackl="ack -l" # show file names only acksubl () { ack -l -i "${1}" | xargs subl } # Do case-insensitive search and open files in sublime. Turns out in practice I don't use regular expressions very often when searching text, and the most frequent question is -- where is this function/variable might have been used?
• harveywi 8y ago
  GNU grep is an excellent tool! A similar tool that is rising in popularity is ripgrep (https://github.com/BurntSushi/ripgrep https://github.com/BurntSushi/ripgrep), which can be orders of magnitude faster than GNU grep. Give it a try!
  • miguelmota 8y ago
    +1 for ripgrep. It's crazy fast
    • vmchale 8y ago
      It's more that it uses concurrency intelligently. The underlying stuff is similar to GNU grep.
      • OrgNet 8y ago
        > It's more that it uses concurrency intelligently if you don't do this at this point, there's a problem... because most CPUs are multicore
      • vesinisa 8y ago
        ripgrep's README has this to say about speed: > ripgrep is built on top of Rust's regex engine. Rust's regex engine uses finite automata, SIMD and aggressive literal optimizations to make searching very fast. Rust's regex library also maintains performance with full Unicode support by building UTF-8 decoding directly into its deterministic finite automaton engine.
        • cyphar 8y ago
          The author said in a sister thread[1] that for similar tasks the performance is comparable. ripgrep (and ag) both feel incredibly fast because they skip whole files and directories which are usually unwanted when searching. [1]: https://news.ycombinator.com/item?id=19523263 https://news.ycombinator.com/item?id=19523263
        • kibwen 8y ago
• Twirrim 8y ago
  It's probably worth pointing out that OS X is using BSD grep. You will see a phenomenal difference if you install the gnu grep via homebrew: $ homebrew info grep GNU grep, egrep and fgrep https://www.gnu.org/software/grep/ /usr/local/Cellar/grep/3.3 (21 files, 885.3KB) * Poured from bottle on 2019-01-03 at 12:23:37 From: https://github.com/Homebrew/homebrew-core/blob/master/Formula/grep.rb ... This is a very arbitrary example, but I've got 1.5Gb application log sitting on my machine right now that'll suffice. I'll even do this in a way that might give a slight performance advantage to BSD, by using gnu grep first: $ time /usr/local/bin/ggrep "foobarbaz" application.log real 0m1.319s user 0m0.948s sys 0m0.345s vs OSX's grep: $ time /usr/bin/grep "foobarbaz" application.log real 0m37.225s user 0m31.036s sys 0m1.286s 1s vs 37s. Same file. There's nothing odd about the file, straight boring application logs, and the line starts with the logging level in capital letters. So I can use a regex that is pinned to the start of the line, about as optimal as you can get: first gnugrep: $ time /usr/local/bin/ggrep -c "^INFO" application.log 1527786 real 0m0.622s user 0m0.323s sys 0m0.292s then OS X's native bsd grep: $ time /usr/bin/grep -c "^INFO" application.log 1527786 real 0m3.588s user 0m3.206s sys 0m0.349s BSD grep was significantly better than the prior search, but it is still notably slower than the gnu grep. In my experience, this isn't the most pathological example, but it's close. Note that this also applies to other tools that leverage grep under the surface, like zgrep etc. I've specifically aliased grep over to ggrep in my shell so that I'm avoiding bsd grep whenever I can: $ alias grep alias grep='/usr/local/bin/ggrep'
  • maxxxxx 8y ago
    How can it crunch through 1GB in 1s? Even just reading the data would take longer on any system I know.
    • Twirrim 8y ago
      The SM0512G in this machine is capable of over 1.5GB/s in sequential read. It's also possible that the file is cached in memory (I ran grep a few times through the file before I carried out the specific measurements).
• abhinai 8y ago
  Early on in my career, like most novice programmers, I thought that custom written C programs could be much faster than unix tools if written well and for a specific purpose. However, I could not beat the speed of unix tools like grep, cut or cat even once. That is when I realized just how well written these tools are and just how much optimization work has been done.
  • byte1918 8y ago
    https://www.reddit.com/r/unix/comments/6gxduc/how_is_gnu_yes_so_fast/?st=j3v3iw3c&sh=5651ea3c https://www.reddit.com/r/unix/comments/6gxduc/how_is_gnu_yes...
  • _bxg1 8y ago
    It's amazing to me how programs like these have seemed to avoid the universal phenomenon of technical debt. They've crystallized into an ideal version of themselves, and haven't continued to decay past that point. Maybe it's because of the Unix philosophy of single-purpose programs; no feature-creep tends to mean no technical debt.
    • Twirrim 8y ago
      By keeping a narrow focus and avoiding feature creep, the technical debt has been pretty minimal, and they've been able to pay it down easily. There's at least something to learn from the approach. It does also help that there is a certain type of developer that sees such things as a personal challenge and will go through hell and high water to come up with more and more efficient ways to do things.
      • deleted 8y ago
        [deleted]
    • asveikau 8y ago
      There is truth in what you say, however, if you think GNU tools are free of technical debt or feature creep, look into how ./configure works, as an example. Or, there's the old joke about GNU echo: https://www.gnu.org/fun/jokes/echo-msg.en.html https://www.gnu.org/fun/jokes/echo-msg.en.html
• js2 8y ago
  See also “The Treacherous Optimization (2006)”: http://ridiculousfish.com/blog/posts/old-age-and-treachery.html http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...
• wiredfool 8y ago
  TLDR: It cheats.
  • danso 8y ago
    That’s an interesting term in this context. The technique is so clever and the gains so big that it does feel a “cheat”. But as long as it replicates the behavior and effects and constraints of the previous algorithm, is it really a “cheat” even in the loosest sense of the word? It feels far more apt to view prior work as “tryhard”
• anonu 8y ago
  Previous Discussions: https://news.ycombinator.com/item?id=1626305 https://news.ycombinator.com/item?id=1626305 https://news.ycombinator.com/item?id=2393587 https://news.ycombinator.com/item?id=2393587 https://news.ycombinator.com/item?id=2860759 https://news.ycombinator.com/item?id=2860759 https://news.ycombinator.com/item?id=6814153 https://news.ycombinator.com/item?id=6814153 https://news.ycombinator.com/item?id=12350890 https://news.ycombinator.com/item?id=12350890 https://news.ycombinator.com/item?id=9153203 https://news.ycombinator.com/item?id=9153203 https://news.ycombinator.com/item?id=6813937 https://news.ycombinator.com/item?id=6813937 (edited)
  • dang 8y ago
    Thanks! It's great to provide links to previous discussions. Just so everybody knows: the links are for curiosity purposes. Reposts are ok after about a year, as the FAQ explains: https://news.ycombinator.com/newsfaq.html https://news.ycombinator.com/newsfaq.html
  • deleted 8y ago
    [deleted]
• lazyant 8y ago
  One of my favorite idioms for searching for a string: find /path -type f |xargs grep blah Has been replaced by `ag` https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher , ag is instant in a big repo compared to find|grep
  • twalla 8y ago
    it's mentioned elsewhere in this thread but you should try ripgrep https://github.com/BurntSushi/ripgrep https://github.com/BurntSushi/ripgrep
    • lazyant 8y ago
      will do, thanks !
    • hwj 8y ago
      ag has PCRE enabled by default. That's why I prefer it over ripgrep.
      • burntsushi 8y ago
        You might already know this, but the current release of ripgrep has support for PCRE2 (as opposed to PCRE1 in ag). All you need to do is pass the -P flag. If you want it enabled by default, then: echo -P > $HOME/.ripgreprc and add this to your .bashrc or equivalent: export RIPGREP_CONFIG_PATH="$HOME/.ripgreprc"
  • cyphar 8y ago
    Yes, though it should be noted that the reason it's faster is fewer command invocations and ignoring usually unwanted files (like .git/ and files listed in .gitignore). grep has a -R option which allows you to avoid the first problem, but avoiding the second one is a bit more difficult. Also there is ripgrep which I've heard is effectively a faster version of ag written in Rust.
    • gray_-_wolf 8y ago
• bibyte 8y ago
  From my experience GNU CLI tools make a particular effort to be really fast (even on embedded hardware).
  • creatornator 8y ago
    I think this is originally to avoid any possible plagiarism claims by Unix--if a Unix tool was originally optimized for one of size/efficiency/speed/memory use, the GNU tools were optimized for one of the others. This is part of why the `yes` utility is so freakin fast in GNU, despite being kind of a weird use case for speed. Mac builtin: yes | pv > /dev/null 139MiB 0:00:05 [28.4MiB/s] GNU: gyes | pv > /dev/null 3.31GiB 0:00:06 [ 584MiB/s]
    • zorked 8y ago
      I don't know if it is or isn't the plagiarism thing but GNU tools were written with a very different, way more modern style than Unix tools. Unix was pretty much "do a quick loop using terse code" and "see what fits in this static small buffer, and if it doesn't, quietly truncate". GNU would reallocate buffers to fit, and take reasonable precautions on performing well on tiny/huge inputs. GNU was actually considered bloated by the Unix crowd ("why so many more kilobytes of code?" ). It's an approach that scaled better for the future though.
      • creatornator 8y ago
        See section 2.1 of [0] and the top response to this comment [1]. You'll note in the GNU standards there, it encourages optimizing for the opposite of Unix to avoid collisions in strategy. [0] https://www.gnu.org/prep/standards/standards.html#Reading-Non_002dFree-Code https://www.gnu.org/prep/standards/standards.html#Reading-No... [1] https://news.ycombinator.com/item?id=14543536 https://news.ycombinator.com/item?id=14543536
    • kccqzy 8y ago
      It obviously has a bit of work put into it to make it fast: https://github.com/coreutils/coreutils/commit/35217221c211f3116f374f305654462195aa634a https://github.com/coreutils/coreutils/commit/35217221c211f3...
• westbywest 8y ago
  I think the author phrased it somewhat differently, but my understanding is grep's high throughput also comes from its use of what we (Computer Engineering grad research group) referred to as a variable state machine. A colleague was researching implementing analogous on an FPGA, for gigabit line-speed throughput. Preferred Computer Science term is apparently Thompson's NFA. https://en.wikipedia.org/wiki/Thompson%27s_construction#The_algorithm https://en.wikipedia.org/wiki/Thompson%27s_construction#The_...
  • burntsushi 8y ago
    Thompson's NFA construction, when used directly to search via an NFA simulation, is dog slow. It does give you a O(nm) search, but in practice it's slow. AIUI, GNU grep uses a lazy DFA, which uses Thompson's NFA construction to build a DFA at search time. This does indeed lead to pretty good performance for the regex engine. But GNU grep's speed largely comes from optimizing the common case: extracting literals from your pattern, identifying candidate matching lines, and then checking with the full regex engine to confirm (or reject) the match.
    • glangdale 8y ago
      I suspect Thompson's NFA is not inherently dog slow (Glushkov can be done reasonably fast for decent-sized NFAs). The fact is that most Thompson-lineage engines opted for the 'lazy DFA' approach and optimized that (which is effective until it isn't). I imagine a more aggressive 'native' Thompson NFA is possible. A nice benefit of that is not having to write to your bytecode - there's a good deal of systems-level complexity stuff in RE2 that springs out of a consequence of the 'lazy DFA construction' decision. That being said, matching literals is always going to be faster, especially if you decompose the pattern to get more use out of your literal matcher - the downside of filtration is that if the literal is always present, you are just doing strictly more work. At least with decomposition you've taken the literal out of the picture. See https://branchfree.org/2019/02/28/paper-hyperscan-a-fast-multi-pattern-regex-matcher-for-modern-cpus/ https://branchfree.org/2019/02/28/paper-hyperscan-a-fast-mul... for those who don't know what I'm talking about (I know you've read it). Am flirting with doing another regex engine that gets some of the benefit of decomposition and literal matching without taking on the nosebleed complexity of Hyperscan...
• peterwwillis 8y ago
  > The key to making programs fast is to make them do practically nothing. ;-) Also key to making them small, stable, intuitive, and usable
  • saagarjha 8y ago
    FWIW GNU's tools tend to be much larger and more complicated that competing versions of the same command.
    • peterwwillis 8y ago
      That's natural when you try to support a standard, are multi-platform, and have extra features.
  • djmips 8y ago
    I like to call this the Zen of optimization. Calm memory is fast.
• GalacticDomin8r 8y ago
  FWIW, BSD grep has significantly closed the gap since then, often by replication GNU approach in some ways. Also BSD grep has other advantages, primarily it's not GNU grep.
  • wglb 8y ago
    This is curious, as I just did a test with grep and ggrep. The latter is almost 3 times faster for a very common use case I have.
    • ComputerGuru 8y ago
      Presumably on macOS? Basically all BSD- or GNU-derived tools that ship on macOS are ancient, ancient versions that deserve to be burnt away and should not be considered indicative of what the current state-of-the-art is capable of.
    • GalacticDomin8r 8y ago
      grep -V ? ldd grep ? Use case sample ?
      • wglb 8y ago
        grep (BSD grep) 2.5.1-FreeBSD The other commenter in this thread pointed out that this is a very old version and the newer bsd version is better. real 0m2.044s user 0m1.932s sys 0m0.085s wgl@pondera:~$ time grep LiteonTe *.text | wc -l 11020 real 0m1.939s user 0m1.905s sys 0m0.038s wgl@pondera:~$ time ggrep LiteonTe *.text | wc -l 11020 real 0m0.130s user 0m0.087s sys 0m0.037s wgl@pondera:~$ time ggrep LiteonTe *.text | wc -l 11020 real 0m0.119s user 0m0.088s sys 0m0.035s wgl@pondera:~$ du -h -s *.text 128M Kismetkismet-kali-pondera-20190325-08-46-27-1.pcapdump.text First one was done to cache then the number discarded. Thus the 'grep' you see above is the second run over the 128 mb pcap file expanded with tshark. Dramatic. I'll stay with the gnu grep and not update the regular ones for now.
        • 8y ago
• opportune 8y ago
  Just in case anybody wants to look at the code, I think these two files [0, 1] contain the main logic when it comes to searching. Please correct me if these files aren't the right ones: [0] https://git.savannah.gnu.org/cgit/grep.git/tree/src/kwset.c https://git.savannah.gnu.org/cgit/grep.git/tree/src/kwset.c [1] https://git.savannah.gnu.org/cgit/grep.git/tree/src/kwsearch.c https://git.savannah.gnu.org/cgit/grep.git/tree/src/kwsearch...
  • TheDong 8y ago
    If you're going to link to gnu grep's source code, you might as well link to the actual git repo grep uses: https://git.savannah.gnu.org/cgit/grep.git/tree/src https://git.savannah.gnu.org/cgit/grep.git/tree/src
    • opportune 8y ago
      Thanks, didn't realize you could actually look at the source in browser for the savannah repo
• stirfrykitty 8y ago
  Also interesting, the Linux network stack is now faster than BSDs, which while a recent development, is still a feat.
  • auvi 8y ago
    could you please point me to a link where i can read about it? i am curious.
    • stirfrykitty 8y ago
      https://medium.com/@matteocroce/linux-and-freebsd-networking-cbadcdb15ddd https://medium.com/@matteocroce/linux-and-freebsd-networking...
      • auvi 8y ago
        thanks, I have got something to read for the weekend :)
  • trasz 8y ago
    Well, the Netflix folks claim the exact opposite :-) Also, note that there were some quite fundamental optimizations in FreeBSD 12, such as introduction of the “epoch” mechanism - basically RCU. 11 still only uses old-fashioned locks.
• blattimwind 8y ago
  For many situations the more complex substring search algorithms gave way to raw, brute force some time ago, I believe. For example, if you are looking for a given relatively short string, you can just take a prefix of say four bytes and then make parallel comparisons within a vector; this simple technique gets you already down to the general area of 1 cpb. The SSE 4.2 PCMPSTR family of instructions is basically the same thing but microcoded, and is a bit faster. For short patterns, which are imho by far the most common use, any algorithm that tries to be smart and skip a couple bytes wastes cycles on being smart where a simpler brute force algorithm has already fetched the next 16 bytes and started to compare them while the prefetcher already went off to get the next line from L2.
  • glangdale 8y ago
    When did you measure SSE4.2 against straightforward vector usage and find it faster? In my experience this was true more or less never. There's almost nothing in SSE4.2 that can't be done better with SSSE3. Intel has slowly deprecated SSE4.2 by not promoting it to wider vectors (it is still 128b when most other instructions are 512b) and letting the throughput/latency stagnate. 1 cycle per byte is not a good result for single string search; you can practically do a shift-and comparison of your input in that speed using general purpose registers.
    • blattimwind 8y ago
      That work was all in the context of searching for a binary string with a mask. I didn't try too long to optimize it, since performance was quickly satisfactory, so it's not just possible, but rather very likely that my implementation isn't particularly good. I'll keep your advice about SSE 4.2 in mind should I revisit that code. https://github.com/rust-lang/regex/blob/master/src/literal/teddy_ssse3/imp.rs https://github.com/rust-lang/regex/blob/master/src/literal/t... might be of interest to casual readers (not necessarily you, considering you were probably very involved in developing that algorithm ;)
      • glangdale 8y ago
        I wouldn't use "Teddy" to look for single strings, at least not without heavy modification. The boring approach of hunting for a predicate or two with PCMPEQB or equivalent then shift-and'ing things together has worked well in practice for that sort of thing, although it can be a bit brittle if you get the predicate(s) wrong.
• oneplane 8y ago
  This is simply a very good technical mailing list discussion. Instead of the whole BSD vs. GNU thing, you get to the point information sharing on processing structures. I do wonder about the later messages discussing the other string matching algorithms (on of them using a Trie to easily track back), while they are considered in the discussion, I didn't find any search/regex implementing them.
  • burntsushi 8y ago
    Are you referring to Aho-Corasick? If so, there are definitely some regex engines that use it, including I believe GNU grep: http://git.savannah.gnu.org/cgit/grep.git/tree/src/kwset.c http://git.savannah.gnu.org/cgit/grep.git/tree/src/kwset.c
    • oneplane 8y ago
      I must've been temporarily blind while scanning the src, thanks! The kinds of implementations that bring together various data structures and algorithms are usually rather interesting to read and learn from.
• KVFinn 8y ago
  I often have the experience of being like, "Surely I can't just do this entire task with a bunch of greps in a timely manner, it's going to take forever, right?" and then boom, the script takes like a minute to finish sorting through bazillions of lines.
• systematical 8y ago
  How is looking at the final letter of a string faster than starting with the first?
  • paulmd 8y ago
    As discussed in TFA: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-sea...
    • systematical 8y ago
      Yeah, thats easy to digest.
• ananonymoususer 8y ago
  This would depend upon which version of GNU grep one installs... About 10 years ago (when this article was written), I upgraded a RedHat system and discovered that some of my scripts were running 10 times slower than they had on the previous install. I isolated the issue to grep and benchmarked the grep from the previous release against the current release. The new grep was 10 times slower. I didn't have much more time to waste on the issue so I simply copied the grep binary from the previous release to the new install and everything was fine afterward.
  • acdha 8y ago
    This sounds a lot like when they started making it handle Unicode correctly. We ran into the same problem but fixed it by setting `LC_ALL=C` in the affected log processing scripts.
• EGreg 8y ago
  That’s so 2010. Here is what I like to read: https://blog.burntsushi.net/ripgrep/ https://blog.burntsushi.net/ripgrep/
• Erwin 8y ago
  This is the journal referenced in the mailing list: https://onlinelibrary.wiley.com/journal/1097024x https://onlinelibrary.wiley.com/journal/1097024x Seems the articles are free, if you don't want to pay the €6085 yearly instituational subscription. Other than Adrian's https://blog.acolyer.org/ https://blog.acolyer.org/ what else is there worth watching that is closer to engineering than theory? I wish we still had DDJ or C/C++ User Journal, but today's periodicals are things like Rasperry Pi enthusiast or Monthly Minecraft Tips.
• emmanueloga_ 8y ago
  I keep this on my bookmarks: [1] (that I fished from this other blog post [2]). Not sure if any actual search tools other than Scalyr use that specific implementation, but it makes for an interesting read anyway if you are into substring search algorithms (the algo described improves on Boyer-Moore). 1: http://volnitsky.com/project/str_search/ http://volnitsky.com/project/str_search/ 2: https://www.scalyr.com/blog/searching-1tb-sec-systems-engineering-before-algorithms https://www.scalyr.com/blog/searching-1tb-sec-systems-engine...
• slowrabbit 8y ago
  use ripgrep it's faster https://github.com/BurntSushi/ripgrep https://github.com/BurntSushi/ripgrep and appropriately named
  • burntsushi 8y ago
    Origins of the name: https://github.com/BurntSushi/ripgrep/blob/master/FAQ.md#intentcountsforsomething https://github.com/BurntSushi/ripgrep/blob/master/FAQ.md#int...
• alexnewman 8y ago
  I mean is it?
• wscott 8y ago
  "Old age and treachery will beat youth and skill every time." http://ridiculousfish.com/blog/posts/old-age-and-treachery.html http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...
• deytempo 8y ago
  I miss the days when the internet was mostly html pages
  • nostrademons 8y ago
    The Internet still mostly is HTML pages. It's just the portion of the Internet that you look at on a daily basis that has moved to JS-heavy SPAs.
• leonardmh 8y ago
  It’s not that fast (comparatively): https://blog.burntsushi.net/ripgrep/ https://blog.burntsushi.net/ripgrep/
  • deleted 8y ago
    [deleted]
• z3t4 8y ago
  Grep is a damn useful tool, I use it every day. But is it just me or does grep sacrifice convenience for performance ? Eg. it rather skips some bytes, then to make sure it finds everything. And case sensitive is default, where you most of the time want to find all case variations.
  • burntsushi 8y ago
    No. Skipping bytes is only done when you can prove there isn't a match. Please see my other comments in this thread. If you want case insensitive matching by default, then use: alias grep="grep -i"
• dreamcompiler 8y ago
  Yes, Boyer-Moore is ridiculously fast, but it's a string search algorithm, not a regular expression search algorithm. You can't use it for regexes. Is TFA still true when you're not searching for literal strings?
  • burntsushi 8y ago
    Yes, because it will extract literals from your regex and seaech for those first. When a match of the literal is found, all you then need to do is find the line boundaries of that match and run the regex engine on just that line. It ends up working pretty well. Of course, if your regex has no required literals at all, then this optimization can't be performed. GNU grep can slow down quite a bit in these cases, especially if you have a non-C locale enabled and use some Unicode aware features such as \w.
• peter_d_sherman 8y ago
  Boyer-Moore + Loop Unrolling... fast. But, perhaps it could be improved further via SSE instructions, or by sending the data to a GPGPU and parallelizing the algorithm...
  • djmips 8y ago
    see ripgrep mentioned elsewhere in comments.