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: NonePriority: 5 - Normal
Status: Ready For TestPrivacy: Public
Assigned to: NoneOpen/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
  • -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 08 Mar 2010 05:19:17 PM UTCbonziniStatusNone=>Ready For Test
    Wed 10 Aug 2005 02:18:47 PM UTCpurpleAttached File-=>Added kwset.bmicase.patch, #4999
    Tue 09 Aug 2005 10:23:12 AM UTCpurpleAttached File-=>Added kwset.diff, #4992
      Carbon-Copy-=>Added -unavailable-

    Back to the top

    Powered by Savane 3.1-cleanup1