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

Submitted by:  Johannes T. Prinz <purple>
Submitted on:  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>


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)

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.




    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

    Back to the top

    Powered by Savane 3.5