| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
For regular, non-`--rebase-merges` runs, there is very little work to do
for the parser when determining the total number of commands in a rebase
script: it is simply the number of lines after stripping the commented
lines and then trimming the trailing empty line, if any.
The `--rebase-merges` mode complicates things by introducing empty lines
and comments in the middle of the script. These should _not_ be counted
as commands, and indeed, when an interactive rebase is interrupted and
subsequently resumed, the total number of commands can magically shrink,
sometimes dramatically.
The reason for this strange behavior is that empty lines _are_ counted
in `edit_todo_list()` (but not the comments, as they are stripped via
`strbuf_stripspace(..., 1)`, which is a bug.
Let's fix this so that the correct total number is shown from the
get-go, by carefully adjusting it according to what's in the rebase
script. Extra care needs to be taken in case the user edits the script:
the number of commands might be different after the user edited than
beforehand.
Note: Even though commented lines are skipped in `edit_todo_list()`, we
still need to handle `TODO_COMMENT` items by decrementing the
already-incremented `total_nr` again: empty lines are also marked as
`TODO_COMMENT`.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Acked-by: Phillip Wood <phillip.wood@dunelm.org.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The `total_nr` field in the `todo_list` structure merely serves display
purposes, and should only be used when generating the progress message.
In these two instances, however, we want to loop over all of the
commands in the parsed rebase script. The loop limit therefore needs to
be `nr`, which refers to the count of commands in the current
`todo_list`.
This is important because the two numbers, `nr` and `total_nr` can
differ wildly, e.g. due to `total_nr` _not_ counting comments or empty
lines, while `nr` skips any commands that already moved from the
`git-rebase-todo` file to the `done` file.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Acked-by: Phillip Wood <phillip.wood@dunelm.org.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Allow users to be more selective over which refs to pack by adding an
--include option to git-pack-refs.
The existing options allow some measure of selectivity. By default
git-pack-refs packs all tags. --all can be used to include all refs,
and the previous commit added the ability to exclude certain refs with
--exclude.
While these knobs give the user some selection over which refs to pack,
it could be useful to give more control. For instance, a repository may
have a set of branches that are rarely updated and would benefit from
being packed. --include would allow the user to easily include a set of
branches to be packed while leaving everything else unpacked.
Signed-off-by: John Cai <johncai86@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
At GitLab, we have a system that creates ephemeral internal refs that
don't live long before getting deleted. Having an option to exclude
certain refs from a packed-refs file allows these internal references to
be deleted much more efficiently.
Add an --exclude option to the pack-refs builtin, and use the ref
exclusions API to exclude certain refs from being packed into the final
packed-refs file
Signed-off-by: John Cai <johncai86@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
--all packs not just branch tips but anything under refs/ with the
exception of hidden refs and broken refs. Clarify this in the
documentation.
Signed-off-by: John Cai <johncai86@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The shebang was missing the leading `/` character, resulting in:
$ ./t5583-push-branches.sh
bash: ./t5583-push-branches.sh: cannot execute: required file not found
Add the missing character so the test can run.
Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Teach the recently invented "password expiry time" trait to the
wincred credential helper.
* mh/credential-password-expiry-wincred:
credential/wincred: store password_expiry_utc
|
|
Code clean-up.
* mh/use-wincred-from-system:
credential/wincred: include wincred.h
|
|
The 'git merge-tree' command handles creating root trees for merges
without using the worktree. This is a critical operation in many Git
hosts, as they typically store bare repositories.
This builtin does not load the default Git config, which can have
several important ramifications.
In particular, one config that is loaded by default is
core.useReplaceRefs. This is typically disabled in Git hosts due to
the ability to spoof commits in strange ways.
Since this config is not loaded specifically during merge-tree, users
were previously able to use refs/replace/ references to make pull
requests that looked valid but introduced malicious content. The
resulting merge commit would have the correct commit history, but the
malicious content would exist in the root tree of the merge.
The fix is simple: load the default Git config in cmd_merge_tree().
This may also fix other behaviors that are effected by reading default
config. The only possible downside is a little extra computation time
spent reading config. The config parsing is placed after basic argument
parsing so it does not slow down usage errors.
Helped-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Derrick Stolee <derrickstolee@github.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The output of git-fetch(1) is obviously designed for consumption by
users, only: we neatly columnize data, we abbreviate reference names, we
print neat arrows and we don't provide information about actual object
IDs that have changed. This makes the output format basically unusable
in the context of scripted invocations of git-fetch(1) that want to
learn about the exact changes that the command performs.
Introduce a new machine-parseable "porcelain" output format that is
supposed to fix this shortcoming. This output format is intended to
provide information about every reference that is about to be updated,
the old object ID that the reference has been pointing to and the new
object ID it will be updated to. Furthermore, the output format provides
the same flags as the human-readable format to indicate basic conditions
for each reference update like whether it was a fast-forward update, a
branch deletion, a rejected update or others.
The output format is quite simple:
```
<flag> <old-object-id> <new-object-id> <local-reference>\n
```
We assume two conditions which are generally true:
- The old and new object IDs have fixed known widths and cannot
contain spaces.
- References cannot contain newlines.
With these assumptions, the output format becomes unambiguously
parseable. Furthermore, given that this output is designed to be
consumed by scripts, the machine-readable data is printed to stdout
instead of stderr like the human-readable output is. This is mostly done
so that other data printed to stderr, like error messages or progress
meters, don't interfere with the parseable data.
A notable ommission here is that the output format does not include the
remote from which a reference was fetched, which might be important
information especially in the context of multi-remote fetches. But as
such a format would require us to print the remote for every single
reference update due to parallelizable fetches it feels wasteful for the
most likely usecase, which is when fetching from a single remote.
In a similar spirit, a second restriction is that this cannot be used
with `--recurse-submodules`. This is because any reference updates would
be ambiguous without also printing the repository in which the update
happens.
Considering that both multi-remote and submodule fetches are user-facing
features, using them in conjunction with `--porcelain` that is intended
for scripting purposes is likely not going to be useful in the majority
of cases. With that in mind these restrictions feel acceptable. If
usecases for either of these come up in the future though it is easy
enough to add a new "porcelain-v2" format that adds this information.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The options of git-fetch(1) which we pass to `parse_options()` are
declared globally in `builtin/fetch.c`. This means we're forced to use
global variables for all the options, which is more likely to cause
confusion than explicitly passing state around.
Refactor the code to move the options into `cmd_fetch()`. Move variables
that were previously forced to be declared globally and which are only
used by `cmd_fetch()` into function-local scope.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Parsing the display format happens inside of `display_state_init()`. As
we only need to check for a simple config entry, this is a natural
location to put this code as it means that display-state logic is neatly
contained in a single location.
We're about to introduce a new "porcelain" output format though that is
intended to be parseable by machines, for example inside of a script.
This format can be enabled by passing the `--porcelain` switch to
git-fetch(1). As a consequence, we'll have to add a second callsite that
influences the output format, which will become awkward to handle.
Refactor the code such that callers are expected to pass the display
format that is to be used into `display_state_init()`. This allows us to
lift up the code into the main function, where we can then hook it into
command line options parser in a follow-up commit.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
We currently have two different display formats in git-fetch(1) with the
"full" and "compact" formats. This is tracked with a boolean value that
simply denotes whether the display format is supposed to be compacted
or not. This works reasonably well while there are only two formats, but
we're about to introduce another format that will make this a bit more
awkward to use.
Introduce a `enum display_format` that is more readily extensible.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
When displaying reference updates, we try to print the references in a
neat table. As the table's width is determined its contents we thus need
to precalculate the overall width before we can start printing updated
references.
The calculation is driven by `display_state_init()`, which invokes
`refcol_width()` for every reference that is to be printed. This split
is somewhat confusing. For one, we filter references that shall be
attributed to the overall width in both places. And second, we
needlessly recalculate the maximum line length based on the terminal
columns and display format for every reference.
Refactor the code so that the complete width calculations are neatly
contained in `refcol_width()`.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
`store_updated_refs()` parses the remote reference for two purposes:
- It gets used as a note when writing FETCH_HEAD.
- It is passed through to `display_ref_update()` to display
updated references in the following format:
```
* branch master -> master
```
In most cases, the parsed remote reference is the prettified reference
name and can thus be used for both cases. But if the remote reference is
HEAD, the parsed remote reference becomes empty. This is intended when
we write the FETCH_HEAD, where we skip writing the note in that case.
But when displaying the updated references this leads to inconsistent
output where the left-hand side of reference updates is missing in some
cases:
```
$ git fetch origin HEAD HEAD:explicit-head :implicit-head main
From https://github.com/git/git
* branch HEAD -> FETCH_HEAD
* [new ref] -> explicit-head
* [new ref] -> implicit-head
* branch main -> FETCH_HEAD
```
This behaviour has existed ever since the table-based output has been
introduced for git-fetch(1) via 165f390250 (git-fetch: more terse fetch
output, 2007-11-03) and was never explicitly documented either in the
commit message or in any of our tests. So while it may not be a bug per
se, it feels like a weird inconsistency and not like it was a concious
design decision.
The logic of how we compute the remote reference name that we ultimately
pass to `display_ref_update()` is not easy to follow. There are three
different cases here:
- When the remote reference name is "HEAD" we set the remote
reference name to the empty string. This is the case that causes
the left-hand side to go missing, where we would indeed want to
print "HEAD" instead of the empty string. This is what
`prettify_refname()` would return.
- When the remote reference name has a well-known prefix then we
strip this prefix. This matches what `prettify_refname()` does.
- Otherwise, we keep the fully qualified reference name. This also
matches what `prettify_refname()` does.
As the return value of `prettify_refname()` would do the correct thing
for us in all three cases, we can thus fix the inconsistency by passing
through the full remote reference name to `display_ref_update()`, which
learns to call `prettify_refname()`. At the same time, this also
simplifies the code a bit.
Note that this patch also changes formatting of the block that computes
the "kind" (which is the category like "branch" or "tag") and "what"
(which is the prettified reference name like "master" or "v1.0")
variables. This is done on purpose so that it is part of the diff,
hopefully making the change easier to comprehend.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Add a testcase that exercises the logic when an invalid output format is
passed via the `fetch.output` configuration.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
We're about to introduce a new porcelain mode for the output of
git-fetch(1). As part of that we'll be introducing a set of new tests
that only relate to the output of this command.
Split out tests that exercise the output format of git-fetch(1) so that
it becomes easier to verify this functionality as a standalone unit. As
the tests assume that the default branch is called "main" we set up the
corresponding GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME environment variable
accordingly.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
When running `git fetch --no-recurse-submodules`, the exectation is that
we don't fetch any submodules. And while this works for fetches of a
single remote, it doesn't when fetching multiple remotes at once. The
result is that we do recurse into submodules even though the user has
explicitly asked us not to.
This is because while we pass on `--recurse-submodules={yes,on-demand}`
if specified by the user, we don't pass on `--no-recurse-submodules` to
the subprocess spawned to perform the submodule fetch.
Fix this by also forwarding this flag as expected.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Doc update.
* sd/doc-gitignore-and-rm-cached:
docs: clarify git rm --cached function in gitignore note
|
|
The titles of manual pages used to be chomped at an unreasonably
short limit, which has been removed.
* fc/doc-man-lift-title-length-limit:
doc: manpage: remove maximum title length
|
|
Our custom callout formatter is no longer used in the documentation
formatting toolchain, as the upstream default ones give better
output these days.
* fc/doc-drop-custom-callout-format:
doc: remove custom callouts format
|
|
The credential subsystem learns to help OAuth framework.
* mh/credential-oauth-refresh-token:
credential: new attribute oauth_refresh_token
|
|
Doc update to clarify how text and eol attributes interact to
specify the end-of-line conversion.
* ah/doc-attributes-text:
docs: rewrite the documentation of the text and eol attributes
|
|
Test cleanup.
* ar/test-cleanup-unused-file-creation-part2:
t2019: don't create unused files
t1502: don't create unused files
t1450: don't create unused files
t1300: don't create unused files
t1300: fix config file syntax error descriptions
t0300: don't create unused file
|
|
"git send-email" learned to give the e-mail headers to the validate
hook by passing an extra argument from the command line.
* ms/send-email-feed-header-to-validate-hook:
send-email: expose header information to git-send-email's sendemail-validate hook
send-email: refactor header generation functions
|
|
The implementation of the default "negotiator", used to find common
ancestor over the network for object tranfer, used to be recursive;
it was updated to be iterative to conserve stackspace usage.
* hx/negotiator-non-recursive:
negotiator/skipping: fix some problems in mark_common()
negotiator/default: avoid stack overflow
|
|
Doc fixes.
* ma/gittutorial-fixes:
gittutorial: wrap literal examples in backticks
gittutorial: drop early mention of origin
|
|
The implementation of credential helpers used fgets() over fixed
size buffers to read protocol messages, causing the remainder of
the folded long line to trigger unexpected behaviour, which has
been corrected.
* tb/credential-long-lines:
contrib/credential: embiggen fixed-size buffer in wincred
contrib/credential: avoid fixed-size buffer in libsecret
contrib/credential: .gitignore libsecret build artifacts
contrib/credential: remove 'gnome-keyring' credential helper
contrib/credential: avoid fixed-size buffer in osxkeychain
t/lib-credential.sh: ensure credential helpers handle long headers
credential.c: store "wwwauth[]" values in `credential_read()`
|
|
ctype tests have been taught to test EOF, too.
* rs/test-ctype-eof:
test-ctype: check EOF
|
|
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Retitle a test script with an overly narrow name.
* ob/t3501-retitle:
t/t3501-revert-cherry-pick.sh: clarify scope of the file
|
|
Doc update to drop use of deprecated app-specific password against
gmail.
* jw/send-email-update-gmail-insn:
send-email docs: Remove mention of discontinued gmail feature
|
|
Message update.
* ob/messages-capitalize-exception:
messages: capitalization and punctuation exceptions
|
|
Message update.
* ob/sequencer-i18n-fix:
sequencer: actually translate report in do_exec()
|
|
More header clean-up.
* en/header-split-cache-h-part-2: (22 commits)
reftable: ensure git-compat-util.h is the first (indirect) include
diff.h: reduce unnecessary includes
object-store.h: reduce unnecessary includes
commit.h: reduce unnecessary includes
fsmonitor: reduce includes of cache.h
cache.h: remove unnecessary headers
treewide: remove cache.h inclusion due to previous changes
cache,tree: move basic name compare functions from read-cache to tree
cache,tree: move cmp_cache_name_compare from tree.[ch] to read-cache.c
hash-ll.h: split out of hash.h to remove dependency on repository.h
tree-diff.c: move S_DIFFTREE_IFXMIN_NEQ define from cache.h
dir.h: move DTYPE defines from cache.h
versioncmp.h: move declarations for versioncmp.c functions from cache.h
ws.h: move declarations for ws.c functions from cache.h
match-trees.h: move declarations for match-trees.c functions from cache.h
pkt-line.h: move declarations for pkt-line.c functions from cache.h
base85.h: move declarations for base85.c functions from cache.h
copy.h: move declarations for copy.c functions from cache.h
server-info.h: move declarations for server-info.c functions from cache.h
packfile.h: move pack_window and pack_entry from cache.h
...
|
|
The detect-compilers script to help auto-tweaking the build system
had trouble working with compilers whose version number has extra
suffixes. The script has been taught that certain suffixes (like
"-win32" in "gcc 10-win32") can be safely stripped as they share
the same features and bugs with the version without the suffix.
* mh/fix-detect-compilers-with-nondigit-versions:
Handle some compiler versions containing a dash
|
|
The commit object parser has been taught to be a bit more lenient
to parse timestamps on the author/committer line with a malformed
author/committer ident.
* jk/parse-commit-with-malformed-ident:
parse_commit(): describe more date-parsing failure modes
parse_commit(): handle broken whitespace-only timestamp
parse_commit(): parse timestamp from end of line
t4212: avoid putting git on left-hand side of pipe
|
|
Remove full index requirement for `git diff-files`. Refactor the
ensure_expanded and ensure_not_expanded functions by introducing a
common helper function, ensure_index_state. Add test to ensure the index
is no expanded in `git diff-files`.
The `p2000` tests demonstrate a ~96% execution time reduction for 'git
diff-files' and a ~97% execution time reduction for 'git diff-files'
for a file using a sparse index:
Test before after
-----------------------------------------------------------------------
2000.94: git diff-files (full-v3) 0.09 0.08 -11.1%
2000.95: git diff-files (full-v4) 0.09 0.09 +0.0%
2000.96: git diff-files (sparse-v3) 0.52 0.02 -96.2%
2000.97: git diff-files (sparse-v4) 0.51 0.02 -96.1%
2000.98: git diff-files -- f2/f4/a (full-v3) 0.06 0.07 +16.7%
2000.99: git diff-files -- f2/f4/a (full-v4) 0.08 0.08 +0.0%
2000.100: git diff-files -- f2/f4/a (sparse-v3) 0.46 0.01 -97.8%
2000.101: git diff-files -- f2/f4/a (sparse-v4) 0.51 0.02 -96.1%
Signed-off-by: Shuqi Liang <cheskaqiqi@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Before integrating the 'git diff-files' builtin with the sparse index
feature, add tests to t1092-sparse-checkout-compatibility.sh to ensure
it currently works with sparse-checkout and will still work with sparse
index after that integration.
When adding tests against a sparse-checkout definition, we test two
modes: all changes are within the sparse-checkout cone and some changes
are outside the sparse-checkout cone.
In order to have staged changes outside of the sparse-checkout cone,
make a directory called 'folder1' and copy `a` into 'folder1/a'.
'folder1/a' is identical to `a` in the base commit. These make
'folder1/a' in the index, while leaving it outside of the
sparse-checkout definition. Change content inside 'folder1/a' in order
to test 'folder1/a' being present on-disk with modifications.
Signed-off-by: Shuqi Liang <cheskaqiqi@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
It seems pretty clear 5236fce6b4 (t1507: stop losing return codes of git
commands, 2019-12-20) missed a test_cmp.
Cc: Denton Liu <liu.denton@gmail.com>
Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
We have a small helper function called "verbose", with the idea that you
can write:
verbose foo
to get a message to stderr when the "foo" command fails, even if it does
not produce any output itself. This goes back to 8ad1652418 (t5304: use
helper to report failure of "test foo = bar", 2014-10-10). It does work,
but overall it has not been a big success for two reasons:
1. Test writers have to remember to put it there (and the resulting
test code is longer as a result).
2. It doesn't handle the opposite case (we expect "foo" to fail, but
it succeeds), leading to inconsistencies in tests (which you can
see in many hunks of this patch, e.g. ones involving "has_cr").
Most importantly, we added a136f6d8ff (test-lib.sh: support -x option
for shell-tracing, 2014-10-10) at the same time, and it does roughly the
same thing. The output is not quite as succinct as "verbose", and you
have to watch out for stray shell-traces ending up in stderr. But it
solves both of the problems above, and has clearly become the preferred
tool.
Let's consider the "verbose" function a failed experiment and remove the
last few callers (which are all many years old, and have been dwindling
as we remove them from scripts we touch for other reasons). It will be
one less thing for new test writers to see and wonder if they should be
using themselves.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Since ls-files recently learned a "--format" option, we can use that
rather than asking for all of "--stage" and then pulling out the bits we
want with "cut". That's simpler and avoids two extra processes (one for
cut, and one for the subshell to hold the intermediate result).
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
We generally avoid git on the left-hand side of a pipe, because it loses
the exit code of the command (and thus we'd miss things like segfaults
or unexpected failures). In the cases in t7001, we wouldn't expect
failures (they are just inspecting the repository state, and are not the
main point of the test), but it doesn't hurt to be careful.
In all but one case here we're piping "ls-files --stage" to cut off the
pathname (since we compare entries before and after moving). Let's pull
that into a helper function to avoid repeating the slightly awkward
replacement.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
* 'on all' in the title of the test 'write-tree on all' was unclear;
remove it.
* Add a baseline 'test_all_match git write-tree' before making any
changes to the index, providing a reference point for the 'write-tree'
prior to any modifications.
* Add a comparison of the output of 'git status --porcelain=v2' to test
the working tree after 'write-tree' exits.
* Ensure SKIP_WORKTREE files weren't materialized on disk by using
"test_path_is_missing".
Signed-off-by: Shuqi Liang <cheskaqiqi@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
When reachability bitmap coverage exists in a repository, Git will use a
different (and hopefully faster) traversal to compute revision walks.
Consider a set of positive and negative tips (which we'll refer to with
their standard bitmap parlance by "wants", and "haves"). In order to
figure out what objects exist between the tips, the existing traversal
in `prepare_bitmap_walk()` does something like:
1. Consider if we can even compute the set of objects with bitmaps,
and fall back to the usual traversal if we cannot. For example,
pathspec limiting traversals can't be computed using bitmaps (since
they don't know which objects are at which paths). The same is true
of certain kinds of non-trivial object filters.
2. If we can compute the traversal with bitmaps, partition the
(dereferenced) tips into two object lists, "haves", and "wants",
based on whether or not the objects have the UNINTERESTING flag,
respectively.
3. Fall back to the ordinary object traversal if either (a) there are
more than zero haves, none of which are in the bitmapped pack or
MIDX, or (b) there are no wants.
4. Construct a reachability bitmap for the "haves" side by walking
from the revision tips down to any existing bitmaps, OR-ing in any
bitmaps as they are found.
5. Then do the same for the "wants" side, stopping at any objects that
appear in the "haves" bitmap.
6. Filter the results if any object filter (that can be easily
computed with bitmaps alone) was given, and then return back to the
caller.
When there is good bitmap coverage relative to the traversal tips, this
walk is often significantly faster than an ordinary object traversal
because it can visit far fewer objects.
But in certain cases, it can be significantly *slower* than the usual
object traversal. Why? Because we need to compute complete bitmaps on
either side of the walk. If either one (or both) of the sides require
walking many (or all!) objects before they get to an existing bitmap,
the extra bitmap machinery is mostly or all overhead.
One of the benefits, however, is that even if the walk is slower, bitmap
traversals are guaranteed to provide an *exact* answer. Unlike the
traditional object traversal algorithm, which can over-count the results
by not opening trees for older commits, the bitmap walk builds an exact
reachability bitmap for either side, meaning the results are never
over-counted.
But producing non-exact results is OK for our traversal here (both in
the bitmap case and not), as long as the results are over-counted, not
under.
Relaxing the bitmap traversal to allow it to produce over-counted
results gives us the opportunity to make some significant improvements.
Instead of the above, the new algorithm only has to walk from the
*boundary* down to the nearest bitmap, instead of from each of the
UNINTERESTING tips.
The boundary-based approach still has degenerate cases, but we'll show
in a moment that it is often a significant improvement.
The new algorithm works as follows:
1. Build a (partial) bitmap of the haves side by first OR-ing any
bitmap(s) that already exist for UNINTERESTING commits between the
haves and the boundary.
2. For each commit along the boundary, add it as a fill-in traversal
tip (where the traversal terminates once an existing bitmap is
found), and perform fill-in traversal.
3. Build up a complete bitmap of the wants side as usual, stopping any
time we intersect the (partial) haves side.
4. Return the results.
And is more-or-less equivalent to using the *old* algorithm with this
invocation:
$ git rev-list --objects --use-bitmap-index $WANTS --not \
$(git rev-list --objects --boundary $WANTS --not $HAVES |
perl -lne 'print $1 if /^-(.*)/')
The new result performs significantly better in many cases, particularly
when the distance from the boundary commit(s) to an existing bitmap is
shorter than the distance from (all of) the have tips to the nearest
bitmapped commit.
Note that when using the old bitmap traversal algorithm, the results can
be *slower* than without bitmaps! Under the new algorithm, the result is
computed faster with bitmaps than without (at the cost of over-counting
the true number of objects in a similar fashion as the non-bitmap
traversal):
# (Computing the number of tagged objects not on any branches
# without bitmaps).
$ time git rev-list --count --objects --tags --not --branches
20
real 0m1.388s
user 0m1.092s
sys 0m0.296s
# (Computing the same query using the old bitmap traversal).
$ time git rev-list --count --objects --tags --not --branches --use-bitmap-index
19
real 0m22.709s
user 0m21.628s
sys 0m1.076s
# (this commit)
$ time git.compile rev-list --count --objects --tags --not --branches --use-bitmap-index
19
real 0m1.518s
user 0m1.234s
sys 0m0.284s
The new algorithm is still slower than not using bitmaps at all, but it
is nearly a 15-fold improvement over the existing traversal.
In a more realistic setting (using my local copy of git.git), I can
observe a similar (if more modest) speed-up:
$ argv="--count --objects --branches --not --tags"
hyperfine \
-n 'no bitmaps' "git.compile rev-list $argv" \
-n 'existing traversal' "git.compile rev-list --use-bitmap-index $argv" \
-n 'boundary traversal' "git.compile -c pack.useBitmapBoundaryTraversal=true rev-list --use-bitmap-index $argv"
Benchmark 1: no bitmaps
Time (mean ± σ): 124.6 ms ± 2.1 ms [User: 103.7 ms, System: 20.8 ms]
Range (min … max): 122.6 ms … 133.1 ms 22 runs
Benchmark 2: existing traversal
Time (mean ± σ): 368.6 ms ± 3.0 ms [User: 325.3 ms, System: 43.1 ms]
Range (min … max): 365.1 ms … 374.8 ms 10 runs
Benchmark 3: boundary traversal
Time (mean ± σ): 167.6 ms ± 0.9 ms [User: 139.5 ms, System: 27.9 ms]
Range (min … max): 166.1 ms … 169.2 ms 17 runs
Summary
'no bitmaps' ran
1.34 ± 0.02 times faster than 'boundary traversal'
2.96 ± 0.05 times faster than 'existing traversal'
Here, the new algorithm is also still slower than not using bitmaps, but
represents a more than 2-fold improvement over the existing traversal in
a more modest example.
Since this algorithm was originally written (nearly a year and a half
ago, at the time of writing), the bitmap lookup table shipped, making
the new algorithm's result more competitive. A few other future
directions for improving bitmap traversal times beyond not using bitmaps
at all:
- Decrease the cost to decompress and OR together many bitmaps
together (particularly when enumerating the uninteresting side of
the walk). Here we could explore more efficient bitmap storage
techniques, like Roaring+Run and/or use SIMD instructions to speed
up ORing them together.
- Store pseudo-merge bitmaps, which could allow us to OR together
fewer "summary" bitmaps (which would also help with the above).
Helped-by: Jeff King <peff@peff.net>
Helped-by: Derrick Stolee <derrickstolee@github.com>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
To prepare for the boundary-based bitmap walk to perform a fill-in
traversal using the boundary of either side as the tips, extract routine
used to perform fill-in traversal by `find_objects()` so that it can be
used in both places.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The object_array API has an OBJECT_ARRAY_INIT macro, but lacks a
function to initialize an object_array at a given location in memory.
Introduce `object_array_init()` to implement such a function.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
* .tmp-gitk:
gitk: escape file paths before piping to git log
gitk: prevent overly long command lines
|
|
We just started piping the file paths via `stdin` instead of passing
them via the command-line, to avoid running into command-line
limitations.
However, since we now pipe the file paths, we need to take care of
special characters.
This fixes https://github.com/git-for-windows/git/issues/2293
Signed-off-by: Nico Rieck <nico.rieck@gmail.com>
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
