grep's running time grows linearly with the -B/-C context value even when little or no context is ever printed, observed in production on multi-gigabyte log files with the Ubuntu 24.04 grep 3.11 package:
$ time grep pattern-that-never-matches 7.9GB.log -C1 # 4.2 s $ time grep pattern-that-never-matches 7.9GB.log -C10000 # 41 s Three independent causes, one patch each, plus tests; all present since the initial 1998 revision: 1. prtext's leading-context loop always iterates OUT_BEFORE times per matching line, even after reaching the boundary where remaining iterations are no-ops. (Visible only in default -O2 builds; GCC's -fsplit-loops, enabled at -O3 as used by Debian's packaging, happens to remove the no-op tail.) 2. grep() rescans backward over up to OUT_BEFORE saved context lines at every 96 KiB buffer refill to find where the context to save begins, rescanning the same bytes each time. This is the dominant cost in the log-file case above. 3. Binary-file detection calls buf_has_nulls on the whole buffer, including the saved context region, at every refill; with -C 1000000 on a 3.4 GB file this alone was over 600 s of strlen. After the series, a matchless -C 10000 search of a 3.4 GB file drops from 33.6 s to 2.5 s (stock -O2 build), and -C 1000000 from over 600 s to 5.0 s, with the residual growth being the unavoidable cost of maintaining the larger rolling context window. Patch 4 adds two tests: an expensive_-guarded timing test in the style of mb-non-UTF8-performance (it fails in under 30 s against unpatched grep and passes against patched grep, on both -O2 and -O3 builds), and a deterministic test comparing -A/-B/-C output against independently computed expected output on input whose match positions drift across buffer-refill boundaries. Verified with make check (no failures), plus 850+ differential comparisons against an unpatched build over context/invert/line number/max-count/binary-files option combinations, files with NUL bytes placed to land inside and outside the saved region, multi-refill inputs up to 50 MB, stdin input, and 120 randomized fuzz trials -- all byte-identical output and exit statuses. Edvard Davtyan (4): grep: avoid O(N) work per match with -B N / -C N grep: don't rescan saved context lines at every buffer refill grep: check only newly read bytes for encoding problems tests: exercise -B and -C with large context values NEWS | 9 ++++++ src/grep.c | 59 ++++++++++++++++++++++++++++------ tests/Makefile.am | 2 ++ tests/big-context-perf | 72 ++++++++++++++++++++++++++++++++++++++++++ tests/context-refill | 55 ++++++++++++++++++++++++++++++++ 5 files changed, 187 insertions(+), 10 deletions(-) create mode 100755 tests/big-context-perf create mode 100755 tests/context-refill -- 2.43.0
