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

Submitter:  Johan Walles <walles>
Submitted:  Sun 25 May 2008 10:38:08 AM UTC
   
 
Category:  None Severity:  3 - Normal
Item Group:  None Status:  Fixed
Privacy:  Public Assigned 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>

 

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

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

    Date Changed by Updated Field Previous Value => Replaced by
    2009-12-23 bonzini StatusNone Fixed
        Open/ClosedOpen Closed
    2008-05-29 walles Attached File- Added insert2-into-dfa.c, #15767
    2008-05-25 walles Attached File- Added insert-into-dfa.c, #15729

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code