Bug #7906 “grep is extremely slow with UTF-8” : Bugs : grep package : Ubuntu

Revision history for this message

In Debian Bug tracker #181378, Michel Daenzer (daenzer) wrote on 2003-08-11: Depends on locale

#1

Package: grep
Version: 2.5.1-5
Followup-For: Bug #181378

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I experienced the same problem, but I just noticed that grep is fast
when the LC_ALL environment variable is set to C. Here's the output of
locale on my system:

LANG=en_US.UTF-8
LC_CTYPE="en_US.UTF-8"
LC_NUMERIC="en_US.UTF-8"
LC_TIME="en_US.UTF-8"
LC_COLLATE=C
LC_MONETARY="en_US.UTF-8"
LC_MESSAGES=en_US.UTF-8
LC_PAPER="en_US.UTF-8"
LC_NAME="en_US.UTF-8"
LC_ADDRESS="en_US.UTF-8"
LC_TELEPHONE="en_US.UTF-8"
LC_MEASUREMENT="en_US.UTF-8"
LC_IDENTIFICATION="en_US.UTF-8"
LC_ALL=

Seems like grep handles character encoding conversions inefficiently or
something?

- -- System Information:
Debian Release: testing/unstable
Architecture: powerpc
Kernel: Linux thor 2.4.20-ben8-xfs-lolat #18 Wed Aug 6 10:56:56 CEST 2003 ppc
Locale: LANG=en_US.UTF-8, LC_CTYPE=en_US.UTF-8

Versions of packages grep depends on:
ii libc6 2.3.1-16 GNU C Library: Shared libraries an

- -- no debconf information

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)

iD8DBQE/N62aWoGvjmrbsgARArZVAJ4iVqUDptDeldcvNgA2DlWmoOuXnwCffIQ5
n9TZeES03gReAsL5IkS9ock=
=KnnW
-----END PGP SIGNATURE-----

Revision history for this message

In Debian Bug tracker #181378, H. S. Teoh (hsteoh-quickfur) wrote on 2003-09-04: Identical bugs

#2

merge 181378 206470
thanks

These bugs appear to be the same (see latest messages in #181378).

As for the bugs themselves, could it be that the problem is caused by grep
localizing every input character, as opposed to localizing the regex and
then matching the resulting bytes? I haven't looked at the code to be
sure, but this is what immediately came to mind when I read about the
LC_CTYPE=C speed difference.

Translating every input character would, indeed, slow things down a lot. A
better alternative would be to localize the regex, match on a byte-by-byte
basis, and then localize the output only if it matches. However, this may
have pathological problems if multiple representations of the same
character are possible (e.g. Unicode combining diacritics vs. precomposed
characters). I'm not sure what the solution would be in this case.

T

--
If you look at a thing nine hundred and ninety-nine times, you are perfectly
safe; if you look at it the thousandth time, you are in frightful danger of
seeing it for the first time. -- G. K. Chesterton

Revision history for this message

In Debian Bug tracker #181378, jidanni (dan-jacobson) wrote on 2003-10-06:

#3

severity 206470 important

Revision history for this message

In Debian Bug tracker #181378, Michel Daenzer (daenzer) wrote on 2003-12-13: patch

#4

This patch seems to help; I extracted it from the src rpm at

http://download.fedora.redhat.com/pub/fedora/linux/core/updates/1/SRPMS/

and tweaked one hunk for it to apply.

--
Earthling Michel Dänzer | Debian (powerpc), X and DRI developer
Software libre enthusiast | http://svcs.affero.net/rm.php?r=daenzer

Revision history for this message

In Debian Bug tracker #181378, Roland Illig (roland-illig) wrote on 2004-02-18: grep: ... and Perl is a thousand times faster ...

#5

Package: grep
Version: 2.5.1.ds1-2
Severity: normal
Followup-For: Bug #181378

I found the magic frontier of grep: DFAs with 1024 states.

Please make grep a little quicker or replace it completely with pcre or
another fast implementation, as far as POSIX allows it.

$ time egrep .\{1024,\} debug | wc
109 17987 169422

real 1m47.522s
user 1m28.960s
sys 0m3.680s

$ time egrep .\{1023,\} debug | wc
109 17987 169422

real 0m1.074s
user 0m0.940s
sys 0m0.100s

$ time perl -ne '/.{1024,}/ and print' debug | wc
109 17987 169422

real 0m0.077s
user 0m0.070s
sys 0m0.000s

-- System Information:
Debian Release: testing/unstable
Architecture: i386
Kernel: Linux wwid 2.4.22-1-k7 #5 Sat Oct 4 14:11:12 EST 2003 i686
Locale: LANG=de_DE.ISO-8859-15@euro, LC_CTYPE=C (ignored: LC_ALL set to de_DE@euro)

Versions of packages grep depends on:
ii libc6 2.3.2.ds1-11 GNU C Library: Shared libraries an

-- no debconf information

Revision history for this message

In Debian Bug tracker #181378, Peter Moulder (peter-moulder) wrote on 2004-06-29: perl not fair comparison: perl gets "wrong" answer for utf-8 text

#6

Suppose UTF-8 LC_CTYPE.

  $ (echo rôle; echo role) | grep 'r.le'
  rôle
  role
  $ (echo rôle; echo role) | perl -ne '/r.le/ and print'
  role
  $ (echo rôle; echo role) | grep 'r..le'
  $ (echo rôle; echo role) | perl -ne '/r..le/ and print'
  rôle

(This is with perl_5.8.3-3, grep_2.5.1.ds1-2.)

Perl is using octet/byte regexps, whereas grep is using character
regexps. Although arguable, I believe users would prefer grep's
behaviour (other than its speed).

I believe a better solution would be for grep to convert the character
regexp to an octet regexp. E.g. the character regexp "." (which I'll assume
for simplicity matches any character) might be translated to
(?:[\x00-\x7f]|[\xc0-\xf7][\x80-\xbf]*).

That translation assumes that an accented character formed by
composition is to be considered distinct from a single unicode character
(H. S. Teoh's example above). I'm not familiar with the unicode spec.
Maybe it's reasonable to consider them different. Otherwise, I believe
the translate-the-regexp approach is still applicable but requires
longer translations.

However, I wonder if the problem is just that the conversion of the
input stream to wchars is inefficient. Off hand, I don't see why it
should make things so much slower.

pjrm.

Revision history for this message

In Debian Bug tracker #181378, Peter Moulder (peter-moulder) wrote on 2004-06-30: gprof; combining diacritical marks; octet regexp conversion

#7

Download full text (4.0 KiB)

According to gprof on grep compiled with -pg (without installing libc6-prof),
~all the time is spent in check_multibyte_string.

In the case of utf-8, we don't need the return value of
check_multibyte_string: bytes other than the initial byte of utf-8
characters (ignoring the composition case) have (c & 0xc0) == 0x80 (i.e. bit7=1, bit6=0).
To handle the composition case, we add a test that the wide character
is a combining diacritical: "|| (c == 0xcc) || ((c == 0xcd) && (nextchar
<= 0xaf))".

