fix slow searching of stdin with large values of -A/--after-context#3185
Merged
BurntSushi merged 2 commits intomasterfrom Oct 14, 2025
Merged
fix slow searching of stdin with large values of -A/--after-context#3185BurntSushi merged 2 commits intomasterfrom
stdin with large values of -A/--after-context#3185BurntSushi merged 2 commits intomasterfrom
Conversation
…g `stdin` This was a crazy subtle bug where ripgrep could slow down exponentially as increasingly larger values of `-A/--after-context` were used. But, interestingly, this would only occur when searching `stdin` and _not_ when searching the same data as a regular file. This confounded me because ripgrep, pretty early on, erases the difference between searching a single file and `stdin`. So it wasn't like there were different code paths. And I mistakenly assumed that they would otherwise behave the same as they are just treated as streams. But... it turns out that running `read` on a `stdin` versus a regular file seems to behave differently. At least on my Linux system, with `stdin`, `read` never seems to fill the buffer with more than 64K. But with a regular file, `read` pretty reliably fills the caller's buffer with as much space as declared. Of course, it is expected that `read` doesn't *have* to fill up the caller's buffer, and ripgrep is generally fine with that. But when `-A/--after-context` is used with a very large value---big enough that the default buffer capacity is too small---then more heap memory needs to be allocated to correctly handle all cases. This can result in passing buffers bigger than 64K to `read`. While we *correctly* handle `read` calls that don't fill the buffer, it turns out that if we don't fill the buffer, then we get into a pathological case where we aren't processing as many bytes as we could. That is, because of the `-A/--after-context` causing us to keep a lot of bytes around while we roll the buffer and because reading from `stdin` gives us fewer bytes than normal, we weren't amortizing our `read` calls as well as we should have been. Indeed, our buffer capacity increases specifically take this amortization into account, but we weren't taking advantage of it. We fix this by putting `read` into an inner loop that ensures our buffer gets filled up. This fixes the performance bug: ``` $ (time rg ZQZQZQZQZQ bigger.txt --no-mmap -A9999) | wc -l real 1.330 user 0.767 sys 0.559 maxmem 29 MB faults 0 10000 $ cat bigger.txt | (time rg ZQZQZQZQZQ --no-mmap -A9999) | wc -l real 2.355 user 0.860 sys 0.613 maxmem 29 MB faults 0 10000 $ (time rg ZQZQZQZQZQ bigger.txt --no-mmap -A99999) | wc -l real 3.636 user 3.091 sys 0.537 maxmem 29 MB faults 0 100000 $ cat bigger.txt | (time rg ZQZQZQZQZQ --no-mmap -A99999) | wc -l real 4.918 user 3.236 sys 0.710 maxmem 29 MB faults 0 100000 $ (time rg ZQZQZQZQZQ bigger.txt --no-mmap -A999999) | wc -l real 5.430 user 4.666 sys 0.750 maxmem 51 MB faults 0 1000000 $ cat bigger.txt | (time rg ZQZQZQZQZQ --no-mmap -A999999) | wc -l real 6.894 user 4.907 sys 0.850 maxmem 51 MB faults 0 1000000 ``` For comparison, here is GNU grep: ``` $ cat bigger.txt | (time grep ZQZQZQZQZQ -A9999) | wc -l real 1.466 user 0.159 sys 0.839 maxmem 29 MB faults 0 10000 $ cat bigger.txt | (time grep ZQZQZQZQZQ -A99999) | wc -l real 1.663 user 0.166 sys 0.941 maxmem 29 MB faults 0 100000 $ cat bigger.txt | (time grep ZQZQZQZQZQ -A999999) | wc -l real 1.631 user 0.204 sys 0.910 maxmem 29 MB faults 0 1000000 ``` GNU grep is still notably faster. We'll fix that in the next commit. Fixes #3184
Previously (with the previous commit): ``` $ cat bigger.txt | (time rg ZQZQZQZQZQ -A999) | wc -l real 2.321 user 0.674 sys 0.735 maxmem 30 MB faults 0 1000 $ cat bigger.txt | (time rg ZQZQZQZQZQ -A9999) | wc -l real 2.513 user 0.823 sys 0.686 maxmem 30 MB faults 0 10000 $ cat bigger.txt | (time rg ZQZQZQZQZQ -A99999) | wc -l real 5.067 user 3.254 sys 0.676 maxmem 30 MB faults 0 100000 $ cat bigger.txt | (time rg ZQZQZQZQZQ -A999999) | wc -l real 6.658 user 4.841 sys 0.778 maxmem 51 MB faults 0 1000000 ``` Now with this commit: ``` $ cat bigger.txt | (time rg ZQZQZQZQZQ -A999) | wc -l real 1.845 user 0.328 sys 0.757 maxmem 30 MB faults 0 1000 $ cat bigger.txt | (time rg ZQZQZQZQZQ -A9999) | wc -l real 1.917 user 0.334 sys 0.771 maxmem 30 MB faults 0 10000 $ cat bigger.txt | (time rg ZQZQZQZQZQ -A99999) | wc -l real 1.972 user 0.319 sys 0.812 maxmem 30 MB faults 0 100000 $ cat bigger.txt | (time rg ZQZQZQZQZQ -A999999) | wc -l real 2.005 user 0.333 sys 0.855 maxmem 30 MB faults 0 1000000 ``` And compare to GNU grep: ``` $ cat bigger.txt | (time grep ZQZQZQZQZQ -A999) | wc -l real 1.488 user 0.143 sys 0.866 maxmem 30 MB faults 0 1000 $ cat bigger.txt | (time grep ZQZQZQZQZQ -A9999) | wc -l real 1.697 user 0.170 sys 0.986 maxmem 30 MB faults 1 10000 $ cat bigger.txt | (time grep ZQZQZQZQZQ -A99999) | wc -l real 1.515 user 0.166 sys 0.856 maxmem 29 MB faults 0 100000 $ cat bigger.txt | (time grep ZQZQZQZQZQ -A999999) | wc -l real 1.490 user 0.174 sys 0.851 maxmem 30 MB faults 0 1000000 ``` Interestingly, GNU grep is still a bit faster. But both commands remain roughly invariant in search time as `-A` is increased. There is definitely something "odd" about searching `stdin`, where it seems substantially slower. We can also observe with GNU grep: ``` $ (time grep ZQZQZQZQZQ -A999999 bigger.txt) | wc -l real 0.692 user 0.184 sys 0.506 maxmem 30 MB faults 0 1000000 $ cat bigger.txt | (time grep ZQZQZQZQZQ -A999999) | wc -l real 1.700 user 0.201 sys 0.954 maxmem 30 MB faults 0 1000000 $ (time rg ZQZQZQZQZQ -A999999 bigger.txt) | wc -l real 0.640 user 0.428 sys 0.209 maxmem 7734 MB faults 0 1000000 $ (time rg ZQZQZQZQZQ --no-mmap -A999999 bigger.txt) | wc -l real 0.866 user 0.282 sys 0.581 maxmem 30 MB faults 0 1000000 $ cat bigger.txt | (time rg ZQZQZQZQZQ -A999999) | wc -l real 1.991 user 0.338 sys 0.819 maxmem 30 MB faults 0 1000000 ``` I wonder if this is related to my discovery in the previous commit where `read` calls on `stdin` seem to never return anything more than ~64K. Oh well, I'm satisfied at this point, especially given that GNU grep seems to do a lot worse than ripgrep with bigger values of `-B/--before-context`: ``` $ cat bigger.txt | (time grep ZQZQZQZQZQ -B9) | wc -l real 1.568 user 0.170 sys 0.885 maxmem 30 MB faults 0 1 $ cat bigger.txt | (time grep ZQZQZQZQZQ -B99) | wc -l real 1.734 user 0.338 sys 0.879 maxmem 30 MB faults 0 1 $ cat bigger.txt | (time grep ZQZQZQZQZQ -B999) | wc -l real 2.349 user 1.723 sys 0.620 maxmem 30 MB faults 0 1 $ cat bigger.txt | (time grep ZQZQZQZQZQ -B9999) | wc -l real 16.459 user 15.848 sys 0.586 maxmem 30 MB faults 0 1 $ time grep ZQZQZQZQZQ -B99999 bigger.txt ZQZQZQZQZQ real 1:45.06 user 1:44.12 sys 0.772 maxmem 30 MB faults 0 ``` The above pattern occurs regardless of whether you put `bigger.txt` on stdin or whether you search it directly. And now ripgrep: ``` $ cat bigger.txt | (time rg ZQZQZQZQZQ -B9) | wc -l real 1.965 user 0.326 sys 0.814 maxmem 29 MB faults 0 1 $ cat bigger.txt | (time rg ZQZQZQZQZQ -B99) | wc -l real 1.941 user 0.423 sys 0.813 maxmem 29 MB faults 0 1 $ cat bigger.txt | (time rg ZQZQZQZQZQ -B999) | wc -l real 2.372 user 0.759 sys 0.703 maxmem 30 MB faults 0 1 $ cat bigger.txt | (time rg ZQZQZQZQZQ -B9999) | wc -l real 2.638 user 0.895 sys 0.665 maxmem 29 MB faults 0 1 $ cat bigger.txt | (time rg ZQZQZQZQZQ -B99999) | wc -l real 5.172 user 3.282 sys 0.748 maxmem 29 MB faults 0 1 ``` NOTE: To get `bigger.txt`: ``` $ curl -LO 'https://burntsushi.net/stuff/opensubtitles/2018/en/sixteenth.txt.gz' $ gzip -d sixteenth.txt.gz $ (echo ZQZQZQZQZQ && for ((i=0;i<10;i++)); do cat sixteenth.txt; done) > bigger.txt ```
stdin with large values of -A/--after-context
1 task
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
The commit messages have the details, but:
stdin, at least on my Linux machine, calls toreadnever seem to return more than 64K. This caused a pathological problem with large values of-A/--after-contextthat prevented ripgrep from amortizingreadcalls as well as it should.-A/--after-contextis used, we don't need to find the last N lines before rolling our search buffer. We still do when-B/--before-contextis set though. And indeed, this can cause ripgrep to be materially slower with large values of-Bbut not with-A. Indeed, GNU grep suffers from a similar problem (but is far far slower than ripgrep).Fixes #3184