On Mon, 19 Dec 2016 15:38:12 -0800 Paul Eggert <egg...@cs.ucla.edu> wrote:
> but the old 'replace' called 'delete' up to N times, Yes, but constraint == 0 does not happen mostly, so in delete() in "while" does not pass normally. > Anyway, I verified that the change improved performance on the test > case with -f /usr/share/dict/words (not as much as your earlier patch > improved things! just 5% to 10%, if I recall correctly), so even if > I'm wrong about the big-O improvement the change should still be a > win. Although I do not look at it, I agree your change, as I believe that the change does not cause slowdown for a case extreamly, > > 1. dfa is not optimize parsed patterns. > > For example, dfa does not replace pattern 'a \|a \|a \| ... \|a \|b' > > to 'a \|b'. > > > > I tried it several times, have not succeeded it yet. > > That sounds a bit like REduce: > > Valgenti VC, Kim MS, Oh S-I, Lee I. REduce: removing redundancy from > regular expression matching in network security. ICCCN 2015. > http://dx.doi.org/10.1109/ICCCN.2015.7288457 > > > > > 2. grep matcher compiles regex always to check syntax of a pattern, > > even when it is not used in searching. > > > > I also tried it, have not succeeded it yet. > > Yes, that sounds worthy too. Also, a lot of work has been done in > regular-expression matches over the past several years, and if > someone has the time it'd be nice to see whether GNU grep can use > this stuff on modern architectures. For example: > > Cameron RD, Medforth N, Lin D, Denis D, Sumner WN. Bitwise data > parallelism with LLVM: the icGrep case study. ICA3PP 2015. LNCS 9529. > http://dx.doi.org/10.1007/978-3-319-27122-4_26 > > Valgenti VC, Chhugani J, Sun Y, Satish N, Kim MS, Kim C, Dubey P. > GPP-grep: high-speed regular expression processing engine on general > purpose processors. RAID 2012. LNCS 7462. > http://dx.doi.org/10.1007/978-3-642-33338-5_17 Special thanks, I will keep them in the back of my head.
