buggrep - Bugs: bug #23354, insert speedup patch

 
 

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

bug #23354: insert speedup patch

Submitted by:  Johan Walles <walles>
Submitted on:  Sun 25 May 2008 10:38:08 AM UTC  
 
Category: NoneSeverity: 3 - Normal
Item Group: NoneStatus: Fixed
Privacy: PublicAssigned to: None
Open/Closed: Closed

Wed 23 Dec 2009 04:31:35 PM UTC, comment #1:

Patch applied.

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>
Sun 25 May 2008 10:38:08 AM UTC, original submission:

The insert() method in dfa.c is really hot. As a benchmark I have used running logcheck on my system, with all logcheck status files removed. This means logcheck will grep through all log files on the system.

Using that benchmark with grep 2.5.3 + calloc + int->char speedups for epsclosure() as a baseline:

baseline: over 11 minutes. 87% of all time is spent in insert()
attached insert(): 5m15s. 55% of all time spent in insert()

What should really be done is to turn the array-based sets into binary trees, but until somebody does that, the attached insert() function helps quite a bit.

I also tried using memmove() rather than the loop for moving things around in the array, but that turned out to be slower (9m14s) than just using the loop(!).

Looping backwards earned me a few percent, but that could be a measurement error. Doesn't hurt though.

The attached function replaces insert() in dfa.c.

Johan Walles <walles>

 

Attached Files
file #15767:  insert2-into-dfa.c added by walles (1KiB - text/x-csrc - Minor cleanups to the last version)
file #15729:  insert-into-dfa.c added by walles (1KiB - text/x-csrc)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by bonzini (Posted a comment)
  • -unavailable- added by walles (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 4 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Wed 23 Dec 2009 04:31:35 PM UTCbonziniStatusNone=>Fixed
      Open/ClosedOpen=>Closed
    Thu 29 May 2008 07:19:10 PM UTCwallesAttached File-=>Added insert2-into-dfa.c, #15767
    Sun 25 May 2008 10:38:08 AM UTCwallesAttached File-=>Added insert-into-dfa.c, #15729

    Back to the top


    Powered by Savane 3.1-cleanup1