Ripgrep – A new command line search tool • Hacker News Board

Re: Ripgrep – A new command line search tool

#171

Post by livestockboy » Sat, Sep 24, 2016, 8:41 AM UTC

dgr-nn-glth wrote: post #145

livestockboy wrote: post #92

Earlier quoted context omitted.

Pandoc Xmonad Darcs Git-annex Although, it would be very hard to write SIMD performant code in Haskell, even its string libraries don't use any optimization tricks.

I was excited when I heard of it, but I thought Darcs had run into some major issues with patch theory and exponential merges. Other than it being written in Haskell, why would I use it over git?

Well, speed issues are currently not that noticeable (a lot of times passed since initial bumps) but I'm pretty sure some large repositories (more than millions of lines of patches) wouldn't be able to work with it.

git is a whole different story compared to darcs, darcs is simpler to use, especially when merging.

if it was consistently fast I'm pretty sure git wouldn't be as popular as it is.

there is rust vcs https://pijul.org/ that seems to be doing the same thing as darcs but faster.

so I guess CJefferson's controversial comment stands :D

Re: Ripgrep – A new command line search tool

#172

Post by krylon » Sat, Sep 24, 2016, 9:22 AM UTC

burntsushi wrote: post #83

krylon wrote: post #42

When I use grep (which is fairly regularly), the bottleneck is nearly always the disk or the network (in case of NFS/SMB volumes). Just out of curiosity, what kind of use case makes grep and prospective replacements scream? The most "hardcore" I got with grep was digging through a few gigabytes of ShamePoint logs looking for those correlation IDs, and that apparently was completely I/O-bound, the CPUs on that machine…

> Just out of curiosity, what kind of use case makes grep and prospective replacements scream? Unicode? Check out the subtitle benchmarks in the blog post. In the best case, grep is a little slower. In the worst case, grep is orders of magnitude slower. ripgrep achieves speed by building UTF-8 decoding straight into its DFA regex engine (well, strictly speaking, this is Rust's regex engine, not ripgrep). The other ca…

Thanks for the explanation!

Re: Ripgrep – A new command line search tool

#173

Post by skanga » Sat, Sep 24, 2016, 9:23 AM UTC

pohl wrote: post #136

losvedir wrote: post #29

Meh, yet another grep tool.... wait, by burntsushi! Whenever I hear of someone wanting to improve grep I think of the classic ridiculous fish piece[0]. But when I saw that this one was by the author of rust's regex tools, which I know from a previous post on here, are quite sophisticated, I perked up. Also, the tool aside, this blog post should be held up as the gold standard of what gets posted to hacker news: detai…

Another burntsushi project was recently posted, but didn't get much attention: https://news.ycombinator.com/item?id=12559515

Looks interesting. But I did not find binaries for it and do not want to setup a rust env to try it out.

Re: Ripgrep – A new command line search tool

#174

Post by visarga » Sat, Sep 24, 2016, 11:10 AM UTC

Great tool. Does there exist a faster implementation of sort as well? I once implemented quicksort in C and it was faster than Unix sort by a lot, I mean, seconds instead of minutes for 1 million lines of text.

Re: Ripgrep – A new command line search tool

#175

Post by luckman212 » Sat, Sep 24, 2016, 12:36 PM UTC

skanga wrote: post #173

pohl wrote: post #136

Earlier quoted context omitted.

Another burntsushi project was recently posted, but didn't get much attention: https://news.ycombinator.com/item?id=12559515

Looks interesting. But I did not find binaries for it and do not want to setup a rust env to try it out.

The releases are right there on GitHub: https://github.com/BurntSushi/ripgrep/releases

Re: Ripgrep – A new command line search tool

#176

Post by burntsushi » Sat, Sep 24, 2016, 12:51 PM UTC

rocho wrote: post #168

burntsushi wrote: post #66

Earlier quoted context omitted.

Thanks for the response! Some notes: 1. In my benchmarks, I do control for line numbers by either explicitly making it a variable (i.e., when you see `(lines)`) or by making all tools count lines to make the comparison fair. For the most part, this only tends to matter in the single-file benchmarks. 2. For memory maps, you might get very different results depending on your environment. For example, I enabled memory m…

I just made a cursory pass at `man rg`, but it seems to me that the `-g` option from ag is also missing. I use it with vim-ctrlp to search file names. Thanks for rg and the very informative blog post!

It's there. You need to pass --files.

Re: Ripgrep – A new command line search tool

#177

Post by burntsushi » Sat, Sep 24, 2016, 12:57 PM UTC

visarga wrote: post #174

Great tool. Does there exist a faster implementation of sort as well? I once implemented quicksort in C and it was faster than Unix sort by a lot, I mean, seconds instead of minutes for 1 million lines of text.

I've never waited more that a few milliseconds to sort a million lines.

I expect GNU sort does quite a bit, including handling data sets that don't fit into memory.

Anyway, this post is about regexes, which really has nothing at all to do with sorting. They are two very different problems. :)

Re: Ripgrep – A new command line search tool

#178

Post by jakewins » Sat, Sep 24, 2016, 3:22 PM UTC

burntsushi wrote: post #151

