bug#44754: Extreme performance degradation in GNU grep 3.4 / 3.6

[Norihiro Tanaka]

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

> On Thu, Nov 26, 2020 at 9:03 AM Jim Meyering <jim@meyering.net> wrote:
> >
> > On Wed, Nov 25, 2020 at 3:12 PM Jim Meyering <jim@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
Description: Text document