patchgrep - Patches: patch #6899, Speed-up for searching in...

 
 

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

patch #6899: Speed-up for searching in multibyte and ignore-icase.

Submitted by:  Norihirio Tanaka <noritnk>
Submitted on:  Mon 24 Aug 2009 01:49:38 AM UTC  
 
Category: NonePriority: 5 - Normal
Status: In ProgressPrivacy: Public
Assigned to: NoneOpen/Closed: Open

Mon 08 Mar 2010 06:22:01 PM UTC, comment #1:

misc is good and should be applied.

Regarding kwsmb, I haven't read it carefully but it seems very good too.

The mb-speedup patch posted in the bugs failed tests for me, and I haven't tested this one. It overlaps with a patch I have that does more or less the same things. Unlike my patch (still unposted) it handles mbstate_t correctly; on the other hand, my patch fixes some existing bugs that are left there by Norihirio's patch.

The dfa-speedup patch is quite a revolution :-) but it is worth considering. It also has some overlap with the patches I hav, which hopefully means that both my patches and Norihirio's make sense! Especially now that there is a good DFA-based matcher in glibc, getting rid of the complication of MBCSET can be a good idea: when the match doesn't hit that path, dfa.c can be very very fast. Doing so for "." as well is also "interesting"! :-) At least for UTF-8 I believe we can get good advantages by expanding the "." to charclasses instead.

Paolo Bonzini <bonzini>
Mon 24 Aug 2009 01:49:38 AM UTC, original submission:

Kwset is an excellent algorithm that selectively uses Boyer-Moore and
Commentz-Walter algorithm. However, it is necessary to convert the
capital-letter into the small-letter of a text before searching in
ignore-icase.

Though DFA is also an excellent algorithm, Multi-byte string cannot be
efficiently treated by invalidating it in a lot of Linux distributions.

These patches will enable to search a pattern in a text efficiently,
without converting the text from the capital-letter into the small-letter,
by using not searching but matching in multibyte and ignore-icase.

Patched grep will be faster than in the Linux distribution in a lot
of cases.

Fixed bugs :

- Bug #387704: grep: -i breaks W in some locales (perhaps UTF-8 locale

krown issue:

- Included regex has no RE_ICASE. It means new regex is needed,
following issue is reproduced.

http://lists.gnu.org/archive/html/bug-grep/2009-05/msg00009.html

Replace regex.h with the one of the system.

Norihirio Tanaka <noritnk>

 

Attached Files
file #18629:  grep-2.5.4.kwsmb.patch added by noritnk (19kB - text/x-diff)
file #18631:  grep-2.5.4.misc.patch added by noritnk (2kB - text/x-diff)

 

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)
  • -unavailable- added by noritnk (Submitted the item)
  •  

    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 5 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Mon 08 Mar 2010 06:22:01 PM UTCbonziniStatusNone=>In Progress
    Mon 24 Aug 2009 01:49:38 AM UTCnoritnkAttached File-=>Added grep-2.5.4.misc.patch, #18631
      Attached File-=>Added grep-2.5.4.dfa-speedup.patch, #18630
      Attached File-=>Added grep-2.5.4.mb-speedup.patch, #18628
      Attached File-=>Added grep-2.5.4.kwsmb.patch, #18629

    Back to the top


    Powered by Savane 3.1-cleanup