* tests/big-context-perf: New test for the performance fixes in the previous three commits. * tests/context-refill: New test checking -A/-B/-C output when context repeatedly spans input buffer refills. * tests/Makefile.am (TESTS): Add them. --- tests/Makefile.am | 2 ++ tests/big-context-perf | 74 ++++++++++++++++++++++++++++++++++++++++++ tests/context-refill | 62 +++++++++++++++++++++++++++++++++++ 3 files changed, 138 insertions(+) create mode 100755 tests/big-context-perf create mode 100755 tests/context-refill
diff --git a/tests/Makefile.am b/tests/Makefile.am index eeb20f0..2753604 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -74,6 +74,7 @@ TESTS = \ backslash-dot \ backslash-s-and-repetition-operators \ backslash-s-vs-invalid-multibyte \ + big-context-perf \ big-hole \ big-match \ binary-file-matches \ @@ -90,6 +91,7 @@ TESTS = \ char-class-multibyte2 \ color-colors \ context-0 \ + context-refill \ count-newline \ dfa-coverage \ dfa-heap-overrun \ diff --git a/tests/big-context-perf b/tests/big-context-perf new file mode 100755 index 0000000..c8ba69a --- /dev/null +++ b/tests/big-context-perf @@ -0,0 +1,74 @@ +#!/bin/sh +# Test for these performance regressions: +# grep through 3.12 would take time proportional to the -B/-C context +# value per buffer refill and per matching line, so large context +# values made grep quadratically slow. + +# Copyright 2026 Free Software Foundation, Inc. + +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. + +# You should have received a copy of the GNU General Public License +# along with this program. If not, see <https://www.gnu.org/licenses/>. + +. "${srcdir=.}/init.sh"; path_prepend_ ../src + +fail=0 + +# This test is susceptible to failure due to differences in +# system load during the two test runs, so we'll mark it as +# "expensive", making it less likely to be run by regular users. +expensive_ +require_perl_ + +# A pattern that never matches seq output but whose frequent partial +# matches make the search cost enough user time to be measurable. +pat=87654321987 + +# Make the input large enough so that even on high-end systems +# the small-context test takes at least 50ms of user time. +n_lines=4000000 +while :; do + seq $n_lines > in || framework_failure_ + small_ms=$(LC_ALL=C user_time_ 1 grep -C 1 $pat in) || fail=1 + test $small_ms -ge 50 && break + n_lines=$(expr $n_lines '*' 2) + case $n_lines:$small_ms in + 128000000:0) skip_ 'user_time_ appears always to report 0 elapsed ms';; + esac +done + +# With a large -C, each buffer refill used to rescan all saved context +# lines to find where the context to save begins, and to recheck them +# for null bytes. +large_ms=$(LC_ALL=C user_time_ 1 grep -C 400000 $pat in) || fail=1 + +# Deliberately recording in an unused variable so it +# shows up in set -x output, in case this test fails. +ratio=$(expr "$large_ms" / "$small_ms") + +# The duration of the large-context run must be no more than 10 times +# that of the small-context one. Before the fix, ratios over 25 were +# typical; after it, ratios are below 4. +returns_ 1 expr $small_ms '<' $large_ms / 10 || fail=1 + +# With a large -B and every line matching, printing each line used to +# iterate up to the full -B value even with no context left to print. +# Send the output to a regular file: grep prints nothing when it +# detects that stdout is /dev/null, bypassing the code being tested. +small_ms=$(LC_ALL=C user_time_ 0 sh -c 'grep -B 1 . in > out') || fail=1 +large_ms=$(LC_ALL=C user_time_ 0 sh -c 'grep -B 5000 . in > out') || fail=1 + +ratio=$(expr "$large_ms" / "$small_ms") + +returns_ 1 expr $small_ms '<' $large_ms / 10 || fail=1 + +Exit $fail diff --git a/tests/context-refill b/tests/context-refill new file mode 100755 index 0000000..34efd99 --- /dev/null +++ b/tests/context-refill @@ -0,0 +1,62 @@ +#!/bin/sh +# Exercise -A, -B and -C with context that repeatedly spans input +# buffer refills, checking output against independently computed +# expected output. + +# Copyright 2026 Free Software Foundation, Inc. + +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. + +# You should have received a copy of the GNU General Public License +# along with this program. If not, see <https://www.gnu.org/licenses/>. + +. "${srcdir=.}/init.sh"; path_prepend_ ../src + +fail=0 + +# 300000 lines of about 60 bytes, with TARGET on every 9973rd line. +# The prime spacing makes match positions drift relative to buffer +# refills, and context of 2000 such lines spans more than one refill. +# Since 9973 > 2000 + 2000 + 1, context groups never touch, so a +# group separator always appears between them. +awk 'BEGIN { + pad = "_________________________________________________" + for (i = 1; i <= 300000; i++) + print i (i % 9973 ? "" : " TARGET") pad +}' > in || framework_failure_ + +for opt in '-C 2000' '-B 2000' '-A 2000' '-C 5'; do + grep -n $opt TARGET in > out || fail=1 + awk -v opt="$opt" 'BEGIN { + split(opt, a, " ") + # -C requests both leading and trailing context lines, + # -B only leading, -A only trailing. + before = a[1] == "-A" ? 0 : a[2] + after = a[1] == "-B" ? 0 : a[2] + pad = "_________________________________________________" + n = 300000 + sep = "" + for (p = 9973; p <= n; p += 9973) { + lo = p - before < 1 ? 1 : p - before + hi = p + after > n ? n : p + after + printf "%s", sep + sep = "--\n" + # grep -n writes "N:" before matching lines and "N-" before + # context lines; each input line then begins with its own + # line number. + for (i = lo; i <= hi; i++) + print i (i == p ? ":" : "-") i (i % 9973 ? "" : " TARGET") pad + } + }' > exp || framework_failure_ + compare exp out || fail=1 +done + +Exit $fail -- 2.43.0
