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

[Paolo Bonzini]

URL:
  <http://savannah.gnu.org/bugs/?29117>

                 Summary: extreme slowness: dfa.c should provide a
callback-on-match interface
                 Project: grep
            Submitted by: bonzini
            Submitted on: Mon 08 Mar 2010 09:51:05 AM CET
                Category: None
                Severity: 4 - Important
              Item Group: None
                  Status: None
                 Privacy: Public
             Assigned to: None
             Open/Closed: Open
         Discussion Lock: Any

    _______________________________________________________

Details:

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.




    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?29117>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/