From: Thomas Rast <hidden> Date: 2016-06-15 22:52:41
Ævar Arnfjörð Bjarmason [off-list ref] writes:
On Fri, Dec 2, 2011 at 14:07, Thomas Rast [off-list ref] wrote:
quoted
I conjecture that this is caused by contention on
read_sha1_mutex. [...] So disable threading entirely when not
scanning the worktree
Why does git-grep even need to keep a mutex to call read_sha1_file()?
It's inherently a read-only operation isn't it? If the lock is needed
because data is being shared between threads in sha1_file.c shouldn't
we tackle that instead of completely disabling threading?
The problem is that all sorts of data is shared. See
http://thread.gmane.org/gmane.comp.version-control.git/186618
But I need to go through it again, there are some races and double locks
in the posted version.
--
Thomas Rast
trast@{inf,student}.ethz.ch
On Fri, Dec 2, 2011 at 14:07, Thomas Rast [off-list ref] wrote:
quoted
I conjecture that this is caused by contention on
read_sha1_mutex. [...] So disable threading entirely when not
scanning the worktree
Why does git-grep even need to keep a mutex to call read_sha1_file()?
It's inherently a read-only operation isn't it? If the lock is needed
because data is being shared between threads in sha1_file.c shouldn't
we tackle that instead of completely disabling threading?
I mentioned this on IRC, but I thought I'd bring it up here too.
Is the expensive part of git-grep all the setup work, or the actual
traversal and searching? I'm guessing it's the latter.
In that case an easy way to do git-grep in parallel would be to simply
spawn multiple sub-processes, e.g. if we had 1000 files and 4 cores:
1. Split the 1000 into 4 parts 250 each.
2. Spawn 4 processes as: git grep <pattern> -- <250 files>
3. Aggregate all of the results in the parent process
From: Jeff King <hidden> Date: 2016-06-15 22:52:41
On Sat, Dec 24, 2011 at 02:39:11AM +0100, Ævar Arnfjörð Bjarmason wrote:
Is the expensive part of git-grep all the setup work, or the actual
traversal and searching? I'm guessing it's the latter.
In that case an easy way to do git-grep in parallel would be to simply
spawn multiple sub-processes, e.g. if we had 1000 files and 4 cores:
1. Split the 1000 into 4 parts 250 each.
2. Spawn 4 processes as: git grep <pattern> -- <250 files>
3. Aggregate all of the results in the parent process
That's an interesting idea. The expense of the traversal and searching
depends on two things:
- how complex is your regex?
- are you reading from objects (which need zlib inflated) or disk?
But you should be able to approximate it by compiling with NO_PTHREADS
and doing (assuming you have GNU xargs):
# grep in working tree
git ls-files | xargs -P 8 git grep "$re" --
# grep tree-ish
git ls-tree -r --name-only $tree | xargs -P 8 git grep "$re" $tree --
I tried to get some timings for this, but ran across some quite
surprising results. Here's a simple grep of the linux-2.6 working tree,
using a single-threaded grep:
$ time git grep SIMPLE >/dev/null
real 0m0.439s
user 0m0.272s
sys 0m0.160s
and then the same thing, via xargs, without even turning on
parallelization. This should give us a measurement of the overhead for
going through xargs at all. We'd expect it to be slower, but not too
much so:
$ time git ls-files | xargs git grep SIMPLE -- >/dev/null
real 0m11.989s
user 0m11.769s
sys 0m0.268s
Twenty-five times slower! Running 'perf' reports the culprit as pathspec
matching:
+ 63.23% git git [.] match_pathspec_depth
+ 28.60% git libc-2.13.so [.] __strncmp_sse42
+ 2.22% git git [.] strncmp@plt
+ 1.67% git git [.] kwsexec
where the strncmps are called as part of match_pathspec_depth. So over
90% of the CPU time is spent on matching the pathspecs, compared to less
than 2% actually grepping.
Which really makes me wonder if our pathspec matching could stand to be
faster. True, giving a bunch of single files is the least efficient way
to use pathspecs, but that's pretty amazingly slow.
The case where we would most expect the setup cost to be drowned out is
using a more complex regex, grepping tree objects. There we have a
baseline of:
$ time git grep 'a.*c' HEAD >/dev/null
real 0m5.684s
user 0m5.472s
sys 0m0.196s
$ time git ls-tree --name-only -r HEAD |
xargs git grep 'a.*c' HEAD -- >/dev/null
real 0m10.906s
user 0m10.725s
sys 0m0.240s
Here, we still almost double our time. It looks like we don't use the
same pathspec matching code in this case. But we do waste a lot of extra
time zlib-inflating the trees in "ls-tree", only to do it separately in
"grep".
Doing it in parallel yields:
$ time git ls-tree --name-only -r HEAD |
xargs -n 4000 -P 8 git grep 'a.*c' HEAD -- >/dev/null
real 0m3.573s
user 0m21.885s
sys 0m0.400s
So that does at least yield a real speedup, albeit only by about half,
despite using over six times as much CPU (though my numbers are skewed
somewhat, as this is a quad i7 with hyperthreading and turbo boost).
-Peff
On Sat, Dec 24, 2011 at 2:07 PM, Jeff King [off-list ref] wrote:
I tried to get some timings for this, but ran across some quite
surprising results. Here's a simple grep of the linux-2.6 working tree,
using a single-threaded grep:
$ time git grep SIMPLE >/dev/null
real 0m0.439s
user 0m0.272s
sys 0m0.160s
and then the same thing, via xargs, without even turning on
parallelization. This should give us a measurement of the overhead for
going through xargs at all. We'd expect it to be slower, but not too
much so:
$ time git ls-files | xargs git grep SIMPLE -- >/dev/null
real 0m11.989s
user 0m11.769s
sys 0m0.268s
Twenty-five times slower! Running 'perf' reports the culprit as pathspec
matching:
+ 63.23% git git [.] match_pathspec_depth
+ 28.60% git libc-2.13.so [.] __strncmp_sse42
+ 2.22% git git [.] strncmp@plt
+ 1.67% git git [.] kwsexec
where the strncmps are called as part of match_pathspec_depth. So over
90% of the CPU time is spent on matching the pathspecs, compared to less
than 2% actually grepping.
Which really makes me wonder if our pathspec matching could stand to be
faster. True, giving a bunch of single files is the least efficient way
to use pathspecs, but that's pretty amazingly slow.
We could eliminate get_pathspec_depth() in grep_directory() when
read_directory() learns to filter path properly using (and at the cost
of) tree_entry_interesting(). The latter function has more
optimizaions built in and should be faster than the former. This is a
good test case for my read_directory() rewrite. Thanks.
get_pathspec_depth() can still use some optimizations though for
grep_cache() case.
--
Duy
(Sorry I replied without reading though the mail)
On Sat, Dec 24, 2011 at 2:07 PM, Jeff King [off-list ref] wrote:
The case where we would most expect the setup cost to be drowned out is
using a more complex regex, grepping tree objects. There we have a
baseline of:
$ time git grep 'a.*c' HEAD >/dev/null
real 0m5.684s
user 0m5.472s
sys 0m0.196s
$ time git ls-tree --name-only -r HEAD |
xargs git grep 'a.*c' HEAD -- >/dev/null
real 0m10.906s
user 0m10.725s
sys 0m0.240s
Here, we still almost double our time. It looks like we don't use the
same pathspec matching code in this case. But we do waste a lot of extra
time zlib-inflating the trees in "ls-tree", only to do it separately in
"grep".
I assume this is gree_tree(), we have another form of pathspec
matching here: tree_entry_interesting() and it's still a bunch of
strcmp inside. Does strcmp show up in perf report?
--
Duy
From: Jeff King <hidden> Date: 2016-06-15 22:52:41
On Sat, Dec 24, 2011 at 05:55:14PM +0700, Nguyen Thai Ngoc Duy wrote:
On Sat, Dec 24, 2011 at 2:07 PM, Jeff King [off-list ref] wrote:
quoted
The case where we would most expect the setup cost to be drowned out is
using a more complex regex, grepping tree objects. There we have a
baseline of:
$ time git grep 'a.*c' HEAD >/dev/null
real 0m5.684s
user 0m5.472s
sys 0m0.196s
$ time git ls-tree --name-only -r HEAD |
xargs git grep 'a.*c' HEAD -- >/dev/null
real 0m10.906s
user 0m10.725s
sys 0m0.240s
Here, we still almost double our time. It looks like we don't use the
same pathspec matching code in this case. But we do waste a lot of extra
time zlib-inflating the trees in "ls-tree", only to do it separately in
"grep".
I assume this is gree_tree(), we have another form of pathspec
matching here: tree_entry_interesting() and it's still a bunch of
strcmp inside. Does strcmp show up in perf report?
Yes, but not nearly as high. The top of the report is:
+ 32.16% git libc-2.13.so [.] re_search_internal
+ 17.82% git libz.so.1.2.3.4 [.] 0xe986
+ 7.81% git git [.] look_ahead
+ 6.24% git libc-2.13.so [.] __strncmp_sse42
+ 4.08% git git [.] tree_entry_interesting
+ 3.27% git git [.] end_of_line
+ 2.63% git libz.so.1.2.3.4 [.] adler32
+ 1.93% git libz.so.1.2.3.4 [.] inflate
where the strncmps are from[1]:
- 6.24% git libc-2.13.so [.] __strncmp_sse42
- __strncmp_sse42
+ 80.92% grep_tree
+ 19.08% tree_entry_interesting
So we're spending maybe 10% of our time on pathspecs, but most of it is
going to zlib and the actual regex search.
-Peff
[1] Note that this is with -O2, so some of that is from inlined calls.
On Sat, Dec 24, 2011 at 2:07 PM, Jeff King [off-list ref] wrote:
The case where we would most expect the setup cost to be drowned out is
using a more complex regex, grepping tree objects. There we have a
baseline of:
$ time git grep 'a.*c' HEAD >/dev/null
real 0m5.684s
user 0m5.472s
sys 0m0.196s
$ time git ls-tree --name-only -r HEAD |
xargs git grep 'a.*c' HEAD -- >/dev/null
real 0m10.906s
user 0m10.725s
sys 0m0.240s
Here, we still almost double our time. It looks like we don't use the
same pathspec matching code in this case. But we do waste a lot of extra
time zlib-inflating the trees in "ls-tree", only to do it separately in
"grep".
Or you could pass blob SHA-1 to git grep to avoid reinflating trees
$ time git ls-tree -r HEAD|cut -c 13-52|xargs git grep 'a.*c' >/dev/null
Doing it in parallel does not seem to save time for me though.
--
Duy