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

 
 

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

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

Submitted by:  Johannes T. Prinz <purple>
Submitted on:  Tue Aug 9 10:23:12 2005  
 
Category: NonePriority: 5 - Normal
Status: Ready For TestPrivacy: Public
Assigned to: NoneOpen/Closed: Open

Mon Mar 8 17:19:17 2010, 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 Aug 10 14:18:47 2005, comment #1:

patch in diff -Naurp format

Johannes T. Prinz <purple>
Tue Aug 9 10:23:12 2005, 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>

 

Attached Files
file #9219:  kwset.bmicase.patch added by purple (2kB - 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
  • -unavailable- added by bonzini (Posted a comment)
  •  

    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
    Mon Mar 8 17:19:17 2010bonziniStatusNone=>Ready For Test
    Wed Aug 10 14:18:47 2005purpleAttached File-=>Added kwset.bmicase.patch, #4999
    Tue Aug 9 10:23:12 2005purpleAttached File-=>Added kwset.diff, #4992
      Carbon-Copy-=>Added -unavailable-

    Back to the top


    Powered by Savane 3.1-cleanup