[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Paul Eggert
Subject: bug#24009: [PATCH] grep: use fastmap in regex
Date: Thu, 1 Sep 2016 22:32:12 -0700
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0

Norihiro Tanaka wrote:
I think this patch should be suspended because of this issue.
I reported it to glibc developers.  

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!

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

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]