| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
Add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag to the test setup suite
in order to toggle writing Bloom filters when running any of the git tests.
If set to true, we will compute and write Bloom filters every time a test
calls `git commit-graph write`, as if the `--changed-paths` option was
passed in.
The test suite passes when GIT_TEST_COMMIT_GRAPH and
GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS are enabled.
Helped-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
These tests exercises writing commit graph with Bloom filters
and exercises 'git log -- path' with all the applicable
options. They check that the output is the same with and
without Bloom filters, confirm Bloom filters were used by
checking if trace2 statistics were logged correctly.
Also confirms cases where Bloom filters are not used:
1. Multiple path specs,
2. --walk-reflogs (see patch titled 'revision.c: use Bloom filters...'
for details,
3. If the latest commit graph does not have Bloom filters
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Add trace2 statistics around Bloom filter usage and behavior
for 'git log -- path' commands that are hoping to benefit from
the presence of computed changed paths Bloom filters.
These statistics are great for performance analysis work and
for formal testing, which we will see in the commit following
this one.
Helped-by: Derrick Stolee <dstolee@microsoft.com
Helped-by: SZEDER Gábor <szeder.dev@gmail.com>
Helped-by: Jonathan Tan <jonathantanmy@google.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Revision walk will now use Bloom filters for commits to speed up
revision walks for a particular path (for computing history for
that path), if they are present in the commit-graph file.
We load the Bloom filters during the prepare_revision_walk step,
currently only when dealing with a single pathspec. Extending
it to work with multiple pathspecs can be explored and built on
top of this series in the future.
While comparing trees in rev_compare_trees(), if the Bloom filter
says that the file is not different between the two trees, we don't
need to compute the expensive diff. This is where we get our
performance gains. The other response of the Bloom filter is '`:maybe',
in which case we fall back to the full diff calculation to determine
if the path was changed in the commit.
We do not try to use Bloom filters when the '--walk-reflogs' option
is specified. The '--walk-reflogs' option does not walk the commit
ancestry chain like the rest of the options. Incorporating the
performance gains when walking reflog entries would add more
complexity, and can be explored in a later series.
Performance Gains:
We tested the performance of `git log -- <path>` on the git repo, the linux
and some internal large repos, with a variety of paths of varying depths.
On the git and linux repos:
- we observed a 2x to 5x speed up.
On a large internal repo with files seated 6-10 levels deep in the tree:
- we observed 10x to 20x speed ups, with some paths going up to 28 times
faster.
Helped-by: Derrick Stolee <dstolee@microsoft.com
Helped-by: SZEDER Gábor <szeder.dev@gmail.com>
Helped-by: Jonathan Tan <jonathantanmy@google.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Add --changed-paths option to git commit-graph write. This option will
allow users to compute information about the paths that have changed
between a commit and its first parent, and write it into the commit graph
file. If the option is passed to the write subcommand we set the
COMMIT_GRAPH_WRITE_BLOOM_FILTERS flag and pass it down to the
commit-graph logic.
Helped-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Add logic to
a) parse Bloom filter information from the commit graph file and,
b) re-use existing Bloom filters.
See Documentation/technical/commit-graph-format for the format in which
the Bloom filter information is written to the commit graph file.
To read Bloom filter for a given commit with lexicographic position
'i' we need to:
1. Read BIDX[i] which essentially gives us the starting index in BDAT for
filter of commit i+1. It is essentially the index past the end
of the filter of commit i. It is called end_index in the code.
2. For i>0, read BIDX[i-1] which will give us the starting index in BDAT
for filter of commit i. It is called the start_index in the code.
For the first commit, where i = 0, Bloom filter data starts at the
beginning, just past the header in the BDAT chunk. Hence, start_index
will be 0.
3. The length of the filter will be end_index - start_index, because
BIDX[i] gives the cumulative 8-byte words including the ith
commit's filter.
We toggle whether Bloom filters should be recomputed based on the
compute_if_not_present flag.
Helped-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Update the technical documentation for commit-graph-format with
the formats for the Bloom filter index (BIDX) and Bloom filter
data (BDAT) chunks. Write the computed Bloom filters information
to the commit graph file using this format.
Helped-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
When running 'git commit-graph write --changed-paths', we sort the
commits by pack-order to save time when computing the changed-paths
bloom filters. This does not help when finding the commits via the
'--reachable' flag.
If not using pack-order, then sort by generation number before
examining the diff. Commits with similar generation are more likely
to have many trees in common, making the diff faster.
On the Linux kernel repository, this change reduced the computation
time for 'git commit-graph write --reachable --changed-paths' from
3m00s to 1m37s.
Helped-by: Jeff King <peff@peff.net>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Looking at the diff of commit objects in pack order is much faster than
in sha1 order, as it gives locality to the access of tree deltas
(whereas sha1 order is effectively random). Unfortunately the
commit-graph code sorts the commits (several times, sometimes as an oid
and sometimes a pointer-to-commit), and we ultimately traverse in sha1
order.
Instead, let's remember the position at which we see each commit, and
traverse in that order when looking at bloom filters. This drops my time
for "git commit-graph write --changed-paths" in linux.git from ~4
minutes to ~1.5 minutes.
Probably the "--reachable" code path would want something similar.
Or alternatively, we could use a different data structure (either a
hash, or maybe even just a bit in "struct commit") to keep track of
which oids we've seen, etc instead of sorting. And then we could keep
the original order.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Add new COMMIT_GRAPH_WRITE_CHANGED_PATHS flag that makes Git compute
Bloom filters for the paths that changed between a commit and it's
first parent, for each commit in the commit-graph. This computation
is done on a commit-by-commit basis.
We will write these Bloom filters to the commit-graph file, to store
this data on disk, in the next change in this series.
Helped-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
When computing the changed-paths bloom filters for the commit-graph,
we limit the size of the filter by restricting the number of paths
in the diff. Instead of computing a large diff and then ignoring the
result, it is better to halt the diff computation early.
Create a new "max_changes" option in struct diff_options. If non-zero,
then halt the diff computation after discovering strictly more changed
paths. This includes paths corresponding to trees that change.
Use this max_changes option in the bloom filter calculations. This
reduces the time taken to compute the filters for the Linux kernel
repo from 2m50s to 2m35s. On a large internal repository with ~500
commits that perform tree-wide changes, the time reduced from
6m15s to 3m48s.
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Add the core implementation for computing Bloom filters for
the paths changed between a commit and it's first parent.
We fill the Bloom filters as (const char *data, int len) pairs
as `struct bloom_filters" within a commit slab.
Filters for commits with no changes and more than 512 changes,
is represented with a filter of length zero. There is no gain
in distinguishing between a computed filter of length zero for
a commit with no changes, and an uncomputed filter for new commits
or for commits with more than 512 changes. The effect on
`git log -- path` is the same in both cases. We will fall back to
the normal diffing algorithm when we can't benefit from the
existence of Bloom filters.
Helped-by: Jeff King <peff@peff.net>
Helped-by: Derrick Stolee <dstolee@microsoft.com>
Reviewed-by: Jakub Narębski <jnareb@gmail.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Introduce the constructs for Bloom filters, Bloom filter keys
and Bloom filter settings.
For details on what Bloom filters are and how they work, refer
to Dr. Derrick Stolee's blog post [1]. It provides a concise
explanation of the adoption of Bloom filters as described in
[2] and [3].
Implementation specifics:
1. We currently use 7 and 10 for the number of hashes and the
size of each entry respectively. They served as great starting
values, the mathematical details behind this choice are
described in [1] and [4]. The implementation, while not
completely open to it at the moment, is flexible enough to allow
for tweaking these settings in the future.
Note: The performance gains we have observed with these values
are significant enough that we did not need to tweak these
settings. The performance numbers are included in the cover letter
of this series and in the commit message of the subsequent commit
where we use Bloom filters to speed up `git log -- path`.
2. As described in [1] and [3], we do not need 7 independent hashing
functions. We use the Murmur3 hashing scheme, seed it twice and
then combine those to procure an arbitrary number of hash values.
3. The filters will be sized according to the number of changes in
each commit, in multiples of 8 bit words.
[1] Derrick Stolee
"Supercharging the Git Commit Graph IV: Bloom Filters"
https://devblogs.microsoft.com/devops/super-charging-the-git-commit-graph-iv-Bloom-filters/
[2] Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, George Varghese
"An Improved Construction for Counting Bloom Filters"
http://theory.stanford.edu/~rinap/papers/esa2006b.pdf
https://doi.org/10.1007/11841036_61
[3] Peter C. Dillinger and Panagiotis Manolios
"Bloom Filters in Probabilistic Verification"
http://www.ccs.neu.edu/home/pete/pub/Bloom-filters-verification.pdf
https://doi.org/10.1007/978-3-540-30494-4_26
[4] Thomas Mueller Graf, Daniel Lemire
"Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters"
https://arxiv.org/abs/1912.08258
Helped-by: Derrick Stolee <dstolee@microsoft.com>
Reviewed-by: Jakub Narębski <jnareb@gmail.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
In preparation for computing changed paths Bloom filters,
implement the Murmur3 hash algorithm as described in [1].
It hashes the given data using the given seed and produces
a uniformly distributed hash value.
[1] https://en.wikipedia.org/wiki/MurmurHash#Algorithm
Helped-by: Derrick Stolee <dstolee@microsoft.com>
Helped-by: Szeder Gábor <szeder.dev@gmail.com>
Reviewed-by: Jakub Narębski <jnareb@gmail.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
This is a minor cleanup to make it easier to change
the number of chunks being written to the commit
graph.
Reviewed-by: Jakub Narębski <jnareb@gmail.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The 'pack.useSparse' configuration variable now defaults to 'true',
enabling an optimization that has been experimental since Git 2.21.
* ds/default-pack-use-sparse-to-true:
pack-objects: flip the use of GIT_TEST_PACK_SPARSE
config: set pack.useSparse=true by default
|
|
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
"git pull" learned to warn when no pull.rebase configuration
exists, and neither --[no-]rebase nor --ff-only is given (which
would result a merge).
* ah/force-pull-rebase-configuration:
pull: warn if the user didn't say whether to rebase or to merge
|
|
"git stash" has kept an escape hatch to use the scripted version
for a few releases, which got stale. It has been removed.
* tg/retire-scripted-stash:
stash: remove the stash.useBuiltin setting
stash: get git_stash_config at the top level
|
|
When "git describe C" finds an annotated tag with tagname A to be
the best name to explain commit C, and the tag is stored in a
"wrong" place in the refs/tags hierarchy, e.g. refs/tags/B, the
command gave a warning message but used A (not B) to describe C.
If C is exactly at the tag, the describe output would be "A", but
"git rev-parse A^0" would not be equal as "git rev-parse C^0". The
behavior of the command has been changed to use the "long" form
i.e. A-0-gOBJECTNAME, which is correctly interpreted by rev-parse.
* jc/describe-misnamed-annotated-tag:
describe: force long format for a name based on a mislocated tag
|
|
The "--fork-point" mode of "git rebase" regressed when the command
was rewritten in C back in 2.20 era, which has been corrected.
* at/rebase-fork-point-regression-fix:
rebase: --fork-point regression fix
|
|
Provide more information (e.g. the object of the tree-ish in which
the blob being converted appears, in addition to its path, which
has already been given) to smudge/clean conversion filters.
* bc/filter-process:
t0021: test filter metadata for additional cases
builtin/reset: compute checkout metadata for reset
builtin/rebase: compute checkout metadata for rebases
builtin/clone: compute checkout metadata for clones
builtin/checkout: compute checkout metadata for checkouts
convert: provide additional metadata to filters
convert: permit passing additional metadata to filter processes
builtin/checkout: pass branch info down to checkout_worktree
|
|
The code to interface with GnuPG has been refactored.
* hi/gpg-prefer-check-signature:
gpg-interface: prefer check_signature() for GPG verification
t: increase test coverage of signature verification output
|
|
SHA-256 transition continues.
* bc/sha-256-part-1-of-4: (22 commits)
fast-import: add options for rewriting submodules
fast-import: add a generic function to iterate over marks
fast-import: make find_marks work on any mark set
fast-import: add helper function for inserting mark object entries
fast-import: permit reading multiple marks files
commit: use expected signature header for SHA-256
worktree: allow repository version 1
init-db: move writing repo version into a function
builtin/init-db: add environment variable for new repo hash
builtin/init-db: allow specifying hash algorithm on command line
setup: allow check_repository_format to read repository format
t/helper: make repository tests hash independent
t/helper: initialize repository if necessary
t/helper/test-dump-split-index: initialize git repository
t6300: make hash algorithm independent
t6300: abstract away SHA-1-specific constants
t: use hash-specific lookup tables to define test constants
repository: require a build flag to use SHA-256
hex: add functions to parse hex object IDs in any algorithm
hex: introduce parsing variants taking hash algorithms
...
|
|
Fix "git checkout --recurse-submodules" of a nested submodule
hierarchy.
* pb/recurse-submodules-fix:
t/lib-submodule-update: add test removing nested submodules
unpack-trees: check for missing submodule directory in merged_entry
unpack-trees: remove outdated description for verify_clean_submodule
t/lib-submodule-update: move a test to the right section
t/lib-submodule-update: remove outdated test description
t7112: remove mention of KNOWN_FAILURE_SUBMODULE_RECURSIVE_NESTED
|
|
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Code clean-up.
* ss/submodule-foreach-cb:
submodule--helper.c: Rename 'cb_foreach' to 'foreach_cb'
|
|
Improve the structure of the documentation source a bit.
* jc/config-tar:
separate tar.* config to its own source file
|
|
Code clean-up.
* en/oidset-uninclude-hashmap:
oidset: remove unnecessary include
|
|
Corner case "git fetch" fix.
* ds/check-connected-reprepare-packed-git:
connected.c: reprepare packs for corner cases
|
|
Doc update.
* rs/doc-passthru-fetch-options:
pull: document more passthru options
|
|
The mechanism to prevent "git commit" from making an empty commit
or amending during an interrupted cherry-pick was broken during the
rewrite of "git rebase" in C, which has been corrected.
* pw/advise-rebase-skip:
commit: give correct advice for empty commit during a rebase
commit: encapsulate determine_whence() for sequencer
commit: use enum value for multiple cherry-picks
sequencer: write CHERRY_PICK_HEAD for reword and edit
cherry-pick: check commit error messages
cherry-pick: add test for `--skip` advice in `git commit`
t3404: use test_cmp_rev
|
|
Update "git p4" to work with Python 3.
* yz/p4-py3:
ci: use python3 in linux-gcc and osx-gcc and python2 elsewhere
git-p4: use python3's input() everywhere
git-p4: simplify regex pattern generation for parsing diff-tree
git-p4: use dict.items() iteration for python3 compatibility
git-p4: use functools.reduce instead of reduce
git-p4: fix freezing while waiting for fast-import progress
git-p4: use marshal format version 2 when sending to p4
git-p4: open .gitp4-usercache.txt in text mode
git-p4: convert path to unicode before processing them
git-p4: encode/decode communication with git for python3
git-p4: encode/decode communication with p4 for python3
git-p4: remove string type aliasing
git-p4: change the expansion test from basestring to list
git-p4: make python2.7 the oldest supported version
|
|
The real_path() convenience function can easily be misused; with a
bit of code refactoring in the callers' side, its use has been
eliminated.
* am/real-path-fix:
get_superproject_working_tree(): return strbuf
real_path_if_valid(): remove unsafe API
real_path: remove unsafe API
set_git_dir: fix crash when used with real_path()
|
|
In-code comment update.
* sg/commit-slab-clarify-peek:
commit-slab: clarify slabname##_peek()'s return value
|
|
Doc update.
* jc/maintain-doc:
update how-to-maintain-git
|
|
A handful of options to configure SSL when talking to proxies have
been added.
* js/https-proxy-config:
http: add environment variable support for HTTPS proxies
http: add client cert support for HTTPS proxies
|
|
Revamping of the advise API to allow more systematic enumeration of
advice knobs in the future.
* hw/advise-ng:
tag: use new advice API to check visibility
advice: revamp advise API
advice: change "setupStreamFailure" to "setUpstreamFailure"
advice: extract vadvise() from advise()
|
|
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Test fix.
* en/rebase-backend:
t3419: prevent failure when run with EXPENSIVE
|
|
l10n-2.26.0-rnd2.1
* tag 'l10n-2.26.0-rnd2.1' of https://github.com/git-l10n/git-po: (28 commits)
l10n: tr.po: change file mode to 644
l10n: de.po: Update German translation for Git 2.26.0
l10n: de.po: add missing space
l10n: tr: Fix a couple of ambiguities
l10n: Update Catalan translation
l10n: sv.po: Update Swedish translation (4839t0f0u)
l10n: zh_CN: Revise v2.26.0 translation
l10n: zh_CN: for git v2.26.0 l10n round 1 and 2
l10n: vi(4839t): Updated Vietnamese translation for v2.26.0
l10n: vi: fix translation + grammar
l10n: zh_TW.po: v2.26.0 round 2 (0 untranslated)
l10n: zh_TW.po: v2.26.0 round 1 (11 untranslated)
l10n: it.po: update the Italian translation for Git 2.26.0 round 2
l10n: es: 2.26.0 round#2
l10n: bg.po: Updated Bulgarian translation (4839t)
l10n: tr: v2.26.0 round 2
l10n: fr : v2.26.0 rnd 2
l10n: git.pot: v2.26.0 round 2 (7 new, 2 removed)
l10n: tr: Add glossary for Turkish translations
l10n: sv.po: Update Swedish translation (4835t0f0u)
...
|
|
Signed-off-by: Jiang Xin <worldhello.net@gmail.com>
|
|
This test runs a function which itself runs several assertions. The
last of these assertions cleans up the .git/rebase-apply directory,
since when run with EXPENSIVE set, the function is invoked a second time
to run the same tests with a larger data set.
However, as of 2ac0d6273f ("rebase: change the default backend from "am"
to "merge"", 2020-02-15), the default backend of rebase has changed, and
cleaning up the rebase-apply directory has no effect: it no longer
exists, since we're using rebase-merge instead.
Since we don't really care which rebase backend is in use, let's just
use the command "git rebase --quit", which will do the right thing
regardless.
Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The environment variable GIT_TEST_PACK_SPARSE was previously used
to allow testing the --sparse option for "git pack-objects" in
the test suite. This allowed interesting cases of "git push" to
also test this algorithm.
Since pack.useSparse is now true by default, we do not need this
variable to _enable_ the --sparse option, but instead to _disable_
it. This flips how we work with the variable a bit.
When checking for the variable, default to a value of -1 for
"unset". If unset, then take the default from the repo settings,
which is currently 1. Then, the --[no-]sparse command-line option
will override either of these settings.
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The pack.useSparse config option was introduced by 3d036eb0
(pack-objects: create pack.useSparse setting, 2019-01-19) and was
first available in v2.21.0. When enabled, the pack-objects process
during 'git push' will use a sparse tree walk when deciding which
trees and blobs to send to the remote. The algorithm was introduced
by d5d2e93 (revision: implement sparse algorithm, 2019-01-16) and
has been in production use by VFS for Git since around that time.
The features.experimental config option also enabled pack.useSparse,
so hopefully that has also increased exposure.
It is worth noting that pack.useSparse has a possibility of
sending more objects across a push, but requires a special
arrangement of exact _copies_ across directories. There is a test
in t5322-pack-objects-sparse.sh that demonstrates this possibility.
This test uses the --sparse option to "git pack-objects" but we
can make it implied by the config value to demonstrate that the
default value has changed.
While updating that test, I noticed that the documentation did not
include an option for --no-sparse, which is now more important than
it was before.
Since the downside is unlikely but the upside is significant, set
the default value of pack.useSparse to true. Remove it from the
set of options implied by features.experimental.
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Signed-off-by: Matthias Rüster <matthias.ruester@gmail.com>
Reviewed-by: Ralf Thielow <ralf.thielow@gmail.com>
Reviewed-by: Phillip Szelat <phillip.szelat@gmail.com>
|
|
Signed-off-by: Ralf Thielow <ralf.thielow@gmail.com>
|
|
* 'master' of https://github.com/prati0100/git-gui:
git-gui: create a new namespace for chord script evaluation
git-gui: reduce Tcl version requirement from 8.6 to 8.5
git-gui--askpass: coerce answers to UTF-8 on Windows
git-gui: fix error popup when doing blame -> "Show History Context"
git-gui: add missing close bracket
git-gui: update German translation
git-gui: extend translation glossary template with more terms
git-gui: update pot template and German translation to current source code
|
|
Signed-off-by: Emir Sarı <bitigchi@me.com>
|
|
Reduce the Tcl version requirement to 8.5 to allow git-gui to run on
MacOS distributions like High Sierra. While here, fix a potential
variable name collision.
* py/remove-tcloo:
git-gui: create a new namespace for chord script evaluation
git-gui: reduce Tcl version requirement from 8.6 to 8.5
|
Garima Singh
Jeff King
Derrick Stolee
Junio C Hamano
Jiang Xin
brian m. carlson
Matthias Rüster
Ralf Thielow
Emir Sarı
Pratyush Yadav