JoshTriplett wrote: post #138

Earlier quoted context omitted.

> 1. Only supporting DFA-able Rust regexes. I'd love to use a lighter-weight regex library in ag, but users are accustomed to full PCRE support. Switching would cause me to receive a lot of angry emails. Maybe I'll do it anyway. PCRE has some annoying limitations. (For example, it can only search up to 2GB at a time.) The standard trick here is to use the faster method for searches that it supports, and use the slowe…

Do you know any engines that actually do this? As in, is it really standard? I thought maybe Spencer's Tcl regex engine did it? Although I confess, I've never read the source. I guess RE2/Rust/Go all kind of do it as well. For example, RE2/Rust/Go will actually do backtracking in some cases! (It's bounded of course, maintaining linear time.) But this doesn't actually meet the criteria of being able to support more ad…

This is probably a digression.. While it's not a regex engine, and I suppose this is standard in compiler development, the Neo4j query planner team uses this approach extensively to incrementally introduce new techniques or to add pointed optimizations.

For instance, Neo4j chooses between a "rule" planner, which can (at least while I still worked at Neo) solve any query and a "cost" planner, which can solve a large subset. For those queries the cost planner can solve, it usually makes significantly better plans, kind of like the example with regex engines here.

For the curious, that happens here: https://github.com/neo4j/neo4j/blob/3.1/community/cypher/cyp...

Likewise, once a plan is made, there are two runtimes that are able to execute them - an interpreting runtime that can execute any plan, and a compiling runtime that converts logical plans to JVM bytecode, much faster but only supports a subset.

That choice is made here: https://github.com/neo4j/neo4j/blob/3.1/community/cypher/cyp...

This goes on in finer and finer detail. Lots of similar examples in how the planners devise graph traversal algorithms on the fly, by looking for patterns they now and falling back to more generic approaches if need be.

FWIW, the overhead of this has, I would argue, massively paid for itself. It has made extremely ambitious projects, like the compile-to-bytecode runtime and the cost-based query planner safely deliverable in incremental steps.

Re: Ripgrep – A new command line search tool

#179

Post by haileys » Sat, Sep 24, 2016, 3:57 PM UTC

wyldfire wrote: post #142

ggreer wrote: post #103

Earlier quoted context omitted.

In terms of core features, ripgrep is totally there. It searches fast . It ignores files pretty accurately. It outputs results in a pleasant and useful format. If a new user tries rg, they'll be very happy. My warning about the feature differences was meant to temper ag users' expectations. There are lots of little things that ag users are accustomed to that are either different or missing in ripgrep. Off the top of…

> detects stdout redirects Is there a portable way for you to find out that stdout is connected to output.txt? isatty() only tells you that there may be a redirection and I suppose on linux you could use /proc/self/fd/1 but I don't know how to do it portably.

If output is redirected, ag calls fstat on stdout and records the inode. It then ignores files based on inode rather than path:

https://github.com/ggreer/the_silver_searcher/blob/b995d3b82...

Re: Ripgrep – A new command line search tool

#180

Post by brandmeyer » Sat, Sep 24, 2016, 5:17 PM UTC

prattmic wrote: post #162

brandmeyer wrote: post #107

Earlier quoted context omitted.

Since all processors must share the mapping, - The initial mapping of each file in any thread must halt all of the threads which are otherwise active. - Every page fault in any mapping must also halt all of the threads. Worse, since the page tables are getting munged, some or all of the TLB cache is getting flushed every time, again, on every processor. I'm not sure of the details, but this hypothesis should be direc…

- The initial mapping of each file in any thread must halt all of the threads which are otherwise active. - Every page fault in any mapping must also halt all of the threads. These are certainly not the case on Linux, and I'd imagine not on other OSes, as it would be terrible for performance. Each mapping (i.e., mmap(2) call) is synchronized with other paths that read process memory maps, such as other mmap(2), munma…

So, I did some testing with 'perf'. This is on an older Intel processor, 2-cores with hyperthreading. These were all done on the same set of files, using the binary release of ripgrep v0.1.16 on Debian Jessie:

At -j1, --mmap: 95 kdTLB load-misses, 2800 page faults

At -j2: --mmap: 170 kdTLB load-misses, 2840 page faults

At -j3: --mmap: 230 kdTLB load-misses, 2800 page faults

At -j4, --mmap: 4180 context switches, 2900 page faults, 200 Minsn, 280 kDTLB load misses, 35 MDTLB loads

At -j1, --no-mmap: 50 kdTLB load misses, 635 page faults

At -j2, --no-mmap: 70 kdTLB load misses, 675 page faults

At -j3, --no-mmap: 90 kdTLB load misses, 715 page faults

At -j4, --no-mmap: 377-400 context switches, 750 page faults, 275 Minsn, 100 kDTLB load misses

As the number of threads goes up, the total amount of TLB pressure goes up in both cases. These results are consistent with a number of TLB cache flushes proportional to N_threads * M_mappings + C for the --mmap case, and N_threads * M_buffer_perthread + D for the --no-mmap case. I think that does support the model that each thread's mmap adds pressure to all of the threads TLB's.