bugGNU Octave - Bugs: bug #57064, Severe slowdown of regexp matching

 
 

bug #57064: Severe slowdown of regexp matching

Submitter:  A.R. Burgers <arb>
Submitted:  Wed 16 Oct 2019 03:28:52 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Regression
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * dev Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Fri 18 Oct 2019 04:54:54 PM UTC, comment #14: 

Thank you both for testing. I pushed the patch here:
http://hg.savannah.gnu.org/hgweb/octave/rev/19ad9150dd69

Closing as fixed.

Markus Mützel <mmuetzel>
Group administrator
Fri 18 Oct 2019 07:47:45 AM UTC, comment #13: 

the patch fixes the issue for me as well.

A.R. Burgers <arb>
Thu 17 Oct 2019 09:55:58 PM UTC, comment #12: 

I tested the patch on another machine and tst.m execution went from 64s down to 0.4s.

Pantxo Diribarne <pantxo>
Group Member
Thu 17 Oct 2019 06:17:03 PM UTC, comment #11: 

With the attached patch, the test case from comment #0 comes back to executing in a few 100 ms on my system.
Thanks again for the diff, Pantxo.

After applying the patch, the bootstrap script must be executed.

(file #47707)

Markus Mützel <mmuetzel>
Group administrator
Thu 17 Oct 2019 02:33:34 PM UTC, comment #10: 

AFAICT, strmblen calculates the number of bytes used for encoding the character starting at position c.
But u8_check [1] looks promising and doesn't seem to be very costly.

[1]: https://www.gnu.org/software/gnulib/MODULES.html#module=unistr/u8-check

Markus Mützel <mmuetzel>
Group administrator
Thu 17 Oct 2019 01:56:16 PM UTC, comment #9: 

@Markus: As for checking the utf8 validity you are much more knowledgeable that me in this area. Couldn't we just check each character in the string passes the test  "(mblen = octave_u8_strmblen_wrapper (c)) > 0"?

Pantxo Diribarne <pantxo>
Group Member
Thu 17 Oct 2019 01:47:31 PM UTC, comment #8: 

AFAICS in [1] the option only prevents the input string (the "subject") from being checked for UTF8 validy.

[1] http://pcre.org/original/doc/html/pcre_exec.html

Pantxo Diribarne <pantxo>
Group Member
Thu 17 Oct 2019 01:36:43 PM UTC, comment #7: 

@Pantxo: Nice find. There is probably a gnulib function that we can use to determine if the string is valid UTF-8. Hopefully this check would perform faster.
Do we have to check both the input string and the pattern?

Markus Mützel <mmuetzel>
Group administrator
Thu 17 Oct 2019 01:21:54 PM UTC, comment #6: 

After earching for "pcre utf8 slow" I've read that if the string can be safely assumed to be utf8, then one can by-pass a time consuming check using the PCRE_NO_UTF8_CHECK option. With this option tst.m returns in 1 s while it takes 51 s without it.

I used the following diff:


diff -r 25479159213b liboctave/util/lo-regexp.cc
--- a/liboctave/util/lo-regexp.cc        Wed Oct 16 14:35:03 2019 -0700
+++ b/liboctave/util/lo-regexp.cc        Thu Oct 17 15:19:09 2019 +0200
@@ -280,7 +280,7 @@

         int matches = pcre_exec (re, nullptr, buffer.c_str (),
                                  buffer.length (), idx,
-                                 (idx ? PCRE_NOTBOL : 0),
+                                 PCRE_NO_UTF8_CHECK | (idx ? PCRE_NOTBOL : 0),
                                  ovector, (subpatterns+1)*3);

         if (matches == PCRE_ERROR_MATCHLIMIT)
@@ -307,7 +307,8 @@
                 pe.match_limit *= 10;
                 matches = pcre_exec (re, &pe, buffer.c_str (),
                                      buffer.length (), idx,
-                                     (idx ? PCRE_NOTBOL : 0),
+                                     PCRE_NO_UTF8_CHECK
+                                     | (idx ? PCRE_NOTBOL : 0),
                                      ovector, (subpatterns+1)*3);
               }
           }


Updating the title, item group and status

Pantxo Diribarne <pantxo>
Group Member
Wed 16 Oct 2019 07:17:55 PM UTC, comment #5: 

