From: Jeff King <hidden> Date: 2021-01-27 22:12:32
This series teaches rev-list to compute the on-disk size used by a set
of objects. You can do the same thing with cat-file, but this is much
faster (see the timings in the second commit).
We've been running it for about 5 years at GitHub. I hesitated sending
it upstream because it's a bit weird and special-purpose. But it does
come in handy for debugging, analyzing repos, etc. So maybe others will
find it useful.
The first patch is just a test-script enhancement to let test_commit
avoid creating tags. During some recent refactoring, we actually broke
the --disk-usage feature but the test script didn't catch it because the
tags were being picked up by "--all". Since this is at least the third
time I've run into that in our test suite, I thought I'd make it a
little more convenient to avoid. :)
[1/2]: t: add --no-tag option to test_commit
[2/2]: rev-list: add --disk-usage option for calculating disk usage
Documentation/rev-list-options.txt | 9 ++++++
builtin/rev-list.c | 49 ++++++++++++++++++++++++++++
pack-bitmap.c | 50 +++++++++++++++++++++++++++++
pack-bitmap.h | 2 ++
t/t4208-log-magic-pathspec.sh | 9 ++----
t/t6114-rev-list-du.sh | 51 ++++++++++++++++++++++++++++++
t/test-lib-functions.sh | 9 +++++-
7 files changed, 171 insertions(+), 8 deletions(-)
create mode 100755 t/t6114-rev-list-du.sh
-Peff
From: Jeff King <hidden> Date: 2021-01-27 22:13:13
One of the conveniences that test_commit offers is making a tag for each
commit. This makes it easy to refer to the commits in subsequent
commands. But it can also be a pain if you care about reachability,
because those tags keep the commits reachable even if they are rewound
from the branch they're made on.
The alternative is that scripts have to call test_tick, git-add, and
git-commit themselves. Let's add a --no-tag option to give them the
one-liner convenience of using test_commit.
This is in preparation for the next patch, which will add some more
calls. But I cleaned up an existing site to show off the feature. There
are probably more cleanups possible.
Signed-off-by: Jeff King <redacted>
---
t/t4208-log-magic-pathspec.sh | 9 ++-------
t/test-lib-functions.sh | 9 ++++++++-
2 files changed, 10 insertions(+), 8 deletions(-)
@@ -31,13 +31,8 @@ test_expect_success '"git log :/a -- " should not be ambiguous' ' test_expect_success'"git log :/detached -- " should find a commit only in HEAD''test_when_finished"git checkout main"&&gitcheckout--detach&&-# Must manually call `test_tick` instead of using `test_commit`,-# because the latter additionally creates a tag, which would make-# the commit reachable not only via HEAD.-test_tick&&-gitcommit--allow-empty-mdetached&&-test_tick&&-gitcommit--allow-empty-msomething-else&&+test_commit--no-tagdetached&&+test_commit--no-tagsomething-else&&gitlog:/detached--'
From: Taylor Blau <hidden> Date: 2021-01-27 22:57:30
On Wed, Jan 27, 2021 at 05:12:25PM -0500, Jeff King wrote:
The alternative is that scripts have to call test_tick, git-add, and
git-commit themselves. Let's add a --no-tag option to give them the
one-liner convenience of using test_commit.
Thanks for finding a spot that does this and making it more readable
with the new --no-tag option.
This patch looks obviously correct. I'm sure that (as you note) there
are more cleanups possible, but I'm happy to just grab an easy one and
let future refactorings clean up the remaining ones.
Thanks,
Taylor
From: Jeff King <hidden> Date: 2021-01-27 22:17:56
It can sometimes be useful to see which refs are contributing to the
overall repository size (e.g., does some branch have a bunch of objects
not found elsewhere in history, which indicates that deleting it would
shrink the size of a clone).
You can find that out by generating a list of objects, getting their
sizes from cat-file, and then summing them, like:
git rev-list --objects main..branch
cut -d' ' -f1 |
git cat-file --batch-check='%(objectsize:disk)' |
perl -lne '$total += $_; END { print $total }'
Though note that the caveats from git-cat-file(1) apply here. We "blame"
base objects more than their deltas, even though the relationship could
easily be flipped. Still, it can be a useful rough measure.
But one problem is that it's slow to run. Teaching rev-list to sum up
the sizes can be much faster for two reasons:
1. It skips all of the piping of object names and sizes.
2. If bitmaps are in use, for objects that are in the
bitmapped packfile we can skip the oid_object_info()
lookup entirely, and just ask the revindex for the
on-disk size.
This patch implements a --disk-usage option which produces the same
answer in a fraction of the time. Here are some timings using a clone of
torvalds/linux:
[rev-list piped to cat-file, no bitmaps]
$ time git rev-list --objects --all |
cut -d' ' -f1 |
git cat-file --buffer --batch-check='%(objectsize:disk)' |
perl -lne '$total += $_; END { print $total }'
1455691059
real 0m34.336s
user 0m46.533s
sys 0m2.953s
[internal, no bitmaps]
$ time git rev-list --disk-usage --all
1455691059
real 0m32.662s
user 0m32.306s
sys 0m0.353s
The wall-clock times aren't that different because of parallelism, but
notice the CPU savings between the two. We saved 35% of the CPU just by
avoiding the pipes.
But the real win is with bitmaps. If we use them without the new option:
[rev-list piped to cat-file, bitmaps]
$ time git rev-list --objects --all --use-bitmap-index |
cut -d' ' -f1 |
git cat-file --batch-check='%(objectsize:disk)' |
perl -lne '$total += $_; END { print $total }'
real 0m9.954s
user 0m11.234s
sys 0m8.522s
then we're faster to generate the list of objects, but we still spend a
lot of time piping and looking things up. But if we do both together:
[internal, bitmaps]
$ time git rev-list --disk-usage --all --use-bitmap-index
1455691059
real 0m0.235s
user 0m0.186s
sys 0m0.049s
then we get the same answer much faster.
For "--all", that answer will correspond closely to "du objects/pack",
of course. But we're actually checking reachability here, so we're still
fast when we ask for more interesting things:
$ time git rev-list --disk-usage --all --use-bitmap-index v5.0..v5.10
374798628
real 0m0.429s
user 0m0.356s
sys 0m0.072s
Signed-off-by: Jeff King <redacted>
---
This _could_ be made more flexible, but I didn't think it was worth the
complexity. Some obvious things one might want are:
- not counting up all reachable objects (i.e., requiring --objects for
this output, and omitting it just counts up commits). This could be
handled in the bitmap case with some extra code (OR-ing with the
type bitmaps).
But after 5 years of this patch, I've never wanted that once. The
disk usage of just some of the objects isn't really that useful (and
of course you can still get it by piping to cat-file).
- an option to output the sizes of specific objects along with their
oids. But if you want to get to this level of flexibility, I think
you're better off just using cat-file (and if we are concerned about
the pipe costs, we should teach rev-list to understand cat-file's
custom formats).
Documentation/rev-list-options.txt | 9 ++++++
builtin/rev-list.c | 49 ++++++++++++++++++++++++++++
pack-bitmap.c | 50 +++++++++++++++++++++++++++++
pack-bitmap.h | 2 ++
t/t6114-rev-list-du.sh | 51 ++++++++++++++++++++++++++++++
5 files changed, 161 insertions(+)
create mode 100755 t/t6114-rev-list-du.sh
@@ -222,6 +222,15 @@ ifdef::git-rev-list[] test the exit status to see if a range of objects is fully connected (or not). It is faster than redirecting stdout to `/dev/null` as the output does not have to be formatted.++--disk-usage::+ Suppress normal output; instead, print the sum of the bytes used+ for on-disk storage by the selected objects. This is equivalent+ to piping the output of `rev-list --objects` into+ `git cat-file --batch-check='%(objectsize:disk)', except that it+ runs much faster (especially with `--use-bitmap-index`). See the+ `CAVEATS` section in linkgit:git-cat-file[1] for the limitations+ of what "on-disk storage" means. endif::git-rev-list[] --cherry-mark::
@@ -80,6 +80,19 @@ static int arg_show_object_names = 1;#define DEFAULT_OIDSET_SIZE (16*1024)+staticintshow_disk_usage;+staticoff_ttotal_disk_usage;++staticoff_tget_object_disk_usage(structobject*obj)+{+off_tsize;+structobject_infooi=OBJECT_INFO_INIT;+oi.disk_sizep=&size;+if(oid_object_info_extended(the_repository,&obj->oid,&oi,0)<0)+die(_("unable to get disk usage of %s"),oid_to_hex(&obj->oid));+returnsize;+}+staticvoidfinish_commit(structcommit*commit);staticvoidshow_commit(structcommit*commit,void*data){
@@ -1430,3 +1430,53 @@ int bitmap_has_oid_in_uninteresting(struct bitmap_index *bitmap_git,returnbitmap_git&&bitmap_walk_contains(bitmap_git,bitmap_git->haves,oid);}++off_tget_disk_usage_from_bitmap(structbitmap_index*bitmap_git)+{+structbitmap*result=bitmap_git->result;+structpacked_git*pack=bitmap_git->pack;+structeindex*eindex=&bitmap_git->ext_index;+structobject_infooi=OBJECT_INFO_INIT;+off_tobject_size;+off_ttotal=0;+size_ti;++oi.disk_sizep=&object_size;++for(i=0;i<result->word_alloc;i++){+eword_tword=result->words[i];+size_tbase=(i*BITS_IN_EWORD);+unsignedoffset;++for(offset=0;offset<BITS_IN_EWORD;offset++){+size_tpos;++if((word>>offset)==0)+break;++offset+=ewah_bit_ctz64(word>>offset);+pos=base+offset;++/*+*Ifit'sinthepack,wecanusethefastpath+*andjustchecktherevindex.Otherwise,we+*fallbacktolookingitup.+*/+if(pos<pack->num_objects){+object_size=+pack_pos_to_offset(pack,pos+1)-+pack_pos_to_offset(pack,pos);+}else{+structobject*obj;+obj=eindex->objects[pos-pack->num_objects];+if(oid_object_info_extended(the_repository,&obj->oid,&oi,0)<0)+die(_("unable to get disk usage of %s"),+oid_to_hex(&obj->oid));+}++total+=object_size;+}+}++returntotal;+}
@@ -0,0 +1,51 @@+#!/bin/sh++test_description='basic tests of rev-list --disk-usage'+../test-lib.sh++# we want a mix of reachable and unreachable, as well as+# objects in the bitmapped pack and some outside of it+test_expect_success'set up repository''+test_commit--no-tagone&&+test_commit--no-tagtwo&&+gitrepack-adb&&+gitreset--hardHEAD^&&+test_commit--no-tagthree&&+test_commit--no-tagfour&&+gitreset--hardHEAD^+'++# We don't want to hardcode sizes, because they depend on the exact details of+# packing, zlib, etc. We'll assume that the regular rev-list and cat-file+# machinery works and compare the --disk-usage output to that.+disk_usage_slow(){+gitrev-list--objects"$@"|+cut-d' '-f1|+gitcat-file--batch-check="%(objectsize:disk)"|+perl-lne'$total += $_; END { print $total}'+}++# check behavior with given rev-list options; note that+# whitespace is not preserved in args+check_du(){+args=$*++test_expect_success"generate expected size ($args)""+disk_usage_slow$args>expect+"++test_expect_success"rev-list --disk-usage without bitmaps ($args)""+gitrev-list--disk-usage$args>actual&&+test_cmpexpectactual+"++test_expect_success"rev-list --disk-usage with bitmaps ($args)""+gitrev-list--disk-usage--use-bitmap-index$args>actual&&+test_cmpexpectactual+"+}++check_duHEAD+check_duHEAD^..HEAD++test_done
From: Taylor Blau <hidden> Date: 2021-01-27 23:01:02
On Wed, Jan 27, 2021 at 05:17:07PM -0500, Jeff King wrote:
It can sometimes be useful to see which refs are contributing to the
overall repository size (e.g., does some branch have a bunch of objects
not found elsewhere in history, which indicates that deleting it would
shrink the size of a clone).
You can find that out by generating a list of objects, getting their
sizes from cat-file, and then summing them, like:
git rev-list --objects main..branch
cut -d' ' -f1 |
I suspect that this is from the original commit message that you wrote a
half-decade ago. Not that it really means much, but you could shave one
process off of this example by passing '--no-object-names' to 'git
rev-list'.
The whole point is that we can avoid having to do this, so I don't think
it really matters, anyway.
[...]
then we're faster to generate the list of objects, but we still spend a
lot of time piping and looking things up. But if we do both together:
[internal, bitmaps]
$ time git rev-list --disk-usage --all --use-bitmap-index
1455691059
real 0m0.235s
user 0m0.186s
sys 0m0.049s
then we get the same answer much faster.
Very nice.
This _could_ be made more flexible, but I didn't think it was worth the
complexity. Some obvious things one might want are:
- not counting up all reachable objects (i.e., requiring --objects for
this output, and omitting it just counts up commits). This could be
handled in the bitmap case with some extra code (OR-ing with the
type bitmaps).
But after 5 years of this patch, I've never wanted that once. The
disk usage of just some of the objects isn't really that useful (and
of course you can still get it by piping to cat-file).
Yeah. I think it's trivial to support it, but I'm in favor of a simpler
interface.
That said, I worry about painting ourselves into a corner if the default
implies --objects. If we wanted to change that, I'm pretty sure you'd
have to write a rule that says "imply objects, unless --tags, --blobs or
etc. are specified, and then only do that".
Maybe we'll never have to address that, but it's worth thinking about
before committing to implying '--objects'.
- an option to output the sizes of specific objects along with their
oids. But if you want to get to this level of flexibility, I think
you're better off just using cat-file (and if we are concerned about
the pipe costs, we should teach rev-list to understand cat-file's
custom formats).
This I agree with completely. Any caller who wants that level of
flexibility shouldn't mind the piping.
I have no comments on the patch itself, which looks fine to me (and I
have seen over and over again as it seems to regularly cause conflicts
when merging new releases into GitHub's fork :-)).
Thanks,
Taylor
From: Jeff King <hidden> Date: 2021-01-27 23:36:36
On Wed, Jan 27, 2021 at 05:57:21PM -0500, Taylor Blau wrote:
quoted
You can find that out by generating a list of objects, getting their
sizes from cat-file, and then summing them, like:
git rev-list --objects main..branch
cut -d' ' -f1 |
I suspect that this is from the original commit message that you wrote a
half-decade ago. Not that it really means much, but you could shave one
process off of this example by passing '--no-object-names' to 'git
rev-list'.
That, plus my muscle memory to do the cut. We should probably model the
better form here, and use it in the test, though (not worth a re-roll on
its own, but it looks like there are a few other minor bits).
quoted
- not counting up all reachable objects (i.e., requiring --objects for
this output, and omitting it just counts up commits). This could be
handled in the bitmap case with some extra code (OR-ing with the
type bitmaps).
But after 5 years of this patch, I've never wanted that once. The
disk usage of just some of the objects isn't really that useful (and
of course you can still get it by piping to cat-file).
Yeah. I think it's trivial to support it, but I'm in favor of a simpler
interface.
That said, I worry about painting ourselves into a corner if the default
implies --objects. If we wanted to change that, I'm pretty sure you'd
have to write a rule that says "imply objects, unless --tags, --blobs or
etc. are specified, and then only do that".
Maybe we'll never have to address that, but it's worth thinking about
before committing to implying '--objects'.
Yeah, the one thing that gives me pause is that it would be hard to undo
later. I didn't write the code to handle it in the bitmap case, but I
don't think it would be _too_ bad. It is slightly annoying for the
all-objects case, because the existing code isn't set up well to iterate
either a specific type, or all types.
I have no comments on the patch itself, which looks fine to me (and I
have seen over and over again as it seems to regularly cause conflicts
when merging new releases into GitHub's fork :-)).
From: Eric Sunshine <hidden> Date: 2021-01-27 23:14:31
On Wed, Jan 27, 2021 at 5:20 PM Jeff King [off-list ref] wrote:
This patch implements a --disk-usage option which produces the same
answer in a fraction of the time. Here are some timings using a clone of
torvalds/linux:
[rev-list piped to cat-file, no bitmaps]
$ time git rev-list --objects --all |
cut -d' ' -f1 |
git cat-file --buffer --batch-check='%(objectsize:disk)' |
perl -lne '$total += $_; END { print $total }'
1455691059
real 0m34.336s
user 0m46.533s
sys 0m2.953s
This example shows the computed size (1455691059)...
But the real win is with bitmaps. If we use them without the new option:
[rev-list piped to cat-file, bitmaps]
$ time git rev-list --objects --all --use-bitmap-index |
cut -d' ' -f1 |
git cat-file --batch-check='%(objectsize:disk)' |
perl -lne '$total += $_; END { print $total }'
real 0m9.954s
user 0m11.234s
sys 0m8.522s
...however, this example does not (but all the others do). Simple
copy/paste error?
Not worth a re-roll, of course.
From: Jeff King <hidden> Date: 2021-01-27 23:42:50
On Wed, Jan 27, 2021 at 06:07:57PM -0500, Eric Sunshine wrote:
This example shows the computed size (1455691059)...
[...]
...however, this example does not (but all the others do). Simple
copy/paste error?
Yep, thanks for catching. (Of course I have since repacked my linux.git,
so now it produces a different answer! It does match the current value
of the other techniques, though).
Not worth a re-roll, of course.
Agreed, but it looks like there are a few other minor bits, so I'll
definitely fix it up at the same time. I'll give a little more time
before re-rolling in case there are any other comments.
-Peff
@@ -222,6 +222,15 @@ ifdef::git-rev-list[] test the exit status to see if a range of objects is fully connected (or not). It is faster than redirecting stdout to `/dev/null` as the output does not have to be formatted.++--disk-usage::+ Suppress normal output; instead, print the sum of the bytes used+ for on-disk storage by the selected objects. This is equivalent+ to piping the output of `rev-list --objects` into+ `git cat-file --batch-check='%(objectsize:disk)', except that it
[ Just a drive-by typo comment from a reader not knowledgeable enough to
review the code change :) ]
The cat-file command is missing its closing quote.
From: Jeff King <hidden> Date: 2021-01-27 23:38:29
On Wed, Jan 27, 2021 at 06:01:51PM -0500, Kyle Meyer wrote:
quoted
+--disk-usage::
+ Suppress normal output; instead, print the sum of the bytes used
+ for on-disk storage by the selected objects. This is equivalent
+ to piping the output of `rev-list --objects` into
+ `git cat-file --batch-check='%(objectsize:disk)', except that it
[ Just a drive-by typo comment from a reader not knowledgeable enough to
review the code change :) ]
The cat-file command is missing its closing quote.
Thanks for catching that. I should have looked at the output of
doc-diff, which does reveal it.
-Peff
From: Taylor Blau <hidden> Date: 2021-01-27 23:26:06
On Wed, Jan 27, 2021 at 05:11:36PM -0500, Jeff King wrote:
The first patch is just a test-script enhancement to let test_commit
avoid creating tags. During some recent refactoring, we actually broke
the --disk-usage feature but the test script didn't catch it because the
tags were being picked up by "--all". Since this is at least the third
time I've run into that in our test suite, I thought I'd make it a
little more convenient to avoid. :)
I appreciate the non-incriminating "we", but the person who caused the
regression was most certainly me ;-).
This happened while cherry-picking Junio's recent merge of
tb/revindex-api, which obviously did not cause a merge conflict with
this new caller. The remaining details are boring, but they definitely
weren't Peff's fault :-).
Thanks,
Taylor
From: Jeff King <hidden> Date: 2021-02-09 10:55:42
Here's a re-roll of my series to add "rev-list --disk-usage", for
counting up object storage used for various slices of history.
This fixes the minor bits mentioned in review for v1, but the big change
is that "--disk-usage" no longer implies "--objects". I think you
generally would want to use it with that option, but it really seemed to
violate the principle of least surprise for the user.
That requires handling each object type independently, but the code for
that turned out to be not too bad (and is modeled after the similar
logic in traverse_bitmap_commit_list()). I was slightly concerned that
it would slow things down to walk over the bitmap multiple times, but it
doesn't seem to make much of a difference in practice.
There's a range-diff below, but it's not really worth looking at. All of
the interesting parts were rewritten completely, so you're better off to
just read patch 2 again (and patch 1 did not change at all).
[1/2]: t: add --no-tag option to test_commit
[2/2]: rev-list: add --disk-usage option for calculating disk usage
Documentation/rev-list-options.txt | 9 ++++
builtin/rev-list.c | 46 +++++++++++++++++
pack-bitmap.c | 81 ++++++++++++++++++++++++++++++
pack-bitmap.h | 2 +
t/t4208-log-magic-pathspec.sh | 9 +---
t/t6114-rev-list-du.sh | 51 +++++++++++++++++++
t/test-lib-functions.sh | 9 +++-
7 files changed, 199 insertions(+), 8 deletions(-)
create mode 100755 t/t6114-rev-list-du.sh
1: 20f8edeff1 = 1: 6365cd94bd t: add --no-tag option to test_commit
2: 64e28cb6c9 ! 2: 8a93583dee rev-list: add --disk-usage option for calculating disk usage
@@ Commit message
You can find that out by generating a list of objects, getting their
sizes from cat-file, and then summing them, like:
- git rev-list --objects main..branch
- cut -d' ' -f1 |
+ git rev-list --objects --no-object-names main..branch
git cat-file --batch-check='%(objectsize:disk)' |
perl -lne '$total += $_; END { print $total }'
@@ Commit message
torvalds/linux:
[rev-list piped to cat-file, no bitmaps]
- $ time git rev-list --objects --all |
- cut -d' ' -f1 |
+ $ time git rev-list --objects --no-object-names --all |
git cat-file --buffer --batch-check='%(objectsize:disk)' |
perl -lne '$total += $_; END { print $total }'
- 1455691059
- real 0m34.336s
- user 0m46.533s
- sys 0m2.953s
+ 1459938510
+ real 0m29.635s
+ user 0m38.003s
+ sys 0m1.093s
[internal, no bitmaps]
- $ time git rev-list --disk-usage --all
- 1455691059
- real 0m32.662s
- user 0m32.306s
- sys 0m0.353s
+ $ time git rev-list --disk-usage --objects --all
+ 1459938510
+ real 0m31.262s
+ user 0m30.885s
+ sys 0m0.376s
- The wall-clock times aren't that different because of parallelism, but
- notice the CPU savings between the two. We saved 35% of the CPU just by
+ Even though the wall-clock time is slightly worse due to parallelism,
+ notice the CPU savings between the two. We saved 21% of the CPU just by
avoiding the pipes.
But the real win is with bitmaps. If we use them without the new option:
[rev-list piped to cat-file, bitmaps]
- $ time git rev-list --objects --all --use-bitmap-index |
- cut -d' ' -f1 |
+ $ time git rev-list --objects --no-object-names --all --use-bitmap-index |
git cat-file --batch-check='%(objectsize:disk)' |
perl -lne '$total += $_; END { print $total }'
- real 0m9.954s
- user 0m11.234s
- sys 0m8.522s
+ 1459938510
+ real 0m6.244s
+ user 0m8.452s
+ sys 0m0.311s
then we're faster to generate the list of objects, but we still spend a
lot of time piping and looking things up. But if we do both together:
[internal, bitmaps]
- $ time git rev-list --disk-usage --all --use-bitmap-index
- 1455691059
- real 0m0.235s
- user 0m0.186s
+ $ time git rev-list --disk-usage --objects --all --use-bitmap-index
+ 1459938510
+ real 0m0.219s
+ user 0m0.169s
sys 0m0.049s
then we get the same answer much faster.
@@ Commit message
of course. But we're actually checking reachability here, so we're still
fast when we ask for more interesting things:
- $ time git rev-list --disk-usage --all --use-bitmap-index v5.0..v5.10
+ $ time git rev-list --disk-usage --use-bitmap-index v5.0..v5.10
374798628
real 0m0.429s
user 0m0.356s
@@ Documentation/rev-list-options.txt: ifdef::git-rev-list[]
+
+--disk-usage::
+ Suppress normal output; instead, print the sum of the bytes used
-+ for on-disk storage by the selected objects. This is equivalent
-+ to piping the output of `rev-list --objects` into
-+ `git cat-file --batch-check='%(objectsize:disk)', except that it
-+ runs much faster (especially with `--use-bitmap-index`). See the
-+ `CAVEATS` section in linkgit:git-cat-file[1] for the limitations
-+ of what "on-disk storage" means.
++ for on-disk storage by the selected commits or objects. This is
++ equivalent to piping the output into `git cat-file
++ --batch-check='%(objectsize:disk)'`, except that it runs much
++ faster (especially with `--use-bitmap-index`). See the `CAVEATS`
++ section in linkgit:git-cat-file[1] for the limitations of what
++ "on-disk storage" means.
endif::git-rev-list[]
--cherry-mark::
@@ builtin/rev-list.c: static int try_bitmap_traversal(struct rev_info *revs,
+ return -1;
+
+ printf("%"PRIuMAX"\n",
-+ (uintmax_t)get_disk_usage_from_bitmap(bitmap_git));
++ (uintmax_t)get_disk_usage_from_bitmap(bitmap_git, revs));
+ return 0;
+}
+
@@ builtin/rev-list.c: int cmd_rev_list(int argc, const char **argv, const char *pr
+ if (!strcmp(arg, "--disk-usage")) {
+ show_disk_usage = 1;
-+ revs.tag_objects = 1;
-+ revs.tree_objects = 1;
-+ revs.blob_objects = 1;
+ info.flags |= REV_LIST_QUIET;
+ continue;
+ }
@@ pack-bitmap.c: int bitmap_has_oid_in_uninteresting(struct bitmap_index *bitmap_g
bitmap_walk_contains(bitmap_git, bitmap_git->haves, oid);
}
+
-+off_t get_disk_usage_from_bitmap(struct bitmap_index *bitmap_git)
++static off_t get_disk_usage_for_type(struct bitmap_index *bitmap_git,
++ enum object_type object_type)
+{
+ struct bitmap *result = bitmap_git->result;
+ struct packed_git *pack = bitmap_git->pack;
-+ struct eindex *eindex = &bitmap_git->ext_index;
-+ struct object_info oi = OBJECT_INFO_INIT;
-+ off_t object_size;
+ off_t total = 0;
++ struct ewah_iterator it;
++ eword_t filter;
+ size_t i;
+
-+ oi.disk_sizep = &object_size;
-+
-+ for (i = 0; i < result->word_alloc; i++) {
-+ eword_t word = result->words[i];
++ init_type_iterator(&it, bitmap_git, object_type);
++ for (i = 0; i < result->word_alloc &&
++ ewah_iterator_next(&filter, &it); i++) {
++ eword_t word = result->words[i] & filter;
+ size_t base = (i * BITS_IN_EWORD);
+ unsigned offset;
+
++ if (!word)
++ continue;
++
+ for (offset = 0; offset < BITS_IN_EWORD; offset++) {
+ size_t pos;
+
@@ pack-bitmap.c: int bitmap_has_oid_in_uninteresting(struct bitmap_index *bitmap_g
+
+ offset += ewah_bit_ctz64(word >> offset);
+ pos = base + offset;
-+
-+ /*
-+ * If it's in the pack, we can use the fast path
-+ * and just check the revindex. Otherwise, we
-+ * fall back to looking it up.
-+ */
-+ if (pos < pack->num_objects) {
-+ object_size =
-+ pack_pos_to_offset(pack, pos + 1) -
-+ pack_pos_to_offset(pack, pos);
-+ } else {
-+ struct object *obj;
-+ obj = eindex->objects[pos - pack->num_objects];
-+ if (oid_object_info_extended(the_repository, &obj->oid, &oi, 0) < 0)
-+ die(_("unable to get disk usage of %s"),
-+ oid_to_hex(&obj->oid));
-+ }
-+
-+ total += object_size;
++ total += pack_pos_to_offset(pack, pos + 1) -
++ pack_pos_to_offset(pack, pos);
+ }
+ }
+
+ return total;
++}
++
++static off_t get_disk_usage_for_extended(struct bitmap_index *bitmap_git)
++{
++ struct bitmap *result = bitmap_git->result;
++ struct packed_git *pack = bitmap_git->pack;
++ struct eindex *eindex = &bitmap_git->ext_index;
++ off_t total = 0;
++ struct object_info oi = OBJECT_INFO_INIT;
++ off_t object_size;
++ size_t i;
++
++ oi.disk_sizep = &object_size;
++
++ for (i = 0; i < eindex->count; i++) {
++ struct object *obj = eindex->objects[i];
++
++ if (!bitmap_get(result, pack->num_objects + i))
++ continue;
++
++ if (oid_object_info_extended(the_repository, &obj->oid, &oi, 0) < 0)
++ die(_("unable to get disk usage of %s"),
++ oid_to_hex(&obj->oid));
++
++ total += object_size;
++ }
++ return total;
++}
++
++off_t get_disk_usage_from_bitmap(struct bitmap_index *bitmap_git,
++ struct rev_info *revs)
++{
++ off_t total = 0;
++
++ total += get_disk_usage_for_type(bitmap_git, OBJ_COMMIT);
++ if (revs->tree_objects)
++ total += get_disk_usage_for_type(bitmap_git, OBJ_TREE);
++ if (revs->blob_objects)
++ total += get_disk_usage_for_type(bitmap_git, OBJ_BLOB);
++ if (revs->tag_objects)
++ total += get_disk_usage_for_type(bitmap_git, OBJ_TAG);
++
++ total += get_disk_usage_for_extended(bitmap_git);
++
++ return total;
+}
## pack-bitmap.h ##
@@ pack-bitmap.h: int bitmap_walk_contains(struct bitmap_index *,
*/
int bitmap_has_oid_in_uninteresting(struct bitmap_index *, const struct object_id *oid);
-+off_t get_disk_usage_from_bitmap(struct bitmap_index *);
++off_t get_disk_usage_from_bitmap(struct bitmap_index *, struct rev_info *);
+
void bitmap_writer_show_progress(int show);
void bitmap_writer_set_checksum(unsigned char *sha1);
@@ t/t6114-rev-list-du.sh (new)
+# packing, zlib, etc. We'll assume that the regular rev-list and cat-file
+# machinery works and compare the --disk-usage output to that.
+disk_usage_slow () {
-+ git rev-list --objects "$@" |
-+ cut -d' ' -f1 |
++ git rev-list --no-object-names "$@" |
+ git cat-file --batch-check="%(objectsize:disk)" |
+ perl -lne '$total += $_; END { print $total}'
+}
@@ t/t6114-rev-list-du.sh (new)
+}
+
+check_du HEAD
-+check_du HEAD^..HEAD
++check_du --objects HEAD
++check_du --objects HEAD^..HEAD
+
+test_done
From: Jeff King <hidden> Date: 2021-02-09 10:56:15
One of the conveniences that test_commit offers is making a tag for each
commit. This makes it easy to refer to the commits in subsequent
commands. But it can also be a pain if you care about reachability,
because those tags keep the commits reachable even if they are rewound
from the branch they're made on.
The alternative is that scripts have to call test_tick, git-add, and
git-commit themselves. Let's add a --no-tag option to give them the
one-liner convenience of using test_commit.
This is in preparation for the next patch, which will add some more
calls. But I cleaned up an existing site to show off the feature. There
are probably more cleanups possible.
Signed-off-by: Jeff King <redacted>
---
t/t4208-log-magic-pathspec.sh | 9 ++-------
t/test-lib-functions.sh | 9 ++++++++-
2 files changed, 10 insertions(+), 8 deletions(-)
@@ -31,13 +31,8 @@ test_expect_success '"git log :/a -- " should not be ambiguous' ' test_expect_success'"git log :/detached -- " should find a commit only in HEAD''test_when_finished"git checkout main"&&gitcheckout--detach&&-# Must manually call `test_tick` instead of using `test_commit`,-# because the latter additionally creates a tag, which would make-# the commit reachable not only via HEAD.-test_tick&&-gitcommit--allow-empty-mdetached&&-test_tick&&-gitcommit--allow-empty-msomething-else&&+test_commit--no-tagdetached&&+test_commit--no-tagsomething-else&&gitlog:/detached--'
From: Jeff King <hidden> Date: 2021-02-09 10:57:17
It can sometimes be useful to see which refs are contributing to the
overall repository size (e.g., does some branch have a bunch of objects
not found elsewhere in history, which indicates that deleting it would
shrink the size of a clone).
You can find that out by generating a list of objects, getting their
sizes from cat-file, and then summing them, like:
git rev-list --objects --no-object-names main..branch
git cat-file --batch-check='%(objectsize:disk)' |
perl -lne '$total += $_; END { print $total }'
Though note that the caveats from git-cat-file(1) apply here. We "blame"
base objects more than their deltas, even though the relationship could
easily be flipped. Still, it can be a useful rough measure.
But one problem is that it's slow to run. Teaching rev-list to sum up
the sizes can be much faster for two reasons:
1. It skips all of the piping of object names and sizes.
2. If bitmaps are in use, for objects that are in the
bitmapped packfile we can skip the oid_object_info()
lookup entirely, and just ask the revindex for the
on-disk size.
This patch implements a --disk-usage option which produces the same
answer in a fraction of the time. Here are some timings using a clone of
torvalds/linux:
[rev-list piped to cat-file, no bitmaps]
$ time git rev-list --objects --no-object-names --all |
git cat-file --buffer --batch-check='%(objectsize:disk)' |
perl -lne '$total += $_; END { print $total }'
1459938510
real 0m29.635s
user 0m38.003s
sys 0m1.093s
[internal, no bitmaps]
$ time git rev-list --disk-usage --objects --all
1459938510
real 0m31.262s
user 0m30.885s
sys 0m0.376s
Even though the wall-clock time is slightly worse due to parallelism,
notice the CPU savings between the two. We saved 21% of the CPU just by
avoiding the pipes.
But the real win is with bitmaps. If we use them without the new option:
[rev-list piped to cat-file, bitmaps]
$ time git rev-list --objects --no-object-names --all --use-bitmap-index |
git cat-file --batch-check='%(objectsize:disk)' |
perl -lne '$total += $_; END { print $total }'
1459938510
real 0m6.244s
user 0m8.452s
sys 0m0.311s
then we're faster to generate the list of objects, but we still spend a
lot of time piping and looking things up. But if we do both together:
[internal, bitmaps]
$ time git rev-list --disk-usage --objects --all --use-bitmap-index
1459938510
real 0m0.219s
user 0m0.169s
sys 0m0.049s
then we get the same answer much faster.
For "--all", that answer will correspond closely to "du objects/pack",
of course. But we're actually checking reachability here, so we're still
fast when we ask for more interesting things:
$ time git rev-list --disk-usage --use-bitmap-index v5.0..v5.10
374798628
real 0m0.429s
user 0m0.356s
sys 0m0.072s
Signed-off-by: Jeff King <redacted>
---
Documentation/rev-list-options.txt | 9 ++++
builtin/rev-list.c | 46 +++++++++++++++++
pack-bitmap.c | 81 ++++++++++++++++++++++++++++++
pack-bitmap.h | 2 +
t/t6114-rev-list-du.sh | 51 +++++++++++++++++++
5 files changed, 189 insertions(+)
create mode 100755 t/t6114-rev-list-du.sh
@@ -227,6 +227,15 @@ ifdef::git-rev-list[] test the exit status to see if a range of objects is fully connected (or not). It is faster than redirecting stdout to `/dev/null` as the output does not have to be formatted.++--disk-usage::+ Suppress normal output; instead, print the sum of the bytes used+ for on-disk storage by the selected commits or objects. This is+ equivalent to piping the output into `git cat-file+ --batch-check='%(objectsize:disk)'`, except that it runs much+ faster (especially with `--use-bitmap-index`). See the `CAVEATS`+ section in linkgit:git-cat-file[1] for the limitations of what+ "on-disk storage" means. endif::git-rev-list[] --cherry-mark::
@@ -80,6 +80,19 @@ static int arg_show_object_names = 1;#define DEFAULT_OIDSET_SIZE (16*1024)+staticintshow_disk_usage;+staticoff_ttotal_disk_usage;++staticoff_tget_object_disk_usage(structobject*obj)+{+off_tsize;+structobject_infooi=OBJECT_INFO_INIT;+oi.disk_sizep=&size;+if(oid_object_info_extended(the_repository,&obj->oid,&oi,0)<0)+die(_("unable to get disk usage of %s"),oid_to_hex(&obj->oid));+returnsize;+}+staticvoidfinish_commit(structcommit*commit);staticvoidshow_commit(structcommit*commit,void*data){
@@ -1430,3 +1430,84 @@ int bitmap_has_oid_in_uninteresting(struct bitmap_index *bitmap_git,returnbitmap_git&&bitmap_walk_contains(bitmap_git,bitmap_git->haves,oid);}++staticoff_tget_disk_usage_for_type(structbitmap_index*bitmap_git,+enumobject_typeobject_type)+{+structbitmap*result=bitmap_git->result;+structpacked_git*pack=bitmap_git->pack;+off_ttotal=0;+structewah_iteratorit;+eword_tfilter;+size_ti;++init_type_iterator(&it,bitmap_git,object_type);+for(i=0;i<result->word_alloc&&+ewah_iterator_next(&filter,&it);i++){+eword_tword=result->words[i]&filter;+size_tbase=(i*BITS_IN_EWORD);+unsignedoffset;++if(!word)+continue;++for(offset=0;offset<BITS_IN_EWORD;offset++){+size_tpos;++if((word>>offset)==0)+break;++offset+=ewah_bit_ctz64(word>>offset);+pos=base+offset;+total+=pack_pos_to_offset(pack,pos+1)-+pack_pos_to_offset(pack,pos);+}+}++returntotal;+}++staticoff_tget_disk_usage_for_extended(structbitmap_index*bitmap_git)+{+structbitmap*result=bitmap_git->result;+structpacked_git*pack=bitmap_git->pack;+structeindex*eindex=&bitmap_git->ext_index;+off_ttotal=0;+structobject_infooi=OBJECT_INFO_INIT;+off_tobject_size;+size_ti;++oi.disk_sizep=&object_size;++for(i=0;i<eindex->count;i++){+structobject*obj=eindex->objects[i];++if(!bitmap_get(result,pack->num_objects+i))+continue;++if(oid_object_info_extended(the_repository,&obj->oid,&oi,0)<0)+die(_("unable to get disk usage of %s"),+oid_to_hex(&obj->oid));++total+=object_size;+}+returntotal;+}++off_tget_disk_usage_from_bitmap(structbitmap_index*bitmap_git,+structrev_info*revs)+{+off_ttotal=0;++total+=get_disk_usage_for_type(bitmap_git,OBJ_COMMIT);+if(revs->tree_objects)+total+=get_disk_usage_for_type(bitmap_git,OBJ_TREE);+if(revs->blob_objects)+total+=get_disk_usage_for_type(bitmap_git,OBJ_BLOB);+if(revs->tag_objects)+total+=get_disk_usage_for_type(bitmap_git,OBJ_TAG);++total+=get_disk_usage_for_extended(bitmap_git);++returntotal;+}
@@ -0,0 +1,51 @@+#!/bin/sh++test_description='basic tests of rev-list --disk-usage'+../test-lib.sh++# we want a mix of reachable and unreachable, as well as+# objects in the bitmapped pack and some outside of it+test_expect_success'set up repository''+test_commit--no-tagone&&+test_commit--no-tagtwo&&+gitrepack-adb&&+gitreset--hardHEAD^&&+test_commit--no-tagthree&&+test_commit--no-tagfour&&+gitreset--hardHEAD^+'++# We don't want to hardcode sizes, because they depend on the exact details of+# packing, zlib, etc. We'll assume that the regular rev-list and cat-file+# machinery works and compare the --disk-usage output to that.+disk_usage_slow(){+gitrev-list--no-object-names"$@"|+gitcat-file--batch-check="%(objectsize:disk)"|+perl-lne'$total += $_; END { print $total}'+}++# check behavior with given rev-list options; note that+# whitespace is not preserved in args+check_du(){+args=$*++test_expect_success"generate expected size ($args)""+disk_usage_slow$args>expect+"++test_expect_success"rev-list --disk-usage without bitmaps ($args)""+gitrev-list--disk-usage$args>actual&&+test_cmpexpectactual+"++test_expect_success"rev-list --disk-usage with bitmaps ($args)""+gitrev-list--disk-usage--use-bitmap-index$args>actual&&+test_cmpexpectactual+"+}++check_duHEAD+check_du--objectsHEAD+check_du--objectsHEAD^..HEAD++test_done
From: Jeff King <hidden> Date: 2021-02-09 11:11:24
On Tue, Feb 09, 2021 at 05:52:28AM -0500, Jeff King wrote:
This fixes the minor bits mentioned in review for v1, but the big change
is that "--disk-usage" no longer implies "--objects". I think you
generally would want to use it with that option, but it really seemed to
violate the principle of least surprise for the user.
That requires handling each object type independently, but the code for
that turned out to be not too bad (and is modeled after the similar
logic in traverse_bitmap_commit_list()). I was slightly concerned that
it would slow things down to walk over the bitmap multiple times, but it
doesn't seem to make much of a difference in practice.
You might reasonably ask whether we could just directly use
traverse_bitmap_commit_list(), since after all it takes a callback. And
indeed, doing so reduces the size of the code (see the patch below).
But it's shockingly slower! It takes consistently 2-3x longer to produce
the same answer on linux.git with bitmaps. The problem is that we give
more information to the callback than the disk-usage computation needs.
In particular, finding nth_packed_object_id() is a big killer. Which
kind of makes sense. We memcpy() the oids out of the .idx file into a
"struct object_id" on the stack. And linux.git has ~200MB of oids to
copy (and I'm sure doing it 20 bytes at a time isn't quite optimal).
That adds several hundred milliseconds. Not a lot in absolute terms, but
we're able to do the whole computation in ~200ms to start with, so it's
relatively a big change.
This could be solved by having a more "bare" callback that just passes
the pack position, and not the oid (and then the callback is responsible
for looking it up if they care). But it gets pretty awkward when we have
to complete the bitmap traversal with non-bitmap objects (for those we
_do_ have an oid to pass, but no pack position). I think the
implementation in my 2/2 isn't so bad in comparison (and we can always
swap it out later; these are all just implementation details).
I did find it a bit interesting, though. When we moved to "struct
object_id" and started copying bits out with nth_packed_object_id(),
rather than just pointing to the mmap'd .idx bytes, we wondered whether
there would be any measurable difference. Likewise when we extended it
to handle the oid size changing at runtime. At the time, I wasn't able
to measure any impact for real operations, but I guess we just needed a
case that highlighted it more.
I don't know that it's really worth digging into that much, though it's
quite possible there may be some easy wins by optimizing those memcpy
calls. E.g., I'm not sure if the compiler ends up inlining them or not.
If it doesn't realize that the_hash_algo->rawsz is only ever "20" or
"32", we could perhaps help it along with specialized versions of
hashcpy(). If somebody does want to play with it, this patch may make a
good testbed. :)
-- >8 --
builtin/pack-objects.c | 3 +-
builtin/rev-list.c | 40 +++++++++++------------
pack-bitmap.c | 86 ++------------------------------------------------
pack-bitmap.h | 1 +
reachable.c | 1 +
5 files changed, 25 insertions(+), 106 deletions(-)
@@ -83,13 +83,13 @@ static int arg_show_object_names = 1;staticintshow_disk_usage;staticoff_ttotal_disk_usage;-staticoff_tget_object_disk_usage(structobject*obj)+staticoff_tget_object_disk_usage(conststructobject_id*oid){off_tsize;structobject_infooi=OBJECT_INFO_INIT;oi.disk_sizep=&size;-if(oid_object_info_extended(the_repository,&obj->oid,&oi,0)<0)-die(_("unable to get disk usage of %s"),oid_to_hex(&obj->oid));+if(oid_object_info_extended(the_repository,oid,&oi,0)<0)+die(_("unable to get disk usage of %s"),oid_to_hex(oid));returnsize;}
@@ -1430,84 +1431,3 @@ int bitmap_has_oid_in_uninteresting(struct bitmap_index *bitmap_git,returnbitmap_git&&bitmap_walk_contains(bitmap_git,bitmap_git->haves,oid);}--staticoff_tget_disk_usage_for_type(structbitmap_index*bitmap_git,-enumobject_typeobject_type)-{-structbitmap*result=bitmap_git->result;-structpacked_git*pack=bitmap_git->pack;-off_ttotal=0;-structewah_iteratorit;-eword_tfilter;-size_ti;--init_type_iterator(&it,bitmap_git,object_type);-for(i=0;i<result->word_alloc&&-ewah_iterator_next(&filter,&it);i++){-eword_tword=result->words[i]&filter;-size_tbase=(i*BITS_IN_EWORD);-unsignedoffset;--if(!word)-continue;--for(offset=0;offset<BITS_IN_EWORD;offset++){-size_tpos;--if((word>>offset)==0)-break;--offset+=ewah_bit_ctz64(word>>offset);-pos=base+offset;-total+=pack_pos_to_offset(pack,pos+1)--pack_pos_to_offset(pack,pos);-}-}--returntotal;-}--staticoff_tget_disk_usage_for_extended(structbitmap_index*bitmap_git)-{-structbitmap*result=bitmap_git->result;-structpacked_git*pack=bitmap_git->pack;-structeindex*eindex=&bitmap_git->ext_index;-off_ttotal=0;-structobject_infooi=OBJECT_INFO_INIT;-off_tobject_size;-size_ti;--oi.disk_sizep=&object_size;--for(i=0;i<eindex->count;i++){-structobject*obj=eindex->objects[i];--if(!bitmap_get(result,pack->num_objects+i))-continue;--if(oid_object_info_extended(the_repository,&obj->oid,&oi,0)<0)-die(_("unable to get disk usage of %s"),-oid_to_hex(&obj->oid));--total+=object_size;-}-returntotal;-}--off_tget_disk_usage_from_bitmap(structbitmap_index*bitmap_git,-structrev_info*revs)-{-off_ttotal=0;--total+=get_disk_usage_for_type(bitmap_git,OBJ_COMMIT);-if(revs->tree_objects)-total+=get_disk_usage_for_type(bitmap_git,OBJ_TREE);-if(revs->blob_objects)-total+=get_disk_usage_for_type(bitmap_git,OBJ_BLOB);-if(revs->tag_objects)-total+=get_disk_usage_for_type(bitmap_git,OBJ_TAG);--total+=get_disk_usage_for_extended(bitmap_git);--returntotal;-}