| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
Ever since we added reachability bitmap support, we've been able to use
it with rev-list to get the full list of objects, like:
git rev-list --objects --use-bitmap-index --all
But you can't do so without --objects, since we weren't ready to just
show the commits. However, the internals of the bitmap code are mostly
ready for this: they avoid opening up trees when walking to fill in the
bitmaps. We just need to actually pass in the rev_info to
traverse_bitmap_commit_list() so it knows which types to bother
triggering our callback for.
For completeness, the perf test now covers both the existing --objects
case, as well as the new commits-only behavior (the objects one got way
faster when we introduced bitmaps, but obviously isn't improved now).
Here are numbers for linux.git:
Test HEAD^ HEAD
------------------------------------------------------------------------
5310.7: rev-list (commits) 8.29(8.10+0.19) 1.76(1.72+0.04) -78.8%
5310.8: rev-list (objects) 8.06(7.94+0.12) 8.14(7.94+0.13) +1.0%
That run was cheating a little, as I didn't have any commit-graph in the
repository, and we'd built it by default these days when running git-gc.
Here are numbers with a commit-graph:
Test HEAD^ HEAD
------------------------------------------------------------------------
5310.7: rev-list (commits) 0.70(0.58+0.12) 0.51(0.46+0.04) -27.1%
5310.8: rev-list (objects) 6.20(6.09+0.10) 6.27(6.16+0.11) +1.1%
Still an improvement, but a lot less impressive.
We could have the perf script remove any commit-graph to show the
out-sized effect, but it probably makes sense to leave it in what would
be a more typical setup.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
In a repository with many packfiles, the cost of the procedure that
avoids registering the same packfile twice was unnecessarily high
by using an inefficient search algorithm, which has been corrected.
* cs/store-packfiles-in-hashmap:
packfile.c: speed up loading lots of packfiles
|
|
Test cleanup.
* jk/perf-wo-git-dot-pm:
t/perf: don't depend on Git.pm
|
|
PerfTest fix to avoid stale result mixed up with the latest round
of test results.
* tg/perf-remove-stale-result:
perf-lib: use a single filename for all measurement types
|
|
When loading packfiles on start-up, we traverse the internal packfile
list once per file to avoid reloading packfiles that have already
been loaded. This check runs in quadratic time, so for poorly
maintained repos with a large number of packfiles, it can be pretty
slow.
Add a hashmap containing the packfile names as we load them so that
the average runtime cost of checking for already-loaded packs becomes
constant.
Add a perf test to p5303 to show speed-up.
The existing p5303 test runtimes are dominated by other factors and do
not show an appreciable speed-up. The new test in p5303 clearly exposes
a speed-up in bad cases. In this test we create 10,000 packfiles and
measure the start-up time of git rev-parse, which does little else
besides load in the packs.
Here are the numbers for the new p5303 test:
Test HEAD^ HEAD
---------------------------------------------------------------------
5303.12: load 10,000 packs 1.03(0.92+0.10) 0.12(0.02+0.09) -88.3%
Signed-off-by: Colin Stolley <cstolley@runbox.com>
Helped-by: Jeff King <peff@peff.net>
[jc: squashed the change to call hashmap in install_packed_git() by peff]
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Code clean-up.
* jk/optim-in-pack-idx-conversion:
pack-objects: avoid pointless oe_map_new_pack() calls
|
|
The perf suite's aggregate.perl depends on Git.pm, which is a mild
annoyance if you've built git with NO_PERL. It turns out that the only
thing we use it for is a single call of the command_oneline() helper.
We can just replace this with backticks or similar.
Annoyingly, perl has no backtick equivalent that avoids a shell eval,
which means our $arg would require quoting. This probably doesn't matter
for our purposes, but it's better to be safe and model good style. So
we'll just provide a short helper around open(), which takes its
arguments as a list.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The perf tests write files recording the results of tests. These
results are later aggregated by 'aggregate.perl'. If the tests are run
multiple times, those results are overwritten by the new results. This
works just fine as long as there are only perf tests measuring the
times, whose results are stored in "$base".times files.
However 22bec79d1a ("t/perf: add infrastructure for measuring sizes",
2018-08-17) introduced a new type of test for measuring the size of
something. The results of this are written to "$base".size files.
"$base" is essentially made up of the basename of the script plus the
test number. So if test numbers shift because a new test was
introduced earlier in the script we might end up with both a ".times"
and a ".size" file for the same test. In the aggregation script the
".times" file is preferred over the ".size" file, so some size tests
might end with performance numbers from a previous run of the test.
This is mainly relevant when writing perf tests that check both
performance and sizes, and can get quite confusing during
developement.
We could fix this by doing a more thorough job of cleaning out old
".times" and ".size" files before running each test. However, an even
easier solution is to just use the same filename for both types of
measurement, meaning we'll always overwrite the previous result. We
don't even need to change the file format to distinguish the two;
aggregate.perl already decides which is which based on a regex of the
content (this may become ambiguous if we add new types in the future,
but we could easily add a header field to the file at that point).
Based on an initial patch from Thomas Gummerer, who discovered the
problem and did all of the analysis (which I stole for the commit
message above):
https://public-inbox.org/git/20191119185047.8550-1-t.gummerer@gmail.com/
Helped-by: Thomas Gummerer <t.gummerer@gmail.com>
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
This patch fixes an extreme slowdown in pack-objects when you have more
than 1023 packs. See below for numbers.
Since 43fa44fa3b (pack-objects: move in_pack out of struct object_entry,
2018-04-14), we use a complicated system to save some per-object memory.
Each object_entry structs gets a 10-bit field to store the index of the
pack it's in. We map those indices into pointers using
packing_data->in_pack_by_idx, which we initialize at the start of the
program. If we have 2^10 or more packs, then we instead create an array
of pack pointers, one per object. This is packing_data->in_pack.
So far so good. But there's one other tricky case: if a new pack arrives
after we've initialized in_pack_by_idx, it won't have an index yet. We
solve that by calling oe_map_new_pack(), which just switches on the fly
to the less-optimal in_pack mechanism, allocating the array and
back-filling it for already-seen objects.
But that logic kicks in even when we've switched to it already (whether
because we really did see a new pack, or because we had too many packs
in the first place). The result doesn't produce a wrong outcome, but
it's very slow. What happens is this:
- imagine you have a repo with 500k objects and 2000 packs that you
want to repack.
- before looking at any objects, we call prepare_in_pack_by_idx(). It
starts allocating an index for each pack. On the 1024th pack, it
sees there are too many, so it bails, leaving in_pack_by_idx as
NULL.
- while actually adding objects to the packing list, we call
oe_set_in_pack(), which checks whether the pack already has an
index. If it's one of the packs after the first 1023, then it
doesn't have one, and we'll call oe_map_new_pack().
But there's no useful work for that function to do. We're already
using in_pack, so it just uselessly walks over the complete list of
objects, trying to backfill in_pack.
And we end up doing this for almost 1000 packs (each of which may be
triggered by more than one object). And each time it triggers, we
may iterate over up to 500k objects. So in the absolute worst case,
this is quadratic in the number of objects.
The solution is simple: we don't need to bother checking whether the
pack has an index if we've already converted to using in_pack, since by
definition we're not going to use it. So we can just push the "does the
pack have a valid index" check down into that half of the conditional,
where we know we're going to use it.
The current test in p5303 sadly doesn't notice this problem, since it
maxes out at 1000 packs. If we add a new test to it at 2000 packs, it
does show the improvement:
Test HEAD^ HEAD
----------------------------------------------------------------------
5303.12: repack (2000) 26.72(39.68+0.67) 15.70(28.70+0.66) -41.2%
However, these many-pack test cases are rather expensive to run, so
adding larger and larger numbers isn't appealing. Instead, we can show
it off more easily by using GIT_TEST_FULL_IN_PACK_ARRAY, which forces us
into the absolute worst case: no pack has an index, so we'll trigger
oe_map_new_pack() pointlessly for every single object, making it truly
quadratic.
Here are the numbers (on git.git) with the included change to p5303:
Test HEAD^ HEAD
----------------------------------------------------------------------
5303.3: rev-list (1) 2.05(1.98+0.06) 2.06(1.99+0.06) +0.5%
5303.4: repack (1) 33.45(33.46+0.19) 2.75(2.73+0.22) -91.8%
5303.6: rev-list (50) 2.07(2.01+0.06) 2.06(2.01+0.05) -0.5%
5303.7: repack (50) 34.21(35.18+0.16) 3.49(4.50+0.12) -89.8%
5303.9: rev-list (1000) 2.87(2.78+0.08) 2.88(2.80+0.07) +0.3%
5303.10: repack (1000) 41.26(51.30+0.47) 10.75(20.75+0.44) -73.9%
Again, those improvements aren't realistic for the 1-pack case (because
in the real world, the full-array solution doesn't kick in), but it's
more useful to be testing the more-complicated code path.
While we're looking at this issue, we'll tweak one more thing: in
oe_map_new_pack(), we call REALLOC_ARRAY(pack->in_pack). But we'd never
expect to get here unless we're back-filling it for the first time, in
which case it would be NULL. So let's switch that to ALLOC_ARRAY() for
clarity, and add a BUG() to document the expectation. Unfortunately this
code isn't well-covered in the test suite because it's inherently racy
(it only kicks in if somebody else adds a new pack while we're in the
middle of repacking).
Signed-off-by: Jeff King <peff@peff.net>
Reviewed-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Reported-by: Jens Schleusener <Jens.Schleusener@fossies.org>
Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
There are two perf scripts numbered p5600, but with otherwise different
names ("clone-reference" versus "partial-clone"). We store timing
results in files named after the whole script, so internally we don't
get confused between the two. But "aggregate.perl" just prints the test
number for each result, giving multiple entries for "5600.3". It also
makes it impossible to skip one test but not the other with
GIT_SKIP_TESTS.
Let's renumber the one that appeared later (by date -- the source of the
problem is that the two were developed on independent branches). For the
non-perf test suite, our test-lint rule would have complained about this
when the two were merged, but t/perf never learned that trick.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
When we receive a remote ref update to sha1 "X", we want to check that
we have all of the objects needed by "X". We can assume that our
repository is not currently corrupted, and therefore if we have a ref
pointing at "Y", we have all of its objects. So we can stop our
traversal from "X" as soon as we hit "Y".
If we make the same non-corruption assumption about any repositories we
use to store alternates, then we can also use their ref tips to shorten
the traversal.
This is especially useful when cloning with "--reference", as we
otherwise do not have any local refs to check against, and have to
traverse the whole history, even though the other side may have sent us
few or no objects. Here are results for the included perf test (which
shows off more or less the maximal savings, getting one new commit and
sharing the whole history):
Test HEAD^ HEAD
--------------------------------------------------------------------
[on git.git]
5600.3: clone --reference 2.94(2.86+0.08) 0.09(0.08+0.01) -96.9%
[on linux.git]
5600.3: clone --reference 45.74(45.34+0.41) 0.36(0.30+0.08) -99.2%
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Performance test framework has been broken and measured the version
of Git that happens to be on $PATH, not the specified one to
measure, for a while, which has been corrected.
* ab/perf-installed-fix:
perf-lib.sh: forbid the use of GIT_TEST_INSTALLED
perf tests: add "bindir" prefix to git tree test results
perf-lib.sh: remove GIT_TEST_INSTALLED from perf-lib.sh
perf-lib.sh: make "./run <revisions>" use the correct gits
perf aggregate: remove GIT_TEST_INSTALLED from --codespeed
perf README: correct docs for 3c8f12c96c regression
|
|
The script to aggregate perf result unconditionally depended on
libjson-perl even though it did not have to, which has been
corrected.
* jk/perf-aggregate-wo-libjson:
t/perf: depend on perl JSON only when using --codespeed
|
|
Fix index-pack perf test so that the repeated invocations always
run in an empty repository, which emulates the initial clone
situation better.
* jk/p5302-avoid-collision-check-cost:
p5302: create the repo in each index-pack test
|
|
The connectivity bitmaps are created by default in bare
repositories now; also the pathname hash-cache is created by
default to avoid making crappy deltas when repacking.
* ew/repack-with-bitmaps-by-default:
pack-objects: default to writing bitmap hash-cache
t5310: correctly remove bitmaps for jgit test
repack: enable bitmaps by default on bare repos
|
|
During an initial "git clone --depth=..." partial clone, it is
pointless to spend cycles for a large portion of the connectivity
check that enumerates and skips promisor objects (which by
definition is all objects fetched from the other side). This has
been optimized out.
* js/partial-clone-connectivity-check:
t/perf: add perf script for partial clones
clone: do faster object check for partial clones
|
|
As noted in preceding commits setting GIT_TEST_INSTALLED has never
been supported or documented, and as noted in an earlier t/perf/README
change to the extent that it's been documented nobody's notices that
the example hasn't worked since 3c8f12c96c ("test-lib: reorder and
include GIT-BUILD-OPTIONS a lot earlier", 2012-06-24).
We could directly support GIT_TEST_INSTALLED for invocations without
the "run" script, such as:
GIT_TEST_INSTALLED=../../ ./p0000-perf-lib-sanity.sh
GIT_TEST_INSTALLED=/home/avar/g/git ./p0000-perf-lib-sanity.sh
But while not having this "error" will "work", it won't write the the
resulting "test-results/*" files to the right place, and thus a
subsequent call to aggregate.perl won't work as expected.
Let's just tell the user that they need to use the "run" script,
which'll correctly deal with this and set the right
PERF_RESULTS_PREFIX.
If someone's in desperate need of bypassing "run" for whatever reason
they can trivially do so by setting "PERF_SET_GIT_TEST_INSTALLED", but
not we won't have people who expect GIT_TEST_INSTALLED to just work
wondering why their aggregation doesn't work, even though they're
running the right "git".
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
|
|
Change the output file names in test-results/ to be
"test-results/bindir_<munged dir>" rather than just
"test-results/<munged dir>".
This is for consistency with the "build_" directories we have for
built revisions, i.e. "test-results/build_<SHA-1>".
There's no user-visible functional changes here, it just makes it
easier to see at a glance what "test-results" files are of what "type"
as they're all explicitly grouped together now, and to grep this code
to find both the run_dirs_helper() implementation and its
corresponding aggregate.perl code.
Note that we already guarantee that the rest of the
PERF_RESULTS_PREFIX is an absolute path, and since it'll start with
e.g. "/" which we munge to "_" we'll up with a readable string like
"bindir_home_avar[...]".
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
|
|
Follow-up my preceding change which fixed the immediate "./run
<revisions>" regression in 0baf78e7bc ("perf-lib.sh: rely on
test-lib.sh for --tee handling", 2019-03-15) and entirely get rid of
GIT_TEST_INSTALLED from perf-lib.sh (and aggregate.perl).
As noted in that change the dance we're doing with GIT_TEST_INSTALLED
perf-lib.sh isn't necessary, but there I was doing the most minimal
set of changes to quickly fix a regression.
But it's much simpler to never deal with the "GIT_TEST_INSTALLED" we
were setting in perf-lib.sh at all. Instead the run_dirs_helper() sets
the previously inferred $PERF_RESULTS_PREFIX directly.
Setting this at the callsite that's already best positioned to
exhaustively know about all the different cases we need to handle
where PERF_RESULTS_PREFIX isn't what we want already (the empty
string) makes the most sense. In one-off cases like:
./run ./p0000-perf-lib-sanity.sh
./p0000-perf-lib-sanity.sh
We'll just do the right thing because PERF_RESULTS_PREFIX will be
empty, and test-lib.sh takes care of finding where our git is.
Any refactoring of this code needs to change both the shell code and
the Perl code in aggregate.perl, because when running e.g.:
./run ../../ -- <test>
The "../../" path to a relative bindir needs to be munged to a
filename containing the results, and critically aggregate.perl does
not get passed the path to those aggregations, just "../..".
Let's fix cases where aggregate.perl would print e.g. ".." in its
report output for this, and "git" for "/home/avar/g/git", i.e. it
would always pick the last element. Now'll always print the full path
instead.
This also makes the code sturdier, e.g. you can feed "../.." to
"./run" and then an absolute path to the aggregate.perl script, as
long as the absolute path and "../.." resolved to the same directory
printing the aggregation will work.
Also simplify the "[_*]" on the RHS of "tr -c", we're trimming
everything to "_", so we don't need that.
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
|
|
Fix a really bad regression in 0baf78e7bc ("perf-lib.sh: rely on
test-lib.sh for --tee handling", 2019-03-15). Since that change all
runs of different <revisions> of git have used the git found in the
user's $PATH, e.g. /usr/bin/git instead of the <revision> we just
built and wanted to performance test.
The problem starts with GIT_TEST_INSTALLED not working like our
non-perf tests with the "run" script. I.e. you can't run performance
tests against a given installed git. Instead we expect to use it
ourselves to point GIT_TEST_INSTALLED to the <revision> we just built.
However, we had been relying on '$(cd "$GIT_TEST_INSTALLED" && pwd)'
to resolve that relative $GIT_TEST_INSTALLED to an absolute
path *before* test-lib.sh was loaded, in cases where it was
e.g. "build/<rev>/bin-wrappers" and we wanted "<abs_path>build/...".
This change post-dates another proposed solution by a few days[1], I
didn't notice that version when I initially wrote this. I'm doing the
most minimal thing to solve the regression here, a follow-up change
will move this result prefix selection logic entirely into the "run"
script.
This makes e.g. these cases all work:
./run . $PWD/../../ origin/master origin/next HEAD -- <tests>
As well as just a plain one-off:
./run <tests>
And, since we're passing down the new GIT_PERF_DIR_MYDIR_REL we make
sure the bug relating to aggregate.perl not finding our files as
described in 0baf78e7bc doesn't happen again.
What *doesn't* work is setting GIT_TEST_INSTALLED to a relative path,
this will subtly fail in test-lib.sh. This has always been the case
even before 0baf78e7bc, and as documented in t/README the
GIT_TEST_INSTALLED variable should be set to an absolute path (needs
to be set "to the bindir", which is always absolute), and the "perf"
framework expects to munge it itself.
Perhaps that should be dealt with in the future to allow manually
setting GIT_TEST_INSTALLED, but as a preceding commit showed the user
can just use the "run" script, which'll also pick the right output
directory for the test results as expected by aggregate.perl.
1. https://public-inbox.org/git/20190502222409.GA15631@sigill.intra.peff.net/
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
|
|
Remove the setting of the "environment" from the --codespeed output. I
don't think this is useful, and it helps with a later refactoring
where we GIT_TEST_INSTALLED stop munging/reading GIT_TEST_INSTALLED in
the perf tests in so many places.
This was added in 05eb1c37ed ("perf/aggregate: implement codespeed
JSON output", 2018-01-05), but since the "run" scripts uses
"GIT_TEST_INSTALLED" internally this was only ever useful for one-off
runs of a single revision as all the "environment" values would be
ones for whatever directory the "run" script ran last.
Let's instead fall back on the "uname -r" case, which is the sort of
thing the environment should be set to, not something that duplicates
other parts of the codpseed output. For setting the "environment" to
something custom the perf.repoName variable can be used. See
19cf57a92e ("perf/run: read GIT_PERF_REPO_NAME from perf.repoName",
2018-01-05).
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
|
|
Since 3c8f12c96c ("test-lib: reorder and include GIT-BUILD-OPTIONS a
lot earlier", 2012-06-24) the suggested advice of overriding
GIT_BUILD_DIR has not worked. We've printed a hard error like this
given e.g. GIT_BUILD_DIR=/home/avar/g/git:
/bin-wrappers/git is not executable; using GIT_EXEC_PATH
error: You haven't built things yet, have you?
Let's just suggest that the user run other gits via the "run"
script. That'll do the right thing for setting the path to the other
git, and running the "aggregate.perl" scripts afterwards will work.
As an aside, if setting GIT_BUILD_DIR had still worked, then the
MODERN_GIT feature/fix added in 1a0962dee5 ("t/perf: fix regression in
testing older versions of git", 2016-06-22) would have broke.
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
|
|
We don't cover the partial clone feature at all in t/perf. Let's at
least run a few basic tests so that we'll notice any regressions.
We'll do a no-blob clone, and split it into two parts: the actual object
transfer, and the subsequent checkout (which will of course require
another transfer to get the blobs). That will help us more clearly
assess the performance of each.
There are obviously a lot more possibilities besides just a no-blob
partial clone, but this should serve as a canary that alerts us to any
generic slow-downs (and we can add more tests later for cases that
aren't exercised here).
There are a few non-ideal things here that make this not an entirely
accurate test, but are probably OK for our purposes:
1. We have to do some extra prep/cleanup work inside the timing tests,
since they impact the on-disk state and the perf harness may run
each one multiple times.
In practice this is probably OK, since these bits should be much
less expensive than the operations we are measuring.
2. The clone time is likely to be dominated by the server's object
enumeration. In the real world, a repo large enough to drive people
to partial clones is likely to have reachability bitmaps enabled.
And in the opposite direction, our object transfer is happening at
the speed of a local pipe, whereas in the real world it would
bottle-neck on the network.
So any percentage speedups should be taken with a grain of salt.
But hopefully any regressions will produce enough of an effect to
be noticeable.
This script also demonstrates the recent improvement from dfa33a298d
(clone: do faster object check for partial clones, 2019-04-19):
Test dfa33a298d^ dfa33a298d
-------------------------------------------------------------------------
5600.2: clone without blobs 18.41(22.72+1.09) 6.83(11.65+0.50) -62.9%
5600.3: checkout of result 1.82(3.24+0.26) 1.84(3.24+0.26) +1.1%
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Performance fix for "rev-list --parents -- pathspec".
* jk/revision-rewritten-parents-in-prio-queue:
revision: use a prio_queue to hold rewritten parents
|
|
Commit 05eb1c37ed (perf/aggregate: implement codespeed JSON output,
2018-01-05) added a dependency on the perl JSON module to show output
from aggregate.perl, but we only need it when the user asks for
--codespeed output. While the module is pretty common, it's not part of
the base system, and this dependency can get in the way of producing the
default human-readable output.
Let's bump the "use" down to a "require" in the code path that needs it,
which will be interpreted at run-time instead of compile-time. People
not using "--codespeed" won't even load the module, and anybody using it
should see the same results (including the same perl error if they don't
have it).
Note that this skips the importing step, so we'll have to fully qualify
our function call. We could accomplish the same thing in other ways.
E.g., calling JSON->import() ourselves, or wrapping "use JSON" in an
eval. Since there's only one such call, this seems like the
least-magical way of doing it.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The p5302 script runs "index-pack --stdin" in each timing test. It does
two things to try to get good timings:
1. we do the repo creation in a separate (non-timed) setup test, so
that our timing is purely the index-pack run
2. we use a separate repo for each test; this is important because the
presence of existing objects in the repo influences the result
(because we'll end up doing collision checks against them)
But this forgets one thing: we generally run each timed test multiple
times to reduce the impact of noise. Which means that repeats of each
test after the first will be subject to the collision slowdown from
point 2, and we'll generally just end up taking the first time anyway.
Instead, let's create the repo in the test (effectively undoing point
1). That does add a constant amount of extra work to each iteration, but
it's quite small compared to the actual effects we're interested in
measuring.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
This patch fixes a quadratic list insertion in rewrite_one() when
pathspec limiting is combined with --parents. What happens is something
like this:
1. We see that some commit X touches the path, so we try to rewrite
its parents.
2. rewrite_one() loops forever, rewriting parents, until it finds a
relevant parent (or hits the root and decides there are none). The
heavy lifting is done by process_parent(), which uses
try_to_simplify_commit() to drop parents.
3. process_parent() puts any intermediate parents into the
&revs->commits list, inserting by commit date as usual.
So if commit X is recent, and then there's a large chunk of history that
doesn't touch the path, we may add a lot of commits to &revs->commits.
And insertion by commit date is O(n) in the worst case, making the whole
thing quadratic.
We tried to deal with this long ago in fce87ae538 (Fix quadratic
performance in rewrite_one., 2008-07-12). In that scheme, we cache the
oldest commit in the list; if the new commit to be added is older, we
can start our linear traversal there. This often works well in practice
because parents are older than their descendants, and thus we tend to
add older and older commits as we traverse.
But this isn't guaranteed, and in fact there's a simple case where it is
not: merges. Imagine we look at the first parent of a merge and see a
very old commit (let's say 3 years old). And on the second parent, as we
go back 3 years in history, we might have many commits. That one
first-parent commit has polluted our oldest-commit cache; it will remain
the oldest while we traverse a huge chunk of history, during which we
have to fall back to the slow, linear method of adding to the list.
Naively, one might imagine that instead of caching the oldest commit,
we'd start at the last-added one. But that just makes some cases faster
while making others slower (and indeed, while it made a real-world test
case much faster, it does quite poorly in the perf test include here).
Fundamentally, these are just heuristics; our worst case is still
quadratic, and some cases will approach that.
Instead, let's use a data structure with better worst-case performance.
Swapping out revs->commits for something else would have repercussions
all over the code base, but we can take advantage of one fact: for the
rewrite_one() case, nobody actually needs to see those commits in
revs->commits until we've finished generating the whole list.
That leaves us with two obvious options:
1. We can generate the list _unordered_, which should be O(n), and
then sort it afterwards, which would be O(n log n) total. This is
"sort-after" below.
2. We can insert the commits into a separate data structure, like a
priority queue. This is "prio-queue" below.
I expected that sort-after would be the fastest (since it saves us the
extra step of copying the items into the linked list), but surprisingly
the prio-queue seems to be a bit faster.
Here are timings for the new p0001.6 for all three techniques across a
few repositories, as compared to master:
master cache-last sort-after prio-queue
--------------------------------------------------------------------------------------------
GIT_PERF_REPO=git.git
0.52(0.50+0.02) 0.53(0.51+0.02) +1.9% 0.37(0.33+0.03) -28.8% 0.37(0.32+0.04) -28.8%
GIT_PERF_REPO=linux.git
20.81(20.74+0.07) 20.31(20.24+0.07) -2.4% 0.94(0.86+0.07) -95.5% 0.91(0.82+0.09) -95.6%
GIT_PERF_REPO=llvm-project.git
83.67(83.57+0.09) 4.23(4.15+0.08) -94.9% 3.21(3.15+0.06) -96.2% 2.98(2.91+0.07) -96.4%
A few items to note:
- the cache-list tweak does improve the bad case for llvm-project.git
that started my digging into this problem. But it performs terribly
on linux.git, barely helping at all.
- the sort-after and prio-queue techniques work well. They approach
the timing for running without --parents at all, which is what you'd
expect (see below for more data).
- prio-queue just barely outperforms sort-after. As I said, I'm not
really sure why this is the case, but it is. You can see it even
more prominently in this real-world case on llvm-project.git:
git rev-list --parents 07ef786652e7 -- llvm/test/CodeGen/Generic/bswap.ll
where prio-queue routinely outperforms sort-after by about 7%. One
guess is that the prio-queue may just be more efficient because it
uses a compact array.
There are three new perf tests:
- "rev-list --parents" gives us a baseline for running with --parents.
This isn't sped up meaningfully here, because the bad case is
triggered only with simplification. But it's good to make sure we
don't screw it up (now, or in the future).
- "rev-list -- dummy" gives us a baseline for just traversing with
pathspec limiting. This gives a lower bound for the next test (and
it's also a good thing for us to be checking in general for
regressions, since we don't seem to have any existing tests).
- "rev-list --parents -- dummy" shows off the problem (and our fix)
Here are the timings for those three on llvm-project.git, before and
after the fix:
Test master prio-queue
------------------------------------------------------------------------------
0001.3: rev-list --parents 2.24(2.12+0.12) 2.22(2.11+0.11) -0.9%
0001.5: rev-list -- dummy 2.89(2.82+0.07) 2.92(2.89+0.03) +1.0%
0001.6: rev-list --parents -- dummy 83.67(83.57+0.09) 2.98(2.91+0.07) -96.4%
Changes in the first two are basically noise, and you can see we
approach our lower bound in the final one.
Note that we can't fully get rid of the list argument from
process_parents(). Other callers do have lists, and it would be hard to
convert them. They also don't seem to have this problem (probably
because they actually remove items from the list as they loop, meaning
it doesn't grow so large in the first place). So this basically just
drops the "cache_ptr" parameter (which was used only by the one caller
we're fixing here) and replaces it with a prio_queue. Callers are free
to use either data structure, depending on what they're prepared to
handle.
Reported-by: Björn Pettersson A <bjorn.a.pettersson@ericsson.com>
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Since its inception, the perf-lib.sh script has manually handled the
"--tee" option (and other options which imply it, like "--valgrind")
with a cut-and-pasted block from test-lib.sh. That block has grown stale
over the years, and has at least three problems:
1. It uses $SHELL to re-exec the script, whereas the version in
test-lib.sh learned to use $TEST_SHELL_PATH.
2. It does an ad-hoc search of the "$*" string, whereas test-lib.sh
learned to carefully parse the arguments left to right.
3. It never learned about --verbose-log (which also implies --tee),
so it would not trigger for that option.
This last one was especially annoying, because t/perf/run uses the
GIT_TEST_OPTS from your config.mak to run the perf scripts. So if you've
set, say, "-x --verbose-log" there, it will be passed as part of most
perf runs. And while this script doesn't recognize the option, the
test-lib.sh that we source _does_, and the behavior ends up being much
more annoying:
- as the comment at the top of the block says, we have to run this
tee code early, before we start munging variables (it says
GIT_BUILD_DIR, but the problematic variable is actually
GIT_TEST_INSTALLED).
- since we don't recognize --verbose-log, we don't trigger the block.
We go on to munge GIT_TEST_INSTALLED, converting it from a relative
to an absolute path.
- then we source test-lib.sh, which _does_ recognize --verbose-log. It
re-execs the script, which runs again. But this time with an
absolute version of GIT_TEST_INSTALLED.
- As a result, we copy the absolute version of GIT_TEST_INSTALLED into
perf_results_prefix. Instead of writing our results to the expected
"test-results/build_1234abcd.p1234-whatever.times", we instead write
them to "test-results/_full_path_to_repo_t_perf_build_1234...".
The aggregate.perl script doesn't expect this, and so it prints
"<missing>" for each result (even though it spent considerable time
running the tests!).
We can solve all of these in one blow by just deleting our custom
handling, and relying on the inclusion of test-lib.sh to handle --tee,
--verbose-log, etc.
There's one catch, though. We want to handle GIT_TEST_INSTALLED after
we've included test-lib.sh, since we want it un-munged in the re-exec'd
version of the script. But if we want to convert it from a relative
to an absolute path, we must do so before we load test-lib.sh, since it
will change our working directory. So we compute the absolute directory
first, store it away, then include test-lib.sh, and finally assign to
GIT_TEST_INSTALLED as appropriate.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Enabling pack.writebitmaphashcache should always be a performance win.
It costs only 4 bytes per object on disk, and the timings in ae4f07fbcc
(pack-bitmap: implement optional name_hash cache, 2013-12-21) show it
improving fetch and partial-bitmap clone times by 40-50%.
The only reason we didn't enable it by default at the time is that early
versions of JGit's bitmap reader complained about the presence of
optional header bits it didn't understand. But that was changed in
JGit's d2fa3987a (Use bitcheck to check for presence of OPT_FULL option,
2013-10-30), which made it into JGit v3.5.0 in late 2014.
So let's turn this option on by default. It's backwards-compatible with
all versions of Git, and if you are also using JGit on the same
repository, you'd only run into problems using a version that's almost 5
years old.
We'll drop the manual setting from all of our test scripts, including
perf tests. This isn't strictly necessary, but it has two advantages:
1. If the hash-cache ever stops being enabled by default, our perf
regression tests will notice.
2. We can use the modified perf tests to show off the behavior of an
otherwise unconfigured repo, as shown below.
These are the results of a few of a perf tests against linux.git that
showed interesting results. You can see the expected speedup in 5310.4,
which was noted in ae4f07fbcc. Curiously, 5310.8 did not improve (and
actually got slower), despite seeing the opposite in ae4f07fbcc.
I don't have an explanation for that.
The tests from p5311 did not exist back then, but do show improvements
(a smaller pack due to better deltas, which we found in less time).
Test HEAD^ HEAD
-------------------------------------------------------------------------------------
5310.4: simulated fetch 7.39(22.70+0.25) 5.64(11.43+0.22) -23.7%
5310.8: clone (partial bitmap) 18.45(24.83+1.19) 19.94(28.40+1.36) +8.1%
5311.31: server (128 days) 0.41(1.13+0.05) 0.34(0.72+0.02) -17.1%
5311.32: size (128 days) 7.4M 7.0M -4.8%
5311.33: client (128 days) 1.33(1.49+0.06) 1.29(1.37+0.12) -3.0%
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Pruning generally has to traverse the whole commit graph in order to
see which objects are reachable. This is the exact problem that
reachability bitmaps were meant to solve, so let's use them (if they're
available, of course).
Here are timings on git.git:
Test HEAD^ HEAD
------------------------------------------------------------------------
5304.6: prune with bitmaps 3.65(3.56+0.09) 1.01(0.92+0.08) -72.3%
And on linux.git:
Test HEAD^ HEAD
--------------------------------------------------------------------------
5304.6: prune with bitmaps 35.05(34.79+0.23) 3.00(2.78+0.21) -91.4%
The tests show a pretty optimal case, as we'll have just repacked and
should have pretty good coverage of all refs with our bitmaps. But
that's actually pretty realistic: normally prune is run via "gc" right
after repacking.
A few notes on the implementation:
- the change is actually in reachable.c, so it would improve
reachability traversals by "reflog expire --stale-fix", as well.
Those aren't performed regularly, though (a normal "git gc" doesn't
use --stale-fix), so they're not really worth measuring. There's a
low chance of regressing that caller, since the use of bitmaps is
totally transparent from the caller's perspective.
- The bitmap case could actually get away without creating a "struct
object", and instead the caller could just look up each object id in
the bitmap result. However, this would be a marginal improvement in
runtime, and it would make the callers much more complicated. They'd
have to handle both the bitmap and non-bitmap cases separately, and
in the case of git-prune, we'd also have to tweak prune_shallow(),
which relies on our SEEN flags.
- Because we do create real object structs, we go through a few
contortions to create ones of the right type. This isn't strictly
necessary (lookup_unknown_object() would suffice), but it's more
memory efficient to use the correct types, since we already know
them.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The general strategy of "git prune" is to do a full reachability walk,
then for each loose object see if we found it in our walk. But if we
don't have any loose objects, we don't need to do the expensive walk in
the first place.
This patch postpones that walk until the first time we need to see its
results.
Note that this is really a specific case of a more general optimization,
which is that we could traverse only far enough to find the object under
consideration (i.e., stop the traversal when we find it, then pick up
again when asked about the next object, etc). That could save us in some
instances from having to do a full walk. But it's actually a bit tricky
to do with our traversal code, and you'd need to do a full walk anyway
if you have even a single unreachable object (which you generally do, if
any objects are actually left after running git-repack).
So in practice this lazy-load of the full walk catches one easy but
common case (i.e., you've just repacked via git-gc, and there's nothing
unreachable).
The perf script is fairly contrived, but it does show off the
improvement:
Test HEAD^ HEAD
-------------------------------------------------------------------------
5304.4: prune with no objects 3.66(3.60+0.05) 0.00(0.00+0.00) -100.0%
and would let us know if we accidentally regress this optimization.
Note also that we need to take special care with prune_shallow(), which
relies on us having performed the traversal. So this optimization can
only kick in for a non-shallow repository. Since this is easy to get
wrong and is not covered by existing tests, let's add an extra test to
t5304 that covers this case explicitly.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Some of the functions in our test library check that they were invoked
properly with conditions like this:
test "$#" = 2 ||
error "bug in the test script: not 2 parameters to test-expect-success"
If this particular condition is triggered, then 'error' will abort the
whole test script with a bold red error message [1] right away.
However, under certain circumstances the test script will be aborted
completely silently, namely if:
- a similar condition in a test helper function like
'test_line_count' is triggered,
- which is invoked from the test script's "main" shell [2],
- and the test script is run manually (i.e. './t1234-foo.sh' as
opposed to 'make t1234-foo.sh' or 'make test') [3]
- and without the '--verbose' option,
because the error message is printed from within 'test_eval_', where
standard output is redirected either to /dev/null or to a log file.
The only indication that something is wrong is that not all tests in
the script are executed and at the end of the test script's output
there is no "# passed all N tests" message, which are subtle and can
easily go unnoticed, as I had to experience myself.
Send these "bug in the test script" error messages directly to the
test scripts standard error and thus to the terminal, so those bugs
will be much harder to overlook. Instead of updating all ~20 such
'error' calls with a redirection, let's add a BUG() function to
'test-lib.sh', wrapping an 'error' call with the proper redirection
and also including the common prefix of those error messages, and
convert all those call sites [4] to use this new BUG() function
instead.
[1] That particular error message from 'test_expect_success' is
printed in color only when running with or without '--verbose';
with '--tee' or '--verbose-log' the error is printed without
color, but it is printed to the terminal nonetheless.
[2] If such a condition is triggered in a subshell of a test, then
'error' won't be able to abort the whole test script, but only the
subshell, which in turn causes the test to fail in the usual way,
indicating loudly and clearly that something is wrong.
[3] Well, 'error' aborts the test script the same way when run
manually or by 'make' or 'prove', but both 'make' and 'prove' pay
attention to the test script's exit status, and even a silently
aborted test script would then trigger those tools' usual
noticable error messages.
[4] Strictly speaking, not all those 'error' calls need that
redirection to send their output to the terminal, see e.g.
'test_expect_success' in the opening example, but I think it's
better to be consistent.
Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
p3400 makes a copy of the current repository to test git-rebase
performance, and creates new branches in the copy with `git checkout
-b'. If the original repository has branches with the same name as the
script is trying to create, this operation will fail.
This replaces these calls by `git checkout -B' to force the creation and
update of these branches.
Signed-off-by: Alban Gruin <alban.gruin@gmail.com>
Acked-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Update fsck.skipList implementation and documentation.
* ab/fsck-skiplist:
fsck: support comments & empty lines in skipList
fsck: use oidset instead of oid_array for skipList
fsck: use strbuf_getline() to read skiplist file
fsck: add a performance test for skipList
fsck: add a performance test
fsck: document that skipList input must be unabbreviated
fsck: document and test commented & empty line skipList input
fsck: document and test sorted skipList input
fsck tests: add a test for no skipList input
fsck tests: setup of bogus commit object
|
|
Create a performance test to see how the skipList implementation
performs. First we setup N bad commits, then we see how progressively
working our way up to 0..N in increments of 10x does. I.e. the
needle(s) in the haystack get progressively more numerous.
Signed-off-by: René Scharfe <l.s.r@web.de>
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Add a plain performance test for "fsck". This test will not be used to
/ referred to in any upcoming commit of mine in this series, but
having a simple test for fsck performance is valuable, so let's add it
while we're at it.
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
A server with bitmapped packs can serve a clone very
quickly. However, fetches are not necessarily made any
faster, because we spend a lot less time in object traversal
(which is what bitmaps help with) and more time finding
deltas (because we may have to throw out on-disk deltas if
the client does not have the base).
As a first step to making this faster, this patch introduces
a new perf script to measure fetches into a repo of various
ages from a fully-bitmapped server.
We separately measure the work done by the server (in
pack-objects) and that done by the client (in index-pack).
Furthermore, we measure the size of the resulting pack.
Breaking it down like this (instead of just doing a regular
"git fetch") lets us see how much each side benefits from
any changes. And since we know the pack size, if we estimate
the network speed, then one could calculate a complete
wall-clock time for the operation (though the script does
not do this automatically).
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The main objective of scripts in the perf framework is to
run "test_perf", which measures the time it takes to run
some operation. However, it can also be interesting to see
the change in the output size of certain operations.
This patch introduces test_size, which records a single
numeric output from the test and shows it in the aggregated
output (with pretty printing and relative size comparison).
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
This will let us reuse the code when we add new values to
aggregate besides times.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
About half of test_perf() is boilerplate preparing to run
_any_ test, and the other half is specifically running a
timing test. Let's split it into two functions, so that we
can reuse the boilerplate in future commits.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Performance test updates.
* cc/perf-bisect:
perf/bisect_run_script: disable codespeed
|
|
When bisecting a performance regression using a config file,
`./bisect_regression --config my_perf.conf` for example, the
config file can contain Codespeed configuration which would
instruct the 'aggregate.perl' script called by the 'run'
script to output results in the Codespeed format and maybe
to try to send this output to a Codespeed server.
This is unfortunate because the 'bisect_run_script' relies
on the regular output from 'aggregate.perl' to mesure
performance, so let's disable Codespeed output and sending
results to a Codespeed server.
Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
When passing an option '--foo' that it does not recognize, the
aggregate.perl script should die with an helpful error message
like:
Unknown option: foo
./aggregate.perl [options] [--] [<dir_or_rev>...] [--] \
[<test_script>...] >
Options:
--codespeed * Format output for Codespeed
--reponame <str> * Send given reponame to codespeed
--sort-by <str> * Sort output (only "regression" \
criteria is supported)
rather than:
fatal: Needed a single revision
rev-parse --verify --foo: command returned error: 128
To implement that let's use Getopt::Long for option parsing
instead of the current manual and sloppy parsing. This should
save some code and make option parsing simpler, tighter and
safer.
This will avoid something like 'foo--sort-by=regression' to
be handled as if '--sort-by=regression' had been used, for
example.
As Getopt::Long eats '--' at the end of options, this changes
a bit the way '--' is handled as we can now have '--' both
after the options and before the scripts.
Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Performance measuring framework in t/perf learned to help bisecting
performance regressions.
* cc/perf-bisect:
t/perf: add scripts to bisect performance regressions
perf/run: add --subsection option
|
|
The new bisect_regression script can be used to automatically bisect
performance regressions. It will pass the new bisect_run_script to
`git bisect run`.
Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
This new option makes it possible to run perf tests as defined
in only one subsection of a config file.
Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Small test-helper programs have been consolidated into a single
binary.
* nd/combined-test-helper: (36 commits)
t/helper: merge test-write-cache into test-tool
t/helper: merge test-wildmatch into test-tool
t/helper: merge test-urlmatch-normalization into test-tool
t/helper: merge test-subprocess into test-tool
t/helper: merge test-submodule-config into test-tool
t/helper: merge test-string-list into test-tool
t/helper: merge test-strcmp-offset into test-tool
t/helper: merge test-sigchain into test-tool
t/helper: merge test-sha1-array into test-tool
t/helper: merge test-scrap-cache-tree into test-tool
t/helper: merge test-run-command into test-tool
t/helper: merge test-revision-walking into test-tool
t/helper: merge test-regex into test-tool
t/helper: merge test-ref-store into test-tool
t/helper: merge test-read-cache into test-tool
t/helper: merge test-prio-queue into test-tool
t/helper: merge test-path-utils into test-tool
t/helper: merge test-online-cpus into test-tool
t/helper: merge test-mktemp into test-tool
t/helper: merge (unused) test-mergesort into test-tool
...
|
|
One of the most interesting thing one can be interested in when
looking at performance test results is possible performance
regressions.
This new option makes it easy to spot such possible regressions.
This new option is named '--sort-by=regression' to make it
possible and easy to add other ways to sort the results, like for
example '--sort-by=utime'.
If we would like to sort according to how much the stime regressed
we could also add a new option called '--sort-by=regression:stime'.
Then '--sort-by=regression' could become a synonym for
'--sort-by=regression:rtime'.
Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
This new helper function will be reused in a subsequent
commit.
Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
Jeff King
Junio C Hamano
Colin Stolley
Elijah Newren
Ævar Arnfjörð Bjarmason
SZEDER Gábor
Alban Gruin
René Scharfe
Christian Couder