bug#24009: [PATCH] grep: use fastmap in regex

[Paul Eggert]

Norihiro Tanaka wrote:
> I think this patch should be suspended because of this issue.
> I reported it to glibc developers.  
> https://sourceware.org/bugzilla/show_bug.cgi?id=20381

After thinking about it a bit, I came up with a variant of the patch that gives 
the performance improvement unless -i is used, so I installed the attached 
patches. The first patch is mostly just refactoring this somewhat-crufty code 
and fixing an O(N**2) reallocation problem. The second is the real improvement.

The second patch just captures the low-hanging fruit. For example, even with -i 
we could use a fastmap if all the pattern's letters (including letters matched 
by ranges) happen to avoid the glibc bug. Something like that might be worth 
pursuing.

Since the attached patch fixes the test case that prompted the bug report I'm 
closing the bug. We can reopen it, or open a new one, if someone wants to fix 
the remaining performance glitches.

Thanks again for all these fixes!

0001-grep-improve-dfasearch-storage-management.patch
Description: Text Data

0002-grep-use-regex-fastmap-unless-i.patch
Description: Text Data