Searcher: make hot loop lock free
Created by: camdencheek
So, I took another pass at optimizing the hot file iteration loop in searcher, and found a few modest gains. Basically, this takes all the operations in the worker goroutines and makes them lockfree. This has the most visible effect on cheap searches (e.g. literal, case sensitive) because iterating over files is a much larger proportion of the work done, so lock contention is meaningful.
The first commit makes iterating over the list of files lockfree by atomically incrementing an index variable and exiting when the index is outside the range of the list of files.
The second commit makes sender lockfree using the same techniques as we do here. We still require the callback to hold a mutex (both for the benchmarks and in real life), so sending results isn't lockfree, but the important part is that sender.Remaining() no longer requires holding a mutex because that is called on every file searched.
The third commit uses an atomic boolean instead of checking ctx.Err() each iteration, which requires a mutex lock. This does require creating a new goroutine, but the benchmarks seemed to indicate that the overhead pays off. An alternative here would be to only check the context every n iterations, but that means we could end up searching extra (maybe very large) files, so I think this is a better tradeoff from a worst-case perspective.
I had previously tried some of these out, but the effects are far less visible before the memory optimizations I made in https://github.com/sourcegraph/sourcegraph/pull/38507.
Test plan
Added tests for the limiting stream, which apparently didn't exist.
Benchmark results:
❯ benchstat -alpha 0.1 /tmp/baseline.txt /tmp/lockfree_ctx.txt
name old time/op new time/op delta
SearchRegex_large_fixed-10 6.20ms ± 0% 5.37ms ± 6% -13.30% (p=0.008 n=5+5)
SearchRegex_rare_fixed-10 7.76ms ± 4% 6.92ms ± 1% -10.85% (p=0.008 n=5+5)
SearchRegex_large_fixed_casesensitive-10 3.92ms ± 1% 2.68ms ± 4% -31.54% (p=0.008 n=5+5)
SearchRegex_large_re_dotstar-10 217ms ± 2% 214ms ± 2% ~ (p=0.310 n=5+5)
SearchRegex_large_re_common-10 6.01ms ± 7% 4.83ms ± 1% -19.61% (p=0.008 n=5+5)
SearchRegex_large_re_anchor-10 70.0ms ± 1% 68.7ms ± 1% -1.86% (p=0.032 n=5+5)
SearchRegex_large_path/path_only-10 301µs ± 1% 302µs ± 0% ~ (p=0.222 n=5+5)
SearchRegex_large_path/content_only-10 6.84ms ± 1% 6.81ms ± 1% ~ (p=0.548 n=5+5)
SearchRegex_large_path/both_path_and_content-10 6.86ms ± 2% 6.73ms ± 1% -1.90% (p=0.016 n=5+5)
SearchRegex_small_fixed-10 132µs ± 0% 130µs ± 0% -1.81% (p=0.008 n=5+5)
SearchRegex_small_fixed_casesensitive-10 86.1µs ± 0% 85.4µs ± 0% -0.74% (p=0.016 n=4+5)
SearchRegex_small_re_dotstar-10 2.23ms ± 0% 2.30ms ± 4% ~ (p=0.310 n=5+5)
SearchRegex_small_re_common-10 87.4µs ± 1% 85.0µs ± 0% -2.71% (p=0.016 n=5+4)
SearchRegex_small_re_anchor-10 769µs ± 0% 767µs ± 1% ~ (p=0.222 n=5+5)
name old alloc/op new alloc/op delta
SearchRegex_large_fixed-10 15.7MB ± 0% 15.7MB ± 0% ~ (p=0.421 n=5+5)
SearchRegex_rare_fixed-10 15.7MB ± 0% 15.7MB ± 0% ~ (p=0.222 n=5+5)
SearchRegex_large_fixed_casesensitive-10 9.89kB ± 0% 10.26kB ± 0% +3.66% (p=0.016 n=4+5)
SearchRegex_large_re_dotstar-10 570MB ± 0% 570MB ± 0% ~ (p=0.310 n=5+5)
SearchRegex_large_re_common-10 6.40MB ± 0% 6.40MB ± 0% -0.04% (p=0.095 n=5+5)
SearchRegex_large_re_anchor-10 4.27MB ± 0% 4.26MB ± 1% ~ (p=0.841 n=5+5)
SearchRegex_large_path/path_only-10 1.03kB ± 1% 1.01kB ± 1% -1.55% (p=0.008 n=5+5)
SearchRegex_large_path/content_only-10 50.6kB ± 0% 51.4kB ± 1% +1.59% (p=0.016 n=4+5)
SearchRegex_large_path/both_path_and_content-10 50.6kB ± 0% 51.2kB ± 1% +1.25% (p=0.008 n=5+5)
SearchRegex_small_fixed-10 360kB ± 0% 348kB ± 0% -3.24% (p=0.008 n=5+5)
SearchRegex_small_fixed_casesensitive-10 4.71kB ± 0% 5.08kB ± 0% +7.87% (p=0.008 n=5+5)
SearchRegex_small_re_dotstar-10 3.75MB ± 0% 3.75MB ± 0% -0.08% (p=0.032 n=5+5)
SearchRegex_small_re_common-10 38.7kB ± 0% 39.1kB ± 0% +1.00% (p=0.008 n=5+5)
SearchRegex_small_re_anchor-10 18.3kB ± 0% 18.7kB ± 0% +2.33% (p=0.008 n=5+5)
name old allocs/op new allocs/op delta
SearchRegex_large_fixed-10 186 ± 1% 188 ± 1% ~ (p=0.111 n=5+5)
SearchRegex_rare_fixed-10 492 ± 0% 493 ± 0% ~ (p=0.246 n=5+5)
SearchRegex_large_fixed_casesensitive-10 138 ± 0% 142 ± 0% +2.90% (p=0.008 n=5+5)
SearchRegex_large_re_dotstar-10 4.51M ± 0% 4.51M ± 0% ~ (p=0.841 n=5+5)
SearchRegex_large_re_common-10 50.6k ± 0% 50.6k ± 0% ~ (p=0.333 n=5+5)
SearchRegex_large_re_anchor-10 37.9k ± 0% 37.9k ± 0% ~ (p=0.190 n=5+5)
SearchRegex_large_path/path_only-10 20.0 ± 0% 19.0 ± 0% -5.00% (p=0.008 n=5+5)
SearchRegex_large_path/content_only-10 462 ± 0% 466 ± 0% +0.87% (p=0.008 n=5+5)
SearchRegex_large_path/both_path_and_content-10 462 ± 0% 466 ± 0% +0.87% (p=0.008 n=5+5)
SearchRegex_small_fixed-10 82.0 ± 0% 85.6 ± 1% +4.39% (p=0.008 n=5+5)
SearchRegex_small_fixed_casesensitive-10 74.0 ± 0% 78.0 ± 0% +5.41% (p=0.008 n=5+5)
SearchRegex_small_re_dotstar-10 29.6k ± 0% 29.6k ± 0% +0.01% (p=0.008 n=5+5)
SearchRegex_small_re_common-10 387 ± 0% 391 ± 0% +1.03% (p=0.008 n=5+5)
SearchRegex_small_re_anchor-10 235 ± 0% 239 ± 0% +1.70% (p=0.008 n=5+5)