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


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

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

Submitter:  Norihirio Tanaka <noritnk>
Submitted:  Mon 24 Aug 2009 01:49:38 AM UTC
Category:  None Priority:  5 - Normal
Status:  In Progress Privacy:  Public
Assigned to:  None Open/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

   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.

    Replace regex.h with the one of the system.

Norihirio Tanaka <noritnk>


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

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


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

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

    Date Changed by Updated Field Previous Value => Replaced by
    2010-03-08 bonzini StatusNone In Progress
    2009-08-24 noritnk Attached 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.13-04b1.
    Corresponding source code