Is the regex crate a bottleneck in your program? If so, can you share the details? #960
Replies: 8 comments 25 replies
-
|
Is pattern disclosure via an email ([email protected]) an option? I am aware that the regexes would end up in public resources in the end, but I'd be keen to discuss their use case outside of a public eye. For my use case I care mostly about the performance of |
Beta Was this translation helpful? Give feedback.
-
|
Email is fine, yes. I would want to find a way to talk about what the regex is used for though. I think that's probably a requirement. As long it there's some (possibly vague) way of describing the problem it's trying to solve, and I can name the software/company that it's used in, then I think I'd be okay with including something like that.
|
Beta Was this translation helpful? Give feedback.
-
|
Apparently we were comparing apples to oranges. According to @BurntSushi Hyperscan's defaults are quite different from this crate's defaults; namely,
Furthermore, when we've benchmarked with |
Beta Was this translation helpful? Give feedback.
-
|
This comes with a big caveat that this is not the regex I wanted to write, but the regex that runs the fastest today when using the I ran less into the current implementation being slow (they're fast enough to make memory bandwidth the bottleneck) and more into the crate not exposing the APIs I need to avoid multiple scans over the input. I need to account for both IIRC I tried using The code and detailed notes about performance can be found here. |
Beta Was this translation helpful? Give feedback.
-
|
I plopped this into my benchmark harness in the following way:
Here are the results, with So you'll get a pretty big boost here and you'll be able to simplify your code. Although, the regexes that you said you tried and were slow don't appear to be that slow. It looks like they're about twice as slow as just the Unix regex though. I suppose if you're running this over a huge corpus of binaries, that could turn, say, a 2 minute search into a 1 minute search, which probably does indeed feel like a huge win. But yeah, still probably fast enough to at least exhaust I/O bandwidth, but nothing here touches memory bandwidth (at least on my system). Unfortunately, your regex just happens to be susceptible to heuristics. Your Unix regex has a nice long prefix. But when you use When the new meta regex engine lands, this could potentially go even faster by rewriting the regex to be "one-pass," but I unfortunately don't see an easy way to do that here. Anyway, thank you, this will eventually be part of the benchmark suite. :-) |
Beta Was this translation helpful? Give feedback.
-
|
The other reason for the speed up here is that the new meta engine uses the bounded backtracker to resolve capture groups, while the status quo uses the slower PikeVM. I'm not sure exactly why that is, but it could have to do with the fact that the new NFA only has 46 states where as the old one has 66, due to various optimizations and changes in state representation. And since this regex is almost one-pass, the backtracker likely zips through this pretty quickly. |
Beta Was this translation helpful? Give feedback.
-
(Disclaimer: I'm way out of my depth here with no experience on real-world regex engines) Have you thought about exposing an API to build the ~automaton graph directly? In cases where the regex to automata generation is not clever enough it might be useful to drop this outer layer. A while back I needed to match paths in an RDF graph, and ditching ~regexes to work directly on the automaton gave me a lot of control to fine-tune the queries and saved me from writing a regex engine and optimizing it. I'm thinking that here, it could be neat to use the regex to get the automaton object, visualize it, and get the code to generate it using the automaton-oriented API so you can try to refactor it. |
Beta Was this translation helpful? Give feedback.
-
|
Ah, so you want to get rid of those pesky heuristics and become master of your own destiny! Well, you'll be able to do that using Notice how without the heuristics and just using the plain old automaton (a lazy DFA in this case), you'll get quite a bit slower than the status quo. You can't really hack a DFA to make it go faster. While there are certainly cases where the lazy DFA falls over due to the huge size of a regex (or pathological cases where NFA->DFA powerset construction is exponential), generally speaking, it tops out at the speeds shown above. You can't really change it to go any faster. The NFA is likely susceptible to some level of hacking, but if the NFA is doing the bulk of the work, then you're probably an order of magnitude slower than even what In order for your regex to be "fast," it really needs the regex engine (or whatever) to do the prefilter search. You could do that yourself and then invoke the automaton for each candidate you find, but then you're (probably, depending on your regex) exposing yourself to worst case quadratic behavior in the size of the haystack. It's quite difficult to compose these types of things. This is why each internal regex engine in With that said, the narrow answer to your question is that Interpreting your question broadly, you probably want access to the heuristics themselves. I don't know how feasible that is. Literal searching is a dark art and the number of knobs is pretty enormous. It's like asking |
Beta Was this translation helpful? Give feedback.
-
|
I don’t really have much to add technically to this specific discussion, but I would really like to extend my gratitude @BurntSushi for your continual output of interesting/enlightening content, via comments like this and your incredible libraries. Even though this area isn’t my speciality, I find your writings about the problem space and optimisations very interesting. Thank you. |
Beta Was this translation helpful? Give feedback.
-
|
I use The regex is here and if you're interested I can provide some arbitrarily large haystacks |
Beta Was this translation helpful? Give feedback.
-
|
YES! Love it. This looks great. If you could provide a haystack that you feel is representative of the real world, that would be amazing. It doesn't have to be huge. These are micro-benchmarks, so somewhere in the 5MB-30MB range is just fine. (If you aren't sure, give me something big and I can trim it down.) Also, how do you use the regex? As in, which API? It looks like probably |
Beta Was this translation helpful? Give feedback.
-
|
Oh yes, Sorry I forgot to say: I'm parsing pretty big files line by line, and then using let reader = BufReader::new(my_file)?;
for line in reader.lines() {
let line = line?;
if let Some(caps) = RE_V4.captures(line).or_else(|| RE_V2.captures(line)) {
// do a bunch of stuff like:
let url = caps.name("url").unwrap();
}
}About 80% of the lines in my file match one of these two regex, 20% don't match either. Here's an example about what one matching line looks like: And a non-matching line might look like: I have gigabytes worth of logs like this that I can sanitize and send to you, but maybe you can derive your own examplars from these two examples. Let me know |
Beta Was this translation helpful? Give feedback.
-
|
It would be great to just get say, a 30MB sanitized sample from a real log file. Basically, if it's available, I'd always rather real data than to make my own up. |
Beta Was this translation helpful? Give feedback.
-
|
@BurntSushi I'm embarrassed to say this fell off my radar and I totally failed to follow through on this. Are you still interested in getting a real-life haystack example for my case? If so, I can get this ready in a few days |
Beta Was this translation helpful? Give feedback.
-
|
Yeah absolutely! |
Beta Was this translation helpful? Give feedback.
-
|
We have run into issues with the size of the compiled regexes. For example |
Beta Was this translation helpful? Give feedback.
-
|
Yes, the size is a problem, but it's not something that can realistically improve much AFAIK. It's also a very different (although connected) problem from the one I'm asking about here. You might consider that you're specifically asking for a very huge matching machine when you use Now I do have some improvements landing that should help. Below, the first command shows the number of NFA states in the status quo. The second command is a new debug tool I'm working on that shows various summary data about the new NFA, including an order of magnitude decrease in the number of states: Basically, the new NFA compiles minimal UTF-8 automata. (Which you can confirm by building a DFA, minimizing it and comparing its states to the ones in the NFA.) Unfortunately, the same gains don't necessarily apply to the reverse case, and most regexes compile both a forward and reverse NFA: It is possible to apply the shrinking algorithm in reverse, but in the reverse case, it causes NFA compilation time to balloon: The other benefit from the status quo is that the new internals will compile two NFAs, where as today, three NFAs are compiled. Overall these things lead to a... modest reduction in size. Consider this program for the status quo: use regex::Regex;
fn main() {
let mut res = vec![];
for _ in 0..10_000 {
res.push(Regex::new(r"\w").unwrap());
}
let haystack = std::env::args().nth(1).unwrap();
let mut count = 0;
for re in res.iter() {
if re.is_match(&haystack) {
count += 1;
}
}
println!("{}", count);
}and this one for the new internal regex engine: use regex_automata::meta::Regex;
fn main() {
let mut res = vec![];
for _ in 0..10_000 {
let re = Regex::new(r"\w").unwrap();
let cache = re.create_cache();
res.push((re, cache));
}
let haystack = std::env::args().nth(1).unwrap();
let mut count = 0;
for (re, cache) in res.iter_mut() {
if re.is_match(cache, &haystack) {
count += 1;
}
}
println!("{}", count);
}Compiling both in release mode and running them: So... somewhat faster and a little less memory usage. I think a better approach here would be for folks to file issues for cases where the memory usage is egregious and causing you actual problems. But not in this thread. I'm specifically asking about search performance here. |
Beta Was this translation helpful? Give feedback.
-
|
Please don’t judge me for this monstrosity (😅), but here is one I use to find potential AWS keys in code:
the comment describes the thought process:
I would use captures if I wasn’t outsourcing this to ripgrep. I ran this over every bit of code published to pypi and rubygems |
Beta Was this translation helpful? Give feedback.
-
|
This is fantastic. Thank you! |
Beta Was this translation helpful? Give feedback.
-
|
I think you may be better off using Pomsky which provides a simpler and cleaner language which are then compiled to regex sources :) |
Beta Was this translation helpful? Give feedback.
-
|
Hello, I believe I have some insights that may be helpful for you, since I've spend a lot of time tuning high-performance regex parsing application some months ago. Brief background & motivation:In our company, we produce large volume of unstructured logs in proprietary format and I often had to do adhoc analysis on files that are around 4GB. something like which lends well to further analysis. As Ripgrep is an excellent tool that can process these multi-GB files in low seconds and regex crate also has great reputation overall, I've got inspired to try rewriting and generalizing this idea as Rust CLI app transforming stream of messages with arbitrary log format specified mainly by hierarchy of regexes into stream of JSON messages. I've managed to do it, but the result wasn't as fast as I've hoped, not enough to casually transform whole files near-interactively, so I had to stick with per-case prefiltering just like before, ultimately making the tool not worth finishing, for now at least. As the regexes are user facing and often adhoc hand tuned for individual servers for handling their own unique message kinds, the intention was to keep them highlevel and not overoptimized - on the other hand, I've put lot of effort into optimizing the program itself, likely even overengineed that a fair bit, so the resulting performance is mostly (75% according to profiling) spent in the regexes themselves. The I/O cost was actually mostly negligible. Overall I've managed to crunch reference 2.2GB file in around 46 seconds from cold start, which isn't terrible, but in real world I had to wait around 3 minutes for some bigger ones and with, say, 8 logfiles, this wasn't what I hoped for. TakeawaysI've played with mmap and madvise and at least on machines I've been using (Debian Stretch & Buster, x86_64) there wasn't any notable difference from conventional Readers - I've read your post somewhere with similar findings in Ripgrep. I've had fancy-regex as optional conditional compilation feature - they are built on top of regex crate, so one would expect that if you don't use advanced features like backtracking, the regexes may be as performant as raw regex crate - unfortunately, it doesn't seem to be the case and there was small, but noticeable perf hit. Profile guided optimization consistently helped gain around 5-10% speed increase. Original version was written on top of unicode strings. As the regexes I've used needed only ascii matching, I've tried moving to bytewise (regex::bytes) regexes, but that instead lead to performance hit. Even after adding The most notable optimization (from around 4.5 minutes to sub 1 minute) I got from parallelization, having worker threads working on lines independently with number of workers matching number of logical cores (so around 12). I've read your post about the internal scratch spaces in Regex and tradeoffs between API simplicity and optimality - and can confirm that difference between sharing the regexes between threads and cloning them was negligible. Most of the processing time was spent in handling the primary regex, so we'll only consider that one. In the rust regex syntax the final version I was using looked like this ConclusionsI wondered why is grepping with ripgrep so much more performant then parsing I did and experimented with various simplified grammars - overall, grep-like usecases that relied on finding string literal (prefix/suffix) were exceptionally fast, while I did try the regex DFA CLI debugging tool and some generated machines were suboptimal or at least far more complex than casual regex user expects, consider following simple examples But even with optimized state machine generation, I somewhat doubt it'd make much difference unless there's a possibility for large performance gain in how loops are handled. I'm not familiar with regex internals, but profiling showed that vast majority of the time was spent in Overall, I feel it's likely that getting notably better performance would require move from regexes to other parsing solution, but that would effectively kill this project, as easy configuration of the parsing was a key selling point. In any case, I hope this writeup was helpful and I'm glad I had a change to talk a bit about this project. |
Beta Was this translation helpful? Give feedback.
-
|
Thank you for the write up! In the future, please feel free to reach out and ask questions on this tracker when you need help optimizing. I am really quite happy to help, assuming you can give me a repro. :) And that's what I'd like to ask for here. What I really need is a way to reproduce the problems you hit. Is there anyway you can write a short Rust program and give a smallish example (perhaps sanitized) of your haystack? 30MB would be more than enough. In particular, note the questions I asked. It isn't just about the regex, but the APIs you're using and the haystack. If you can minimize the fundamental part of your perf problem down to a short program, then I can in exchange give you an analysis. Sand that analysis should hopefully tell you whether there are any opportunities for going faster, including by using a different regex engine. |
Beta Was this translation helpful? Give feedback.
-
|
Sorry for not posting more concrete details, I was aware that's what you were mainly after, but I didn't have time to dig for that at the time. I've been using The most useful area to explore from things I've mentioned IMO is that bytewise regex parser was notably slower that unicode one on the apparently same regex, so I've made a example of that. Hope that's enough! By the way, I wonder if there is a lot of wisdom/tips on how to write efficient regexes based on how this crate operates under the hood. If so, that could be a great addition to the documentation! |
Beta Was this translation helpful? Give feedback.
-
|
Thanks! That's perfect. So you'll get a small boost with the internal refactoring here, but not much: As for the difference between "bytewise" and not, this is actually a function of whether Unicode is enabled or not. So you could use
This already exists: https://github.com/rust-lang/regex/blob/master/PERFORMANCE.md Otherwise there's really not much else to say here, especially for regexes like yours. Your use case isn't about how quickly matches can be found in a huge haystack, but rather, how quickly the engine can parse a short haystack into capture groups. That is, it's less about "where are the matches" and more about "split the haystack into pieces I understand." They are two very different things, and honestly, backtrackers tend to be better here: Incidentally, in your case, the But this is a great benchmark, thank you! |
Beta Was this translation helpful? Give feedback.
-
|
Awesome, glad I could help and thanks for additional clarifications.
Right, I recall now reading that in the past, so it's definitely discoverable. If I'll ever come across some info that would be a good fit there, I'll make an issue/PR. The pcre2/jit results look very amazing indeed and picked my curiosity enough to try quickly plugging it in my application (using your |
Beta Was this translation helpful? Give feedback.
-
I think this is a lot harder than you think it is unfortunately. The best way to do this IMO is to publish a benchmark. That's what I'm trying to do, and that's what I started this entire discussion with. :-)
Also, you say you tried PCRE... Do you mean PCRE2? When possible, don't describe what you did, show what you did. :) And yes, your description of there being extra allocs everywhere doesn't make sense to me. PCRE2 provides APIs to amortize allocs. Also, have you tried this? https://docs.rs/regex/latest/regex/struct.Regex.html#method.captures_read |
Beta Was this translation helpful? Give feedback.
-
|
Finally got time to have a good look at this.
Yes, as I've said, I tried your PCRE2 bindings 0.2.3 compared to In my previous post I used
At least on relative scale seen in flamegraphs, allocation took more significant portion in the PCRE case, but I've mostly came to that conclusion by looking at data from incomparable workloads where that effect looked far more severe i.e. it's mostly comparable. If you're interested, here are the flamegraphs on same tasks with same level of optimization, look mostly at
After that, I did move on to However, the true reason the PCRE2 version wasn't as fast for me was an unrelated problem in my parallelization design. In short, as I increase number of threads, there is a quickly rising contention cost that soon beats the gains of parallelizing the task - and as workers using PCRE2 get their job done sooner, this magnifies the issue. Some sample values of whole program time on identical workload illustrating this:
The problem is likely in my use of 6 workers vs 20 workers: (Sidenote: I used a work-stealing queue originally, but the performance was actually worse than a simple channel, but maybe there'd be room for improvement.) Time measurements on regex itself, made on captures_read call let before_regex =
measurer.regex_started(part_path, regex_ix);
let whole_match = regex.captures_read(capture_locations, part)?;
measurer.regex_complete(before_regex);show that PCRE2 is consistently very fast. There is a slowdown as number of threads goes up, possibly by contention on inner shared state (regexes are cloned into each worker). Following table shows total time, execution count and average time per execution:
I also did try to recreate the regexes from scratch per worker to disprove it was affecting the major slowdown of the whole application and indeed it did not. So there are no problems in the regex crate and PCRE is indeed faster for my usecase. |
Beta Was this translation helpful? Give feedback.
-
|
I wanted to share a case where replacing a regex with some hand-crafted string searching proved to be a nearly ~2x win. It's not necessarily exactly the same result (didn't fuzz etc) but it's functionally equivalent. The program is rustfilt, which finds and demangles Rust symbols in arbitrary text (and prints that text to stdout/file). Here is the regex in question: https://github.com/luser/rustfilt/blob/3c81f107b73fdcf7bbb98b426c1214f15946ec90/src/main.rs#L36: Here is the PRs (rust-lang/rustc-demangle#62, rust-lang/rustc-demangle#63) that added code to rustc-demangle which is in my measurements ~2x faster end-to-end, essentially replacing the regex crate's replace_all with a hand-coded routine which accomplishes the same result. As far as I can tell, the speedup is pretty much entirely down to avoiding some sort of backtracking in I've attached (rustc.script.zst.zip) a zstd-compressed (and then zip'd, so GitHub accepts it) ~980MB file (can likely be cut down, should be pretty uniform) that can be used to reproduce this. The file is the result of The rustfilt diff to produce the faster version can be found here: luser/rustfilt#21, in general it's just calling into the rustc_demangle::demangle_stream function though. Let me know if this is helpful / I can provide more sample data, etc. (Or if you find bugs in the replacement for regex for this scenario :) |
Beta Was this translation helpful? Give feedback.
-
|
Mangled symbols are typically ascii-only - can you try a |
Beta Was this translation helpful? Give feedback.
-
|
Oh excellent! Thank your @Mark-Simulacrum, I had not see this report. Completely missed it. I'll see about digging into this. (The |
Beta Was this translation helpful? Give feedback.
-
I am working on a regex benchmark (to be made public probably some time this year), and I'm looking to add regexes to it that are used in the real world. The benchmark will of course include regexes that I've conjured to test certain properties of regex implementations, but I would also like to balance that with real world regexes. I am especially interested in regexes that are used in performance sensitive aspects of your application. It doesn't necessarily have to be the number 1 bottleneck, but ideally it's impacting your bottom line performance in some way.
If you're willing to share, I would love to know both the regex and an example haystack that is searched. I would also like to know which regex APIs you use, for example,
is_match,findorcaptures. Finally, if you could briefly explain what the regex is doing conceptually that would be awesome.Note: many folks are responding which is great. But many are describing the bottleneck they hit instead of showing it. What I'm really asking for here is the actual regex, a (possibly sanitized) haystack, and the API you're using. An ideal submission is a short program that you agree recapitulates the essential performance problem you're facing. The haystack doesn't need to be big. 30MB should be more than enough for example.
Beta Was this translation helpful? Give feedback.
All reactions