When enumerating objects to place in a pack-file during 'git
pack-objects --revs', we discover the "frontier" of commits
that we care about and the boundary with commit we find
uninteresting. From that point, we walk trees to discover which
trees and blobs are uninteresting. Finally, we walk trees from the
interesting commits to find the interesting objects that are
placed in the pack.
This commit introduces a new, "sparse" way to discover the
uninteresting trees. We use the perspective of a single user trying
to push their topic to a large repository. That user likely changed
a very small fraction of the paths in their working directory, but
we spend a lot of time walking all reachable trees.
The way to switch the logic to work in this sparse way is to start
caring about which paths introduce new trees. While it is not
possible to generate a diff between the frontier boundary and all
of the interesting commits, we can simulate that behavior by
inspecting all of the root trees as a whole, then recursing down
to the set of trees at each path.
We already had taken the first step by passing an oidset to
mark_trees_uninteresting_sparse(). We now create a dictionary
whose keys are paths and values are oidsets. We consider the set
of trees that appear at each path. While we inspect a tree, we
add its subtrees to the oidsets corresponding to the tree entry's
path. We also mark trees as UNINTERESTING if the tree we are
parsing is UNINTERESTING.
To actually improve the performance, we need to terminate our
recursion. If the oidset contains only UNINTERESTING trees, then
we do not continue the recursion. This avoids walking trees that
are likely to not be reachable from interesting trees. If the
oidset contains only interesting trees, then we will walk these
trees in the final stage that collects the intersting objects to
place in the pack. Thus, we only recurse if the oidset contains
both interesting and UNINITERESTING trees.
There are a few ways that this is not a universally better option.
First, we can pack extra objects. If someone copies a subtree
from one tree to another, the first tree will appear UNINTERESTING
and we will not recurse to see that the subtree should also be
UNINTERESTING. We will walk the new tree and see the subtree as
a "new" object and add it to the pack. A test is modified to
demonstrate this behavior and to verify that the new logic is
being exercised.
Second, we can have extra memory pressure. If instead of being a
single user pushing a small topic we are a server sending new
objects from across the entire working directory, then we will
gain very little (the recursion will rarely terminate early) but
will spend extra time maintaining the path-oidset dictionaries.
Despite these potential drawbacks, the benefits of the algorithm
are clear. By adding a counter to 'add_children_by_path' and
'mark_tree_contents_uninteresting', I measured the number of
parsed trees for the two algorithms in a variety of repos.
For git.git, I used the following input:
v2.19.0
^v2.19.0~10
Objects to pack: 550
Walked (old alg): 282
Walked (new alg): 130
For the Linux repo, I used the following input:
v4.18
^v4.18~10
Objects to pack: 518
Walked (old alg): 4,836
Walked (new alg): 188
The two repos above are rather "wide and flat" compared to
other repos that I have used in the past. As a comparison,
I tested an old topic branch in the Azure DevOps repo, which
has a much deeper folder structure than the Linux repo.
Objects to pack: 220
Walked (old alg): 22,804
Walked (new alg): 129
I used the number of walked trees the main metric above because
it is consistent across multiple runs. When I ran my tests, the
performance of the pack-objects command with the same options
could change the end-to-end time by 10x depending on the file
system being warm. However, by repeating the same test on repeat
I could get more consistent timing results. The git.git and
Linux tests were too fast overall (less than 0.5s) to measure
an end-to-end difference. The Azure DevOps case was slow enough
to see the time improve from 15s to 1s in the warm case. The
cold case was 90s to 9s in my testing.
These improvements will have even larger benefits in the super-
large Windows repository. In our experiments, we see the
"Enumerate objects" phase of pack-objects taking 60-80% of the
end-to-end time of non-trivial pushes, taking longer than the
network time to send the pack and the server time to verify the
pack.
Signed-off-by: Derrick Stolee <dstolee@microsoft.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
When creating a pack-file using 'git pack-objects --revs' we provide
a list of interesting and uninteresting commits. For example, a push
operation would make the local topic branch be interesting and the
known remote refs as uninteresting. We want to discover the set of
new objects to send to the server as a thin pack.
We walk these commits until we discover a frontier of commits such
that every commit walk starting at interesting commits ends in a root
commit or unintersting commit. We then need to discover which
non-commit objects are reachable from uninteresting commits. This
commit walk is not changing during this series.
The mark_edges_uninteresting() method in list-objects.c iterates on
the commit list and does the following:
* If the commit is UNINTERSTING, then mark its root tree and every
object it can reach as UNINTERESTING.
* If the commit is interesting, then mark the root tree of every
UNINTERSTING parent (and all objects that tree can reach) as
UNINTERSTING.
At the very end, we repeat the process on every commit directly
given to the revision walk from stdin. This helps ensure we properly
cover shallow commits that otherwise were not included in the
frontier.
The logic to recursively follow trees is in the
mark_tree_uninteresting() method in revision.c. The algorithm avoids
duplicate work by not recursing into trees that are already marked
UNINTERSTING.
Add a new 'sparse' option to the mark_edges_uninteresting() method
that performs this logic in a slightly different way. As we iterate
over the commits, we add all of the root trees to an oidset. Then,
call mark_trees_uninteresting_sparse() on that oidset. Note that we
include interesting trees in this process. The current implementation
of mark_trees_unintersting_sparse() will walk the same trees as
the old logic, but this will be replaced in a later change.
Add a '--sparse' flag in 'git pack-objects' to call this new logic.
Add a new test script t/t5322-pack-objects-sparse.sh that tests this
option. The tests currently demonstrate that the resulting object
list is the same as the old algorithm. This includes a case where
both algorithms pack an object that is not needed by a remote due to
limits on the explored set of trees. When the sparse algorithm is
changed in a later commit, we will add a test that demonstrates a
change of behavior in some cases.
Signed-off-by: Derrick Stolee <dstolee@microsoft.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
In preparation for a new algorithm that walks fewer trees when
creating a pack from a set of revisions, create a method that
takes an oidset of tree oids and marks reachable objects as
UNINTERESTING.
The current implementation uses the existing
mark_tree_uninteresting to recursively walk the trees and blobs.
This will walk the same number of trees as the old mechanism. To
ensure that mark_tree_uninteresting walks the tree, we need to
remove the UNINTERESTING flag before calling the method. This
implementation will be replaced entirely in a later commit.
There is one new assumption in this approach: we are also given
the oids of the interesting trees. This implementation does not
use those trees at the moment, but we will use them in a later
rewrite of this method.
Signed-off-by: Derrick Stolee <dstolee@microsoft.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Some items that should be in "Performance, Internal Implementation,
Development Support etc." have ended up in "UI, Workflows & Features"
and "Fixes since v2.19". Move them, and do s/uses/use/ while at it.
Signed-off-by: Martin Ågren <martin.agren@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
range-diff: always pass at least minimal diff options
Commit d8981c3f88 ("format-patch: do not let its diff-options affect
--range-diff", 2018-11-30) taught `show_range_diff()` to accept a
NULL-pointer as an indication that it should use its own "reasonable
default". That fixed a regression from a5170794 ("Merge branch
'ab/range-diff-no-patch'", 2018-11-18), but unfortunately it introduced
a regression of its own.
In particular, it means we forget the `file` member of the diff options,
so rather than placing a range-diff in the cover-letter, we write it to
stdout. In order to fix this, rewrite the two callers adjusted by d8981c3f88 to instead create a "dummy" set of diff options where they
only fill in the fields we absolutely require, such as output file and
color.
Modify and extend the existing tests to try and verify that the right
contents end up in the right place.
Don't revert `show_range_diff()`, i.e., let it keep accepting NULL.
Rather than removing what is dead code and figuring out it isn't
actually dead and we've broken 2.20, just leave it for now.
[es: retain diff coloring when going to stdout]
Signed-off-by: Martin Ågren <martin.agren@gmail.com> Signed-off-by: Eric Sunshine <sunshine@sunshineco.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
test framework has been updated to make a bug in the test script
(as opposed to bugs in Git that are discovered by running the
tests) stand out more prominently.
* sg/test-BUG:
tests: send "bug in the test script" errors to the script's stderr
The advice message to tell the user to migrate an existing graft
file to the replace system when a graft file was read was shown
even when "git replace --convert-graft-file" command, which is the
way the message suggests to use, was running, which made little
sense.
"git rebase --stat" to transplant a piece of history onto a totally
unrelated history were not working before and silently showed wrong
result. With the recent reimplementation in C, it started to instead
die with an error message, as the original logic was not prepared
to cope with this case. This has now been fixed.
* js/rebase-stat-unrelated-fix:
rebase --stat: fix when rebasing to an unrelated history
"git rebase" reimplemented recently in C accidentally changed the
way reflog entries are recorded (earlier "rebase -i" identified the
entries it leaves with "rebase -i", but the new version always
marks them with "rebase"). This has been corrected.
"git format-patch --range-diff" by mistake passed the diff options
used to generate the primary output of the command to the
range-diff machinery, which caused the range-diff in the cover
letter to include fairly useless "--stat" output. This has been
corrected by forcing a non-customizable default formatting options
on the range-diff machinery when driven by format-patch.
* jc/format-patch-range-diff-fix:
format-patch: do not let its diff-options affect --range-diff
builtin/rebase.c: remove superfluous space in messages
The whitespace breakages in these messages were introduced while
reimplementing the subcommand in C. Match these messages to those
in the original scripted version.
Signed-off-by: Ralf Thielow <ralf.thielow@gmail.com> Acked-by: Johannes Schindelin <Johannes.Schindelin@gmx.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
rebase --stat: fix when rebasing to an unrelated history
When rebasing to a commit history that has no common commits with the
current branch, there is no merge base. In diffstat mode, this means
that we cannot compare to the merge base, but we have to compare to the
empty tree instead.
Also, if running in verbose diffstat mode, we should not output
Changes from <merge-base> to <onto>
as that does not make sense without any merge base.
Note: neither scripted nor built-in versoin of `git rebase` were
prepared for this situation well. We use this opportunity not only to
fix the bug(s), but also to make both versions' output consistent in
this instance. And add a regression test to keep this working in all
eternity.
Reported-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com> Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
The scripted version of "rebase" honored the `GIT_REFLOG_ACTION`,
and some automation scripts expected the reflog entries to be
prefixed with "rebase -i", not "rebase", after running "rebase -i".
This regressed in the reimplementation in C.
Fix that, and add a regression test, both with `GIT_REFLOG_ACTION`
set and unset.
Note: the reflog message for "rebase finished" did *not* honor
GIT_REFLOG_ACTION, and as we are very late in the v2.20.0-rcN phase,
we leave that bug for later (as it seems that that bug has been with
us from the very beginning).
Reported by Ian Jackson.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
format-patch: do not let its diff-options affect --range-diff
Stop leaking how the primary output of format-patch is customized to
the range-diff machinery and instead let the latter use its own
"reasonable default", in order to correct the breakage introduced by a5170794 ("Merge branch 'ab/range-diff-no-patch'", 2018-11-18) on
the 'master' front. "git format-patch --range-diff..." without any
weird diff option started to include the "range-diff --stat" output,
which is rather useless right now, that made the whole thing
unusable and this is probably the least disruptive way to whip the
codebase into a shippable shape.
We may want to later make the range-diff driven by format-patch more
configurable, but that would have to wait until we have a good
design.
git-reset.txt: render literal examples as monospace
Large parts of this document do not use `backticks` around literal
examples such as branch names (`topic/wip`), git usages, `HEAD` and
`<commit-ish>` so they render as ordinary text. Fix that.
Signed-off-by: Martin Ågren <martin.agren@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
git-reset.txt: render tables correctly under Asciidoctor
Asciidoctor removes the indentation of each line in these tables, so the
last lines of each table have a completely broken alignment.
Similar to 379805051d ("Documentation: render revisions correctly under
Asciidoctor", 2018-05-06), use an explicit literal block to indicate
that we want to keep the leading whitespace in the tables.
Because this gives us some extra indentation, we can remove the one that
we have been carrying explicitly. That is, drop the first six spaces of
indentation on each line. With Asciidoc (8.6.10), this results in
identical rendering before and after this commit, both for git-reset.1
and git-reset.html.
Reported-by: Paweł Samoraj <samoraj.pawel@gmail.com> Signed-off-by: Martin Ågren <martin.agren@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
The advice to run 'git replace --convert-graft-file' added in f9f99b3f7d ("Deprecate support for .git/info/grafts", 2018-04-29)
didn't add an exception for the 'git replace --convert-graft-file'
codepath itself.
As a result we'd suggest running --convert-graft-file while the user
was running --convert-graft-file, which makes no sense. Before:
$ git replace --convert-graft-file
hint: Support for <GIT_DIR>/info/grafts is deprecated
hint: and will be removed in a future Git version.
hint:
hint: Please use "git replace --convert-graft-file"
hint: to convert the grafts into replace refs.
hint:
hint: Turn this message off by running
hint: "git config advice.graftFileDeprecated false"
Add a check for that case and skip printing the advice while the user
is busy following our advice.
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Test scripts checking 'git daemon' stop the daemon with a TERM signal,
and the 'stop_git_daemon' helper checks the daemon's exit status to
make sure that it indeed died because of that signal.
This check is bogus since 03c39b3458 (t/lib-git-daemon: use
test_match_signal, 2016-06-24), for two reasons:
- Right after killing 'git daemon', 'stop_git_daemon' saves its exit
status in a variable, but since 03c39b3458 the condition checking
the exit status looks at '$?', which at this point is not the exit
status of 'git daemon', but that of the variable assignment, i.e.
it's always 0.
- The unexpected exit status should abort the whole test script with
'error', but it doesn't, because 03c39b3458 forgot to negate
'test_match_signal's exit status in the condition.
This patch fixes both issues.
Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
The code recently added to "git clone" to see if the platform's
filesystem is adequate to check out and use the project code
correctly (e.g. a case smashing filesystem cannot be used for a
project with two files whose paths are different only in case) was
meant to help Windows users, but the test for it was not enabled
for that platform, which has been corrected.
* tb/clone-case-smashing-warning-test:
t5601-99: Enable colliding file detection for MINGW
doc: update diff-format.txt for removed ellipses in --raw
Since 7cb6ac1e4b ("diff: diff_aligned_abbrev: remove ellipsis after
abbreviated SHA-1 value", 2017-12-03), the "--raw" format of diff
does not add ellipses in an attempt to align the output, but the
documentation was not updated to reflect this.
Signed-off-by: Greg Hurrell <greg@hurrell.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
t5601-99: Enable colliding file detection for MINGW
Commit b878579ae7 (clone: report duplicate entries on case-insensitive
filesystems - 2018-08-17) adds a warning to user when cloning a repo
with case-sensitive file names on a case-insensitive file system.
This test has never been enabled for MINGW.
It had been working since day 1, but I forget to report that to the
author.
Enable it after a re-test.
Signed-off-by: Torsten Bögershausen <tboegi@web.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
* ma/commit-graph-docs:
Doc: refer to the "commit-graph file" with dash
git-commit-graph.txt: refer to "*commit*-graph file"
git-commit-graph.txt: typeset more in monospace
git-commit-graph.txt: fix bullet lists
* fe/doc-updates:
git-describe.1: clarify that "human readable" is also git-readable
git-column.1: clarify initial description, provide examples
git-archimport.1: specify what kind of Arch we're talking about