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

 
 

bug #57064: Severe slowdown of regexp matching

Submitted by:  A.R. Burgers <arb>
Submitted on:  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

Add a New Comment (Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

( 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>
Project Member
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>
Project 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>
Project Member
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>
Project Member
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>
Project 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>
Project 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>
Project Member
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>
Project 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>
Project Member
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>
Project Member
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)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only project 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 => 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.5