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

Submitted by:  Paolo Bonzini <bonzini>
Submitted on:  Mon 08 Mar 2010 08:51:05 AM UTC  
 
Category: NoneSeverity: 4 - Important
Item Group: NoneStatus: Fixed
Privacy: PublicAssigned 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>

 

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by bonzini (Submitted the item)
  •  

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

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 2 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Tue 16 Mar 2010 02:39:18 PM UTCbonziniStatusNone=>Fixed
      Open/ClosedOpen=>Closed

    Back to the top


    Powered by Savane 3.1-cleanup1