Combining diacritical marks are a hassle for grep. According to
http://en.wikipedia.org/wiki/Combining_diacritical_mark, a character can
be followed by more than one combining diacritical mark character.
Presumably, order doesn't matter, so grep 'a<string of n combining
diacritical mark characters>' can match n factorial different strings in
the haystack text, without counting use of precomposed characters.
The simplest way of handling this would be to convert to a canonical
form, say decomposed form with combining diacritical marks in sorted
order.

Note that I haven't checked the unicode standards on this point:
possibly order is to be considered significant, in which case the only
possible matches are decomposed vs use of precomposed character. This
would make the convert-to-octet-regexp approach practical (see below).

Another issue with decomposable characters is that we must use negative
lookahead tests: if searching for `o' then we must check that the
matched 'o' isn't followed by a combining diacritical mark character.
The alternative of canonicalizing to precomposed form instead of
decomposed form has its own expense: if there are 112 possible
diacritical mark characters, and characters can be followed by an
arbitrary selection of those, then we need an extra 112 bits per
canonical character to represent those. And even that only presence or
absence (rather than number or order) is significant for combining
diacritical marks, i.e. it assumes that e<macron><acute><acute> is to be
considered equivalent to e<acute><macron>. If number and order are
significant then no finite number of bits suffices.

Note that grep doesn't currently handle combining diacritical marks:

  $ printf 'e\xcc\x80\n'
  è
  $ printf 'e\xcc\x80\n' | grep 'è'
  <nothing>
  $ printf 'e\xcc\x80\n' | grep '^.$'
  <nothing>

More remarks on the idea of converting character regexps to byte regexps
(see previous message).

First, note that it works for UTF-8, but not e.g. GBK, precisely because
in UTF-8 one can't mistake the middle of a character for the beginning
of one. E.g. in GBK, the string for 我我 contains the string for 椅;
there is no way to tell where the character beginnings are short of
something like what grep is already doing.

Is it worth adding special code for UTF-8 (probably sharable with other
UTF encodings) if we still need something like the current code to
handle GBK and other multi-byte encodings? Well, UTF-8 is likely to
become the primary encoding on Debian systems.

The example translation given for "." may discourage from its
complexity. However, we should note that many, perhaps most, common
regexps don't need any translation at all (ignoring chara...

Message-id: <20040630064642.GA1588@bowman.csse.monash.edu.au>
Date: Wed, 30 Jun 2004 16:46:42 +1000
From: Peter Moulder <Peter.Moulder@infotech.monash.edu.au>
To: 181378@bugs.debian.org
Subject: gprof; combining diacritical marks; octet regexp conversion

According to gprof on grep compiled with -pg (without installing libc=
6-prof),
~all the time is spent in check_multibyte_string.

In the case of utf-8, we don't need the return value of
check_multibyte_string: bytes other than the initial byte of utf-8
characters (ignoring the composition case) have (c & 0xc0) =3D=3D 0x8=
0 (i.e. bit7=3D1, bit6=3D0).
To handle the composition case, we add a test that the wide character
is a combining diacritical: "|| (c =3D=3D 0xcc) || ((c =3D=3D 0xcd) &=
& (nextchar
<=3D 0xaf))".

Combining diacritical marks are a hassle for grep.  According to
http://en.wikipedia.org/wiki/Combining_diacritical_mark, a character =
can
be followed by more than one combining diacritical mark character.
Presumably, order doesn't matter, so grep 'a<string of n combining
diacritical mark characters>' can match n factorial different strings=
 in
the haystack text, without counting use of precomposed characters.
The simplest way of handling this would be to convert to a canonical
form, say decomposed form with combining diacritical marks in sorted
order.

Note that I haven't checked the unicode standards on this point:
possibly order is to be considered significant, in which case the onl=
y
possible matches are decomposed vs use of precomposed character.  Thi=
s
would make the convert-to-octet-regexp approach practical (see below)=
.

Another issue with decomposable characters is that we must use negati=
ve
lookahead tests: if searching for `o' then we must check that the
matched 'o' isn't followed by a combining diacritical mark character.
The alternative of canonicalizing to precomposed form instead of
decomposed form has its own expense: if there are 112 possible
diacritical mark characters, and characters can be followed by an
arbitrary selection of those, then we need an extra 112 bits per
canonical character to represent those.  And even that only presence =
or
absence (rather than number or order) is significant for combining
diacritical marks, i.e. it assumes that e<macron><acute><acute> is to=
 be
considered equivalent to e<acute><macron>.  If number and order are
significant then no finite number of bits suffices.

Note that grep doesn't currently handle combining diacritical marks:

$ printf 'e\xcc\x80\n'
  =C3=A8
  $ printf 'e\xcc\x80\n' | grep '=C3=A8'
  <nothing>
  $ printf 'e\xcc\x80\n' | grep '^.$'
  <nothing>

More remarks on the idea of converting character regexps to byte rege=
xps
(see previous message).

First, note that it works for UTF-8, but not e.g. GBK, precisely beca=
use
in UTF-8 one can't mistake the middle of a character for the beginnin=
g
of one.  E.g. in GBK, the string for =E6=88=91=E6=88=91 contains the =
string for =E6=A4=85;
there is no way to tell where the character beginnings are short of
something like what grep is already doing.

Is it worth adding special code for UTF-8 (probably sharable with oth=
er
UTF encodings) if we still need something like the current code to
handle GBK and other multi-byte encodings?  Well, UTF-8 is likely to
become the primary encoding on Debian systems.

The example translation given for "." may discourage from its
complexity.  However, we should note that many, perhaps most, common
regexps don't need any translation at all (ignoring character
composition issues).  E.g. '[abc]a.*b($|\>)' doesn't need any change.
'r=C3=B4*l' needs a minor change of wrapping the multi-byte =C3=B4: '=
r(?:=C3=B4)*l'.
Similarly for character ranges that include multi-byte characters:
'r[io=C3=B4=C3=A9]le' becomes 'r(?:[io]|=C3=B4|=C3=A9)le'.  The fragm=
ent '.+' (extended
regexp) may or may not need change, depending on whether preceding &
following fragments only match whole characters.  E.g. 'a.+b' doesn't
need change, but 'a.+.+b' does need changing.  Whether '[a-z]' needs
changing depends on LC_COLLATE, i.e. it depends whether that range
includes =C3=B4 and so on.  However, in most places where a regexp us=
es
[a-z], one would want to exclude =C3=B4 and so on, so it would be a b=
ug not
to specify LC_COLLATE=3DC.

