GNU bug report logs - #17700
[PATCH] dfa: speed-up for a pattern that many atoms are catenated

Previous Next

Package: grep;

Reported by: Norihiro Tanaka <noritnk <at> kcn.ne.jp>

Date: Thu, 5 Jun 2014 11:41:01 UTC

Severity: normal

Tags: patch

Done: Norihiro Tanaka <noritnk <at> kcn.ne.jp>

Bug is archived. No further changes may be made.

Full log


View this message in rfc822 format

From: help-debbugs <at> gnu.org (GNU bug Tracking System)
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Subject: bug#17700: closed (Re: bug#17700: [PATCH] dfa: speed-up for a
 pattern that many atoms are catenated)
Date: Fri, 06 Jun 2014 13:20:03 +0000
[Message part 1 (text/plain, inline)]
Your bug report

#17700: [PATCH] dfa: speed-up for a pattern that many atoms are catenated

which was filed against the grep package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to 17700 <at> debbugs.gnu.org.

-- 
17700: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=17700
GNU Bug Tracking System
Contact help-debbugs <at> gnu.org with problems
[Message part 2 (message/rfc822, inline)]
From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: Aharon Robbins <arnold <at> skeeve.com>, 17700-done <at> debbugs.gnu.org
Subject: Re: bug#17700: [PATCH] dfa: speed-up for a pattern that many atoms
 are catenated
Date: Fri, 06 Jun 2014 22:19:13 +0900
Paul Eggert wrote:
> So it looks like your patch confers some advantage, but on my platform
> almost all the speedup is achieved simply by switching to the system strstr.

First, I tested on CentOS 5.10.  Next, I tested on RHEL 6.5, and get
result as same as you.  strstr() on CentOS 5.10 may be too old.  I'm
sure that this bug has already been fixed.  So closing.

Thanks,
Norihiro


[Message part 3 (message/rfc822, inline)]
From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: bug-grep <at> gnu.org
Subject: [PATCH] dfa: speed-up for a pattern that many atoms are catenated
Date: Thu, 05 Jun 2014 20:32:44 +0900
[Message part 4 (text/plain, inline)]
When many atoms are catenated, dfamust() is very slow in order that
pushing a string into `in' list is slow.  This change fixes it.

I tested below to confirm the effect.

  $ printf '%08192d\n' 0 | time -p src/grep -f - /dev/null
[0001-dfa-speed-up-for-a-pattern-that-many-atoms-are-caten.patch (text/plain, attachment)]

This bug report was last modified 11 years and 42 days ago.

Previous Next


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