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
grep of MacOS nor in any
sed version where I mainly use backreferences.