patchgrep - Patches: patch #4288, grep -i: Use of faster Boyer-Moore...

 
 

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

patch #4288: grep -i: Use of faster Boyer-Moore instead of commentz-walter algorithm for single key word

Submitter:  Johannes T. Prinz <purple>
Submitted:  Tue 09 Aug 2005 10:23:12 AM UTC
   
 
Category:  None Priority:  5 - Normal
Status:  Ready For Test Privacy:  Public
Assigned to:  None Open/Closed:  Open

Mon 08 Mar 2010 05:19:17 PM UTC, comment #2: 

I don't understand the patch to say the least :-) and "LANG=C grep -i" is not very common; however it definitely looks worthwhile.  Do you have any performance numbers?

Paolo Bonzini <bonzini>
Wed 10 Aug 2005 02:18:47 PM UTC, comment #1: 

patch in diff -Naurp format

Johannes T. Prinz <purple>
Tue 09 Aug 2005 10:23:12 AM UTC, original submission:  

In case of of a single key word combined with an ignore-case match grep uses the commentz-walter algorithm.

The patch modifies the faster Boyer-Moore algo so that it can and will be used instead. For a single character string still commentz-walter is used since bmexec() then uses memchr(), something that will not do with a trans table.

In case of multibyte strings available a modification of bmexec() would not be necessary: All characters are normalized to lower case in search.c anyway. But for the sake of generality and the "mind your own business"-philosophy the change to kwset.c are necessary.

Something to be considered for the future:
Should a normalization still take place in search.c (each character has to be modified!)? Or should the trans-table be used (will that always work with multibyte strings?)?

Johannes T. Prinz <purple>

 

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

Attached Files
file #9219:  kwset.bmicase.patch added by purple (2KiB - application/octet-stream)
file #9212:  kwset.diff added by purple (750B - application/octet-stream)

 

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)
  •  

    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
    2010-03-08 bonzini StatusNone Ready For Test
    2005-08-10 purple Attached File- Added kwset.bmicase.patch, #4999
    2005-08-09 purple Attached File- Added kwset.diff, #4992
        Carbon-Copy- Added -email is unavailable-

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code