From: Jeff King <hidden> Date: 2016-06-15 22:59:42
This series fixes a rev-list performance regression in fbd4a70 (list-objects:
mark more commits as edges in mark_edges_uninteresting, 2013-08-16). That
commit is a little tricky because it actually _knows_ it's trading off CPU for
a better packfile, but I think we're performing the tradeoff in too many
places. See the second commit for details.
[1/2]: t/perf: time rev-list with UNINTERESTING commits
[2/2]: list-objects: only look at cmdline trees with edge_hint
Here's t/perf/p0001 output that shows the problem:
0001.5: rev-list --objects $commit --not --all
fbd4a703^ fbd4a703 HEAD
0.04(0.04+0.00) 0.28(0.27+0.00) +600.0% 0.04(0.04+0.00) +0.0%
-Peff
PS If you are wondering about the output format above, I had to munge it
manually to avoid giant 115-character lines. We should maybe teach the
perf suite an alternate output format. :)
From: Jeff King <hidden> Date: 2016-06-15 22:59:42
We time a straight "rev-list --all" and its "--object"
counterpart, both going all the way to the root. However, we
do not time a partial history walk. This patch adds an
extreme case: a walk over a very small slice of history, but
with a very large set of UNINTERESTING tips. This is similar
to the connectivity check run by git on a small fetch, or
the walk done by any pre-receive hooks that want to check
incoming commits.
This test reveals a performance regression in git v1.8.4.2,
caused by fbd4a70 (list-objects: mark more commits as edges
in mark_edges_uninteresting, 2013-08-16):
Test fbd4a703^ fbd4a703
------------------------------------------------------------------------------------------
0001.1: rev-list --all 0.69(0.67+0.02) 0.69(0.68+0.01) +0.0%
0001.2: rev-list --all --objects 3.47(3.44+0.02) 3.48(3.44+0.03) +0.3%
0001.4: rev-list $commit --not --all 0.04(0.04+0.00) 0.04(0.04+0.00) +0.0%
0001.5: rev-list --objects $commit --not --all 0.04(0.03+0.00) 0.27(0.24+0.02) +575.0%
Signed-off-by: Jeff King <redacted>
---
Sorry for the long lines in the commit message. I'm open to suggestions
on reformatting.
t/perf/p0001-rev-list.sh | 17 +++++++++++++++++
1 file changed, 17 insertions(+)
From: Jeff King <hidden> Date: 2016-06-15 22:59:42
When rev-list is given a command-line like:
git rev-list --objects $commit --not --all
the most accurate answer is the difference between the set
of objects reachable from $commit and the set reachable from
all of the existing refs. However, we have not historically
provided that answer, because it is very expensive to
calculate. We would have to open every tree of every commit
in the entire history.
Instead, we find the accurate set difference of the
reachable commits, and then mark the trees at the boundaries
as uninteresting. This misses objects which appear in the
trees of both the interesting commits and deep within the
uninteresting history.
Commit fbd4a70 (list-objects: mark more commits as edges in
mark_edges_uninteresting, 2013-08-16) noticed that we miss
those objects during pack-objects, and added code to examine
the trees of all of the "--not" refs given on the
command-line. Note that this is still not the complete set
difference, because we look only at the tips of the
command-line arguments, not all of their reachable commits.
But it increases the set of boundary objects we consider,
which is especially important for shallow fetches. So we
are trading extra CPU time for a larger set of boundary
objects, which can improve the resulting pack size for a
--thin pack.
This tradeoff probably makes sense in the context of
pack-objects, where we have set revs->edge_hint to have the
traversal feed us the set of boundary objects. For a
regular rev-list, though, it is probably not a good
tradeoff. It is true that it makes our list slightly closer
to a true set difference, but it is a rare case where this
is important. And because we do not have revs->edge_hint
set, we do nothing useful with the larger set of boundary
objects.
This patch therefore ties the extra tree examination to the
revs->edge_hint flag; it is the presence of that flag that
makes the tradeoff worthwhile.
Here is output from the p0001-rev-list showing the
improvement in performance:
Test HEAD^ HEAD
-----------------------------------------------------------------------------------------
0001.1: rev-list --all 0.69(0.65+0.02) 0.69(0.66+0.02) +0.0%
0001.2: rev-list --all --objects 3.22(3.19+0.03) 3.23(3.20+0.03) +0.3%
0001.4: rev-list $commit --not --all 0.04(0.04+0.00) 0.04(0.04+0.00) +0.0%
0001.5: rev-list --objects $commit --not --all 0.27(0.26+0.01) 0.04(0.04+0.00) -85.2%
Signed-off-by: Jeff King <redacted>
---
list-objects.c | 20 +++++++++++---------
1 file changed, 11 insertions(+), 9 deletions(-)
This is bad to be touching the repo and assuming it is non-bare. For
some reason I assumed that the perf suite made a copy of the repo, but
it doesn't. If you point to a bare repo via GIT_PERF_REPO, this part of
the test fails.
It's actually enough to demonstrate the problem without changing the
tree at all. So this produces the same numbers, and works everywhere:
From: Jeff King <hidden> Date: 2016-06-15 22:59:42
On Mon, Jan 20, 2014 at 04:28:45PM -0500, Jeff King wrote:
[1/2]: t/perf: time rev-list with UNINTERESTING commits
[2/2]: list-objects: only look at cmdline trees with edge_hint
Here's t/perf/p0001 output that shows the problem:
0001.5: rev-list --objects $commit --not --all
fbd4a703^ fbd4a703 HEAD
0.04(0.04+0.00) 0.28(0.27+0.00) +600.0% 0.04(0.04+0.00) +0.0%
Those numbers are on git.git. Obviously 600% is a lot, but 24ms is not.
However, the cost is a factor of the tree size times the number of refs.
For the "homebrew.git" repository stored at GitHub, which has ~28,000
refs (mostly pointing at pull-request tips in refs/pull), the numbers
are much more dramatic:
fbd4a703^ fbd4a703 HEAD
0.50(0.46+0.02) 8.23(8.17+0.06) +1546.0% 0.50(0.48+0.01) +0.0%
-Peff
On Tue, Jan 21, 2014 at 4:32 AM, Jeff King [off-list ref] wrote:
This patch therefore ties the extra tree examination to the
revs->edge_hint flag; it is the presence of that flag that
makes the tradeoff worthwhile.
Here is output from the p0001-rev-list showing the
improvement in performance:
Test HEAD^ HEAD
-----------------------------------------------------------------------------------------
0001.1: rev-list --all 0.69(0.65+0.02) 0.69(0.66+0.02) +0.0%
0001.2: rev-list --all --objects 3.22(3.19+0.03) 3.23(3.20+0.03) +0.3%
0001.4: rev-list $commit --not --all 0.04(0.04+0.00) 0.04(0.04+0.00) +0.0%
0001.5: rev-list --objects $commit --not --all 0.27(0.26+0.01) 0.04(0.04+0.00) -85.2%
You must have so much fun (or headache, depending on your view) with
the variety of repos on github :)
From: Jeff King <hidden> Date: 2016-06-15 22:59:42
On Mon, Jan 20, 2014 at 04:28:45PM -0500, Jeff King wrote:
This series fixes a rev-list performance regression in fbd4a70 (list-objects:
mark more commits as edges in mark_edges_uninteresting, 2013-08-16). That
commit is a little tricky because it actually _knows_ it's trading off CPU for
a better packfile, but I think we're performing the tradeoff in too many
places. See the second commit for details.
[1/2]: t/perf: time rev-list with UNINTERESTING commits
[2/2]: list-objects: only look at cmdline trees with edge_hint
Here's t/perf/p0001 output that shows the problem:
0001.5: rev-list --objects $commit --not --all
fbd4a703^ fbd4a703 HEAD
0.04(0.04+0.00) 0.28(0.27+0.00) +600.0% 0.04(0.04+0.00) +0.0%
Here's v2 that addresses the minor comments on the list (simpler test in
the first patch, and dropping the now-redundant revs->edge_hint check in
the second patch).
-Peff
From: Jeff King <hidden> Date: 2016-06-15 22:59:42
We time a straight "rev-list --all" and its "--object"
counterpart, both going all the way to the root. However, we
do not time a partial history walk. This patch adds an
extreme case: a walk over a very small slice of history, but
with a very large set of UNINTERESTING tips. This is similar
to the connectivity check run by git on a small fetch, or
the walk done by any pre-receive hooks that want to check
incoming commits.
This test reveals a performance regression in git v1.8.4.2,
caused by fbd4a70 (list-objects: mark more commits as edges
in mark_edges_uninteresting, 2013-08-16):
Test fbd4a703^ fbd4a703
------------------------------------------------------------------------------------------
0001.1: rev-list --all 0.69(0.67+0.02) 0.69(0.68+0.01) +0.0%
0001.2: rev-list --all --objects 3.47(3.44+0.02) 3.48(3.44+0.03) +0.3%
0001.4: rev-list $commit --not --all 0.04(0.04+0.00) 0.04(0.04+0.00) +0.0%
0001.5: rev-list --objects $commit --not --all 0.04(0.03+0.00) 0.27(0.24+0.02) +575.0%
Signed-off-by: Jeff King <redacted>
---
t/perf/p0001-rev-list.sh | 12 ++++++++++++
1 file changed, 12 insertions(+)
From: Jeff King <hidden> Date: 2016-06-15 22:59:42
When rev-list is given a command-line like:
git rev-list --objects $commit --not --all
the most accurate answer is the difference between the set
of objects reachable from $commit and the set reachable from
all of the existing refs. However, we have not historically
provided that answer, because it is very expensive to
calculate. We would have to open every tree of every commit
in the entire history.
Instead, we find the accurate set difference of the
reachable commits, and then mark the trees at the boundaries
as uninteresting. This misses objects which appear in the
trees of both the interesting commits and deep within the
uninteresting history.
Commit fbd4a70 (list-objects: mark more commits as edges in
mark_edges_uninteresting, 2013-08-16) noticed that we miss
those objects during pack-objects, and added code to examine
the trees of all of the "--not" refs given on the
command-line. Note that this is still not the complete set
difference, because we look only at the tips of the
command-line arguments, not all of their reachable commits.
But it increases the set of boundary objects we consider,
which is especially important for shallow fetches. So we
are trading extra CPU time for a larger set of boundary
objects, which can improve the resulting pack size for a
--thin pack.
This tradeoff probably makes sense in the context of
pack-objects, where we have set revs->edge_hint to have the
traversal feed us the set of boundary objects. For a
regular rev-list, though, it is probably not a good
tradeoff. It is true that it makes our list slightly closer
to a true set difference, but it is a rare case where this
is important. And because we do not have revs->edge_hint
set, we do nothing useful with the larger set of boundary
objects.
This patch therefore ties the extra tree examination to the
revs->edge_hint flag; it is the presence of that flag that
makes the tradeoff worthwhile.
Here is output from the p0001-rev-list showing the
improvement in performance:
Test HEAD^ HEAD
-----------------------------------------------------------------------------------------
0001.1: rev-list --all 0.69(0.65+0.02) 0.69(0.66+0.02) +0.0%
0001.2: rev-list --all --objects 3.22(3.19+0.03) 3.23(3.20+0.03) +0.3%
0001.4: rev-list $commit --not --all 0.04(0.04+0.00) 0.04(0.04+0.00) +0.0%
0001.5: rev-list --objects $commit --not --all 0.27(0.26+0.01) 0.04(0.04+0.00) -85.2%
Signed-off-by: Jeff King <redacted>
---
list-objects.c | 20 +++++++++++---------
1 file changed, 11 insertions(+), 9 deletions(-)