I've now checked Single Unix Spec for the regexp '.': it matches all
characters other than NUL (and in particular it matches \n, except th=
at
grep should already have split its input into lines excluding \n).

pjrm.

Revision history for this message

Debian Bug Importer (debzilla) wrote on 2004-09-11:

#19

Message-ID: <email address hidden>
Date: Sat, 11 Sep 2004 04:33:28 +0800
From: Dan Jacobson <email address hidden>
To: <email address hidden>
Cc: <email address hidden>, <email address hidden>
Subject: LC_CTYPE makes grep 800 times slower!

reassign 224993 grep
severity 224993 grave
severity 206470 grave
merge 206470 224993
thanks
Somebody on gnu-utils-bug please fix the grep LC_CTYPE bug!
See it http://bugs.debian.org/206470
Often greps that would take just a second have to be killed as the CPU
meter goes to max and minutes go by!
You guys in the western world don't notice it because you don't use
(certain) LC_CTYPEs.

Revision history for this message

Thom May (thombot) wrote on 2004-09-11:

#20

This is an absolutely absurd inflation of severity.

Revision history for this message

Debian Bug Importer (debzilla) wrote on 2004-09-11:

#21

Message-ID: <email address hidden>
Date: Sat, 11 Sep 2004 01:14:59 +0100
From: Colin Watson <email address hidden>
To: <email address hidden>
Subject: not release-critical

severity 181378 important
thanks

--
Colin Watson [<email address hidden>]

Revision history for this message

In Debian Bug tracker #181378, Justin Pryzby (justinpryzby-users) wrote on 2004-12-06: profile

#22

I don't know that I can add useful info here, but this just bit me
too.

$ wc -l /tmp/setuid;
50 /tmp/setuid

$ time ltrace grep -v /dev/ /tmp/setuid 2>&1 |LANG=C grep '^mbrtowc(' |wc -l
77989

  real 0m14.802s
  user 0m6.118s
  sys 0m8.071s

$ calc 50/14.802
~3.37792190244561545737

Justin

Revision history for this message

Debian Bug Importer (debzilla) wrote on 2004-12-06:

#23

Message-ID: <20041206152037.GA23899@andromeda>
Date: Mon, 6 Dec 2004 10:20:37 -0500
From: Justin Pryzby <email address hidden>
To: <email address hidden>
Subject: profile

I don't know that I can add useful info here, but this just bit me
too.

$ wc -l /tmp/setuid;
50 /tmp/setuid

$ time ltrace grep -v /dev/ /tmp/setuid 2>&1 |LANG=C grep '^mbrtowc(' |wc -l
77989

  real 0m14.802s
  user 0m6.118s
  sys 0m8.071s

$ calc 50/14.802
~3.37792190244561545737

Justin

Revision history for this message

In Debian Bug tracker #181378, Simon Law (sfllaw) wrote on 2004-12-08: Red Hat's UTF-8 speedup patch

#24

tags 181378 +patch
thanks

Here is Fedora Core 3's patch to grep that makes it work quickly in
UTF-8 environments.

I haven't tested if it applies cleanly to Debian's grep. But if you
make me a co-maintainer, I'll happily spend a couple of hours merging
this and other useful Red Hat patches into our grep.

Simon

Revision history for this message

Debian Bug Importer (debzilla) wrote on 2004-12-08:

#25

Download full text (19.7 KiB)

Message-ID: <email address hidden>
Date: Wed, 8 Dec 2004 16:29:56 -0500
From: Simon Law <email address hidden>
To: <email address hidden>
Subject: Red Hat's UTF-8 speedup patch

--mP3DRpeJDSE+ciuQ
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

tags 181378 +patch
thanks

Here is Fedora Core 3's patch to grep that makes it work quickly in
UTF-8 environments.

I haven't tested if it applies cleanly to Debian's grep. But if you
make me a co-maintainer, I'll happily spend a couple of hours merging
this and other useful Red Hat patches into our grep.

Simon

--mP3DRpeJDSE+ciuQ
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="grep-2.5.1-gofast.patch"

This patch is written by Tim Waugh <email address hidden> and is ripped
from Fedora Core 3's grep 2.5.1-31 package.

It is meant to cache results from mbrtowc(), which significantly speeds
up execution speed in UTF-8 locales.

-- Simon Law <email address hidden> Wed, 8 Dec 2004 16:28:03 -0500

--- grep-2.5.1/src/grep.c.gofast 2004-02-26 13:17:39.000000000 +0000
+++ grep-2.5.1/src/grep.c 2004-02-26 13:17:39.000000000 +0000
@@ -186,7 +186,8 @@

/* Functions we'll use to search. */
static void (*compile) PARAMS ((char const *, size_t));
-static size_t (*execute) PARAMS ((char const *, size_t, size_t *, int));
+static size_t (*execute) PARAMS ((char const *, size_t, struct mb_cache *,
+ size_t *, int));

/* Like error, but suppress the diagnostic if requested. */
static void
@@ -516,7 +517,7 @@
}

