With -B N or -C N, each refill of the input buffer scanned backward
over as many as N lines to find the start of the leading context to
save, rescanning the same saved bytes at every refill. Each 96 KiB
read therefore cost O(N) extra time, making grep's total running time
grow linearly with N -- e.g., a matchless search of a 3.4 GB log file
took 1.3 s with -C 1 but 33.6 s with -C 10000. Instead, remember how
many complete lines the saved region holds, scan backward only over
the data read this iteration, and when older lines are needed, skip
forward past the lines dropped from the region's front, so each byte
is scanned O(1) times regardless of N.
* src/grep.c (grep): New local NSAVED, the count of saved
leading-context lines. Compute the context start from NSAVED and the
newly read lines instead of rescanning from the end of the buffer,
and decrease NSAVED when prpending prints saved lines.
---
src/grep.c | 45 +++++++++++++++++++++++++++++++++++++++++----
1 file changed, 41 insertions(+), 4 deletions(-)
diff --git a/src/grep.c b/src/grep.c
index 8e4ecff..a5afbe5 100644
--- a/src/grep.c
+++ b/src/grep.c
@@ -1510,7 +1510,7 @@ grepbuf (char *beg, char const *lim)
static intmax_t
grep (int fd, struct stat const *st, bool *ineof)
{
- intmax_t nlines, i;
+ intmax_t nlines, i, nsaved;
idx_t residue, save;
char eol = eolbyte;
char nul_zapper = '\0';
@@ -1537,6 +1537,7 @@ grep (int fd, struct stat const *st, bool *ineof)
nlines = 0;
residue = 0;
save = 0;
+ nsaved = 0;
if (! fillbuf (save, st))
{
@@ -1596,12 +1597,25 @@ grep (int fd, struct stat const *st, bool *ineof)
char *lim = last_eol ? last_eol + 1 : beg;
residue = buflim - lim;
+ /* This iteration scans data starting here. Before it lie the
+ NSAVED leading-context lines saved by the previous iteration. */
+ char const *round_beg = beg;
+
if (beg < lim)
{
if (outleft)
nlines += grepbuf (beg, lim);
if (pending)
- prpending (lim);
+ {
+ intmax_t pend0 = pending;
+ bool from_saved = lastout && lastout < round_beg;
+ prpending (lim);
+ /* Lines printed from before ROUND_BEG were saved
+ leading-context lines; do not count them as saved
+ any longer. */
+ if (from_saved)
+ nsaved -= MIN (nsaved, pend0 - pending);
+ }
if ((!outleft && !pending)
|| (done_on_match && MAX (0, nlines_first_null) < nlines))
goto finish_grep;
@@ -1609,10 +1623,12 @@ grep (int fd, struct stat const *st, bool *ineof)
/* The last OUT_BEFORE lines at the end of the buffer will be needed as
leading context if there is a matching line at the begin of the
- next data. Make beg point to their begin. */
+ next data. Make beg point to their begin. Scan backward only
+ over the lines read this iteration. */
+ char const *stop = lastout && lastout > round_beg ? lastout : round_beg;
i = 0;
beg = lim;
- while (i < out_before && beg > bufbeg && beg != lastout)
+ while (i < out_before && beg > stop)
{
++i;
do
@@ -1620,6 +1636,27 @@ grep (int fd, struct stat const *st, bool *ineof)
while (beg[-1] != eol);
}
+ /* If more lines are needed, extend into the yet-unprinted lines
+ saved by the previous iteration, between LASTOUT (or BUFBEG)
+ and ROUND_BEG. Skip forward past the lines dropped from their
+ front rather than rescanning backward from LIM, so that each
+ saved byte is scanned O(1) times no matter how large
+ OUT_BEFORE is. */
+ if (i < out_before && beg == round_beg
+ && (!lastout || lastout < round_beg))
+ {
+ intmax_t take = MIN (out_before - i, nsaved);
+ char *p = lastout ? lastout : bufbeg;
+ for (intmax_t drop = nsaved - take; 0 < drop; drop--)
+ {
+ char *nl = rawmemchr (p, eol);
+ p = nl + 1;
+ }
+ beg = p;
+ i += take;
+ }
+ nsaved = i;
+
/* Detect whether leading context is adjacent to previous output. */
if (beg != lastout)
lastout = nullptr;
--
2.43.0
