5 ms·
I've not looked too far into it but my guess is that ripgrep being faster is just due to Gnu grep using a slower algorithm (and supporting unnecessary extension
by 2038AD 6y ago
I've not looked too far into it but my guess is that ripgrep being faster is just due to Gnu grep using a slower algorithm (and supporting unnecessary extensions). The Rust regex library excludes look-arounds and backreferences and is openly inspired by RE2. Russ Cox, one of the guys behind RE2, wrote something[0] on the topic.
[0] https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
- burntsushi 6y agoNo, that's not why. I wrote about why: https://blog.burntsushi.net/ripgrep/ https://blog.burntsushi.net/ripgrep/ GNU grep doesn't have look-arounds either. It does have back-references, but that doesn't impact searches that don't use back-references. I don't think there is really a concise way to describe why ripgrep is faster when comparing apples-to-apples. It depends on the queries and the corpus. The primary reasons are that it makes more efficient use of the hardware with algorithms that utilize SIMD. If you do an apples-to-oranges comparison (i.e., "why is `rg foo ./` so much faster than `grep -r foo ./`), then the answer is pretty easily "because ripgrep uses parallelism and employs smart filtering by default."
- pjot 6y agoGenuinely curious how you noticed that this thread had referenced your work. And, ironically enough, a thread about text search!
- burntsushi 6y agoFor this thread, I just saw a thread that mentioned grep. At that point, I naturally gravitate toward it since I'm obviously very interested in the topic!
- pjot 6y agoPretty cool coincidence nonetheless! The reason I asked was because I noticed that your comment was within minutes of the parent comment which was a response to another comment about _your_ text-search project and how fast it is. I said out loud, "Wow" and browsed through ripgrep. Nice work! Was torn on whether you were tailing the HN api with ripgrep to alert you or if it was just the right place and time. I had a good time going through how that would work, so, thank you haha! Occam's razor, right?
- burntsushi 6y agoHah. Nah nothing like that. Just right place right time. When you combine that with the fact that I probably check HN a little too frequently, it makes sense. :P I do occasionally manually search HN for mentions of ripgrep. But that wasn't how I found this thread.
- dilap 6y agoWeird question for you: how much of ripgrep's awesomeness is you/product focus vs. the power of rust? To put it another way, do you think you could've written ripgrep in another language? In C? In C++? In Go?
- burntsushi 6y agoI think Rust is probably a force multiplier here. The same program, IMO, would be harder to maintain in a language like C or C++. Although of course there are alternatives to ripgrep written in C or C++, so I'm not sure how compelling of an argument that is. But the force multiplier doesn't just need to make me more productive. Rust makes it pretty natural to factor things into libraries, and developing ripgrep over the years has caused me to produce many of them. Those in turn have been reused by other tooling, including rustc and Cargo themselves. That is something you don't often see in the C or C++ world. As for Go, I don't know. The garbage collector seems likely to be a problem. Ben Boyter wrote about working on a similarish tool in Go and problems with the GC: https://boyter.org/posts/sloc-cloc-code-performance/ https://boyter.org/posts/sloc-cloc-code-performance/ At the very least, such a tool in Go would probably require writing your own regex engine if you want to get comparable performance. (You can see how similar tools in Go, such as pt and sift, fall off a performance cliff as soon as you lean too heavily on the regex engine.) Or at the very least, contribute back to Go's standard library and make `regexp` faster. Whether it can match the speed of a Rust/C/C++ regex engine, I don't know. It's an open question I think.
- dilap 6y agoThanks for the thoughtful response! My own experience w/ Rust is limited to just kicking the tires implementing my favorite toy problem, but it was incredibly positive -- my solution ended up faster than my previous best (in C++) while also having extremely-straightforward, clean code. (Something that particularly blew my mind was crossbeam_channel being (arguably) nicer than Go's built-in channels, and being able to spread work over threads w/ zero possibility of races -- that's some fuckin' cool shit.) That experience, combined w/ observation of tools like fd and ripgrep, have convinced me that rust is actually unlocking a higher level of quality for software, at least in practice, if not in theory. Your answer has not disabused me of the perception! :-) > Although of course there are alternatives to ripgrep written in C or C++, so I'm not sure how compelling of an argument that is. But they're not as good as ripgrep ;-)
- CamperBob2 6y agoSomewhat germane to the ripgrep topic, what's the reasoning behind failing to support simple wildcard searches? I've been playing with rg.exe under Windows for a few minutes now, encouraged by this thread, but have run into a common problem: https://www.grailbox.com/2018/08/restricting-ripgrep-to-certain-file-types/ https://www.grailbox.com/2018/08/restricting-ripgrep-to-cert... Why don't most grep utilities just do the obvious right thing and support searches on .c* or .h or .txt or whatever? (HN is mangling the text, but you can read the above as "star dot c star," "star dot h," or "star dot txt.")
- burntsushi 6y agoThe reason is because someone hasn't worked on it yet. The reality is that Windows leaves glob expansion up to the CLI tool itself, where as the shell in a Unix environment does glob expansion before invoking the executable. On top of that, there appears to be no consensus on whether ripgrep should use standard Windows APIs to expand globs (which are much much less expressive than Unix-style globs), or to just implement its own globbing. There is a ticket tracking it: https://github.com/BurntSushi/ripgrep/issues/234 https://github.com/BurntSushi/ripgrep/issues/234 I've done a lot of work to make ripgrep work well on Windows. But haven't done this. You can usually work around it pretty easily with the -g flag. e.g., rg foo -g '*.{c,h}' or even shorter rg foo -tc
- CamperBob2 6y agoThanks, soms interesting inside-baseball lore there. I should probably just suck it and get used to the -g syntax, I guess. It does seem like a superb grep implementation.
- burntsushi 6y agoFWIW, you opinion about which glob syntax to use would be much appreciated. :)
- CamperBob2 6y ago
- 2038AD 6y agoThanks! As I said, I hadn't look too far into it.