Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ripgrep – A new command line search tool

blog.burntsushi.net

Post reply on HN
Print view View original

161–170 of 219 posts

Re: Ripgrep – A new command line search tool

#161

Post by JoshTriplett »

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…

> Do you know any engines that actually do this? As in, is it really standard?

I don't know about choosing between multiple regex engines, but GNU grep and other grep implementations check for non-regex fixed strings or trivial patterns, and have special cases for those.

Re: Ripgrep – A new command line search tool

#162

Post by prattmic »

brandmeyer wrote: post #107
karmakaze wrote: post #61

Earlier quoted context omitted.

I recently questioned if/ why parallel mmap might be slower without a satisfactory conclusion. One specific thing I couldn't answer is if reusing the same filesystem buffer and program memory addresses has a less negative effect than reading a wide range of mapped memory addresses.

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), munmap(2), etc syscalls, and page faults being handled for other threads. (i.e., mmap(2) takes the mmap_sem semaphore for writing). Running threads are not halted. The page tables are not touched at all during mmap, unless MAP_POPULATE is passed. (Linux delays actual population of the page tables until the page is accessed.)

The page fault handler takes mmap_sem for reading (synchronizing with mmap(2), etc, but allowing multiple page fault handlers to read concurrently) the mappings and page_table_lock for the very small period when it actually updates the page tables.

Again, running threads are not halted. The active page tables are updated while other cores may be accessing them. This must be done carefully to avoid spurious faults, but it is certainly feasible.

In fact, at least on x86, handling page faults does not require a TLB flush. The TLB does not cache non-present page table entries, and taking a page fault invalidates the entry that caused the fault, if one existed.

There are plenty of places here that may cause contention, but nothing nearly so bad as halting execution.

munmap will be rather noisy. It involves tons of invalidations and a TLB flush. I wouldn't be surprised if a good bit of performance could be regained by avoiding munmapping the file until the process exits.

Re: Ripgrep – A new command line search tool

#163

Post by thristian »

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…

Apparently Vim does this: http://vimhelp.appspot.com/pattern.txt.html#two-engines

Re: Ripgrep – A new command line search tool

#164

Post by burntsushi »

JoshTriplett wrote: post #161
burntsushi wrote: post #151

Earlier quoted context omitted.

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…

> Do you know any engines that actually do this? As in, is it really standard? I don't know about choosing between multiple regex engines, but GNU grep and other grep implementations check for non-regex fixed strings or trivial patterns, and have special cases for those.

Well... yeah... I was more thinking about really big switches like between PCRE and a DFA.

It looks like the sibling comment found one that I think qualifies based on the description (assuming "NFA" is used correctly :P).

Re: Ripgrep – A new command line search tool

#165

Post by pcwalton »

saurik wrote: post #129
burntsushi wrote: post #78

Earlier quoted context omitted.

> (or maybe had some core in there that was, while leaving the other UI parts he wants to change on top) But I did! Have you looked at the dependency list of ripgrep? It's utterly filled with tons of tools that you can pick out and use in other projects for any purpose you like. I didn't mention this in the blog post because there's already too much there, but sure, here they are: memchr - Fast single byte search: ht…

> I'm sure five years from now, when I've moved on to other problems, someone will come along and beat ripgrep, and I can only hope that they write about it. :-) I contend that the world would be a much better place if instead of someone building a new tool which beats yours, they worked to improve your tool (which, at the point where you moved on, would hopefully have been granted to a body of separate maintainers,…

I don't really accept moral arguments that argue that one thing is a better use of one's free time than some other thing. Even the best cancer researchers have every right to use their free time to watch a movie or read fiction instead of working on solving problems, even though they could theoretically save human lives by doing so. If they get to, then surely people who write programmer tools to search files get to do whatever they want in their free time too.

The author chose to spend his time writing his own file searching tool instead of trying to work with GNU. That's his call.

Re: Ripgrep – A new command line search tool

#166

Post by ggreer »

petre wrote: post #156
ggreer wrote: post #63

I'm the author of ag. That was a really good comparison of the different code searching tools. The author did a great job of showing how each tool misbehaved or performed poorly in certain circumstances. He's also totally right about defaults mattering. It looks like ripgrep gets most of its speedup on ag by: 1. Only supporting DFA-able Rust regexes. I'd love to use a lighter-weight regex library in ag, but users are…

I've just installed ag. It defaults to case insensitive searches when the pattern is in lowercase. Is there a way to change this default? Perhaps a config file of some sort?

There's no config file for default options. You probably want to add an alias to your bash/zsh/fishrc:

    alias ag='ag -s'
I tend to favor aliases over config files. It reduces complexity and improves startup time. Startup time may not seem like a big deal, but it really matters if you're running something like:

    find . -ctime 2 -exec ag blah
(Find all files modified in the past two days and search them for instances of "blah".) If 10,000 files were changed in the past two days, and your search program takes 10 milliseconds to parse a config file, that's an extra 100 seconds wasted.

Re: Ripgrep – A new command line search tool

#167

Post by fragmede »

ggreer wrote: post #63

I'm the author of ag. That was a really good comparison of the different code searching tools. The author did a great job of showing how each tool misbehaved or performed poorly in certain circumstances. He's also totally right about defaults mattering. It looks like ripgrep gets most of its speedup on ag by: 1. Only supporting DFA-able Rust regexes. I'd love to use a lighter-weight regex library in ag, but users are…

> It looks like ripgrep gets most of its speedup on ag by:

A non-trivial amount of time spent is simply reading the files off the disk. If speed is the all-encompassing metric, there's a big gain to be made by pre-processing the files into an index and loading that into memory instead, and that's what livegrep[1] does.

If you find yourself waiting for grep often enough, it's a pretty handy internal tool to configure across all repos.

[1] https://livegrep.com/about

Re: Ripgrep – A new command line search tool

#168

Post by rocho »

burntsushi wrote: post #66
ggreer wrote: post #63

I'm the author of ag. That was a really good comparison of the different code searching tools. The author did a great job of showing how each tool misbehaved or performed poorly in certain circumstances. He's also totally right about defaults mattering. It looks like ripgrep gets most of its speedup on ag by: 1. Only supporting DFA-able Rust regexes. I'd love to use a lighter-weight regex library in ag, but users are…

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!

Re: Ripgrep – A new command line search tool

#170

Post by therein »

fragmede wrote: post #167
ggreer wrote: post #63

I'm the author of ag. That was a really good comparison of the different code searching tools. The author did a great job of showing how each tool misbehaved or performed poorly in certain circumstances. He's also totally right about defaults mattering. It looks like ripgrep gets most of its speedup on ag by: 1. Only supporting DFA-able Rust regexes. I'd love to use a lighter-weight regex library in ag, but users are…

> It looks like ripgrep gets most of its speedup on ag by: A non-trivial amount of time spent is simply reading the files off the disk. If speed is the all-encompassing metric, there's a big gain to be made by pre-processing the files into an index and loading that into memory instead, and that's what livegrep[1] does. If you find yourself waiting for grep often enough, it's a pretty handy internal tool to configure…

You just said that to the author of The Silver Searcher (ag).

[0] https://github.com/ggreer/the_silver_searcher

Post reply on HN