I don't know if this massive slowdown is to be expected or if this is an error in PCRE or how we are using it.

As it stands I am tempted to revert the change for bug #35910 and just document in regexp that the UTF-8 mode can be used by manually prepending (*UTF8) to the pattern.

Markus Mützel <mmuetzel>
Group administrator
Wed 16 Oct 2019 06:37:26 PM UTC, comment #4: 

Yes, with UTF8 5.1.1 has similar slowdowns


ver = 5.1.1
hg_id = eeb2275424bc+
numel_rawdata =  1872837
prepend (*UTF8) ...
Elapsed time is 158.902 seconds.


A.R. Burgers <arb>
Wed 16 Oct 2019 06:21:00 PM UTC, comment #3: 

This might be related to the changes for bug #35910. Particularly, this changeset:
http://hg.savannah.gnu.org/hgweb/octave/rev/94d490815aa8

Is 5.1.1 slow if you prepend "(*UTF8)" to the pattern?

load('rawdata.mat');
val = regexp (rawdata, '(*UTF8)<c r="(\w+)"(?:[^t>]*(>)|(?:[^t>]*t="(\w+)")>)(?:<f.+?(?:</f>|/>))?(?:<v(?:[^>]*)>([^<]*)</v>|<is><t>([^<]*)</t></is>|<v/>([^<]*))', "tokens");



Markus Mützel <mmuetzel>
Group administrator
Wed 16 Oct 2019 05:31:40 PM UTC, comment #2: 

Indeed it terminates, but takes quite a bit longer in my case


ver = 5.1.1
hg_id = eeb2275424bc+
Elapsed 0.428855

ver = 6.0.0
hg_id = 9d3c895cbe38+
Elapsed 158.762


A.R. Burgers <arb>
Wed 16 Oct 2019 04:31:51 PM UTC, comment #1: 

it took a while on my old Xeon computer, but it has finished OK.



octave:3> tic; tst; toc
Elapsed time is 83.1461 seconds.
octave:4> who
Variables visible from the current scope:

ans      rawdata  val

octave:5> whos rawdata
Variables visible from the current scope:

variables in scope: top scope

   Attr Name         Size                     Bytes  Class
   ==== ====         ====                     =====  =====
        rawdata      1x1872837              1872837  char

Total is 1872837 elements using 1872837 bytes


Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Wed 16 Oct 2019 03:28:52 PM UTC, original submission:  

octave dev (stable won't) will hang in this regexp invocation (attached as script tst.m)


load('rawdata.mat');
val = regexp (rawdata, '<c r="(\w+)"(?:[^t>]*(>)|(?:[^t>]*t="(\w+)")>)(?:<f.+?(?:</f>|/>))?(?:<v(?:[^>]*)>([^<]*)</v>|<is><t>([^<]*)</t></is>|<v/>([^<]*))', "tokens");


the regular expression comes from the _OCT_xlsx2oct_.m function from the IO package around line 100.

I also attach rawdata.mat. I have not been able yet to reproduce this with a smaller example.

A.R. Burgers <arb>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #47707:  bug57064_regexp_u8_check.patch added by mmuetzel (4KiB - application/octet-stream)
file #47698:  tst.m added by arb (190B - text/plain)
file #47699:  rawdata.mat added by arb (271KiB - application/octet-stream)

 

Digest:
   bug dependencies.

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by pantxo (Posted a comment)
  • -email is unavailable- added by mmuetzel (Posted a comment)
  • -email is unavailable- added by dasergatskov (Posted a comment)
  • -email is unavailable- added by arb (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 11 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2019-10-18 mmuetzel StatusPatch Reviewed Fixed
        Open/ClosedOpen Closed
    2019-10-17 pantxo StatusPatch Submitted Patch Reviewed
    2019-10-17 mmuetzel Attached File- Added bug57064_regexp_u8_check.patch, #47707
        StatusConfirmed Patch Submitted
    2019-10-17 pantxo Item GroupUnexpected Error or Warning Regression
        StatusNone Confirmed
        Summaryregexp hangs in infinite loop Severe slowdown of regexp matching
    2019-10-16 mmuetzel Dependencies- Depends on bugs #35910
    2019-10-16 arb Attached File- Added tst.m, #47698
        Attached File- Added rawdata.mat, #47699

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code