[bug #23354] insert speedup patch

[Johan Walles]

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

                 Summary: insert speedup patch
                 Project: grep
            Submitted by: walles
            Submitted on: söndag 2008-05-25 den 12:38
                Category: None
                Severity: 3 - Normal
              Item Group: None
                  Status: None
                 Privacy: Public
             Assigned to: None
             Open/Closed: Open
         Discussion Lock: Any

    _______________________________________________________

Details:

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.




    _______________________________________________________

File Attachments:


-------------------------------------------------------
Date: söndag 2008-05-25 den 12:38  Name: insert-into-dfa.c  Size: 1 kB   By:
walles

<http://savannah.gnu.org/bugs/download.php?file_id=15729>

    _______________________________________________________

Reply to this item at:

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

_______________________________________________
  Meddelandet skickades via/av Savannah
  http://savannah.gnu.org/