grep: make threading smarter
cover grep: make threading smarter
833e3df171 (pack-objects: Add runtime detection of online CPU's, 2008-02-22) added the capability to check the number of online CPUs at runtime to do better threading, so use that as well with grep.
Testing with a large (more than 4) number of cores and no grep.threads configuration in real hardware encouraged, to confirm that no other bottleneck is preventing the additional threads to improve performance.
If platform specific testing shows degradation (specially with HP-UX), make sure that the right number of CPUs is reported by :
$ ./t/helper/test-tool online-cpus 4
There are additional cleanups possible in the grep code but had left it out of this RFC to avoid confusion and make the change in patch 2 as straight forward as possible.
There is also a chance that the online_cpus() function will be updated as it predates POSIX and might be associated with one known performance issue in HP-UX[1]
Lastly the performance numbers point to deficiencies in kwset and the compat/regex code that will need to be addressed independently.
Carlo Marcelo Arenas Belón (2):
p7810: add more grep performance relevant cases
grep: make default number of threads reflect runtime
Documentation/git-grep.txt | 2 +- builtin/grep.c | 3 +-- t/perf/p7810-grep.sh | 25 +++++++++++++++++++++++-- 3 files changed, 25 insertions(+), 5 deletions(-)
Signature · 1 line
2.23.0.rc1
RFC PATCH 1/2 p7810: add more grep performance relevant cases
Add a baseline for a matching regex and make clear the distinction between fixed (now using kwset) and a real simple expression.
--- t/perf/p7810-grep.sh | 25 +++++++++++++++++++++++-- 1 file changed, 23 insertions(+), 2 deletions(-)
t/perf/p7810-grep.sh +23 -2
@@ -7,13 +7,34 @@ test_description="git-grep performance in various modes" test_perf_large_repo test_checkout_worktree -test_perf 'grep worktree, cheap regex' ' +test_perf 'grep worktree, fixed regex (no match)' ' git grep some_nonexistent_string || : ' +test_perf 'grep worktree, fixed regex (common)' ' + git grep void || : +' +test_perf 'grep -I, fixed non binary regex (common)' ' + git grep -i void || : +' +test_perf 'grep -i, fixed caseless regex (common)' ' + git grep -i void || : +' +test_perf 'grep --no-index, fixed regex (common)' ' + git grep --no-index void || : +' +test_perf 'grep worktree, simple regex (common)' ' + git grep "void|int" || : +' +test_perf 'grep -I, simple non binary regex (common)' ' + git grep -I "void|int" || : +' +test_perf 'grep -i, simple caseless regex (common)' ' + git grep -i "void|int" || : +' test_perf 'grep worktree, expensive regex' ' git grep "^.* *some_nonexistent_string$" || : ' -test_perf 'grep --cached, cheap regex' ' +test_perf 'grep --cached, fixed regex' ' git grep --cached some_nonexistent_string || : ' test_perf 'grep --cached, expensive regex' '
Signature · 1 line
2.23.0.rc1
RFC PATCH 2/2 grep: make default number of threads reflect runtime
In reply to Carlo Marcelo Arenas Belón5b594f457a (Threaded grep, 2010-01-25) added a hardcoded number of threads(8) to use in grep and 89f09dd34e (grep: add --threads=<num> option and grep.threads configuration, 2015-12-15) made it configurable through a knob as a workaround for systems where that default was not effective.
Use instead the industry standard of 2x number of CPUs (to allow for IO wait) for the default.
Using Debian 10 amd64 in a 2 CPU VirtualBox running in macOS 10.14.6 and that might had been representative of the original author environment shows an overall performance improvement by avoiding thread trashing:
Test origin/maint HEAD
-----------------------------------------------------------------------------------------------
7810.1: grep worktree, fixed regex (no match) 0.52(0.43+0.49) 0.50(0.44+0.46) -3.8% 7810.2: grep worktree, fixed regex (common) 0.94(1.20+0.50) 0.91(1.24+0.44) -3.2% 7810.3: grep -I, fixed non binary regex (common) 0.98(1.24+0.51) 0.94(1.30+0.44) -4.1% 7810.4: grep -i, fixed caseless regex (common) 0.97(1.31+0.45) 0.93(1.18+0.56) -4.1% 7810.5: grep --no-index, fixed regex (common) 1.02(1.28+0.50) 0.97(1.14+0.59) -4.9% 7810.6: grep worktree, simple regex (common) 0.77(0.96+0.45) 0.73(0.88+0.48) -5.2% 7810.7: grep -I, simple non binary regex (common) 0.78(0.96+0.48) 0.73(0.94+0.43) -6.4% 7810.8: grep -i, simple caseless regex (common) 0.87(1.11+0.48) 0.82(1.16+0.38) -5.7% 7810.9: grep worktree, expensive regex 10.37(19.67+0.76) 10.20(19.46+0.76) -1.6% 7810.10: grep --cached, fixed regex 4.48(4.37+0.10) 4.63(4.54+0.09) +3.3% 7810.11: grep --cached, expensive regex 23.74(23.61+0.11) 23.39(23.28+0.09) -1.5%
--- Documentation/git-grep.txt | 2 +- builtin/grep.c | 3 +-- 2 files changed, 2 insertions(+), 3 deletions(-)
Documentation/git-grep.txt +1 -1
@@ -60,7 +60,7 @@ grep.extendedRegexp:: grep.threads:: Number of grep worker threads to use. If unset (or set to 0), - 8 threads are used by default (for now). + 2 threads per core are used by default. grep.fullName:: If set to true, enable `--full-name` option by default.
builtin/grep.c +1 -2
@@ -32,7 +32,6 @@ static char const * const grep_usage[] = {static int recurse_submodules; -#define GREP_NUM_THREADS_DEFAULT 8static int num_threads;static pthread_t *threads;
@@ -1068,7 +1067,7 @@ int cmd_grep(int argc, const char **argv, const char *prefix) }else if (num_threads <0 )die (_ ("invalid number of threads specified (%d)" ), num_threads);else if (num_threads ==0 ) - num_threads =HAVE_THREADS ?GREP_NUM_THREADS_DEFAULT :1 ; + num_threads =HAVE_THREADS ?online_cpus () *2 :1 ;if (num_threads >1 ) {if (!HAVE_THREADS )
Signature · 1 line
2.23.0.rc1
Re: [RFC PATCH 2/2] grep: make default number of threads reflect runtime
Quoted 8 lines · Carlo Marcelo Arenas Belón
5b594f457a(Threaded grep, 2010-01-25) added a hardcoded number of threads(8) to use in grep and89f09dd34e(grep: add --threads=<num> option and grep.threads configuration, 2015-12-15) made it configurable through a knob as a workaround for systems where that default was not effective.Use instead the industry standard of 2x number of CPUs (to allow for IO wait) for the default.
Thanks.
While I am not bold enough to endorse the "industry standard is twice the number of CPUs" claim, my gut feeling agrees with you that 8 threads may be too many for a 2 CPU box.
I think we cap the parallelism to the number of CPUs (not twice that) in all the codepaths that currently call online_cpus(), and some codepaths even cap it further to avoid creating tasks that are too small (e.g. name-hash, index-pack).
There may not be a single one-size-fits-all scaling factor (as I/O bound jobs tend to do better with a bit more workers than there are cores, but adding more workers would not help when you are CPU bound), but we'd be better off to have a mechanism to allow us to later have a consistent way to auto-scale the number of workers?
Random ideas include (not mutually exclusive)
- accept "[grep] threads = 2xCPU", in addition to "[grep] threads = 8", to mean "this many workers per CPUs"?
- add "cpuBound.numThreads" and "ioBound.numThreads" variables to configure the number of workers for cpu and io bound jobs, so that the users do not have to configure them for each command?
- build an num_threads() API that is used by the current callers of online_cpus(), including the new one this patch adds, perhaps with a signature allows it to take configuration key (e.g. "git grep" would pass "grep.threads") and if the task is expected to be IO or CPU bound ("git grep" may pass "I am heavy on IO"), e.g.
int num_threads(const char *config_key,
enum { CPUBOUND, IOBOUND } task_type);to hide the complexity of the first two items?
Quoted 3 lines
Using Debian 10 amd64 in a 2 CPU VirtualBox running in macOS 10.14.6 and that might had been representative of the original author environment shows an overall performance improvement by avoiding thread trashing:
The above does not parse very well, at least to me.
Quoted 34 lines
Documentation/git-grep.txt +1
-1@@ -60,7 +60,7 @@ grep.extendedRegexp:: grep.threads:: Number of grep worker threads to use. If unset (or set to 0), - 8 threads are used by default (for now). + 2 threads per core are used by default. grep.fullName:: If set to true, enable `--full-name` option by default.builtin/grep.c +1
-2@@ -32,7 +32,6 @@ static char const * const grep_usage[] = {static int recurse_submodules; -#define GREP_NUM_THREADS_DEFAULT 8static int num_threads;static pthread_t *threads;@@ -1068,7 +1067,7 @@ int cmd_grep(int argc, const char **argv, const char *prefix) }else if (num_threads <0 )die (_ ("invalid number of threads specified (%d)" ), num_threads);else if (num_threads ==0 ) - num_threads =HAVE_THREADS ?GREP_NUM_THREADS_DEFAULT :1 ; + num_threads =HAVE_THREADS ?online_cpus () *2 :1 ;if (num_threads >1 ) {if (!HAVE_THREADS )