static void
-prline (char const *beg, char const *lim, int sep)
+prline (char const *beg, char const *lim, int sep, struct mb_cache *mb_cache)
{
   if (out_file)
     printf ("%s%c", filename, sep & filename_mask);
@@ -539,7 +540,8 @@
     {
       size_t match_size;
       size_t match_offset;
- while ((match_offset = (*execute) (beg, lim - beg, &match_size, 1))
+ while ((match_offset = (*execute) (beg, lim - beg, mb_cache,
+ &match_size, 1))
    != (size_t) -1)
         {
    char const *b = beg + match_offset;
@@ -573,7 +575,8 @@
    int i;
    for (i = 0; i < lim - beg; i++)
      ibeg[i] = tolower (beg[i]);
- while ((match_offset = (*execute) (ibeg, ilim-ibeg, &match_size, 1))
+ while ((match_offset = (*execute) (ibeg, ilim-ibeg, mb_cache,
+ &match_size, 1))
    != (size_t) -1)
      {
        char const *b = beg + match_offset;
@@ -591,7 +594,8 @@
    lastout = lim;
    return;
  }
- while (lim-beg && (match_offset = (*execute) (beg, lim - beg, &match_size, 1))
+ while (lim-beg && (match_offset = (*execute) (beg, lim - beg, mb_cache,
+ &match_size, 1))
       != (size_t) -1)
  {
    char const *b = beg + match_offset;
@@ -619,7 +623,7 @@
/* Print pending lines of trailing context prior to LIM. Trailing context ends
    at the next matching line when OUTLEFT is 0. */
static void
-prpending (char const *lim)
+prpending (char const *lim, struct mb_cache *mb_cache)
{
   if (!lastout)
     lastout = bufbeg;
@@ -629,9 +633,10 @@
       size_t match_size;
       --pending;
       if (outleft
- || (((*execute) (lastout, nl - lastout, &match_size, 0) == (size_t) -1)
+ || (((*ex...

Message-ID: <20041208212956.GD8600@law.yi.org>
Date: Wed, 8 Dec 2004 16:29:56 -0500
From: Simon Law <sfllaw@debian.org>
To: 181378@bugs.debian.org
Subject: Red Hat's UTF-8 speedup patch

--mP3DRpeJDSE+ciuQ
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

tags 181378 +patch
thanks

Here is Fedora Core 3's patch to grep that makes it work quickly in
UTF-8 environments.

I haven't tested if it applies cleanly to Debian's grep.  But if you
make me a co-maintainer, I'll happily spend a couple of hours merging
this and other useful Red Hat patches into our grep.

Simon

--mP3DRpeJDSE+ciuQ
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="grep-2.5.1-gofast.patch"

This patch is written by Tim Waugh <twaugh@redhat.com> and is ripped
from Fedora Core 3's grep 2.5.1-31 package.

It is meant to cache results from mbrtowc(), which significantly speeds
up execution speed in UTF-8 locales.

-- Simon Law  <sfllaw@debian.org>  Wed,  8 Dec 2004 16:28:03 -0500

--- grep-2.5.1/src/grep.c.gofast	2004-02-26 13:17:39.000000000 +0000
+++ grep-2.5.1/src/grep.c	2004-02-26 13:17:39.000000000 +0000
@@ -186,7 +186,8 @@
 
 /* Functions we'll use to search. */
 static void (*compile) PARAMS ((char const *, size_t));
-static size_t (*execute) PARAMS ((char const *, size_t, size_t *, int));
+static size_t (*execute) PARAMS ((char const *, size_t, struct mb_cache *,
+				  size_t *, int));
 
 /* Like error, but suppress the diagnostic if requested.  */
 static void
@@ -516,7 +517,7 @@
 }
 
 static void
-prline (char const *beg, char const *lim, int sep)
+prline (char const *beg, char const *lim, int sep, struct mb_cache *mb_cache)
 {
   if (out_file)
     printf ("%s%c", filename, sep & filename_mask);
@@ -539,7 +540,8 @@
     {
       size_t match_size;
       size_t match_offset;
-      while ((match_offset = (*execute) (beg, lim - beg, &match_size, 1))
+      while ((match_offset = (*execute) (beg, lim - beg, mb_cache,
+					 &match_size, 1))
 	  != (size_t) -1)
         {
 	  char const *b = beg + match_offset;
@@ -573,7 +575,8 @@
 	  int i;
 	  for (i = 0; i < lim - beg; i++)
 	    ibeg[i] = tolower (beg[i]);
-	  while ((match_offset = (*execute) (ibeg, ilim-ibeg, &match_size, 1))
+	  while ((match_offset = (*execute) (ibeg, ilim-ibeg, mb_cache,
+					     &match_size, 1))
 		 != (size_t) -1)
 	    {
 	      char const *b = beg + match_offset;
@@ -591,7 +594,8 @@
 	  lastout = lim;
 	  return;
 	}
-      while (lim-beg && (match_offset = (*execute) (beg, lim - beg, &match_size, 1))
+      while (lim-beg && (match_offset = (*execute) (beg, lim - beg, mb_cache,
+						    &match_size, 1))
 	     != (size_t) -1)
 	{
 	  char const *b = beg + match_offset;
@@ -619,7 +623,7 @@
 /* Print pending lines of trailing context prior to LIM. Trailing context ends
    at the next matching line when OUTLEFT is 0.  */
 static void
-prpending (char const *lim)
+prpending (char const *lim, struct mb_cache *mb_cache)
 {
   if (!lastout)
     lastout = bufbeg;
@@ -629,9 +633,10 @@
       size_t match_size;
       --pending;
       if (outleft
-	  || (((*execute) (lastout, nl - lastout, &match_size, 0) == (size_t) -1)
+	  || (((*execute) (lastout, nl - lastout, mb_cache,
+			   &match_size, 0) == (size_t) -1)
 	      == !out_invert))
-	prline (lastout, nl + 1, '-');
+	prline (lastout, nl + 1, '-', mb_cache);
       else
 	pending = 0;
     }
@@ -640,7 +645,8 @@
 /* Print the lines between BEG and LIM.  Deal with context crap.
    If NLINESP is non-null, store a count of lines between BEG and LIM.  */
 static void
-prtext (char const *beg, char const *lim, int *nlinesp)
+prtext (char const *beg, char const *lim, int *nlinesp,
+	struct mb_cache *mb_cache)
 {
   static int used;		/* avoid printing "--" before any output */
   char const *bp, *p;
@@ -648,7 +654,7 @@
   int i, n;
 
   if (!out_quiet && pending > 0)
-    prpending (beg);
+    prpending (beg, mb_cache);
 
   p = beg;
 
@@ -672,7 +678,7 @@
 	{
 	  char const *nl = memchr (p, eol, beg - p);
 	  nl++;
-	  prline (p, nl, '-');
+	  prline (p, nl, '-', mb_cache);
 	  p = nl;
 	}
     }
@@ -685,7 +691,7 @@
 	  char const *nl = memchr (p, eol, lim - p);
 	  nl++;
 	  if (!out_quiet)
-	    prline (p, nl, ':');
+	    prline (p, nl, ':', mb_cache);
 	  p = nl;
 	}
       *nlinesp = n;
@@ -695,7 +701,7 @@
     }
   else
     if (!out_quiet)
-      prline (beg, lim, ':');
+      prline (beg, lim, ':', mb_cache);
 
   pending = out_quiet ? 0 : out_after;
   used = 1;
@@ -705,7 +711,7 @@
    between matching lines if OUT_INVERT is true).  Return a count of
    lines printed. */
 static int
-grepbuf (char const *beg, char const *lim)
+grepbuf (char const *beg, char const *lim, struct mb_cache *mb_cache)
 {
   int nlines, n;
   register char const *p;
@@ -714,7 +720,8 @@
 
   nlines = 0;
   p = beg;
-  while ((match_offset = (*execute) (p, lim - p, &match_size, 0)) != (size_t) -1)
+  while ((match_offset = (*execute) (p, lim - p, mb_cache,
+				     &match_size, 0)) != (size_t) -1)
     {
       char const *b = p + match_offset;
       char const *endp = b + match_size;
@@ -723,7 +730,7 @@
 	break;
       if (!out_invert)
 	{
-	  prtext (b, endp, (int *) 0);
+	  prtext (b, endp, (int *) 0, mb_cache);
 	  nlines++;
           outleft--;
 	  if (!outleft || done_on_match)
@@ -736,7 +743,7 @@
 	}
       else if (p < b)
 	{
-	  prtext (p, b, &n);
+	  prtext (p, b, &n, mb_cache);
 	  nlines += n;
           outleft -= n;
 	  if (!outleft)
@@ -746,7 +753,7 @@
     }
   if (out_invert && p < lim)
     {
-      prtext (p, lim, &n);
+      prtext (p, lim, &n, mb_cache);
       nlines += n;
       outleft -= n;
     }
@@ -766,7 +773,9 @@
   char *beg;
   char *lim;
   char eol = eolbyte;
+  struct mb_cache mb_cache;
 
+  memset (&mb_cache, 0, sizeof (mb_cache));
   if (!reset (fd, file, stats))
     return 0;
 
@@ -833,9 +842,9 @@
       if (beg < lim)
 	{
 	  if (outleft)
-	    nlines += grepbuf (beg, lim);
+	    nlines += grepbuf (beg, lim, &mb_cache);
 	  if (pending)
-	    prpending (lim);
+	    prpending (lim, &mb_cache);
 	  if((!outleft && !pending) || (nlines && done_on_match && !out_invert))
 	    goto finish_grep;
 	}
@@ -863,6 +872,11 @@
 	totalcc = add_count (totalcc, buflim - bufbeg - save);
       if (out_line)
 	nlscan (beg);
+      if (mb_cache.wcs_buf)
+	free (mb_cache.wcs_buf);
+      if (mb_cache.mblen_buf)
+	free (mb_cache.mblen_buf);
+      memset (&mb_cache, 0, sizeof (mb_cache));
       if (! fillbuf (save, stats))
 	{
 	  if (! is_EISDIR (errno, file))
@@ -874,9 +888,9 @@
     {
       *buflim++ = eol;
       if (outleft)
-	nlines += grepbuf (bufbeg + save - residue, buflim);
+	nlines += grepbuf (bufbeg + save - residue, buflim, &mb_cache);
       if (pending)
-        prpending (buflim);
+        prpending (buflim, &mb_cache);
     }
 
  finish_grep:
@@ -884,6 +898,11 @@
   out_quiet -= not_text;
   if ((not_text & ~out_quiet) && nlines != 0)
     printf (_("Binary file %s matches\n"), filename);
+
+  if (mb_cache.wcs_buf)
+    free (mb_cache.wcs_buf);
+  if (mb_cache.mblen_buf)
+    free (mb_cache.mblen_buf);
   return nlines;
 }
 
--- grep-2.5.1/src/grep.h.gofast	2001-03-04 05:39:41.000000000 +0000
+++ grep-2.5.1/src/grep.h	2004-02-26 13:17:39.000000000 +0000
@@ -20,6 +20,8 @@
 # define __attribute__(x)
 #endif
 
+#include "mbcache.h"
+
 /* Grep.c expects the matchers vector to be terminated
    by an entry with a NULL compile, and to contain at least
    an entry named "default". */
@@ -28,7 +30,8 @@
 {
   char name[8];
   void (*compile) PARAMS ((char const *, size_t));
-  size_t (*execute) PARAMS ((char const *, size_t, size_t *, int));
+  size_t (*execute) PARAMS ((char const *, size_t, struct mb_cache *,
+			     size_t *, int));
 } const matchers[];
 
 /* Exported from fgrepmat.c, egrepmat.c, grepmat.c.  */
--- grep-2.5.1/src/search.c	2004-10-13 17:17:09.929706014 +0100
+++ grep-2.5.1/src/search.c	2004-10-13 17:44:21.470690774 +0100
@@ -71,17 +71,27 @@
 static int kwset_exact_matches;
 
 #if defined(MBS_SUPPORT)
-static char* check_multibyte_string PARAMS ((char const *buf, size_t size));
+/* For Fexecute: we might be able to elide multibyte processing. */
+static int pattern_contains_multibyte = 0;
+#endif
+
+#if defined(MBS_SUPPORT)
+static char* check_multibyte_string PARAMS ((char const *buf, size_t size,
+					     struct mb_cache *,
+					     char const *orig_buf));
 #endif
 static void kwsinit PARAMS ((void));
 static void kwsmusts PARAMS ((void));
 static void Gcompile PARAMS ((char const *, size_t));
 static void Ecompile PARAMS ((char const *, size_t));
-static size_t EGexecute PARAMS ((char const *, size_t, size_t *, int ));
+static size_t EGexecute PARAMS ((char const *, size_t, struct mb_cache *,
+				 size_t *, int ));
 static void Fcompile PARAMS ((char const *, size_t));
-static size_t Fexecute PARAMS ((char const *, size_t, size_t *, int));
+static size_t Fexecute PARAMS ((char const *, size_t, struct mb_cache *,
+				size_t *, int));
 static void Pcompile PARAMS ((char const *, size_t ));
-static size_t Pexecute PARAMS ((char const *, size_t, size_t *, int));
+static size_t Pexecute PARAMS ((char const *, size_t, struct mb_cache *,
+				size_t *, int));
 
 void
 dfaerror (char const *mesg)
@@ -147,35 +157,66 @@
    are not singlebyte character nor the first byte of a multibyte
    character.  Caller must free the array.  */
 static char*
-check_multibyte_string(char const *buf, size_t size)
+check_multibyte_string(char const *buf, size_t size, struct mb_cache *mb_cache,
+		       char const *orig_buf)
 {
   char *mb_properties = xmalloc(size);
   mbstate_t cur_state;
   wchar_t wc;
   int i;
   memset(&cur_state, 0, sizeof(mbstate_t));
-  memset(mb_properties, 0, sizeof(char)*size);
-  for (i = 0; i < size ;)
-    {
-      size_t mbclen;
-      mbclen = mbrtowc(&wc, buf + i, size - i, &cur_state);
 
-      if (mbclen == (size_t) -1 || mbclen == (size_t) -2 || mbclen == 0)
+  if (mb_cache && mb_cache->mblen_buf &&
+      orig_buf > mb_cache->orig_buf &&
+      (orig_buf + size) <= (mb_cache->orig_buf + mb_cache->len))
+    {
+      /* The cache can help us. */
+      memcpy (mb_properties,
+	      mb_cache->mblen_buf + (orig_buf - mb_cache->orig_buf),
+	      size);
+    
+    }
+  else
+    {
+      memset(mb_properties, 0, sizeof(char)*size);
+      for (i = 0; i < size ;)
 	{
-	  /* An invalid sequence, or a truncated multibyte character.
-	     We treat it as a singlebyte character.  */
-	  mbclen = 1;
+	  size_t mbclen;
+	  mbclen = mbrtowc(&wc, buf + i, size - i, &cur_state);
+
+	  if (mbclen == (size_t) -1 || mbclen == (size_t) -2 || mbclen == 0)
+	    {
+	      /* An invalid sequence, or a truncated multibyte character.
+		 We treat it as a singlebyte character.  */
+	      mbclen = 1;
+	    }
+	  else if (match_icase)
+	    {
+	      if (iswupper((wint_t)wc))
+		{
+		  wc = towlower((wint_t)wc);
+		  wcrtomb(buf + i, wc, &cur_state);
+		}
+	    }
+	  mb_properties[i] = mbclen;
+	  i += mbclen;
 	}
-      else if (match_icase)
+
+      /* Now populate the cache. */
+      if (mb_cache)
 	{
-	  if (iswupper((wint_t)wc))
+	  if (mb_cache->wcs_buf)
 	    {
-	      wc = towlower((wint_t)wc);
-	      wcrtomb(buf + i, wc, &cur_state);
+	      free (mb_cache->wcs_buf);
+	      mb_cache->wcs_buf = NULL;
 	    }
+	  if (mb_cache->mblen_buf)
+	    free (mb_cache->mblen_buf);
+	  mb_cache->len = size;
+	  mb_cache->orig_buf = orig_buf;
+	  mb_cache->mblen_buf = xmalloc (size);
+	  memcpy (mb_cache->mblen_buf, mb_properties, size);
 	}
-      mb_properties[i] = mbclen;
-      i += mbclen;
     }
 
   return mb_properties;
@@ -342,9 +383,11 @@
 }
 
 static size_t
-EGexecute (char const *buf, size_t size, size_t *match_size, int exact)
+EGexecute (char const *buf, size_t size, struct mb_cache *mb_cache,
+	   size_t *match_size, int exact)
 {
   register char const *buflim, *beg, *end;
+  char const *orig_buf = buf;
   char eol = eolbyte;
   int backref, start, len;
   struct kwsmatch kwsm;
@@ -360,7 +403,7 @@
           buf = case_buf;
         }
       if (kwset)
-        mb_properties = check_multibyte_string(buf, size);
+        mb_properties = check_multibyte_string(buf, size, mb_cache, orig_buf);
     }
 #endif /* MBS_SUPPORT */
 
@@ -389,13 +432,13 @@
 		--beg;
 	      if (kwsm.index < kwset_exact_matches)
 		goto success_in_beg_and_end;
-	      if (dfaexec (&dfa, beg, end - beg, &backref) == (size_t) -1)
+	      if (dfaexec (&dfa, beg, end - beg, &backref, mb_cache) == (size_t) -1)
 		continue;
 	    }
 	  else
 	    {
 	      /* No good fixed strings; start with DFA. */
-	      size_t offset = dfaexec (&dfa, beg, buflim - beg, &backref);
+	      size_t offset = dfaexec (&dfa, beg, buflim - beg, &backref, mb_cache);
 	      if (offset == (size_t) -1)
 		break;
 	      /* Narrow down to the line we've found. */
@@ -503,13 +546,25 @@
 Fcompile (char const *pattern, size_t size)
 {
   char const *beg, *lim, *err;
+#ifdef MBS_SUPPORT
+  mbstate_t ps;
+  memset (&ps, '\0', sizeof (mbstate_t));
+#endif
 
   kwsinit ();
   beg = pattern;
   do
     {
       for (lim = beg; lim < pattern + size && *lim != '\n'; ++lim)
-	;
+	{
+#ifdef MBS_SUPPORT
+	  if (!pattern_contains_multibyte && match_icase)
+	    pattern_contains_multibyte = 1;
+	  if (!pattern_contains_multibyte &&
+	      mbrlen (lim, size - (lim - pattern), &ps) != 1)
+	    pattern_contains_multibyte = 1;
+#endif
+	}
       if ((err = kwsincr (kwset, beg, lim - beg)) != 0)
 	error (2, 0, err);
       if (lim < pattern + size)
@@ -523,16 +578,18 @@
 }
 
 static size_t
-Fexecute (char const *buf, size_t size, size_t *match_size, int exact)
+Fexecute (char const *buf, size_t size, struct mb_cache *mb_cache,
+	  size_t *match_size, int exact)
 {
   register char const *beg, *try, *end;
+  char const *orig_buf = buf;
   register size_t len;
   char eol = eolbyte;
   struct kwsmatch kwsmatch;
   size_t ret_val;
 #ifdef MBS_SUPPORT
   char *mb_properties = NULL;
-  if (MB_CUR_MAX > 1)
+  if (pattern_contains_multibyte && MB_CUR_MAX > 1)
     {
       if (match_icase)
         {
@@ -540,7 +597,7 @@
           memcpy(case_buf, buf, size);
           buf = case_buf;
         }
-      mb_properties = check_multibyte_string(buf, size);
+      mb_properties = check_multibyte_string(buf, size, mb_cache, orig_buf);
     }
 #endif /* MBS_SUPPORT */
 
@@ -550,7 +607,8 @@
       if (offset == (size_t) -1)
 	goto failure;
 #ifdef MBS_SUPPORT
-      if (MB_CUR_MAX > 1 && mb_properties[offset+beg-buf] == 0)
+      if (pattern_contains_multibyte &&
+	  MB_CUR_MAX > 1 && mb_properties[offset+beg-buf] == 0)
 	continue; /* It is a part of multibyte character.  */
 #endif /* MBS_SUPPORT */
       beg += offset;
@@ -598,7 +656,7 @@
 
  failure:
 #ifdef MBS_SUPPORT
-  if (MB_CUR_MAX > 1)
+  if (pattern_contains_multibyte && MB_CUR_MAX > 1)
     {
       if (match_icase)
         free((char *) buf);
@@ -619,7 +677,7 @@
  success_in_beg_and_len:
   *match_size = len;
 #ifdef MBS_SUPPORT
-  if (MB_CUR_MAX > 1)
+  if (pattern_contains_multibyte && MB_CUR_MAX > 1)
     {
       if (mb_properties)
 	free (mb_properties);
@@ -704,7 +762,8 @@
 }
 
 static size_t
-Pexecute (char const *buf, size_t size, size_t *match_size, int exact)
+Pexecute (char const *buf, size_t size, struct mb_cache *mb_cache,
+	  size_t *match_size, int exact)
 {
 #if !HAVE_LIBPCRE
   abort ();
--- grep-2.5.1/src/dfa.c.gofast	2004-02-26 13:17:39.000000000 +0000
+++ grep-2.5.1/src/dfa.c	2004-02-26 13:17:39.000000000 +0000
@@ -2747,7 +2747,8 @@
    match needs to be verified by a backtracking matcher.  Otherwise
    we store a 0 in *backref. */
 size_t
-dfaexec (struct dfa *d, char const *begin, size_t size, int *backref)
+dfaexec (struct dfa *d, char const *begin, size_t size, int *backref,
+	 struct mb_cache *mb_cache)
 {
   register int s;	/* Current state. */
   register unsigned char const *p; /* Current input character. */
@@ -2779,43 +2780,79 @@
 #ifdef MBS_SUPPORT
   if (MB_CUR_MAX > 1)
     {
-      int remain_bytes, i;
       buf_begin = begin;
       buf_end = end;
-
-      /* initialize mblen_buf, and inputwcs.  */
-      MALLOC(mblen_buf, unsigned char, end - (unsigned char const *)begin + 2);
-      MALLOC(inputwcs, wchar_t, end - (unsigned char const *)begin + 2);
-      memset(&mbs, 0, sizeof(mbstate_t));
-      remain_bytes = 0;
-      for (i = 0; i < end - (unsigned char const *)begin + 1; i++)
+      if (mb_cache && mb_cache->mblen_buf && mb_cache->wcs_buf &&
+	  begin > mb_cache->orig_buf &&
+	  (begin + size) <= (mb_cache->orig_buf + mb_cache->len))
+	{
+	  /* The cache can help us. */
+	  MALLOC(mblen_buf, unsigned char, size + 2);
+	  MALLOC(inputwcs, wchar_t, size + 2);
+	  memcpy (mblen_buf,
+		  mb_cache->mblen_buf + (begin - mb_cache->orig_buf),
+		  (size + 2) * sizeof (unsigned char));
+	  memcpy (inputwcs,
+		  mb_cache->wcs_buf + (begin - mb_cache->orig_buf),
+		  (size + 2) * sizeof (wchar_t));
+	  mblen_buf[size + 1] = 0;
+	  inputwcs[size + 1] = 0;
+	}
+      else
 	{
-	  if (remain_bytes == 0)
+	  int remain_bytes, i;
+
+	  /* initialize mblen_buf, and inputwcs.  */
+	  MALLOC(mblen_buf, unsigned char, end - (unsigned char const *)begin + 2);
+	  MALLOC(inputwcs, wchar_t, end - (unsigned char const *)begin + 2);
+	  memset(&mbs, 0, sizeof(mbstate_t));
+	  remain_bytes = 0;
+	  for (i = 0; i < end - (unsigned char const *)begin + 1; i++)
 	    {
-	      remain_bytes
-		= mbrtowc(inputwcs + i, begin + i,
-			  end - (unsigned char const *)begin - i + 1, &mbs);
-	      if (remain_bytes <= 1)
+	      if (remain_bytes == 0)
 		{
-		  remain_bytes = 0;
-		  inputwcs[i] = (wchar_t)begin[i];
-		  mblen_buf[i] = 0;
+		  remain_bytes
+		    = mbrtowc(inputwcs + i, begin + i,
+			      end - (unsigned char const *)begin - i + 1, &mbs);
+		  if (remain_bytes <= 1)
+		    {
+		      remain_bytes = 0;
+		      inputwcs[i] = (wchar_t)begin[i];
+		      mblen_buf[i] = 0;
+		    }
+		  else
+		    {
+		      mblen_buf[i] = remain_bytes;
+		      remain_bytes--;
+		    }
 		}
 	      else
 		{
 		  mblen_buf[i] = remain_bytes;
+		  inputwcs[i] = 0;
 		  remain_bytes--;
 		}
 	    }
-	  else
+	  mblen_buf[i] = 0;
+	  inputwcs[i] = 0; /* sentinel */
+
+	  if (mb_cache)
 	    {
-	      mblen_buf[i] = remain_bytes;
-	      inputwcs[i] = 0;
-	      remain_bytes--;
+	      /* Populate the cache. */
+	      mb_cache->len = size;
+	      mb_cache->orig_buf = begin;
+	      if (mb_cache->mblen_buf)
+		      free (mb_cache->mblen_buf);
+	      if (mb_cache->wcs_buf)
+		      free (mb_cache->wcs_buf);
+	      MALLOC(mb_cache->mblen_buf, unsigned char, size + 2);
+	      MALLOC(mb_cache->wcs_buf, wchar_t, size + 2);
+	      memcpy (mb_cache->mblen_buf, mblen_buf,
+		      (size + 2) * sizeof (unsigned char));
+	      memcpy (mb_cache->wcs_buf, inputwcs,
+		      (size + 2) * sizeof (wchar_t));
 	    }
 	}
-      mblen_buf[i] = 0;
-      inputwcs[i] = 0; /* sentinel */
     }
 #endif /* MBS_SUPPORT */
 
--- /dev/null	2004-02-23 21:02:56.000000000 +0000
+++ grep-2.5.1/src/mbcache.h	2004-02-26 13:17:39.000000000 +0000
@@ -0,0 +1,10 @@
+#ifndef MB_CACHE_DEFINED
+#define MB_CACHE_DEFINED
+struct mb_cache
+{
+  size_t len;
+  const char *orig_buf; /* not the only reference; do not free */
+  wchar_t *wcs_buf;
+  unsigned char *mblen_buf;
+};
+#endif
--- grep-2.5.1/src/dfa.h.gofast	2001-03-07 04:11:27.000000000 +0000
+++ grep-2.5.1/src/dfa.h	2004-02-26 13:17:39.000000000 +0000
@@ -22,6 +22,8 @@
    In addition to clobbering modularity, we eat up valuable
    name space. */
 
+#include "mbcache.h"
+
 #ifdef __STDC__
 # ifndef _PTR_T
 # define _PTR_T
@@ -403,7 +405,8 @@
    order to verify backreferencing; otherwise the flag will be cleared.
    Returns (size_t) -1 if no match is found, or the offset of the first
    character after the first & shortest matching string in the buffer. */
-extern size_t dfaexec PARAMS ((struct dfa *, char const *, size_t, int *));
+extern size_t dfaexec PARAMS ((struct dfa *, char const *, size_t, int *,
+			       struct mb_cache *));
 
 /* Free the storage held by the components of a struct dfa. */
 extern void dfafree PARAMS ((struct dfa *));

--mP3DRpeJDSE+ciuQ--

Revision history for this message

Matt Zimmerman (mdz) wrote on 2005-04-09:

#26

*** Bug 15162 has been marked as a duplicate of this bug. ***

Revision history for this message

Matt Zimmerman (mdz) wrote on 2005-06-03:

#27

<dooglus> the fedora guys fixed it ages ago (see patch, here:
http://cvs.fedora.redhat.com/viewcvs/devel/grep/grep-2.5.1-egf-speedup.patch )

I haven't looked at the above patch myself, but I'm archiving it here

Revision history for this message

Chris Moore (dooglus) wrote on 2005-06-05:

#28

I have mentioned this bug to a few people, and the response I usually get is
"well, UTF handling is bound to be a bit slower, don't worry about it".

That's missing the point. This bug doesn't make grep 'a bit slower', it changes
it from using linear time to using quadratic time in some cases.

Here's an example, grepping through a million short lines of text:

yes | head -999999 | LC_ALL=C time grep . > /dev/null

it runs in 0.27 seconds on my laptop.

Here's the same example, doing the same work, but in a UTF-8 locale:

yes | head -999999 | LC_ALL=en_US.UTF-8 time grep . > /dev/null

it runs in about *40 hours* on the same laptop. It is around 500,000 times
slower than using the 'C' locale.

That's 40 hours to grep through a 2 megabyte file.

Some people have been unable to reproduce this severe slow-down. I suspect it
may be that they don't have the en_US.UTF-8 locale generated. You can find a
list of UTF-8 locales that have been generated in /etc/locale.gen.

I hope this bug can be fixed, because it really is quite a problem, especially
since the default locale in a ubuntu install is a UTF-8 one!

Note that the fedora fix referred to in the previous comment works around this
problem in the dfa code by disabling the dfa code when using a UTF-8 locale,
rather than by addressing the real root of the problem (which is that dfaexec()
in src/dfa.c does a complete scan of the remaining input buffer each time it is
called).

Revision history for this message

Matt Zimmerman (mdz) wrote on 2005-06-24:

#29

You said on IRC that you'd fixed the bug; perhaps you'd care to share your patch?

Revision history for this message

Chris Moore (dooglus) wrote on 2005-06-25:

#30

I was mistaken. My changes certainly sped things up, but broke more than they
fixed, sorry.

Revision history for this message

In Debian Bug tracker #181378, Nicolas François (nicolas-francois) wrote on 2005-09-07:

#31

Package: grep
Version: 2.5.1.ds1-5
Followup-For: Bug #181378

Hello,

I tried the gofast patche, and did not find a real improvement.

However, Fedora is now using a different patch, which improve dramaticaly
grep performances on an UTF-8 environment.

Please find attached the following patches:
  * I put the original Fedora patches in the orig directory. The other
    patches are updated for the Debian package.
  * 64-egf-speedup.patch
    It does most of the work. Here is the explanation, according to:
    http://savannah.gnu.org/patch/?func=detailitem&item_id=3803
> The full story behind this patch is that grep-2.5.1a does not handle
> UTF-8 gracefully at all. The basic plan with handling UTF-8 in 2.5.1a
> is:
> * whenever a buffer is parsed, go through the entire buffer deciding
> how many bytes make up each character
> * use this information when necessary
>
> This patch changes that to:
> * when information about how many bytes make up a character is needed,
> work it out on demand
>
> On the face of it, this is a small obvious improvement. In fact it is
> much better than that, because the original scheme would calculate
> character lengths several times for each buffer: in fact, one full
> pass for every single potential match!

  * 65-dfa-optional.patch
    I'm not sure this one is really needed.
    I've read the DFA algorithme is slow for UTF-8 and this patch disable
    it in that case (and it can be forced enabled by setting an evirronment
    variable)
  * grep-2.5.1-tests.patch
    Fedora also added a test for UTF-8.
  * 66-match_icase.patch
  * 67-w.patch
    After testing the new UTF-8 tests, these too seems to be needed.
    (It is not really related to the grep's speed, but these patches may
    be interresting)

I tried a grep packages with all these patches, and for the following
command:
grep '^' /var/lib/dpkg/available> /dev/null
grep is more than 1500 faster on an UTF-8 environment.
(on my machine, it take less than 3/4s instead of more than 10 minutes!)

Also, I did not notice any regression, and grep is not dramatically
slower on the C locale.

These patches may be important for Etch since the transition to UTF-8 is
mentionned on the (unofficial) Etch TODO list:
http://wiki.debian.net/?EtchTODOList

(And the French team is considering using UTF-8 for the default French
locale)

Thanks in advance,
--
Nekral

Package: grep
Version: 2.5.1.ds1-5
Followup-For: Bug #181378

Hello,

I tried the gofast patche, and did not find a real improvement.

However, Fedora is now using a different patch, which improve dramaticaly
grep performances on an UTF-8 environment.

Please find attached the following patches:
  * I put the original Fedora patches in the orig directory. The other
    patches are updated for the Debian package.
  * 64-egf-speedup.patch
    It does most of the work. Here is the explanation, according to:
    http://savannah.gnu.org/patch/?func=detailitem&item_id=3803
>    The full story behind this patch is that grep-2.5.1a does not handle
>    UTF-8 gracefully at all. The basic plan with handling UTF-8 in 2.5.1a
>    is:
>    * whenever a buffer is parsed, go through the entire buffer deciding
>      how many bytes make up each character
>    * use this information when necessary
>
>    This patch changes that to:
>    * when information about how many bytes make up a character is needed,
>      work it out on demand
>
>    On the face of it, this is a small obvious improvement. In fact it is
>    much better than that, because the original scheme would calculate
>    character lengths several times for each buffer: in fact, one full
>    pass for every single potential match!

* 65-dfa-optional.patch
    I'm not sure this one is really needed.
    I've read the DFA algorithme is slow for UTF-8 and this patch disable
    it in that case (and it can be forced enabled by setting an evirronment
    variable)
  * grep-2.5.1-tests.patch
    Fedora also added a test for UTF-8.
  * 66-match_icase.patch
  * 67-w.patch
    After testing the new UTF-8 tests, these too seems to be needed.
    (It is not really related to the grep's speed, but these patches may
    be interresting)

I tried a grep packages with all these patches, and for the following
command:
    grep '^' /var/lib/dpkg/available> /dev/null
grep is more than 1500 faster on an UTF-8 environment.
(on my machine, it take less than 3/4s instead of more than 10 minutes!)

Also, I did not notice any regression, and grep is not dramatically
slower on the C locale.

These patches may be important for Etch since the transition to UTF-8 is
mentionned on the (unofficial) Etch TODO list:
http://wiki.debian.net/?EtchTODOList

(And the French team is considering using UTF-8 for the default French
locale)

Thanks in advance,
-- 
Nekral

Revision history for this message

Debian Bug Importer (debzilla) wrote on 2005-09-07:

#32

Download full text (15.8 KiB)

Message-ID: <email address hidden>
Date: Wed, 7 Sep 2005 11:52:34 +0200
From: Nicolas =?iso-8859-1?Q?Fran=E7ois?= <email address hidden>
To: Debian Bug Tracking System <email address hidden>
Subject: grep is extremely slow with UTF-8

--EVF5PPMfhYS0aIcm
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline