GNU bug report logs - #44754
Extreme performance degradation in GNU grep 3.4 / 3.6

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 44754 in the body.
You can then email your comments to 44754 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Frank Heckenbach <f.heckenbach <at> fh-soft.de>
To: bug-grep <at> gnu.org
Subject: Extreme performance degradation in GNU grep 3.4 / 3.6
Date: Fri, 20 Nov 2020 06:20:55 +0100

Hi,

I have a use case where I run grep with a large number of search
patterns on a large text file. It works well with grep-3.3, but with
grep-3.4 it quickly burned through GBs of memory and almost locked
up my system due to swapping.

To avoid attaching those large files, I could mostly reproduce the
effects like this:

ulimit -d 5000000  # avoid system lockup due to excessive swapping
export LC_ALL=C    # make sure no Unicode case conversions are needed

% time  ./grep-3.3 -Fwif <(seq 300000 | tr 0-9 A-J) <<<foo

real    0m0.054s
user    0m0.048s
sys     0m0.012s

% time  ./grep-3.4 -Fwif <(seq 30000 | tr 0-9 A-J) <<<foo
./grep-3.4: Memory exhausted
Aborted

real    0m1.291s
user    0m0.696s
sys     0m0.599s

% time  ./grep-3.6 -Fwif <(seq 300000 | tr 0-9 A-J) <<<foo

real    0m13.162s
user    0m12.955s
sys     0m0.211s

grep-3.3 behaves well, even with much larger number of patterns.
Time seems to grow linearly, and memory usage is constant.

grep-3.4 behaves the worst of these 3 versions. Even with just 30000
patterns it exceeds the ulimit of 5 GB.

grep-3.6 behaves a bit better than 3.4, but still bad. Time seems to
be quadratic in the number of patterns, and though memory usage in
this case seems to be almost constant, in my actual use case it also
runs out of memory where grep-3.3 works well with just a few 100 MB
used.

Without "-i", grep-3.4 seems to run as fast as grep-3.3, but
grep-3.6 is almost as slow as with "-i".

So there might actually be two different issues here, one that
affects 3.4 with "-i" and one that affects 3.6 with or without "-i".

Regards,
Frank

Message #8 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Jim Meyering <jim <at> meyering.net>
To: bug-grep <at> gnu.org, f.heckenbach <at> fh-soft.de
Cc: 44754 <at> debbugs.gnu.org
Subject: Re: bug#44754: Extreme performance degradation in GNU grep 3.4 / 3.6
Date: Wed, 25 Nov 2020 15:12:04 -1000

[Message part 1 (text/plain, inline)]

On Thu, Nov 19, 2020 at 7:32 PM Frank Heckenbach
<f.heckenbach <at> fh-soft.de> wrote:
> I have a use case where I run grep with a large number of search
> patterns on a large text file. It works well with grep-3.3, but with
> grep-3.4 it quickly burned through GBs of memory and almost locked
> up my system due to swapping.
>
> To avoid attaching those large files, I could mostly reproduce the
> effects like this:
>
> ulimit -d 5000000  # avoid system lockup due to excessive swapping
> export LC_ALL=C    # make sure no Unicode case conversions are needed
>
> % time  ./grep-3.3 -Fwif <(seq 300000 | tr 0-9 A-J) <<<foo
>
> real    0m0.054s
> user    0m0.048s
> sys     0m0.012s
>
> % time  ./grep-3.4 -Fwif <(seq 30000 | tr 0-9 A-J) <<<foo
> ./grep-3.4: Memory exhausted
> Aborted
>
> real    0m1.291s
> user    0m0.696s
> sys     0m0.599s
>
> % time  ./grep-3.6 -Fwif <(seq 300000 | tr 0-9 A-J) <<<foo
>
> real    0m13.162s
> user    0m12.955s
> sys     0m0.211s
>
> grep-3.3 behaves well, even with much larger number of patterns.
> Time seems to grow linearly, and memory usage is constant.
>
> grep-3.4 behaves the worst of these 3 versions. Even with just 30000
> patterns it exceeds the ulimit of 5 GB.
>
> grep-3.6 behaves a bit better than 3.4, but still bad. Time seems to
> be quadratic in the number of patterns, and though memory usage in
> this case seems to be almost constant, in my actual use case it also
> runs out of memory where grep-3.3 works well with just a few 100 MB
> used.
>
> Without "-i", grep-3.4 seems to run as fast as grep-3.3, but
> grep-3.6 is almost as slow as with "-i".
>
> So there might actually be two different issues here, one that
> affects 3.4 with "-i" and one that affects 3.6 with or without "-i".

Thank you for the fine bug report.
The grep-3.6 bug you've exposed is due to the fact that your input
triggers excessive hash collisions when using the code modeled after
gnulib/lib/hash-pjw.c. That made the new pattern-preprocessing phase
take O(N^2) time for N patterns. In the attached, I've switched grep
to use the djb2 hash function, and that resolves the problem. I'll
also add a NEWS entry and a test before pushing this.

[0001-grep-avoid-performance-regression-with-many-patterns.patch (application/octet-stream, attachment)]

Message #14 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Jim Meyering <jim <at> meyering.net>
To: bug-grep <at> gnu.org, f.heckenbach <at> fh-soft.de
Cc: 44754 <at> debbugs.gnu.org
Subject: Re: bug#44754: Extreme performance degradation in GNU grep 3.4 / 3.6
Date: Thu, 26 Nov 2020 09:03:42 -1000

[Message part 1 (text/plain, inline)]

On Wed, Nov 25, 2020 at 3:12 PM Jim Meyering <jim <at> meyering.net> wrote:
> Thank you for the fine bug report.
> The grep-3.6 bug you've exposed is due to the fact that your input
> triggers excessive hash collisions when using the code modeled after
> gnulib/lib/hash-pjw.c. That made the new pattern-preprocessing phase
> take O(N^2) time for N patterns. In the attached, I've switched grep
> to use the djb2 hash function, and that resolves the problem. I'll
> also add a NEWS entry and a test before pushing this.

Timings suggest that grep-3.6's preprocessing came closer to O(N^3).
Here's an example that would take 2-3 days with grep-3.6 and only
seconds with this fix:

  : | grep -Ff <(seq 6400000 | tr 0-9 A-J)

Here's a complete patch.
I'll push it later today.

[0001-grep-avoid-performance-regression-with-many-patterns.patch (application/octet-stream, attachment)]

Message #20 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Jim Meyering <jim <at> meyering.net>
To: bug-grep <at> gnu.org, f.heckenbach <at> fh-soft.de
Cc: 44754-done <at> debbugs.gnu.org
Subject: Re: bug#44754: Extreme performance degradation in GNU grep 3.4 / 3.6
Date: Thu, 26 Nov 2020 21:41:20 -1000

On Thu, Nov 26, 2020 at 9:03 AM Jim Meyering <jim <at> meyering.net> wrote:
>
> On Wed, Nov 25, 2020 at 3:12 PM Jim Meyering <jim <at> meyering.net> wrote:
> > Thank you for the fine bug report.
> > The grep-3.6 bug you've exposed is due to the fact that your input
> > triggers excessive hash collisions when using the code modeled after
> > gnulib/lib/hash-pjw.c. That made the new pattern-preprocessing phase
> > take O(N^2) time for N patterns. In the attached, I've switched grep
> > to use the djb2 hash function, and that resolves the problem. I'll
> > also add a NEWS entry and a test before pushing this.
>
> Timings suggest that grep-3.6's preprocessing came closer to O(N^3).
> Here's an example that would take 2-3 days with grep-3.6 and only
> seconds with this fix:
>
>   : | grep -Ff <(seq 6400000 | tr 0-9 A-J)
>
> Here's a complete patch.
> I'll push it later today.

Pushed along with two gnulib-related changes.

Message #28 received at 44754 <at> debbugs.gnu.org (full text, mbox):

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: 44754 <at> debbugs.gnu.org
Cc: jim <at> meyering.net, f.heckenbach <at> fh-soft.de
Subject: Re: bug#44754: Extreme performance degradation in GNU grep 3.4 / 3.6
Date: Thu, 03 Dec 2020 17:26:46 +0900

[Message part 1 (text/plain, inline)]

On Thu, 26 Nov 2020 21:41:20 -1000
Jim Meyering <jim <at> meyering.net> wrote:

> On Thu, Nov 26, 2020 at 9:03 AM Jim Meyering <jim <at> meyering.net> wrote:
> >
> > On Wed, Nov 25, 2020 at 3:12 PM Jim Meyering <jim <at> meyering.net> wrote:
> > > Thank you for the fine bug report.
> > > The grep-3.6 bug you've exposed is due to the fact that your input
> > > triggers excessive hash collisions when using the code modeled after
> > > gnulib/lib/hash-pjw.c. That made the new pattern-preprocessing phase
> > > take O(N^2) time for N patterns. In the attached, I've switched grep
> > > to use the djb2 hash function, and that resolves the problem. I'll
> > > also add a NEWS entry and a test before pushing this.
> >
> > Timings suggest that grep-3.6's preprocessing came closer to O(N^3).
> > Here's an example that would take 2-3 days with grep-3.6 and only
> > seconds with this fix:
> >
> >   : | grep -Ff <(seq 6400000 | tr 0-9 A-J)
> >
> > Here's a complete patch.
> > I'll push it later today.
> 
> Pushed along with two gnulib-related changes.

The fix has improved some performance.  However, it's still quite slow
compared to version 3.3, and that can be remedied.

It converts to grep only if the potential match does not match the word
frequently.

[0001-grep-improvement-of-grep-convertion-for-fgrep.patch (text/plain, attachment)]

Message #31 received at 44754 <at> debbugs.gnu.org (full text, mbox):

From: Jim Meyering <jim <at> meyering.net>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 44754 <at> debbugs.gnu.org, f.heckenbach <at> fh-soft.de
Subject: Re: bug#44754: Extreme performance degradation in GNU grep 3.4 / 3.6
Date: Sat, 5 Dec 2020 10:06:27 -0800

On Thu, Dec 3, 2020 at 12:26 AM Norihiro Tanaka <noritnk <at> kcn.ne.jp> wrote:
> On Thu, 26 Nov 2020 21:41:20 -1000
> Jim Meyering <jim <at> meyering.net> wrote:
>
> > On Thu, Nov 26, 2020 at 9:03 AM Jim Meyering <jim <at> meyering.net> wrote:
> > >
> > > On Wed, Nov 25, 2020 at 3:12 PM Jim Meyering <jim <at> meyering.net> wrote:
> > > > Thank you for the fine bug report.
> > > > The grep-3.6 bug you've exposed is due to the fact that your input
> > > > triggers excessive hash collisions when using the code modeled after
> > > > gnulib/lib/hash-pjw.c. That made the new pattern-preprocessing phase
> > > > take O(N^2) time for N patterns. In the attached, I've switched grep
> > > > to use the djb2 hash function, and that resolves the problem. I'll
> > > > also add a NEWS entry and a test before pushing this.
> > >
> > > Timings suggest that grep-3.6's preprocessing came closer to O(N^3).
> > > Here's an example that would take 2-3 days with grep-3.6 and only
> > > seconds with this fix:
> > >
> > >   : | grep -Ff <(seq 6400000 | tr 0-9 A-J)
> > >
> > > Here's a complete patch.
> > > I'll push it later today.
> >
> > Pushed along with two gnulib-related changes.
>
> The fix has improved some performance.  However, it's still quite slow
> compared to version 3.3, and that can be remedied.
>
> It converts to grep only if the potential match does not match the word
> frequently.

Thank you for that patch. Can you say a little more about the domain
of the problem?
I.e., is it specific to invocations with "-w"?
Can you provide an example that exhibits the performance improvement,
with timings?

Message #34 received at 44754 <at> debbugs.gnu.org (full text, mbox):

