Replies: 1 comment 12 replies
-
Out of curiosity, why not just implement the sparse set yourself? It's not a lot of code and it's pretty simple. As to your question... It's hard to say. If you could show a MRE Rust program that uses a lot more memory than an equivalent C++ program using RE2, then I could likely give you a better answer. Otherwise, the main knob to turn is probably to disable Unicode mode. The regex crate and RE2 have different support for Unicode. While there's a lot of differences in the details, probably the biggest difference is that the regexes Also, in a multi-threaded environment, I would generally expect the regex crate to use more memory than RE2. RE2's lazy DFA makes use one of one shared cache across all threads for a single lazy DFA, where as the regex crate uses one cache per thread. But if you aren't measuring memory in a multi-threaded benchmark, this difference shouldn't come up. There could also be memory usage related bugs. For example, I haven't looked at #1116 yet. Otherwise it's very difficult to answer your question in the abstract. I would really want an MRE to give a more precise answer. (For example, maybe there's something different about how the NFAs are represented? Or maybe there's something causing a prefilter somewhere to be bigger than one might expect?) In general, there is a lot of pressure on runtime performance in the form of benchmarks, but very little on memory usage. So there could very well be gains to be had here. |
Beta Was this translation helpful? Give feedback.
-
Yeah sorry I posted an early version of the comment but figured I'd forgotten to take note of the old "accumulative" version of the bench script, so I went to rewrite it before posting it again.
It's my understanding that that's what jemalloc stats are supposed to surface. But I can always try using a more simplistic proxy allocator, given dtolnay posted the entire thing. I'll give that a shot. |
Beta Was this translation helpful? Give feedback.
-
Dammit from the documentation (and friends' suggestions) I assumed jemalloc's stats.allocated would be... the allocated stuff. But apparently it's doing weird things behind the scenes indeed. Custom allocators do seem to be a lot more reliable. I put up https://github.com/masklinn/remem which provides for the regexes dataset and test scripts. I tried to get the evaluation / testing programs similar enough that comparisons mostly hold, but I'll readily admit that my C++ is really far from good. Also some of the behaviours I don't understand (e.g. in some cases Anyway setting asides the unicode stuff, it looks like:
e.g. two of the initial entries are:
So
With a simpler case (and ignoring the capture memory)
On this one specifically regex actually does quite well on repetitions except for the repetition + capture unicode version, however since its baseline is 10x that of re2 it's still quite a ways behind. |
Beta Was this translation helpful? Give feedback.
-
|
For what it's worth, although the upstream of what I'm using regex-filtered for does not specify their regex semantics the reference implementation is in javascript which uses strict ASCII for their perl-style character classes, and as you wrote up in the initial answer re2 also documents that they use strict ASCII semantics for the same. So while not touching regex-filtered I added a downgrade step to the sub-project, which converts Through log-diving I also confirmed that the extensive use of bounded repetitions is not actually to bound repetitions but to mitigate catastrophic backtracking concerns, so while that's a lot iffier the downgrade filter also converts "large" bounded repetitions to unbounded (as it is my understanding that finite automata engines like regex are not affected). This results in a ~50% reduction in peak memory footprint on processing a sample file, and despite the additional prefiltering (and allocations) a ~10% reduction in runtime. Feel free to close this discussion if you don't see a point to keeping it open. PS: no idea what could be done about the amplification caused by bounded repetitions and captures, but maybe I know that |
Beta Was this translation helpful? Give feedback.
-
|
With respect to Perl style classes being ASCII, that's already supported: just disable Unicode mode. Either globally, or locally within the regex: The simplifications you made to your regexes sound good to me. I had no idea that the bounds were added not for semantics, but to deal with backtrackers. That is interesting! I do think a more careful analysis of the memory footprint differences between this crate and RE2 is warranted, but I don't currently consider it higher priority. |
Beta Was this translation helpful? Give feedback.
-
Yes, that is indeed what I meant as the upstream in this cases uses
Yeah I had no idea either, I only found out when I tried to log dive to see if I could find explanations of the semantics requirements, and stumbled on a commit converting a bunch of unbounded repetitions to bounded ones. |
Beta Was this translation helpful? Give feedback.
-
I've finally done some very basic benching
regex-filteredagainstFilteredRE2: ua-parser/uap-rust@1af15c1After fixing a dumb mistake it's basically on par in terms of runtime (and that's hot even its final form).
However there's an other standout issue: the RSS / memory footprint of the regex-filtered version is much higher than that of the re2 version, and simple tracking of the rss over phases using memory-stats shows it is largely attributable to
regex, this was confirmed by just loading all the regexes into aVec<Regex>and finding that the RSS climbs from ~2MB (after loading the arguments and reading the 633 regex strings from the file) to ~100MB (and then a bit further to ~140MB when matching, I assume that's because caches come into play then).I looked at the different features of regex, and the only knob which seemed to influence RSS is
dfa, which reduces RSS down to ~50MB before matching which is similar to re2 (though caches then tack ~ 20MB on when matching occurs). Sadly, it's also very much load bearing and disabling it makes runtime shoot up from 46 seconds to 157 seconds on my machine (for 100 iterations over 75158 strings, using 633 regexes).And so I wanted to know, is there a knob I missed? Maybe something wrong I did with regex::bytes or something? Or is it the tradeoff? I assume
regex-litewould also be an option but wouldn't really be competitive with re2?In fairness I can't say it's of major importance, the runtime seems a lot more relevant, but it's useful information to stash away given the use case for
regex-filteredwould routinely be to load hundreds to thousands of regexes and it might inform e.g. lazy-compiling regexes (under the assumption that most of them will never actually be needed).Beta Was this translation helpful? Give feedback.
All reactions