buggrep - Bugs: bug #29117, extreme slowness: dfa.c should...

 
 

You are not allowed to post comments on this tracker with your current authentication level.

bug #29117: extreme slowness: dfa.c should provide a callback-on-match interface

Submitter:  Paolo Bonzini <bonzini>
Submitted:  Mon 08 Mar 2010 08:51:05 AM UTC
   
 
Category:  None Severity:  4 - Important
Item Group:  None Status:  Fixed
Privacy:  Public Assigned to:  None
Open/Closed:  Closed

Tue 16 Mar 2010 02:39:18 PM UTC, comment #2: 

Thank you for the bug report. This bug has been fixed in the
development sources, which can be downloaded using git from
git://git.sv.gnu.org/grep.git

Paolo Bonzini <bonzini>
Mon 08 Mar 2010 01:15:04 PM UTC, comment #1: 

See also bug #14472, involving the same kind of slowness but in check_multibyte_string.

Paolo Bonzini <bonzini>
Mon 08 Mar 2010 08:51:05 AM UTC, original submission:  

dfaexec is being called on a full (~32k) buffer every time.  However, dfaexec performs multibyte->wide char conversion of the entire buffer every time, which is very expensive and leads to several thousand more mbrtowc calls than would be necessary.

In this gdb session, consider that mbrtowc is called every time "size" times:

Breakpoint 1, dfaexec (d=0x628800,
    begin=0x62b04c ..., size=32678, backref=0x7fffffffdddc) at ../../src/dfa.c:2792
2792 {
(gdb)
Continuing.

Breakpoint 1, dfaexec (d=0x628800,
    begin=0x62b0d1 ..., size=32545, backref=0x7fffffffdddc) at ../../src/dfa.c:2792
2792 {
(gdb)
Continuing.

Breakpoint 1, dfaexec (d=0x628800,
    begin=0x62b11b ..., size=32471, backref=0x7fffffffdddc) at ../../src/dfa.c:2792
2792 {
(gdb)
Continuing.

Breakpoint 1, dfaexec (d=0x628800,
    begin=0x62b16d ..., size=32389, backref=0x7fffffffdddc) at ../../src/dfa.c:2792
2792 {
(gdb)
Continuing.

Breakpoint 1, dfaexec (d=0x628800,
    begin=0x62b1ac ..., size=32326, backref=0x7fffffffdddc) at ../../src/dfa.c:2792
2792 {
(gdb)
Continuing.

Breakpoint 1, dfaexec (d=0x628800,
    begin=0x62b203 ..., size=32239, backref=0x7fffffffdddc) at ../../src/dfa.c:2792
2792 {
(gdb)

If a callback interface was provided, this additional cost could be eliminated.  dfaexec could easily be implemented on top of this new interface.

Paolo Bonzini <bonzini>

 

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

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by bonzini (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.

     

    Follow 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2010-03-16 bonzini StatusNone Fixed
        Open/ClosedOpen Closed

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code