[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[bug #23354] insert speedup patch

From: Johan Walles
Subject: [bug #23354] insert speedup patch
Date: Sun, 25 May 2008 10:38:09 +0000
User-agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv: Gecko/20080313 Iceape/1.1.9 (Debian-1.1.9-3)


                 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



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

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:



Reply to this item at:


  Meddelandet skickades via/av Savannah

reply via email to

[Prev in Thread] Current Thread [Next in Thread]