With -B N (and -C N), prtext's leading-context loop always iterated
N times per matching line, even after reaching the start of unprinted
input, where remaining iterations are no-ops. With many matching
lines and large N, this cost O(N) time per match -- quadratic overall
behavior -- unless the compiler happened to rescue it (GCC removes
the no-op tail only with -fsplit-loops, enabled at -O3 but not at
the default -O2). For example, with a stock '-g -O2' build on
20,000 matching lines, 'grep -B 1000000 x' took 5.1 s versus 0.01 s
for 'grep -B 1000'; after this change both take 0.01 s. Exit the
loop as soon as the boundary is reached, as the analogous loop in
grep() already does; output is unchanged.
* src/grep.c (prtext): Move the 'p > bp' test from the loop body
into the loop condition, so the loop exits once P reaches BP
instead of continuing to iterate up to OUT_BEFORE times.
---
src/grep.c | 9 ++++-----
1 file changed, 4 insertions(+), 5 deletions(-)
diff --git a/src/grep.c b/src/grep.c
index 841e225..8e4ecff 100644
--- a/src/grep.c
+++ b/src/grep.c
@@ -1383,11 +1383,10 @@ prtext (char *beg, char *lim)
/* Deal with leading context. */
char const *bp = lastout ? lastout : bufbeg;
intmax_t i;
- for (i = 0; i < out_before; ++i)
- if (p > bp)
- do
- --p;
- while (p[-1] != eol);
+ for (i = 0; i < out_before && p > bp; ++i)
+ do
+ --p;
+ while (p[-1] != eol);
/* Print the group separator unless the output is adjacent to
the previous output in the file. */
--
2.43.0