From: Frank Heckenbach <f.heckenbach <at> fh-soft.de>
To: noritnk <at> kcn.ne.jp, jim <at> meyering.net
Cc: 44754 <at> debbugs.gnu.org
Subject: Re: bug#44754: Extreme performance degradation in GNU grep 3.4 / 3.6
Date: Sun, 06 Dec 2020 06:34:11 +0100

Jim Meyering <jim <at> meyering.net> wrote:

> On Thu, Dec 3, 2020 at 12:26 AM Norihiro Tanaka <noritnk <at> kcn.ne.jp> wrote:
> > On Thu, 26 Nov 2020 21:41:20 -1000
> > Jim Meyering <jim <at> meyering.net> wrote:
> >
> > > On Thu, Nov 26, 2020 at 9:03 AM Jim Meyering <jim <at> meyering.net> wrote:
> > > >
> > > > On Wed, Nov 25, 2020 at 3:12 PM Jim Meyering <jim <at> meyering.net> wrote:
> > > > > Thank you for the fine bug report.
> > > > > The grep-3.6 bug you've exposed is due to the fact that your input
> > > > > triggers excessive hash collisions when using the code modeled after
> > > > > gnulib/lib/hash-pjw.c. That made the new pattern-preprocessing phase
> > > > > take O(N^2) time for N patterns. In the attached, I've switched grep
> > > > > to use the djb2 hash function, and that resolves the problem. I'll
> > > > > also add a NEWS entry and a test before pushing this.
> > > >
> > > > Timings suggest that grep-3.6's preprocessing came closer to O(N^3).
> > > > Here's an example that would take 2-3 days with grep-3.6 and only
> > > > seconds with this fix:
> > > >
> > > >   : | grep -Ff <(seq 6400000 | tr 0-9 A-J)
> > > >
> > > > Here's a complete patch.
> > > > I'll push it later today.
> > >
> > > Pushed along with two gnulib-related changes.
> >
> > The fix has improved some performance.  However, it's still quite slow
> > compared to version 3.3, and that can be remedied.
> >
> > It converts to grep only if the potential match does not match the word
> > frequently.
> 
> Thank you for that patch. Can you say a little more about the domain
> of the problem?
> I.e., is it specific to invocations with "-w"?
> Can you provide an example that exhibits the performance improvement,
> with timings?

I can confirm that it seems to solve my problem (my actual use
case):

grep-3.3:
real    0m0.861s
user    0m0.784s
sys     0m0.076s

grep-3.6 with this patch:
real    0m1.052s
user    0m0.943s
sys     0m0.108s

grep-3.6 with both your patch and this one:

real    0m1.097s
user    0m1.037s
sys     0m0.060s

Apparently there were at least two issues here. While your patch
fixes the simplified case I reported and had no effect on my actual
use case, Norihiro Tanaka's patch fixes the latter (and has no big
effect on the former).

So it looks like both patches are indeed needed.

Thanks,
Frank

Message #37 received at 44754 <at> debbugs.gnu.org (full text, mbox):

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: Jim Meyering <jim <at> meyering.net>
Cc: 44754 <at> debbugs.gnu.org, f.heckenbach <at> fh-soft.de
Subject: Re: bug#44754: Extreme performance degradation in GNU grep 3.4 / 3.6
Date: Mon, 07 Dec 2020 16:37:51 +0900

On Sat, 5 Dec 2020 10:06:27 -0800
Jim Meyering <jim <at> meyering.net> wrote:

> Thank you for that patch. Can you say a little more about the domain
> of the problem?
> I.e., is it specific to invocations with "-w"?
> Can you provide an example that exhibits the performance improvement,
> with timings?

The test case shown by Frank speeds-up about 10x.  That is a little
slower than grep 3.3.

Before:
$ env LC_ALL=C time -p src/grep -Fwif <(seq 300000 | tr 0-9 A-J) <<<foo
real 4.91
user 4.41
sys 0.30

After:
$ env LC_ALL=C time -p src/grep -Fwif <(seq 300000 | tr 0-9 A-J) <<<foo
real 0.37
user 0.16
sys 0.01

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.