Thread
Commits
-
Suppress unnecessary regex subre nodes in a couple more cases.
- 4604f83fdfe0 14.0 landed
-
Improve memory management in regex compiler.
- 0fc1af174cf7 14.0 landed
-
Extend a test case a little
- b3a9e9897ec7 14.0 cited
-
Allow complemented character class escapes within regex brackets.
- 2a0af7fe460e 14.0 landed
-
Suppress compiler warning in new regex match-all detection code.
- 3db05e76f928 14.0 landed
-
Avoid generating extra subre tree nodes for capturing parentheses.
- ea1268f6301c 14.0 landed
-
Convert regex engine's subre tree from binary to N-ary style.
- 581043089472 14.0 landed
-
Fix regex engine to suppress useless concatenation sub-REs.
- cebc1d34e520 14.0 landed
-
Recognize "match-all" NFAs within the regex engine.
- 824bf71902db 14.0 landed
-
Invent "rainbow" arcs within the regex engine.
- 08c0d6ad65f7 14.0 landed
-
Make some minor improvements in the regex code.
- 4e703d67193d 14.0 landed
-
Display the time when the process started waiting for the lock, in pg_locks, take 2
- 46d6e5f56790 14.0 cited
-
README/C-comment: document GiST's NSN value
- 8facf1ea00b7 14.0 cited
-
doc: Mention NO DEPENDS ON EXTENSION in its supported ALTER commands
- 8063d0f6f56e 14.0 cited
-
Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-11T04:39:43Z
As I mentioned in connection with adding the src/test/modules/test_regex test code, I've been fooling with some performance improvements to our regular expression engine. Here's the first fruits of that labor. This is mostly concerned with cutting the overhead for handling trivial unconstrained patterns like ".*". 0001 creates the concept of a "rainbow" arc within regex NFAs. You can read background info about this in the "Colors and colormapping" part of regex/README, but the basic point is that right now, representing a dot (".", match anything) within an NFA requires a separate arc for each "color" (character equivalence class) that the regex needs. This uses up a fair amount of storage and processing effort, especially in larger regexes which tend to have a lot of colors. We can replace such a "rainbow" of arcs with a single arc labeled with a special color RAINBOW. This is worth doing on its own account, just because it saves space and time. For example, on the reg-33.15.1 test case in test_regex.sql (a moderately large real-world RE), I find that HEAD requires 1377614 bytes to represent the compiled RE, and the peak space usage during pg_regcomp() is 3124376 bytes. With this patch, that drops to 1077166 bytes for the RE (21% savings) with peak compilation space 2800752 bytes (10% savings). Moreover, the runtime for that test case drops from ~57ms to ~44ms, a 22% savings. (This is mostly measuring the RE compilation time. Execution time should drop a bit too since miss() need consider fewer arcs; but that savings is in a cold code path so it won't matter much.) These aren't earth-shattering numbers of course, but for the amount of code needed, it seems well worth while. A possible point of contention is that I exposed the idea of a rainbow arc in the regexport.h APIs, which will force consumers of that API to adapt --- see the changes to contrib/pg_trgm for an example. I'm not too concerned about this because I kinda suspect that pg_trgm is the only consumer of that API anywhere. (codesearch.debian.net knows of no others, anyway.) We could in principle hide the change by having the regexport functions expand a rainbow arc into one for each color, but that seems like make-work. pg_trgm would certainly not see it as an improvement, and in general users of that API should appreciate recognizing rainbows as such, since they might be able to apply optimizations that depend on doing so. Which brings us to 0002, which is exactly such an optimization. The idea here is to short-circuit character-by-character scanning when matching a sub-NFA that is like "." or ".*" or variants of that, ie it will match any sequence of some number of characters. This requires the ability to recognize that a particular pair of NFA states are linked by a rainbow, so it's a lot less painful to do when rainbows are represented explicitly. The example that got me interested in this is adapted from a Tcl trouble report: select array_dims(regexp_matches(repeat('x',40) || '=' || repeat('y',50000), '^(.*)=(.*)$')); On my machine, this takes about 6 seconds in HEAD, because there's an O(N^2) effect: we try to match the sub-NFA for the first "(.*)" capture group to each possible starting string, and only after expensively verifying that tautological match do we check to see if the next character is "=". By not having to do any per-character work to decide that .* matches a substring, the O(N^2) behavior is removed and the time drops to about 7 msec. (One could also imagine fixing this by rearranging things to check for the "=" match before verifying the capture-group matches. That's an idea I hope to look into in future, because it could help for cases where the variable parts are not merely ".*". But I don't have clear ideas about how to do that, and in any case ".*" is common enough that the present change should still be helpful.) There are two non-boilerplate parts of the 0002 patch. One is the checkmatchall() function that determines whether an NFA is match-all, and if so what the min and max match lengths are. This is actually not very complicated once you understand what the regex engine does at the "pre" and "post" states. (See the "Detailed semantics" part of regex/README for some info about that, which I tried to clarify as part of the patch.) Other than those endpoint conditions it's just a recursive graph search. The other hard part is the changes in rege_dfa.c to provide the actual short-circuit behavior at runtime. That's ticklish because it's trying to emulate some overly complicated and underly documented code, particularly in longest() and shortest(). I think that stuff is right; I've studied it and tested it. But it could use more eyeballs. Notably, I had to add some more test cases to test_regex.sql to exercise the short-circuit part of matchuntil() properly. That's only used for lookbehind constraints, so we won't hit the short-circuit path except with something like '(?<=..)', which is maybe a tad silly. I'll add this to the upcoming commitfest. regards, tom lane -
Re: Some regular-expression performance hacking
Joel Jacobson <joel@compiler.org> — 2021-02-13T17:19:34Z
Hi Tom, On Thu, Feb 11, 2021, at 05:39, Tom Lane wrote: >0001-invent-rainbow-arcs.patch >0002-recognize-matchall-NFAs.patch Many thanks for working on the regex engine, this looks like an awesome optimization. To test the correctness of the patches, I thought it would be nice with some real-life regexes, and just as important, some real-life text strings, to which the real-life regexes are applied to. I therefore patched Chromium's v8 regexes engine, to log the actual regexes that get compiled when visiting websites, and also the text strings that are the regexes are applied to during run-time when the regexes are executed. I logged the regex and text strings as base64 encoded strings to STDOUT, to make it easy to grep out the data, so it could be imported into PostgreSQL for analytics. In total, I scraped the first-page of some ~50k websites, which produced 45M test rows to import, which when GROUP BY pattern and flags was reduced down to 235k different regex patterns, and 1.5M different text string subjects. Here are some statistics on the different flags used: SELECT *, SUM(COUNT) OVER () FROM (SELECT flags, COUNT(*) FROM patterns GROUP BY flags) AS x ORDER BY COUNT DESC; flags | count | sum -------+--------+-------- | 150097 | 235204 i | 43537 | 235204 g | 22029 | 235204 gi | 15416 | 235204 gm | 2411 | 235204 gim | 602 | 235204 m | 548 | 235204 im | 230 | 235204 y | 193 | 235204 gy | 60 | 235204 giy | 29 | 235204 giu | 26 | 235204 u | 11 | 235204 iy | 6 | 235204 gu | 5 | 235204 gimu | 2 | 235204 iu | 1 | 235204 my | 1 | 235204 (18 rows) As we can see, no flag at all is the most common, followed by the "i" flag. Most of the Javascript-regexes (97%) could be understood by PostgreSQL, only 3% produced some kind of error, which is not unexpected, since some Javascript-regex features like \w and \W have different syntax in PostgreSQL: SELECT *, SUM(COUNT) OVER () FROM (SELECT is_match,error,COUNT(*) FROM subjects GROUP BY is_match,error) AS x ORDER BY count DESC; is_match | error | count | sum ----------+---------------------------------------------------------------+--------+--------- f | | 973987 | 1489489 t | | 474225 | 1489489 | invalid regular expression: invalid escape \ sequence | 39141 | 1489489 | invalid regular expression: invalid character range | 898 | 1489489 | invalid regular expression: invalid backreference number | 816 | 1489489 | invalid regular expression: brackets [] not balanced | 327 | 1489489 | invalid regular expression: invalid repetition count(s) | 76 | 1489489 | invalid regular expression: quantifier operand invalid | 17 | 1489489 | invalid regular expression: parentheses () not balanced | 1 | 1489489 | invalid regular expression: regular expression is too complex | 1 | 1489489 (10 rows) Having had some fun looking at statistics, let's move on to look at if there are any observable differences between HEAD (8063d0f6f56e53edd991f53aadc8cb7f8d3fdd8f) and when these two patches have been applied. To detect any differences, for each (regex pattern, text string subject) pair, the columns, is_match boolean captured text[] error text were set by a PL/pgSQL function running HEAD: BEGIN _is_match := _subject ~ _pattern; _captured := regexp_match(_subject, _pattern); EXCEPTION WHEN OTHERS THEN UPDATE subjects SET error = SQLERRM WHERE subject_id = _subject_id; CONTINUE; END; UPDATE subjects SET is_match = _is_match, captured = _captured WHERE subject_id = _subject_id; The patches 0001-invent-rainbow-arcs.patch 0002-recognize-matchall-NFAs.patch were then applied and this query was executed to spot any differences: SELECT is_match <> (subject ~ pattern) AS is_match_diff, captured IS DISTINCT FROM regexp_match(subject, pattern) AS captured_diff, COUNT(*) FROM subjects WHERE error IS NULL AND (is_match <> (subject ~ pattern) OR captured IS DISTINCT FROM regexp_match(subject, pattern)) GROUP BY 1,2 ORDER BY 3 DESC ; The query was first run on the unpatched HEAD to verify it detects no results. 0 rows indeed, and it took this long to finish the query: Time: 186077.866 ms (03:06.078) Running the same query with the two patches, was significantly faster: Time: 111785.735 ms (01:51.786) No is_match differences were detected, good! However, there were 23 cases where what got captured differed: -[ RECORD 1 ]--+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (?:^v-([a-z0-9-]+))?(?:(?::|^@|^#)(\[[^\]]+\]|[^\.]+))?(.+)?$ subject | v-cloak is_match_head | t captured_head | {cloak,NULL,NULL} is_match_patch | t captured_patch | {NULL,NULL,v-cloak} -[ RECORD 2 ]--+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (?:^v-([a-z0-9-]+))?(?:(?::|^@|^#)(\[[^\]]+\]|[^\.]+))?(.+)?$ subject | v-if is_match_head | t captured_head | {if,NULL,NULL} is_match_patch | t captured_patch | {NULL,NULL,v-if} -[ RECORD 3 ]--+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (^.*://)?((www.)?a5oc.com).* subject | https://a5oc.com/attachments/6b184e79-6a7f-43e0-ac59-7ed9d0a8eb7e-jpeg.179582/ is_match_head | t captured_head | {https://,a5oc.com,NULL <https://%2Ca5oc.com%2Cnull/>} is_match_patch | t captured_patch | -[ RECORD 4 ]--+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (^.*://)?((www.)?allfordmustangs.com).* subject | https://allfordmustangs.com/attachments/e463e329-0397-4e13-ad41-f30c6bc0659e-jpeg.779299/ is_match_head | t captured_head | {https://,allfordmustangs.com,NULL <https://%2Callfordmustangs.com%2Cnull/>} is_match_patch | t captured_patch | -[ RECORD 5 ]--+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (^.*://)?((www.)?audi-forums.com).* subject | https://audi-forums.com/attachments/screenshot_20210207-151100_ebay-jpg.11506/ is_match_head | t captured_head | {https://,audi-forums.com,NULL <https://%2Caudi-forums.com%2Cnull/>} is_match_patch | t captured_patch | -[ RECORD 6 ]--+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (^.*://)?((www.)?can-amforum.com).* subject | https://can-amforum.com/attachments/resized_20201214_163325-jpeg.101395/ is_match_head | t captured_head | {https://,can-amforum.com,NULL <https://%2Ccan-amforum.com%2Cnull/>} is_match_patch | t captured_patch | -[ RECORD 7 ]--+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (^.*://)?((www.)?contractortalk.com).* subject | https://contractortalk.com/attachments/maryann-porch-roof-quote-12feb2021-jpg.508976/ is_match_head | t captured_head | {https://,contractortalk.com,NULL <https://%2Ccontractortalk.com%2Cnull/>} is_match_patch | t captured_patch | -[ RECORD 8 ]--+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (^.*://)?((www.)?halloweenforum.com).* subject | https://halloweenforum.com/attachments/dead-fred-head-before-and-after-jpg.744080/ is_match_head | t captured_head | {https://,halloweenforum.com,NULL <https://%2Challoweenforum.com%2Cnull/>} is_match_patch | t captured_patch | -[ RECORD 9 ]--+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (^.*://)?((www.)?horseforum.com).* subject | https://horseforum.com/attachments/dd90f089-9ae9-4521-98cd-27bda9ad38e9-jpeg.1109329/ is_match_head | t captured_head | {https://,horseforum.com,NULL <https://%2Chorseforum.com%2Cnull/>} is_match_patch | t captured_patch | -[ RECORD 10 ]-+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (^.*://)?((www.)?passatworld.com).* subject | https://passatworld.com/attachments/clean-passat-jpg.102337/ is_match_head | t captured_head | {https://,passatworld.com,NULL <https://%2Cpassatworld.com%2Cnull/>} is_match_patch | t captured_patch | -[ RECORD 11 ]-+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (^.*://)?((www.)?plantedtank.net).* subject | https://plantedtank.net/attachments/brendon-60p-jpg.1026075/ is_match_head | t captured_head | {https://,plantedtank.net,NULL <https://%2Cplantedtank.net%2Cnull/>} is_match_patch | t captured_patch | -[ RECORD 12 ]-+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (^.*://)?((www.)?vauxhallownersnetwork.co.uk).* subject | https://vauxhallownersnetwork.co.uk/attachments/opelnavi-jpg.96639/ is_match_head | t captured_head | {https://,vauxhallownersnetwork.co.uk,NULL <https://%2Cvauxhallownersnetwork.co.uk%2Cnull/>} is_match_patch | t captured_patch | -[ RECORD 13 ]-+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (^.*://)?((www.)?volvov40club.com).* subject | https://volvov40club.com/attachments/img_20210204_164157-jpg.17356/ is_match_head | t captured_head | {https://,volvov40club.com,NULL <https://%2Cvolvov40club.com%2Cnull/>} is_match_patch | t captured_patch | -[ RECORD 14 ]-+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (^.*://)?((www.)?vwidtalk.com).* subject | https://vwidtalk.com/attachments/1613139846689-png.1469/ is_match_head | t captured_head | {https://,vwidtalk.com,NULL <https://%2Cvwidtalk.com%2Cnull/>} is_match_patch | t captured_patch | -[ RECORD 15 ]-+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (^.*://)?((www.)?yellowbullet.com).* subject | https://yellowbullet.com/attachments/20210211_133934-jpg.204604/ is_match_head | t captured_head | {https://,yellowbullet.com,NULL <https://%2Cyellowbullet.com%2Cnull/>} is_match_patch | t captured_patch | -[ RECORD 16 ]-+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (^[^\?]*)?(\?[^#]*)?(#.*$)? subject | https://www.disneyonice.com/oneIdResponder.html is_match_head | t captured_head | {https://www.disneyonice.com/oneIdResponder.html,NULL,NULL} is_match_patch | t captured_patch | -[ RECORD 17 ]-+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (^[a-zA-Z0-9\/_-]+)*(\.[a-zA-Z]+)? subject | / is_match_head | t captured_head | {/,NULL} is_match_patch | t captured_patch | -[ RECORD 18 ]-+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (^[a-zA-Z0-9\/_-]+)*(\.[a-zA-Z]+)? subject | /en.html is_match_head | t captured_head | {/en,.html} is_match_patch | t captured_patch | -[ RECORD 19 ]-+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | (^https?:\/\/)?(((\[[^\]]+\])|([^:\/\?#]+))(:(\d+))?)?([^\?#]*)(.*)? subject | https://e.echatsoft.com/mychat/visitor is_match_head | t captured_head | {https://,e.echatsoft.com,e.echatsoft.com,NULL,e.echatsoft.com,NULL,NULL,/mychat/visitor <https://%2Ce.echatsoft.com%2Ce.echatsoft.com%2Cnull%2Ce.echatsoft.com%2Cnull%2Cnull%2C/mychat/visitor>,""} is_match_patch | t captured_patch | {NULL,https,https,NULL,https,NULL,NULL,://e.echatsoft.com/mychat/visitor,""} -[ RECORD 20 ]-+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ---------------------------------------- pattern | (^|.)41nbc.com$|(^|.)41nbc.dev$|(^|.)52.23.179.12$|(^|.)52.3.245.221$|(^|.)clipsyndicate.com$|(^|.)michaelbgiordano.com$|(^|.)syndicaster.tv$|(^|.)wdef.com$|(^|.)wdef.dev$|(^|.)wxxv.mysiteserver.net$|(^|.)wxxv25.dev$|(^|.)clipsyndicate.com$|(^|.)syndicaster.tv$ subject | wdef.com is_match_head | t captured_head | {NULL,NULL,NULL,NULL,NULL,NULL,NULL,"",NULL,NULL,NULL,NULL,NULL} is_match_patch | t captured_patch | -[ RECORD 21 ]-+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | ^((^\w+:|^)\/\/)?(?:www\.)? subject | https://www.deputy.com/ is_match_head | t captured_head | {https://,https <https://%2Chttps/>:} is_match_patch | t captured_patch | -[ RECORD 22 ]-+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | ^((^\w+:|^)\/\/)?(?:www\.)? subject | https://www.westernsydney.edu.au/ is_match_head | t captured_head | {https://,https <https://%2Chttps/>:} is_match_patch | t captured_patch | -[ RECORD 23 ]-+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pattern | ^(https?:){0,1}\/\/| subject | https://ui.powerreviews.com/api/ is_match_head | t captured_head | {https:} is_match_patch | t captured_patch | {NULL} The code to reproduce the results have been pushed here: https://github.com/truthly/regexes-in-the-wild Let me know if you want access to the dataset, I could open up a port to my PostgreSQL so you could take a dump. SELECT pg_size_pretty(pg_relation_size('patterns')) AS patterns, pg_size_pretty(pg_relation_size('subjects')) AS subjects; patterns | subjects ----------+---------- 20 MB | 568 MB (1 row) /Joel -
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-13T17:35:45Z
"Joel Jacobson" <joel@compiler.org> writes: > In total, I scraped the first-page of some ~50k websites, > which produced 45M test rows to import, > which when GROUP BY pattern and flags was reduced > down to 235k different regex patterns, > and 1.5M different text string subjects. This seems like an incredibly useful test dataset. I'd definitely like a copy. > No is_match differences were detected, good! Cool ... > However, there were 23 cases where what got captured differed: I shall take a closer look at that. Many thanks for doing this work! regards, tom lane
-
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-13T21:11:37Z
"Joel Jacobson" <joel@compiler.org> writes: > No is_match differences were detected, good! > However, there were 23 cases where what got captured differed: These all stem from the same oversight: checkmatchall() was being too cavalier by ignoring "pseudocolor" arcs, which are arcs that match start-of-string or end-of-string markers. I'd supposed that pseudocolor arcs necessarily match parallel RAINBOW arcs, because they start out that way (cf. newnfa). But it turns out that some edge-of-string constraints can be optimized in such a way that they only appear in the final NFA in the guise of missing or extra pseudocolor arcs. We have to actually check that the pseudocolor arcs match the RAINBOW arcs, otherwise our "matchall" NFA isn't one because it acts differently at the start or end of the string than it does elsewhere. So here's a revised pair of patches (0001 is actually the same as before). Thanks again for testing! regards, tom lane
-
Re: Some regular-expression performance hacking
Joel Jacobson <joel@compiler.org> — 2021-02-14T12:52:55Z
On Sat, Feb 13, 2021, at 22:11, Tom Lane wrote: >0001-invent-rainbow-arcs-2.patch >0002-recognize-matchall-NFAs-2.patch I've successfully tested both patches against the 1.5M regexes-in-the-wild dataset. Out of the 1489489 (pattern, text string) pairs tested, there was only one single deviation: This 100577 bytes big regex (pattern_id = 207811)... \.(ac|com\.ac|edu\.ac|gov\.ac|net\.ac|mil\.ac| ... |wmflabs\.org|yolasite\.com|za\.net|za\.org)$ ...previously raised... error invalid regular expression: regular expression is too complex ...but now goes through: is_match <NULL> => t captured <NULL> => {de} error invalid regular expression: regular expression is too complex => <NULL> Nice. The patched regex engine is apparently capable of handling even more complex regexes than before. The test that found the deviation tests each (pattern, text string) individually, to catch errors. But I've also made a separate query to just test regexes known to not cause errors, to allow testing all regexes in one big query, which fully utilizes the CPU cores and also runs quicker. Below is the result of the performance test query: \timing SELECT tests.is_match IS NOT DISTINCT FROM (subjects.subject ~ patterns.pattern), tests.captured IS NOT DISTINCT FROM regexp_match(subjects.subject, patterns.pattern), COUNT(*) FROM tests JOIN subjects ON subjects.subject_id = tests.subject_id JOIN patterns ON patterns.pattern_id = subjects.pattern_id JOIN server_versions ON server_versions.server_version_num = tests.server_version_num WHERE server_versions.server_version = current_setting('server_version') AND tests.error IS NULL GROUP BY 1,2 ORDER BY 1,2; -- 8facf1ea00b7a0c08c755a0392212b83e04ae28a: ?column? | ?column? | count ----------+----------+--------- t | t | 1448212 (1 row) Time: 592196.145 ms (09:52.196) -- 8facf1ea00b7a0c08c755a0392212b83e04ae28a+patches: ?column? | ?column? | count ----------+----------+--------- t | t | 1448212 (1 row) Time: 461739.364 ms (07:41.739) That's an impressive 22% speed-up! /Joel -
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-14T16:45:40Z
"Joel Jacobson" <joel@compiler.org> writes: > I've successfully tested both patches against the 1.5M regexes-in-the-wild dataset. > Out of the 1489489 (pattern, text string) pairs tested, > there was only one single deviation: > This 100577 bytes big regex (pattern_id = 207811)... > ... > ...previously raised... > error invalid regular expression: regular expression is too complex > ...but now goes through: > Nice. The patched regex engine is apparently capable of handling even more complex regexes than before. Yeah. There are various limitations that can lead to REG_ETOOBIG, but the main ones are "too many states" and "too many arcs". The RAINBOW change directly reduces the number of arcs and thus makes larger regexes feasible. I'm sure it's coincidental that the one such example you captured happens to be fixed by this change, but hey I'll take it. regards, tom lane
-
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-15T03:11:37Z
"Joel Jacobson" <joel@compiler.org> writes: > Below is the result of the performance test query: > -- 8facf1ea00b7a0c08c755a0392212b83e04ae28a: > Time: 592196.145 ms (09:52.196) > -- 8facf1ea00b7a0c08c755a0392212b83e04ae28a+patches: > Time: 461739.364 ms (07:41.739) > That's an impressive 22% speed-up! I've been doing some more hacking over the weekend, and have a couple of additional improvements to show. The point of these two additional patches is to reduce the number of "struct subre" sub-regexps that the regex parser creates. The subre's themselves aren't that large, so this might seem like it would have only small benefit. However, each subre requires its own NFA for the portion of the RE that it matches. That adds space, and it also adds compilation time because we run the "optimize()" pass separately for each such NFA. Maybe there'd be a way to share some of that work, but I'm not very clear how. In any case, not having a subre at all is clearly better where we can manage it. 0003 is a small patch that fixes up parseqatom() so that it doesn't emit no-op subre's for empty portions of a regexp branch that are adjacent to a "messy" regexp atom (that is, a capture node, a backref, or an atom with greediness different from what preceded it). 0004 is a rather larger patch whose result is to get rid of extra subre's associated with alternation subre's. If we have a|b|c and any of those alternation branches are messy, we end up with * / \ a * / \ b * / \ c NULL where each "*" is an alternation subre node, and all those "*"'s have identical NFAs that match the whole a|b|c construct. This means that for an N-way alternation we're going to need something like O(N^2) work to optimize all those NFAs. That's embarrassing (and I think it's my fault --- if memory serves, I put in this representation of messy alternations years ago). We can improve matters by having just one parent node for an alternation: * \ a -> b -> c That requires replacing the binary-tree structure of subre's with a child-and-sibling arrangement, which is not terribly difficult but accounts for most of the bulk of the patch. (I'd wanted to do that for years, but up till now I did not think it would have any real material benefit.) There might be more that can be done in this line, but that's as far as I got so far. I did some testing on this using your dataset (thanks for giving me a copy) and this query: SELECT pattern, subject, is_match AS is_match_head, captured AS captured_head, subject ~ pattern AS is_match_patch, regexp_match(subject, pattern) AS captured_patch FROM subjects WHERE error IS NULL AND (is_match <> (subject ~ pattern) OR captured IS DISTINCT FROM regexp_match(subject, pattern)); I got these runtimes (non-cassert builds): HEAD 313661.149 ms (05:13.661) +0001 297397.293 ms (04:57.397) 5% better than HEAD +0002 151995.803 ms (02:31.996) 51% better than HEAD +0003 139843.934 ms (02:19.844) 55% better than HEAD +0004 95034.611 ms (01:35.035) 69% better than HEAD Since I don't have all the tables used in your query, I can't try to reproduce your results exactly. I suspect the reason I'm getting a better percentage improvement than you did is that the joining/grouping/ordering involved in your query creates a higher baseline query cost. Anyway, I'm feeling pretty pleased with these results ... regards, tom lane -
Re: Some regular-expression performance hacking
Joel Jacobson <joel@compiler.org> — 2021-02-15T08:21:21Z
On Mon, Feb 15, 2021, at 04:11, Tom Lane wrote: >I got these runtimes (non-cassert builds): > >HEAD 313661.149 ms (05:13.661) >+0001 297397.293 ms (04:57.397) 5% better than HEAD >+0002 151995.803 ms (02:31.996) 51% better than HEAD >+0003 139843.934 ms (02:19.844) 55% better than HEAD >+0004 95034.611 ms (01:35.035) 69% better than HEAD > >Since I don't have all the tables used in your query, I can't >try to reproduce your results exactly. I suspect the reason >I'm getting a better percentage improvement than you did is >that the joining/grouping/ordering involved in your query >creates a higher baseline query cost. Mind blowing speed-up, wow! I've tested all 4 patches successfully. To eliminate the baseline cost of the join, I first created this table: CREATE TABLE performance_test AS SELECT subjects.subject, patterns.pattern, tests.is_match, tests.captured FROM tests JOIN subjects ON subjects.subject_id = tests.subject_id JOIN patterns ON patterns.pattern_id = subjects.pattern_id JOIN server_versions ON server_versions.server_version_num = tests.server_version_num WHERE server_versions.server_version = current_setting('server_version') AND tests.error IS NULL ; Then I ran this query: \timing SELECT is_match <> (subject ~ pattern), captured IS DISTINCT FROM regexp_match(subject, pattern), COUNT(*) FROM performance_test GROUP BY 1,2 ORDER BY 1,2 ; All patches gave the same result: ?column? | ?column? | count ----------+----------+--------- f | f | 1448212 (1 row) I.e., no detected semantic differences. Timing differences: HEAD 570632.722 ms (09:30.633) +0001 472938.857 ms (07:52.939) 17% better than HEAD +0002 451638.049 ms (07:31.638) 20% better than HEAD +0003 439377.813 ms (07:19.378) 23% better than HEAD +0004 96447.038 ms (01:36.447) 83% better than HEAD I tested on my MacBook Pro 2.4GHz 8-Core Intel Core i9, 32 GB 2400 MHz DDR4 running macOS Big Sur 11.1: SELECT version(); version ---------------------------------------------------------------------------------------------------------------------- PostgreSQL 14devel on x86_64-apple-darwin20.2.0, compiled by Apple clang version 12.0.0 (clang-1200.0.32.29), 64-bit (1 row) My HEAD = 46d6e5f567906389c31c4fb3a2653da1885c18ee. PostgreSQL was compiled with just ./configure, no parameters, and the only non-default postgresql.conf settings were these: log_destination = 'csvlog' logging_collector = on log_filename = 'postgresql.log' Amazing work! I hope to have a new dataset ready soon with regex flags for applied subjects as well. /Joel -
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-17T21:00:36Z
"Joel Jacobson" <joel@compiler.org> writes: > I've tested all 4 patches successfully. Thanks! I found one other area that could be improved with the same idea of getting rid of unnecessary subre's: right now, every pair of capturing parentheses gives rise to a "capture" subre with an NFA identical to its single child subre (which is what does the actual matching work). While this doesn't really add any runtime cost, the duplicate NFA definitely does add to the compilation cost, since we run it through optimization independently of the child. I initially thought that we could just flush capture subres altogether in favor of annotating their children with a "we need to capture this result" marker. However, Spencer's regression tests soon exposed the flaw in that notion. It's legal to write "((x))" or even "((((x))))", so that there can be multiple sets of capturing parentheses with a single child node. The solution adopted in the attached 0005 is to handle the innermost capture with a marker on the child subre, but if we need an additional capture on a node that's already marked, put a capture subre on top just like before. One could instead complicate the data structure by allowing N capture markers on a single subre node, but I judged that not to be a good tradeoff. I don't see any reason except spec compliance to allow such equivalent capture groups, so I don't care if they're a bit inefficient. (If anyone knows of a useful application for writing REs like this, we could reconsider that choice.) One small issue with marking the child directly is that we can't get away any longer with overlaying capture and backref subexpression numbers, since you could theoretically write (\1) which'd result in needing to put a capture label on a backref subre. This could again have been handled by making the capture a separate node, but I really don't much care for the way that subre.subno has been overloaded for three(!) different purposes depending on node type. So I just broke it into three separate fields. Maybe the incremental cost of the larger subre struct was worth worrying about back in 1997 ... but I kind of doubt that it was a useful micro-optimization even then, considering the additional NFA baggage that every subre carries. Also, I widened "subre.id" from short to int, since the narrower field no longer saves anything given the new struct layout. The existing choice was dubious already, because every other use of subre ID numbers was int or even size_t, and there was nothing checking for overflow of the id fields. (Although perhaps it doesn't matter, since I'm unsure that the id fields are really used for anything except debugging purposes.) For me, 0005 makes a fairly perceptible difference on your test case subject_id = 611875, which I've been paying attention to because it's the one that failed with "regular expression is too complex" before. I see about a 20% time savings from 0004 on that case, but not really any noticeable difference in the total runtime for the whole suite. So I think we're getting to the point of diminishing returns for this concept (another reason for not chasing after optimization of the duplicate-captures case). Still, we're clearly way ahead of where we started. Attached is an updated patch series; it's rebased over 4e703d671 which took care of some not-really-related fixes, and I made a pass of cleanup and comment improvements. I think this is pretty much ready to commit, unless you want to do more testing or code-reading. regards, tom lane
-
Re: Some regular-expression performance hacking
Joel Jacobson <joel@compiler.org> — 2021-02-18T10:30:09Z
On Wed, Feb 17, 2021, at 22:00, Tom Lane wrote: > Attached is an updated patch series; it's rebased over 4e703d671 > which took care of some not-really-related fixes, and I made a > pass of cleanup and comment improvements. I think this is pretty > much ready to commit, unless you want to do more testing or > code-reading. I've produced a new dataset which now also includes the regex flags (if any) used for each subject applied to a pattern. The new dataset contains 318364 patterns and 4474520 subjects. (The old one had 235204 patterns and 1489489 subjects.) I've tested the new dataset against PostgreSQL 10.16, 11.11, 12.6, 13.2, HEAD (4e703d671) and HEAD+patches. I based the comparisons on the subjects that didn't cause an error on 13.2: CREATE TABLE performance_test AS SELECT subjects.subject, patterns.pattern, patterns.flags, tests.is_match, tests.captured FROM tests JOIN subjects ON subjects.subject_id = tests.subject_id JOIN patterns ON patterns.pattern_id = subjects.pattern_id WHERE tests.error IS NULL ; I then measured the query below for each PostgreSQL version: \timing SELECT version(); SELECT is_match <> (subject ~ pattern) AS is_match_diff, captured IS DISTINCT FROM regexp_match(subject, pattern, flags) AS captured_diff, COUNT(*) FROM performance_test GROUP BY 1,2 ORDER BY 1,2 ; All versions produces the same result: is_match_diff | captured_diff | count ---------------+---------------+--------- f | f | 3254769 (1 row) Good! Not a single case that differs of over 3 million different regex pattern/subject combinations, between five major PostgreSQL versions! That's a very stable regex engine. To get a feeling for the standard deviation of the timings, I executed the same query above three times for each PostgreSQL version: PostgreSQL 10.16 on x86_64-apple-darwin14.5.0, compiled by Apple LLVM version 7.0.2 (clang-700.1.81), 64-bit Time: 795674.830 ms (13:15.675) Time: 794249.704 ms (13:14.250) Time: 771036.707 ms (12:51.037) PostgreSQL 11.11 on x86_64-apple-darwin16.7.0, compiled by Apple LLVM version 8.1.0 (clang-802.0.42), 64-bit Time: 765466.191 ms (12:45.466) Time: 787135.316 ms (13:07.135) Time: 779582.635 ms (12:59.583) PostgreSQL 12.6 on x86_64-apple-darwin16.7.0, compiled by Apple LLVM version 8.1.0 (clang-802.0.42), 64-bit Time: 785500.516 ms (13:05.501) Time: 784511.591 ms (13:04.512) Time: 786727.973 ms (13:06.728) PostgreSQL 13.2 on x86_64-apple-darwin19.6.0, compiled by Apple clang version 11.0.3 (clang-1103.0.32.62), 64-bit Time: 758514.703 ms (12:38.515) Time: 755883.600 ms (12:35.884) Time: 746522.107 ms (12:26.522) PostgreSQL 14devel on x86_64-apple-darwin20.3.0, compiled by Apple clang version 12.0.0 (clang-1200.0.32.29), 64-bit HEAD (4e703d671) Time: 519620.646 ms (08:39.621) Time: 518998.366 ms (08:38.998) Time: 519696.129 ms (08:39.696) HEAD (4e703d671)+0001+0002+0003+0004+0005 Time: 141290.329 ms (02:21.290) Time: 141849.709 ms (02:21.850) Time: 141630.819 ms (02:21.631) That's a mind-blowing speed-up! I also ran the more detailed test between 13.2 and HEAD+patches, that also tests for differences in errors. Like before, one similar improvement was found, which previously resulted in an error, but now goes through OK: SELECT * FROM vdeviations; -[ RECORD 1 ]----+------------------------------------------------------------------------------------------------------- pattern | \.(ac|com\.ac|edu\.ac|gov\.ac|net\.ac|mi ... 100497 chars ... abs\.org|yolasite\.com|za\.net|za\.org)$ flags | subject | www.aeroexpo.online count | 1 a_server_version | 13.2 a_duration | 00:00:00.298253 a_is_match | a_captured | a_error | invalid regular expression: regular expression is too complex b_server_version | 14devel b_duration | 00:00:00.665958 b_is_match | t b_captured | {online} b_error | Very nice. I've uploaded the new dataset to the same place as before. The schema for it can be found at https://github.com/truthly/regexes-in-the-wild If anyone else would like a copy of the 715MB dataset, please let me know. /Joel -
Re: Some regular-expression performance hacking
Joel Jacobson <joel@compiler.org> — 2021-02-18T11:04:55Z
On Thu, Feb 18, 2021, at 11:30, Joel Jacobson wrote: >SELECT * FROM vdeviations; >-[ RECORD 1 ]----+------------------------------------------------------------------------------------------------------- >pattern | \.(ac|com\.ac|edu\.ac|gov\.ac|net\.ac|mi ... 100497 chars ... abs\.org|yolasite\.com|za\.net|za\.org)$ Heh, what a funny coincidence: The regex I used to shrink the very-long-pattern, actually happens to run a lot faster with the patches. I noticed it when trying to read from the vdeviations view in PostgreSQL 13.2. Here is my little helper-function which I used to shrink patterns/subjects longer than N characters: CREATE OR REPLACE FUNCTION shrink_text(text,integer) RETURNS text LANGUAGE sql AS $$ SELECT CASE WHEN length($1) < $2 THEN $1 ELSE format('%s ... %s chars ... %s', m[1], length(m[2]), m[3]) END FROM ( SELECT regexp_matches($1,format('^(.{1,%1$s})(.*?)(.{1,%1$s})$',$2/2)) AS m ) AS q $$; The regex aims to produce three capture groups, where I wanted the first and third ones to be greedy and match up to $2 characters (controlled by the second input param to the function), and the second capture group in the middle to be non-greedy, but match the remainder to make up a fully anchored match. It works like expected in both 13.2 and HEAD+patches, but the speed-up it enormous: PostgreSQL 13.2: EXPLAIN ANALYZE SELECT regexp_matches(repeat('a',100000),'^(.{1,80})(.*?)(.{1,80})$'); QUERY PLAN ------------------------------------------------------------------------------------------------- ProjectSet (cost=0.00..0.02 rows=1 width=32) (actual time=23600.816..23600.838 rows=1 loops=1) -> Result (cost=0.00..0.01 rows=1 width=0) (actual time=0.001..0.002 rows=1 loops=1) Planning Time: 0.432 ms Execution Time: 23600.859 ms (4 rows) HEAD+0001+0002+0003+0004+0005: EXPLAIN ANALYZE SELECT regexp_matches(repeat('a',100000),'^(.{1,80})(.*?)(.{1,80})$'); QUERY PLAN ------------------------------------------------------------------------------------------- ProjectSet (cost=0.00..0.02 rows=1 width=32) (actual time=36.656..36.661 rows=1 loops=1) -> Result (cost=0.00..0.01 rows=1 width=0) (actual time=0.000..0.002 rows=1 loops=1) Planning Time: 0.575 ms Execution Time: 36.689 ms (4 rows) Cool stuff. /Joel -
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-18T18:10:47Z
"Joel Jacobson" <joel@compiler.org> writes: >> I've produced a new dataset which now also includes the regex flags (if >> any) used for each subject applied to a pattern. Again, thanks for collecting this data! I'm a little confused about how you produced the results in the "tests" table, though. It sort of looks like you tried to feed the Javascript flags to regexp_match(), which unsurprisingly doesn't work all that well. Even discounting that, I'm not getting quite the same results, and I don't understand why not. So how was that made from the raw "patterns" and "subjects" tables? > PostgreSQL 13.2 on x86_64-apple-darwin19.6.0, compiled by Apple clang version 11.0.3 (clang-1103.0.32.62), 64-bit > Time: 758514.703 ms (12:38.515) > Time: 755883.600 ms (12:35.884) > Time: 746522.107 ms (12:26.522) > > PostgreSQL 14devel on x86_64-apple-darwin20.3.0, compiled by Apple clang version 12.0.0 (clang-1200.0.32.29), 64-bit > HEAD (4e703d671) > Time: 519620.646 ms (08:39.621) > Time: 518998.366 ms (08:38.998) > Time: 519696.129 ms (08:39.696) Hmmm ... we haven't yet committed any performance-relevant changes to the regex code, so it can't take any credit for this improvement from 13.2 to HEAD. I speculate that this is due to some change in our parallelism stuff (since I observe that this query is producing a parallelized hash plan). Still, the next drop to circa 2:21 runtime is impressive enough by itself. > Heh, what a funny coincidence: > The regex I used to shrink the very-long-pattern, > actually happens to run a lot faster with the patches. Yeah, that just happens to be a poster child for the MATCHALL idea: > EXPLAIN ANALYZE SELECT regexp_matches(repeat('a',100000),'^(.{1,80})(.*?)(.{1,80})$'); Each of the parenthesized subexpressions of the RE is successfully recognized as being MATCHALL, with length range 1..80 for two of them and 0..infinity for the middle one. That means the engine doesn't have to physically scan the text to determine whether a possible division point satisfies the sub-regexp; and that means we can find the correct division points in O(N) not O(N^2) time. regards, tom lane -
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-18T18:53:05Z
I thought it was worth looking a little more closely at the error cases in this set of tests, as a form of competition analysis versus Javascript's regex engine. I ran through the cases that gave errors, and pinned down exactly what was causing the error for as many cases as I could. (These results are from your first test corpus, but I doubt the second one would give different conclusions.) We have these errors reported in the test corpus: error | count -----------------------------------+------- invalid escape \ sequence | 39141 invalid character range | 898 invalid backreference number | 816 brackets [] not balanced | 327 invalid repetition count(s) | 76 quantifier operand invalid | 17 parentheses () not balanced | 1 regular expression is too complex | 1 The existing patchset takes care of the one "regular expression is too complex" failure. Of the rest: It turns out that almost 39000 of the "invalid escape \ sequence" errors are due to use of \D, \S, or \W within a character class. We support the positive-class shorthands \d, \s, \w there, but not their negations. I think that this might be something that Henry Spencer just never got around to; I don't see any fundamental reason we can't allow it, although some refactoring might be needed in the regex lexer. Given the apparent popularity of this notation, maybe we should put some work into that. (Having said that, I can't help noticing that a very large fraction of those usages look like, eg, "[\w\W]". It seems to me that that's a very expensive and unwieldy way to spell ".". Am I missing something about what that does in Javascript?) About half of the remaining escape-sequence complaints seem to be due to just randomly backslashing alphanumeric characters that don't need it, as for example "i" in "\itunes\.apple\.com". Apparently Javascript is content to take "\i" as just meaning "i". Our engine rejects that, with a view to keeping such combinations reserved for future definition. That's fine by me so I don't want to change it. Of the rest, many are abbreviated numeric escapes, eg "\u45" where our engine wants to see "\u0045". I don't think being laxer about that would be a great idea either. Lastly, there are some occurrences like "[\1]", which in context look like the \1 might be intended as a back-reference? But I don't really understand what that's supposed to do inside a bracket expression. The "invalid character range" errors seem to be coming from constructs like "[A-Za-z0-9-/]", which our engine rejects because it looks like a messed-up character range. All but 123 of the "invalid backreference number" complaints stem from using backrefs inside lookahead constraints. Some of the rest look like they think you can put capturing parens inside a lookahead constraint and then backref that. I'm not really convinced that such constructs have a well-defined meaning. (I looked at the ECMAscript definition of regexes, and they do say it's allowed, but when trying to define it they resort to handwaving about backtracking; at best that is a particularly lame version of specification by implementation.) Spencer chose to forbid these cases in our engine, and I think there are very good implementation reasons why it won't work. Perhaps we could provide a clearer error message about it, though. 307 of the "brackets [] not balanced" errors, as well as the one "parentheses () not balanced" error, seem to trace to the fact that Javascript considers "[]" to be a legal empty character class, whereas POSIX doesn't allow empty character classes so our engine takes the "]" literally, and then looks for a right bracket it won't find. (That is, in POSIX "[]x]" is a character class matching ']' and 'x'.) Maybe I'm misinterpreting this too, because if I read the documentation correctly, "[]" in Javascript matches nothing, making it impossible for the regex to succeed. Why would such a construct appear this often? The remainder of the bracket errors happen because in POSIX, the sequences "[:", "[=", and "[." within a bracket expression introduce special syntax, whereas in Javascript '[' is just an ordinary data character within a bracket expression. Not much we can do here; the standards are just incompatible. All but 3 of the "invalid repetition count(s)" errors come from quantifiers larger than our implementation limit of 255. A lot of those are exactly 256, though I saw one as high as 3000. The remaining 3 errors are from syntax like "[0-9]{0-3}", which is a syntax error according to our engine ("[0-9]{0,3}" is correct). AFAICT it's not a valid quantifier according to Javascript either; perhaps that engine is just taking the "{0-3}" as literal text? Given this, it seems like there's a fairly strong case for increasing our repetition-count implementation limit, at least to 256, and maybe 1000 or so. I'm hesitant to make the limit *really* large, but if we can handle a regex containing thousands of "x"'s, it's not clear why you shouldn't be able to write that as "x{0,1000}". All of the "quantifier operand invalid" errors come from these three patterns: ((?!\\)?\{0(?!\\)?\}) ((?!\\)?\{1(?!\\)?\}) class="(?!(tco-hidden|tco-display|tco-ellipsis))+.*?"|data-query-source=".*?"|dir=".*?"|rel=".*?" which are evidently trying to apply a quantifier to a lookahead constraint, which is just silly. In short, a lot of this is from incompatible standards, or maybe from varying ideas about whether to throw an error for invalid constructs. But I see a couple things we could improve. regards, tom lane -
Re: Some regular-expression performance hacking
Joel Jacobson <joel@compiler.org> — 2021-02-18T19:58:07Z
On Thu, Feb 18, 2021, at 19:10, Tom Lane wrote: > "Joel Jacobson" <joel@compiler.org> writes: > >> I've produced a new dataset which now also includes the regex flags (if > >> any) used for each subject applied to a pattern. > > Again, thanks for collecting this data! I'm a little confused about > how you produced the results in the "tests" table, though. It sort > of looks like you tried to feed the Javascript flags to regexp_match(), > which unsurprisingly doesn't work all that well. That's exactly what I did. Some of the flags work the same between Javascript and PostgreSQL, others don't. I thought maybe something interesting would surface in just trying them blindly. Flags that aren't supported and gives errors are reported as tests where error is not null. Most patterns have no flags, and second most popular is just the "i" flag, which should work the same. SELECT flags, COUNT(*) FROM patterns GROUP BY 1 ORDER BY 2 DESC; flags | count -------+-------- | 151927 i | 120336 gi | 26057 g | 13263 gm | 4606 gim | 699 im | 491 y | 367 m | 365 gy | 105 u | 50 giy | 38 giu | 20 gimu | 14 iy | 11 iu | 6 gimy | 3 gu | 2 gmy | 2 imy | 1 my | 1 (21 rows) This query shows what Javascript-regex-flags that could be used as-is without errors: SELECT patterns.flags, COUNT(*) FROM tests JOIN subjects ON subjects.subject_id = tests.subject_id JOIN patterns ON patterns.pattern_id = subjects.pattern_id WHERE tests.error IS NULL GROUP BY 1 ORDER BY 2; flags | count -------+--------- im | 2534 m | 4460 i | 543598 | 2704177 (4 rows) I considered filtering/converting the flags to PostgreSQL, maybe that would be an interesting approach to try as well. > > Even discounting > that, I'm not getting quite the same results, and I don't understand > why not. So how was that made from the raw "patterns" and "subjects" > tables? The rows in the tests table were generated by the create_regexp_tests() function [1] Each subject now has a foreign key to a specific pattern, where the (pattern, flags) combination are unique in patterns. The actual unique constraint is on (pattern_hash, flags) to avoid an index directly on pattern which can be huge as we've seen. So, for each subject, it is known via the pattern_id exactly what flags were used when the regex was compiled (and later executed/applied with the subject). [1] https://github.com/truthly/regexes-in-the-wild/blob/master/create_regexp_tests.sql > > > PostgreSQL 13.2 on x86_64-apple-darwin19.6.0, compiled by Apple clang version 11.0.3 (clang-1103.0.32.62), 64-bit > > Time: 758514.703 ms (12:38.515) > > Time: 755883.600 ms (12:35.884) > > Time: 746522.107 ms (12:26.522) > > > > PostgreSQL 14devel on x86_64-apple-darwin20.3.0, compiled by Apple clang version 12.0.0 (clang-1200.0.32.29), 64-bit > > HEAD (4e703d671) > > Time: 519620.646 ms (08:39.621) > > Time: 518998.366 ms (08:38.998) > > Time: 519696.129 ms (08:39.696) > > Hmmm ... we haven't yet committed any performance-relevant changes to the > regex code, so it can't take any credit for this improvement from 13.2 to > HEAD. I speculate that this is due to some change in our parallelism > stuff (since I observe that this query is producing a parallelized hash > plan). Still, the next drop to circa 2:21 runtime is impressive enough > by itself. OK. Another factor might perhaps be the PostgreSQL 10, 11, 12, 13 versions were compiled elsewhere, I used the OS X binaries from https://postgresapp.com/, whereas version 14 I of course compiled myself. Maybe I should have compiled 10, 11, 12, 13 myself instead, for a better comparison, but I mostly just wanted to verify if I could find any differences, the performance comparison was a bonus. > > > Heh, what a funny coincidence: > > The regex I used to shrink the very-long-pattern, > > actually happens to run a lot faster with the patches. > > Yeah, that just happens to be a poster child for the MATCHALL idea: > > > EXPLAIN ANALYZE SELECT regexp_matches(repeat('a',100000),'^(.{1,80})(.*?)(.{1,80})$'); > > Each of the parenthesized subexpressions of the RE is successfully > recognized as being MATCHALL, with length range 1..80 for two of them and > 0..infinity for the middle one. That means the engine doesn't have to > physically scan the text to determine whether a possible division point > satisfies the sub-regexp; and that means we can find the correct division > points in O(N) not O(N^2) time. Very nice. Like you said earlier, perhaps the regex engine has been optimized enough for this time. If not, you want to investigate an additional idea, that I think can be seen as a generalization of the optimization trick for (.*), if I've understood how it works correctly. Let's see if I can explain the idea: One of the problems with representing regexes with large bracket range expressions, like [a-z], is you get an explosion of edges, if the model can only represent state transitions for single characters. If we could instead let a single edge (for a state transition) represent a set of characters, or normally even more efficiently, a set of range of characters, then we could reduce the number of edges we need to represent the graph. The naive approach to just use the ranges as-is doesn't work. Instead, the graph must first be created with single-character edges. It is then examined what ranges can be constructed in a way that no single range overlaps any other range, so that every range can be seen as a character in an alphabet. Perhaps a bit of fiddling with some examples is easiest to get a grip of the idea. Here is a live demo of the idea: https://compiler.org/reason-re-nfa/src/index.html The graphs are rendered live when typing in the regex, using a Javascript port of GraphViz. For example, try entering the regex: t[a-z]*m This generates this range-optimized graph for the regex: /--[a-ln-su-z]-----------------\ |/------t--------------------\ | || | | -->(0)--t-->({0,1})----m-------->({0 1 2}) | | ^---[a-ln-su-z]--/ | | ^-------t-------/ | | ^---------------------------/ | ^-----------------------------/ Notice how the [a-z] bracket expression has been split up, and we now have 3 distinct set of "ranges": t m [a-ln-su-z] Since no ranges are overlapping, each such range can safely be seen as a letter in an alphabet. Once we have our final graph, but before we proceed to generate the machine code for it, we can shrink the graph further by merging ranges together, which eliminate some edges: /--------------\ | | --->(0)--t-->(1)<--[a-ln-z]--/ |^-[a-lnz]-\ \----m-->((2))<----\ | | \---m---/ Notice how [a-ln-su-z]+t becomes [a-ln-z]. Another optimization I've come up with (or probably re-invented because it feels quite obvious), is to read more than one character, when knowing for sure multiple characters-in-a-row are expected, by concatenating edges having only one parent and one child. In our example, we know for sure at least two characters will be read for the regex t[a-z]*m, so with this optimization enabled, we get this graph: /--[a-ln-z] | | --->(0)---t[a-ln-z]--->(1)<---+--[a-ln-z] | | / | \---m--->((2))<------\ \--------------tm------------^ | | \----m----/ This makes not much difference for a few characters, but if we have a long pattern with a long sentence that is repeated, we could e.g. read in 32 bytes and compare them all in one operation, if our machine had 256-bits SIMD registers/instructions. This idea has also been implemented in the online demo. There is a level which can be adjusted from 0 to 32 to control how many bytes to merge at most, located in the "[+]dfa5 = merge_linear(dfa4)" step. Anyway, I can totally understand if you've had enough of regex optimizations for this time, but in case not, I wanted to share my work in this field, in case it's interesting to look at now or in the future. /Joel -
Re: Some regular-expression performance hacking
Joel Jacobson <joel@compiler.org> — 2021-02-18T20:44:07Z
On Thu, Feb 18, 2021, at 20:58, Joel Jacobson wrote: >Like you said earlier, perhaps the regex engine has been optimized enough for this time. >If not, you want to investigate an additional idea, In the above sentence, I meant "you _may_ want to". I'm not at all sure these idea are applicable in the PostgreSQL regex engine, so feel free to silently ignore these if you feel there is a risk for time waste. >that I think can be seen as a generalization of the optimization trick for (.*), >if I've understood how it works correctly. Actually not sure if it can be seen as a generalization, I just came to think of my ideas since they also improve the case when you have lots of (.*) or bracket expressions of large ranges. /Joel
-
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-18T20:44:47Z
"Joel Jacobson" <joel@compiler.org> writes: > Let's see if I can explain the idea: > One of the problems with representing regexes with large bracket range expressions, like [a-z], > is you get an explosion of edges, if the model can only represent state transitions for single characters. > If we could instead let a single edge (for a state transition) represent a set of characters, > or normally even more efficiently, a set of range of characters, then we could reduce the > number of edges we need to represent the graph. > The naive approach to just use the ranges as-is doesn't work. > Instead, the graph must first be created with single-character edges. > It is then examined what ranges can be constructed in a way that no single range > overlaps any other range, so that every range can be seen as a character in an alphabet. Hmm ... I might be misunderstanding, but I think our engine already does a version of this. See the discussion of "colors" in src/backend/regex/README. > Another optimization I've come up with (or probably re-invented because it feels quite obvious), > is to read more than one character, when knowing for sure multiple characters-in-a-row > are expected, by concatenating edges having only one parent and one child. Maybe. In practice the actual scanning tends to be tracking more than one possible NFA state in parallel, so I'm not sure how often we could expect to be able to use this idea. That is, even if we know that state X can only succeed by following an arc to Y and then another to Z, we might also be interested in what happens if the NFA is in state Q at this point; and it seems unlikely that Q would have exactly the same two following arc colors. I do have some ideas about possible future optimizations, and one reason I'm grateful for this large set of real regexes is that it can provide a concrete basis for deciding that particular optimizations are or are not worth pursuing. So thanks again for collecting it! regards, tom lane
-
Re: Some regular-expression performance hacking
Joel Jacobson <joel@compiler.org> — 2021-02-18T20:54:38Z
On Thu, Feb 18, 2021, at 21:44, Tom Lane wrote: >Hmm ... I might be misunderstanding, but I think our engine already >does a version of this. See the discussion of "colors" in >src/backend/regex/README. Thanks, I will read it with great interest. >Maybe. In practice the actual scanning tends to be tracking more than one >possible NFA state in parallel, so I'm not sure how often we could expect >to be able to use this idea. That is, even if we know that state X can >only succeed by following an arc to Y and then another to Z, we might >also be interested in what happens if the NFA is in state Q at this point; >and it seems unlikely that Q would have exactly the same two following >arc colors. Right. Actually I don't have a clear idea on how it could be implemented in an NFA engine. >I do have some ideas about possible future optimizations, and one reason >I'm grateful for this large set of real regexes is that it can provide a >concrete basis for deciding that particular optimizations are or are not >worth pursuing. So thanks again for collecting it! My pleasure. Thanks for using it! /Joel
-
Re: Some regular-expression performance hacking
Joel Jacobson <joel@compiler.org> — 2021-02-19T12:45:34Z
On Thu, Feb 18, 2021, at 19:53, Tom Lane wrote: >(Having said that, I can't help noticing that a very large fraction >of those usages look like, eg, "[\w\W]". It seems to me that that's >a very expensive and unwieldy way to spell ".". Am I missing >something about what that does in Javascript?) This popular regex ^(?:\s*(<[\w\W]+>)[^>]*|#([\w-]+))$ is coming from jQuery: // A simple way to check for HTML strings // Prioritize #id over <tag> to avoid XSS via location.hash (#9521) // Strict HTML recognition (#11290: must start with <) // Shortcut simple #id case for speed rquickExpr = /^(?:\s*(<[\w\W]+>)[^>]*|#([\w-]+))$/, From: https://code.jquery.com/jquery-3.5.1.js I think this is a non-POSIX hack to match any character, including newlines, which are not included unless the "s" flag is set. Javascript test: "foo\nbar".match(/(.+)/)[1]; "foo" "foo\nbar".match(/(.+)/s)[1]; "foo bar" "foo\nbar".match(/([\w\W]+)/)[1]; "foo bar" /Joel -
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-19T15:26:20Z
"Joel Jacobson" <joel@compiler.org> writes: > On Thu, Feb 18, 2021, at 19:53, Tom Lane wrote: >> (Having said that, I can't help noticing that a very large fraction >> of those usages look like, eg, "[\w\W]". It seems to me that that's >> a very expensive and unwieldy way to spell ".". Am I missing >> something about what that does in Javascript?) > I think this is a non-POSIX hack to match any character, including newlines, > which are not included unless the "s" flag is set. > "foo\nbar".match(/([\w\W]+)/)[1]; > "foo > bar" Oooh, that's very interesting. I guess the advantage of that over using the 's' flag is that you can have different behaviors at different places in the same regex. I was just wondering about this last night in fact, while hacking on the code to get it to accept \W etc in bracket expressions. I see that right now, our code thinks that NLSTOP mode ('n' switch, the opposite of 's') should cause \W \D \S to not match newline. That seems a little weird, not least because \S should probably be different from the other two, and it isn't. And now we see it'd mean that you couldn't use the 'n' switch to duplicate Javascript's default behavior in this area. Should we change it? (I wonder what Perl does.) regards, tom lane -
Re: Some regular-expression performance hacking
Joel Jacobson <joel@compiler.org> — 2021-02-20T09:19:04Z
On Fri, Feb 19, 2021, at 16:26, Tom Lane wrote: >"Joel Jacobson" <joel@compiler.org> writes: >> On Thu, Feb 18, 2021, at 19:53, Tom Lane wrote: >>> (Having said that, I can't help noticing that a very large fraction >>> of those usages look like, eg, "[\w\W]". It seems to me that that's >>> a very expensive and unwieldy way to spell ".". Am I missing >>> something about what that does in Javascript?) > >> I think this is a non-POSIX hack to match any character, including newlines, >> which are not included unless the "s" flag is set. > >> "foo\nbar".match(/([\w\W]+)/)[1]; >> "foo >> bar" > >Oooh, that's very interesting. I guess the advantage of that over using >the 's' flag is that you can have different behaviors at different places >in the same regex. I would guess the same thing. >I was just wondering about this last night in fact, while hacking on >the code to get it to accept \W etc in bracket expressions. I see that >right now, our code thinks that NLSTOP mode ('n' switch, the opposite >of 's') should cause \W \D \S to not match newline. That seems a little >weird, not least because \S should probably be different from the other >two, and it isn't. And now we see it'd mean that you couldn't use the 'n' >switch to duplicate Javascript's default behavior in this area. Should we >change it? (I wonder what Perl does.) > >regards, tom lane To allow comparing PostgreSQL vs Javascript vs Perl, I installed three helper-functions using plv8 and plperl, and also one convenience function for PostgreSQL to catch errors and return the error string instead: The string used in this test is "foo!\n!bar", which aims to detect differences in how new-lines and non alpha-number characters are handled. To allow PostgreSQL to be compared with Javascript and Perl, the "n" flag is used for PostgreSQL when no flags are used for Javascript/Perl, and no flag for PostgreSQL when the "s" flag is used for Javascript/Perl, for the results to be comparable. In Javascript, when a regex contains capture groups, the entire match is always returns as the first array element. To make it easier to visually compare the results, the first element is removed from Javascript, which works in this test since all regexes contain exactly one capture group. Here are the results: $ psql -e -f not_alnum.sql regex SELECT regexp_match_pg(E'foo!\n!bar', '(.+)', 'n'), (regexp_match_v8(E'foo!\n!bar', '(.+)', ''))[2:], regexp_match_pl(E'foo!\n!bar', '(.+)', '') ; regexp_match_pg | regexp_match_v8 | regexp_match_pl -----------------+-----------------+----------------- {foo!} | {foo!} | {foo!} (1 row) SELECT regexp_match_pg(E'foo!\n!bar', '(.+)', ''), (regexp_match_v8(E'foo!\n!bar', '(.+)', 's'))[2:], regexp_match_pl(E'foo!\n!bar', '(.+)', 's') ; regexp_match_pg | regexp_match_v8 | regexp_match_pl -----------------+-----------------+----------------- {"foo! +| {"foo! +| {"foo! + !bar"} | !bar"} | !bar"} (1 row) SELECT regexp_match_pg(E'foo!\n!bar', '([\w\W]+)', 'n'), (regexp_match_v8(E'foo!\n!bar', '([\w\W]+)', ''))[2:], regexp_match_pl(E'foo!\n!bar', '([\w\W]+)', '') ; regexp_match_pg | regexp_match_v8 | regexp_match_pl ------------------------------------------------------------+-----------------+----------------- {"invalid regular expression: invalid escape \\ sequence"} | {"foo! +| {"foo! + | !bar"} | !bar"} (1 row) SELECT regexp_match_pg(E'foo!\n!bar', '([\w\W]+)', ''), (regexp_match_v8(E'foo!\n!bar', '([\w\W]+)', 's'))[2:], regexp_match_pl(E'foo!\n!bar', '([\w\W]+)', 's') ; regexp_match_pg | regexp_match_v8 | regexp_match_pl ------------------------------------------------------------+-----------------+----------------- {"invalid regular expression: invalid escape \\ sequence"} | {"foo! +| {"foo! + | !bar"} | !bar"} (1 row) SELECT regexp_match_pg(E'foo!\n!bar', '([\w]+)', 'n'), (regexp_match_v8(E'foo!\n!bar', '([\w]+)', ''))[2:], regexp_match_pl(E'foo!\n!bar', '([\w]+)', '') ; regexp_match_pg | regexp_match_v8 | regexp_match_pl -----------------+-----------------+----------------- {foo} | {foo} | {foo} (1 row) SELECT regexp_match_pg(E'foo!\n!bar', '([\w]+)', ''), (regexp_match_v8(E'foo!\n!bar', '([\w]+)', 's'))[2:], regexp_match_pl(E'foo!\n!bar', '([\w]+)', 's') ; regexp_match_pg | regexp_match_v8 | regexp_match_pl -----------------+-----------------+----------------- {foo} | {foo} | {foo} (1 row) SELECT regexp_match_pg(E'foo!\n!bar', '([\W]+)', 'n'), (regexp_match_v8(E'foo!\n!bar', '([\W]+)', ''))[2:], regexp_match_pl(E'foo!\n!bar', '([\W]+)', '') ; regexp_match_pg | regexp_match_v8 | regexp_match_pl ------------------------------------------------------------+-----------------+----------------- {"invalid regular expression: invalid escape \\ sequence"} | {"! +| {"! + | !"} | !"} (1 row) SELECT regexp_match_pg(E'foo!\n!bar', '([\W]+)', ''), (regexp_match_v8(E'foo!\n!bar', '([\W]+)', 's'))[2:], regexp_match_pl(E'foo!\n!bar', '([\W]+)', 's') ; regexp_match_pg | regexp_match_v8 | regexp_match_pl ------------------------------------------------------------+-----------------+----------------- {"invalid regular expression: invalid escape \\ sequence"} | {"! +| {"! + | !"} | !"} (1 row) SELECT regexp_match_pg(E'foo!\n!bar', '(\w+)', 'n'), (regexp_match_v8(E'foo!\n!bar', '(\w+)', ''))[2:], regexp_match_pl(E'foo!\n!bar', '(\w+)', '') ; regexp_match_pg | regexp_match_v8 | regexp_match_pl -----------------+-----------------+----------------- {foo} | {foo} | {foo} (1 row) SELECT regexp_match_pg(E'foo!\n!bar', '(\w+)', ''), (regexp_match_v8(E'foo!\n!bar', '(\w+)', 's'))[2:], regexp_match_pl(E'foo!\n!bar', '(\w+)', 's') ; regexp_match_pg | regexp_match_v8 | regexp_match_pl -----------------+-----------------+----------------- {foo} | {foo} | {foo} (1 row) SELECT regexp_match_pg(E'foo!\n!bar', '(\W+)', 'n'), (regexp_match_v8(E'foo!\n!bar', '(\W+)', ''))[2:], regexp_match_pl(E'foo!\n!bar', '(\W+)', '') ; regexp_match_pg | regexp_match_v8 | regexp_match_pl -----------------+-----------------+----------------- {!} | {"! +| {"! + | !"} | !"} (1 row) SELECT regexp_match_pg(E'foo!\n!bar', '(\W+)', ''), (regexp_match_v8(E'foo!\n!bar', '(\W+)', 's'))[2:], regexp_match_pl(E'foo!\n!bar', '(\W+)', 's') ; regexp_match_pg | regexp_match_v8 | regexp_match_pl -----------------+-----------------+----------------- {"! +| {"! +| {"! + !"} | !"} | !"} (1 row) /Joel -
Re: Some regular-expression performance hacking
Chapman Flack <chap@anastigmatix.net> — 2021-02-20T23:31:39Z
On 02/19/21 10:26, Tom Lane wrote: >> "foo\nbar".match(/([\w\W]+)/)[1]; >> "foo >> bar" > > Oooh, that's very interesting. I guess the advantage of that over using > the 's' flag is that you can have different behaviors at different places > in the same regex. Perl, Python, and Java (at least) all have a common syntax for changing flags locally in a non-capturing group, so you could just match (?s:.) -- which I guess isn't any shorter than [\w\W] but makes the intent more clear. I see that JavaScript, for some reason, does not advertise that. We don't either; we have (?:groups) without flags, and we have (?flags) but only global at the start of the regex. Would it be worthwhile to jump on the bandwagon and support local flags in groups? We currently give 2201B: invalid regular expression: invalid embedded option on an attempt to use the syntax, so implementing it couldn't break anything someone is already doing. Regards, -Chap
-
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-21T01:13:29Z
Chapman Flack <chap@anastigmatix.net> writes: > On 02/19/21 10:26, Tom Lane wrote: >> Oooh, that's very interesting. I guess the advantage of that over using >> the 's' flag is that you can have different behaviors at different places >> in the same regex. > Perl, Python, and Java (at least) all have a common syntax for changing > flags locally in a non-capturing group, so you could just match (?s:.) > -- which I guess isn't any shorter than [\w\W] but makes the intent more > clear. Hmm, interesting. > I see that JavaScript, for some reason, does not advertise that. We don't > either; we have (?:groups) without flags, and we have (?flags) but only > global at the start of the regex. Would it be worthwhile to jump on the > bandwagon and support local flags in groups? Yeah, perhaps. Not sure whether there are any built-in assumptions about these flags holding still throughout the regex; that'd require some review. But it seems like it could be a useful feature, and I don't see any argument why we shouldn't have it. regards, tom lane
-
Re: Some regular-expression performance hacking
Andres Freund <andres@anarazel.de> — 2021-02-23T17:34:37Z
Hi, One of the recent commits have introduce a new warning with gcc 10, when building with optimizations: In file included from /home/andres/src/postgresql/src/backend/regex/regcomp.c:2304: /home/andres/src/postgresql/src/backend/regex/regc_nfa.c: In function ‘checkmatchall’: /home/andres/src/postgresql/src/backend/regex/regc_nfa.c:3087:20: warning: array subscript -1 is outside array bounds of ‘_Bool[257]’ [-Warray-bounds] 3087 | hasmatch[depth] = true; | ^ /home/andres/src/postgresql/src/backend/regex/regc_nfa.c:2920:8: note: while referencing ‘hasmatch’ 2920 | bool hasmatch[DUPINF + 1]; | ^~~~~~~~ Greetings, Andres Freund -
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-23T17:39:09Z
Andres Freund <andres@anarazel.de> writes: > One of the recent commits have introduce a new warning with gcc 10, when > building with optimizations: > In file included from /home/andres/src/postgresql/src/backend/regex/regcomp.c:2304: > /home/andres/src/postgresql/src/backend/regex/regc_nfa.c: In function ‘checkmatchall’: > /home/andres/src/postgresql/src/backend/regex/regc_nfa.c:3087:20: warning: array subscript -1 is outside array bounds of ‘_Bool[257]’ [-Warray-bounds] > 3087 | hasmatch[depth] = true; > | ^ Hmph. There's an "assert(depth >= 0)" immediately in front of that, so I'm not looking too kindly on the compiler thinking it's smarter than I am. Do you have a suggestion on how to shut it up? regards, tom lane
-
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-23T17:52:28Z
I wrote: > Hmph. There's an "assert(depth >= 0)" immediately in front of that, > so I'm not looking too kindly on the compiler thinking it's smarter > than I am. Do you have a suggestion on how to shut it up? On reflection, maybe the thing to do is convert the assert into an always-on check, "if (depth < 0) return false". The assertion is essentially saying that there's no arc leading directly from the pre state to the post state. Which there had better not be, or a lot of other stuff is going to go wrong; but I suppose there's no way to explain that to gcc. It is annoying to have to expend an always-on check for a can't-happen case, though. regards, tom lane
-
Re: Some regular-expression performance hacking
Andres Freund <andres@anarazel.de> — 2021-02-23T18:05:35Z
Hi, On 2021-02-23 12:52:28 -0500, Tom Lane wrote: > I wrote: > > Hmph. There's an "assert(depth >= 0)" immediately in front of that, > > so I'm not looking too kindly on the compiler thinking it's smarter > > than I am. Do you have a suggestion on how to shut it up? gcc can't see the assert though, in an non-cassert optimized build... If I force assertions to be used, the warning vanishes. > On reflection, maybe the thing to do is convert the assert into > an always-on check, "if (depth < 0) return false". The assertion > is essentially saying that there's no arc leading directly from > the pre state to the post state. Which there had better not be, > or a lot of other stuff is going to go wrong; but I suppose there's > no way to explain that to gcc. It is annoying to have to expend > an always-on check for a can't-happen case, though. Wouldn't quite work like that because of the restrictions of what pg infrastructure we want to expose the regex engine to, but a if (depth < 0) pg_unreachable(); would avoid the runtime overhead and does fix the warning. I have been wondering about making Asserts do something along those lines - but it'd need to be opt-in, since we clearly have a lot of assertions that would cost too much. Greetings, Andres Freund -
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-23T18:09:18Z
Andres Freund <andres@anarazel.de> writes: > One of the recent commits have introduce a new warning with gcc 10, when > building with optimizations: Oddly, I see no such warning with Fedora's current compiler, gcc version 10.2.1 20201125 (Red Hat 10.2.1-9) (GCC) Are you using any special compiler switches? regards, tom lane
-
Re: Some regular-expression performance hacking
Andres Freund <andres@anarazel.de> — 2021-02-23T18:18:51Z
On 2021-02-23 13:09:18 -0500, Tom Lane wrote: > Andres Freund <andres@anarazel.de> writes: > > One of the recent commits have introduce a new warning with gcc 10, when > > building with optimizations: > > Oddly, I see no such warning with Fedora's current compiler, > gcc version 10.2.1 20201125 (Red Hat 10.2.1-9) (GCC) > > Are you using any special compiler switches? A few. At first I didn't see any relevant ones - but I think it's just that you need to use -O3 instead of -O2. andres@awork3:~/build/postgres/dev-optimize/vpath$ (cd src/backend/regex/ && ccache gcc-10 -Wall -Wmissing-prototypes -Wpointer-arith -Wdeclaration-after-statement -Werror=vla -Wendif-labels -Wmissing-format-attribute -Wimplicit-fallthrough=3 -Wcast-function-type -Wformat-security -fno-strict-aliasing -fwrapv -fexcess-precision=standard -I../../../src/include -I/home/andres/src/postgresql/src/include -D_GNU_SOURCE -I/usr/include/libxml2 -c -o regcomp.o /home/andres/src/postgresql/src/backend/regex/regcomp.c -O2) andres@awork3:~/build/postgres/dev-optimize/vpath$ (cd src/backend/regex/ && ccache gcc-10 -Wall -Wmissing-prototypes -Wpointer-arith -Wdeclaration-after-statement -Werror=vla -Wendif-labels -Wmissing-format-attribute -Wimplicit-fallthrough=3 -Wcast-function-type -Wformat-security -fno-strict-aliasing -fwrapv -fexcess-precision=standard -I../../../src/include -I/home/andres/src/postgresql/src/include -D_GNU_SOURCE -I/usr/include/libxml2 -c -o regcomp.o /home/andres/src/postgresql/src/backend/regex/regcomp.c -O3) In file included from /home/andres/src/postgresql/src/backend/regex/regcomp.c:2304: /home/andres/src/postgresql/src/backend/regex/regc_nfa.c: In function ‘checkmatchall’: /home/andres/src/postgresql/src/backend/regex/regc_nfa.c:3086:20: warning: array subscript -1 is outside array bounds of ‘_Bool[257]’ [-Warray-bounds] 3086 | hasmatch[depth] = true; | ^ /home/andres/src/postgresql/src/backend/regex/regc_nfa.c:2920:8: note: while referencing ‘hasmatch’ 2920 | bool hasmatch[DUPINF + 1]; | ^~~~~~~~ andres@awork3:~/build/postgres/dev-optimize/vpath$ gcc-10 --version gcc-10 (Debian 10.2.1-6) 10.2.1 20210110 Copyright (C) 2020 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. Greetings, Andres Freund -
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-23T18:22:35Z
Andres Freund <andres@anarazel.de> writes: > On 2021-02-23 12:52:28 -0500, Tom Lane wrote: >> ... It is annoying to have to expend >> an always-on check for a can't-happen case, though. > Wouldn't quite work like that because of the restrictions of what pg > infrastructure we want to expose the regex engine to, but a > if (depth < 0) > pg_unreachable(); > would avoid the runtime overhead and does fix the warning. Yeah, I still have dreams of someday converting the regex engine into an independent project, so I don't want to make it depend on pg_unreachable. I'll put in the low-tech fix. regards, tom lane
-
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-23T18:36:16Z
Andres Freund <andres@anarazel.de> writes: > On 2021-02-23 13:09:18 -0500, Tom Lane wrote: >> Oddly, I see no such warning with Fedora's current compiler, >> gcc version 10.2.1 20201125 (Red Hat 10.2.1-9) (GCC) >> Are you using any special compiler switches? > A few. At first I didn't see any relevant ones - but I think it's just > that you need to use -O3 instead of -O2. Ah-hah, -O3 plus remembering to disable assertions makes it happen here too. Will fix. regards, tom lane
-
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-24T02:32:50Z
Here's another little piece of regex performance hacking. This is based on looking at a slow regexp I found in Tcl's bug tracker: -- Adapted from http://core.tcl.tk/tcl/tktview?name=446565 select regexp_matches( repeat('<script> 123 </script> <script> 345 </script> <script> 123 </script>', 100000), '<script(.(?!</script>))*?(doubleclick|flycast|burstnet|spylog)+?.*?</script>'); The core of the problem here is the lookahead constraint (?!</script>), which gets applied O(N^2) times for an N-character data string. The present patch doesn't do anything to cut down the big-O problem, but it does take a swipe at cutting the constant factor, which should remain useful even if we find a way to avoid the O(N^2) issue. Poking at this with perf, I was surprised to observe that the dominant cost is not down inside lacon() as one would expect, but in the loop in miss() that is deciding where to call lacon(). 80% of the runtime is going into these three lines: for (i = 0; i < d->nstates; i++) if (ISBSET(d->work, i)) for (ca = cnfa->states[i]; ca->co != COLORLESS; ca++) So there are two problems here. The outer loop is iterating over all the NFA states, even though only a small fraction of the states are likely to have LACON out-arcs. (In the case at hand, the main NFA has 78 states, of which just one has LACON out-arcs.) Then, for every reachable state, we're scanning all its out-arcs to find the ones that are LACONs. (Again, just a fraction of the out-arcs are likely to be LACONs.) So the main thrust of this patch is to rearrange the "struct cnfa" representation to separate plain arcs from LACON arcs, allowing this loop to not waste time looking at irrelevant states or arcs. This also saves some time in miss()'s preceding main loop, which is only interested in plain arcs. Splitting the LACON arcs from the plain arcs complicates matters in a couple of other places, but none of them are in the least performance-critical. The other thing I noticed while looking at miss() is that it will call lacon() for each relevant arc, even though it's quite likely to see multiple arcs labeled with the same constraint number, for which the answer must be the same. So I added some simple logic to cache the last answer and re-use it if the next arc of interest has the same color. (We could imagine working harder to cache in the presence of multiple interesting LACONs, but I'm doubtful that it's worth the trouble. The one-entry cache logic is so simple it can hardly be a net loss, though.) On my machine, the combination of these two ideas reduces the runtime of the example above from ~150 seconds to ~53 seconds, or nearly 3x better. I see something like a 2% improvement on Joel's test corpus, which might just be noise. So this isn't any sort of universal panacea, but it sure helps when LACON evaluation is the bottleneck. Any objections? or better ideas? regards, tom lane -
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-24T23:19:52Z
I wrote: > On my machine, the combination of these two ideas reduces the > runtime of the example above from ~150 seconds to ~53 seconds, > or nearly 3x better. I see something like a 2% improvement on > Joel's test corpus, which might just be noise. So this isn't > any sort of universal panacea, but it sure helps when LACON > evaluation is the bottleneck. After another round of testing, I really can't see any improvement at all from that patch on anything except the original Tcl test case. Indeed, a lot of cases seem very slightly worse, perhaps because compact() now has to make two passes over all the arcs. So that's leaving me a bit dissatisfied with it; I'm going to stick it on the back burner for now, in hopes of a better idea. However, in a different line of thought, I realized that the memory allocation logic could use some polishing. It gives out ten arcs per NFA state initially, and then adds ten more at a time. However, that's not very bright when you look at the actual usage patterns, because most states have only one or two out-arcs, but some have lots and lots. I instrumented things to gather stats about arcs-per-state on your larger corpus, and I got this, where the seond column is the total fraction of states having the given number of arcs or fewer: arcs | cum_fraction ------+------------------------ 0 | 0.03152871318455725868 1 | 0.55852399556959499493 2 | 0.79408539124378449284 3 | 0.86926656199366447221 4 | 0.91726891675794579062 5 | 0.92596934405572457792 6 | 0.93491612836055807037 7 | 0.94075102352639209644 8 | 0.94486598829672779379 9 | 0.94882085883928361399 10 | 0.95137992908336444821 11 | 0.95241399914559696173 12 | 0.95436547669138874594 13 | 0.95534682472329051385 14 | 0.95653340893356523452 15 | 0.95780804864876924571 16 | 0.95902387577636979702 17 | 0.95981494467267418552 18 | 0.96048662216159976997 19 | 0.96130294229052153065 20 | 0.96196856160309755204 ... 3238 | 0.99999985870142624926 3242 | 0.99999987047630739515 4095 | 0.99999987342002768163 4535 | 0.99999987930746825457 4642 | 0.99999988225118854105 4706 | 0.99999989402606968694 5890 | 0.99999989696978997342 6386 | 0.99999990874467111931 7098 | 0.99999991168839140579 7751 | 0.99999994701303484347 7755 | 0.99999998233767828116 7875 | 0.99999998822511885410 8049 | 1.00000000000000000000 So it seemed clear to me that we should only give out a couple of arcs per state initially, but then let it ramp up faster than 10 arcs per additional malloc. After a bit of fooling I have the attached. This does nothing for the very largest examples in the corpus (the ones that cause "regex too complex") --- those were well over the REG_MAX_COMPILE_SPACE limit before and they still are. But all the rest get nicely smaller. The average pg_regcomp memory consumption drops from ~89K to ~48K. regards, tom lane -
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-26T00:16:32Z
I wrote: > However, in a different line of thought, I realized that the > memory allocation logic could use some polishing. It gives out > ten arcs per NFA state initially, and then adds ten more at a time. > However, that's not very bright when you look at the actual usage > patterns, because most states have only one or two out-arcs, > but some have lots and lots. Hold the phone ... after a bit I started to wonder why Spencer made arc allocation be per-state at all, rather than using one big pool of arcs. Maybe there's some locality-of-reference argument to be made for that, but I doubt he was worrying about that back in the 90s. Besides, the regex compiler spends a lot of time iterating over in-chains and color-chains, not just out-chains; it's hard to see why trying to privilege the latter case would help much. What I suspect, based on this old comment in regguts.h: * Having a "from" pointer within each arc may seem redundant, but it * saves a lot of hassle. is that Henry did it like this initially to save having a "from" pointer in each arc, and never re-thought the allocation mechanism after he gave up on that idea. So I rearranged things to allocate arcs out of a common pool, and for good measure made the state allocation code do the same thing. I was pretty much blown away by the results: not only is the average-case space usage about half what it is on HEAD, but the worst-case drops by well more than a factor of ten. I'd previously found, by raising REG_MAX_COMPILE_SPACE, that the regexes in the second corpus that trigger "regex too complex" errors all need 300 to 360 MB to compile with our HEAD code. With the new patch attached, they compile successfully in a dozen or so MB. (Yesterday's patch really did nothing at all for these worst-case regexes, BTW.) I also see about a 10% speedup overall, which I'm pretty sure is down to needing fewer interactions with malloc() (this is partially a function of having batched the state allocations, of course). So even if there is a locality-of-reference loss, it's swamped by fewer mallocs and less total space used. regards, tom lane
-
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-26T03:51:47Z
I wrote: > So I rearranged things to allocate arcs out of a common pool, and for > good measure made the state allocation code do the same thing. I was > pretty much blown away by the results: not only is the average-case > space usage about half what it is on HEAD, but the worst-case drops > by well more than a factor of ten. BTW, I was initially a bit baffled by how this could be. Per previous measurements, the average number of arcs per state is around 4; so if the code is allocating ten arcs for each state right off the bat, it's pretty clear how we could have a factor-of-two-or-so bloat problem. And I think that does explain the average-case results. But it can't possibly explain bloats of more than 10x. After further study I think this is what explains it: * The "average number of arcs" is pretty misleading, because in a large NFA some of the states have hundreds of out-arcs, while most have only a couple. * The NFA is not static; the code moves arcs around all the time. There's actually a function (moveouts) that deletes all the out-arcs of a state and creates images of them on another state. That operation can be invoked a lot of times during NFA optimization. * Once a given state has acquired N out-arcs, it keeps that pool of arc storage, even if some or all of those arcs get deleted. Indeed, the state itself could be dropped and later recycled, but it still keeps its arc pool. Unfortunately, even if it does get recycled for re-use, it's likely to be resurrected as a state with only a couple of out-arcs. So I think the explanation for 20x or 30x bloat arises from the optimize pass resulting in having a bunch of states that have large but largely unused arc pools. Getting rid of the per-state arc pools in favor of one common pool fixes that nicely. I realized while looking at this that some cycles could be shaved from moveouts, because there's no longer a reason why it can't just scribble on the arcs in-place (cf. now-obsolete comment on changearctarget()). It's late but I'll see about improving that tomorrow. regards, tom lane
-
Re: Some regular-expression performance hacking
Joel Jacobson <joel@compiler.org> — 2021-02-26T16:42:32Z
Hi, On Fri, Feb 26, 2021, at 01:16, Tom Lane wrote: > 0007-smarter-regex-allocation-2.patch I've successfully tested this patch. I had to re-create the performance_test table since some cases the previously didn't give an error, now gives error "invalid regular expression: invalid character range". This is expected and of course an improvement, but just wanted to explain why the number of rows don't match the previous test runs. CREATE TABLE performance_test AS SELECT subjects.subject, patterns.pattern, patterns.flags, tests.is_match, tests.captured FROM tests JOIN subjects ON subjects.subject_id = tests.subject_id JOIN patterns ON patterns.pattern_id = subjects.pattern_id WHERE tests.error IS NULL -- -- the below part is added to ignore cases -- that now results in error: -- AND NOT EXISTS ( SELECT 1 FROM deviations WHERE deviations.test_id = tests.test_id AND deviations.error IS NOT NULL ); SELECT 3253889 Comparing 13.2 with HEAD, not a single test resulted in a different is_match value, i.e. the test just using the ~ regex operator, to only check if it matches or not. Good. SELECT COUNT(*) FROM deviations JOIN tests ON tests.test_id = deviations.test_id WHERE tests.is_match <> deviations.is_match count ------- 0 (1 row) The below query shows a frequency count per error message: SELECT error, COUNT(*) FROM deviations GROUP BY 1 ORDER BY 2 DESC error | count -----------------------------------------------------+-------- | 106173 regexp_match() does not support the "global" option | 5799 invalid regular expression: invalid character range | 1060 invalid regular expression option: "y" | 277 (4 rows) As we can see, 106173 cases now goes through without an error, that previously gave an error. This is thanks to now allowing escape sequences within bracket expressions. The other errors are expected and all good. End of correctness analysis. Now let's look at performance! I reran the same query three times to get a feeling for the stddev. \timing SELECT is_match <> (subject ~ pattern), captured IS DISTINCT FROM regexp_match(subject, pattern, flags), COUNT(*) FROM performance_test GROUP BY 1,2 ORDER BY 1,2; ?column? | ?column? | count ----------+----------+--------- f | f | 3253889 (1 row) HEAD (b3a9e9897ec702d56602b26a8cdc0950f23b29dc) Time: 125938.747 ms (02:05.939) Time: 125414.792 ms (02:05.415) Time: 126185.496 ms (02:06.185) HEAD (b3a9e9897ec702d56602b26a8cdc0950f23b29dc)+0007-smarter-regex-allocation-2.patch ?column? | ?column? | count ----------+----------+--------- f | f | 3253889 (1 row) Time: 89145.030 ms (01:29.145) Time: 89083.210 ms (01:29.083) Time: 89166.442 ms (01:29.166) That's a 29% speed-up compared to HEAD! Truly amazing. Let's have a look at the total speed-up compared to PostgreSQL 13. In my previous benchmarks testing against old versions, I used precompiled binaries, but this time I compiled REL_13_STABLE: Time: 483390.132 ms (08:03.390) That's a 82% speed-up in total! Amazing! /Joel -
Re: Some regular-expression performance hacking
Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-26T18:55:10Z
"Joel Jacobson" <joel@compiler.org> writes: > On Fri, Feb 26, 2021, at 01:16, Tom Lane wrote: >> 0007-smarter-regex-allocation-2.patch > I've successfully tested this patch. Cool, thanks for testing! > That's a 29% speed-up compared to HEAD! Truly amazing. Hmm, I'm still only seeing about 10% or a little better. I wonder why the difference in your numbers. Either way, though, I'll take it, since the main point here is to cut memory consumption and not so much cycles. regards, tom lane
-
Re: Some regular-expression performance hacking
Joel Jacobson <joel@compiler.org> — 2021-03-06T05:03:30Z
On Fri, Feb 26, 2021, at 19:55, Tom Lane wrote: > "Joel Jacobson" <joel@compiler.org> writes: > > On Fri, Feb 26, 2021, at 01:16, Tom Lane wrote: > >> 0007-smarter-regex-allocation-2.patch > > > I've successfully tested this patch. > > Cool, thanks for testing! I thought it would be interesting to see if any differences in *where* matches occur not only *what* matches. I've compared the output from regexp_positions() between REL_13_STABLE and HEAD. I'm happy to report no differences were found, except some new expected invalid regular expression: invalid character range errors due to the fixes. This time I also ran into the (["'`])(?:\\\1|.)*?\1 pattern due to using the flags, which caused a timeout on REL_13_STABLE, but the same pattern is fast on HEAD. All good. /Joel -
Re: Some regular-expression performance hacking
Noah Misch <noah@leadboat.com> — 2021-03-06T18:09:25Z
On Sat, Feb 13, 2021 at 06:19:34PM +0100, Joel Jacobson wrote: > To test the correctness of the patches, > I thought it would be nice with some real-life regexes, > and just as important, some real-life text strings, > to which the real-life regexes are applied to. > > I therefore patched Chromium's v8 regexes engine, > to log the actual regexes that get compiled when > visiting websites, and also the text strings that > are the regexes are applied to during run-time > when the regexes are executed. > > I logged the regex and text strings as base64 encoded > strings to STDOUT, to make it easy to grep out the data, > so it could be imported into PostgreSQL for analytics. > > In total, I scraped the first-page of some ~50k websites, > which produced 45M test rows to import, > which when GROUP BY pattern and flags was reduced > down to 235k different regex patterns, > and 1.5M different text string subjects. It's great to see this kind of testing. Thanks for doing it.