3

Let's say I have a text file with 20 chars per line like this:

wertzuiopasdfghjkl<
asdfghjkl<yxcvbnm,.-
<yxcvbnm,.-123456789
1234567890QWERTZUIOP
QWERTZUIOPASDFGHJKL<

and so on ...

and I want the lines the contain at least two identical chars, I can use grep like this

grep '\(.\).*\1' n20x1M

with a backreference. This takes 15.7 s on my machine for a million lines without match.

If I double the number of rows, the used cpu time is also doubled to 31.4, as expected.

I also expect the time to double if I have 28 columns instead of 20 (20 chars give 190 possible combinations to test, 28 chars give 378 possible combinations). But it's only 28,2 s on my machine.

So the slowdown of backreferencing is not just by the pure number of combinations to test? I tried this one:

grep '^\(.\).*\1' n20x1M

which drastically melts down the number of combinations from 190 to only 19: Just read the first char and see if it matches one of the remaining chars. This should take only 1.6 s, but it takes 2.8 s!

Maybe some overhead for reading the lines into memory and into cache? No, if I do

grep '.*_' n20x1M

it's only 0.004 s processing time! It's mainly doing the same (searching for a char in a line of 20 chars), but by simply not giving a fixed char but instead searching for the first char of the line among the remaining 19 chars, I get a slowdown of more than factor 1000!

Is there an error in my understanding?

Is there so much hidden overhead introduced by the backreference?

Or is backreferencing in GNU regex badly implemented?

Who can explain what is happening here?

What can I do to improve performance?

Update @Sundeep mentioned the disclaimer about slow backreferences. But that's the calculated effect caused by too many possible solutions. I expected this, but there is an additional penalty for using them even if they don't add complexity.

It really seems to be an implementation issue, as with his other hint to use option -P, I get a speedup from 15.4 s to 2.0 s!

The trivial case with the ^ anchor gets a speedup from 2.8 s to 0.25 s, but still doesn't meet searching for a fixed char (0.004 s). Funny enough, with option -P, the fixed char case gets slowed down to 0.13 s, so there is less penalty for the backreference, but more like an overall penalty ...

Unfortunally, I neither have -P in grep of MacOS nor in any sed version where I mainly use backreferences.

  • 1
    from man page of GNU grep: Back-references are very slow, and may require exponential time... if you have PCRE option, grep -P will certainly speed things up – Sundeep Jul 12 '17 at 6:03
  • and there is a bug I found(debbugs.gnu.org/cgi/bugreport.cgi?bug=26864) as well when using obscure back-references – Sundeep Jul 12 '17 at 6:04
  • for ex: grep -xP '([a-d]..)\1' /usr/share/dict/words takes about 0m0.007s (multiple runs) while grep -xE '([a-d]..)\1' takes about 0m0.222s – Sundeep Jul 12 '17 at 6:07
  • 1
    @Sundeep Interesting, I updated my question. The bug with nested backreferences doesn't seem related to me; I try to avoid them. – Philippos Jul 12 '17 at 6:52
  • you can perhaps use perl? it seems faster then grep when using backreferences... perl -ne 'print if /^([a-d]..)\1$/' /usr/share/dict/words is about 0m0.052s – Sundeep Jul 12 '17 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.