[07/13] rev-list: allow bitmaps when counting objects

Commit Message

Jeff King Feb. 13, 2020, 2:20 a.m. UTC

The prior commit taught "--count --objects" to work without bitmaps. We
should be able to get the same answer much more quickly with bitmaps.

Note that we punt on the max_count case here. This perhaps _could_ be
made to work if we find all of the boundary commits and treat them as
UNINTERESTING, subtracting them (and their reachable objects) from the
set we return. That implies an actual commit traversal, but we'd still
be faster due to avoiding opening up any trees. Given the complexity and
the fact that anyone is unlikely to want this, it makes sense to just
fall back to the non-bitmap case for now.

Signed-off-by: Jeff King <[e-mail]>
---
 builtin/rev-list.c      | 21 ++++++++++++++++++---
 t/t5310-pack-bitmaps.sh |  6 ++++++
 2 files changed, 24 insertions(+), 3 deletions(-)

Comments

Junio C Hamano Feb. 13, 2020, 9:47 p.m. UTC | #1

Jeff King <[e-mail]> writes:

> -	count_bitmap_commit_list(bitmap_git, &commit_count, NULL, NULL, NULL);
> +	count_bitmap_commit_list(bitmap_git, &commit_count,
> +				 revs->tree_objects ? &tree_count : NULL,
> +				 revs->blob_objects ? &blob_count : NULL,
> +				 revs->tag_objects ? &tag_count : NULL);

So count_bitmap_commit_list() has been prepared to count non-commits
already, but we are just starting to use that feature?

Interesting.

> -	printf("%d\n", commit_count);
> +	printf("%d\n", commit_count + tree_count + blob_count + tag_count);

Thanks.

Jeff King Feb. 13, 2020, 10:27 p.m. UTC | #2

On Thu, Feb 13, 2020 at 01:47:38PM -0800, Junio C Hamano wrote:

> Jeff King <[e-mail]> writes:
> 
> > -	count_bitmap_commit_list(bitmap_git, &commit_count, NULL, NULL, NULL);
> > +	count_bitmap_commit_list(bitmap_git, &commit_count,
> > +				 revs->tree_objects ? &tree_count : NULL,
> > +				 revs->blob_objects ? &blob_count : NULL,
> > +				 revs->tag_objects ? &tag_count : NULL);
> 
> So count_bitmap_commit_list() has been prepared to count non-commits
> already, but we are just starting to use that feature?
> 
> Interesting.

Yeah, it goes all the way back to fff42755ef (pack-bitmap: add support
for bitmap indexes, 2013-12-21), but was never used for non-commits. I
was pleasantly surprised that it actually worked. ;)

-Peff

Patch

diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index b4fd507f25..ce1cfc7da0 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -374,7 +374,10 @@  static inline int parse_missing_action_value(const char *value)
 
 static int try_bitmap_count(struct rev_info *revs)
 {
-	uint32_t commit_count;
+	uint32_t commit_count = 0,
+		 tag_count = 0,
+		 tree_count = 0,
+		 blob_count = 0;
 	int max_count;
 	struct bitmap_index *bitmap_git;
 
@@ -389,6 +392,15 @@  static int try_bitmap_count(struct rev_info *revs)
 	if (revs->left_right || revs->cherry_mark)
 		return -1;
 
+	/*
+	 * If we're counting reachable objects, we can't handle a max count of
+	 * commits to traverse, since we don't know which objects go with which
+	 * commit.
+	 */
+	if (revs->max_count >= 0 &&
+	    (revs->tag_objects || revs->tree_objects || revs->blob_objects))
+		return -1;
+
 	/*
 	 * This must be saved before doing any walking, since the revision
 	 * machinery will count it down to zero while traversing.
@@ -399,11 +411,14 @@  static int try_bitmap_count(struct rev_info *revs)
 	if (!bitmap_git)
 		return -1;
 
-	count_bitmap_commit_list(bitmap_git, &commit_count, NULL, NULL, NULL);
+	count_bitmap_commit_list(bitmap_git, &commit_count,
+				 revs->tree_objects ? &tree_count : NULL,
+				 revs->blob_objects ? &blob_count : NULL,
+				 revs->tag_objects ? &tag_count : NULL);
 	if (max_count >= 0 && max_count < commit_count)
 		commit_count = max_count;
 
-	printf("%d\n", commit_count);
+	printf("%d\n", commit_count + tree_count + blob_count + tag_count);
 	free_bitmap_index(bitmap_git);
 	return 0;
 }
diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh
index 6640329ebf..7ba7d294a5 100755
--- a/t/t5310-pack-bitmaps.sh
+++ b/t/t5310-pack-bitmaps.sh
@@ -74,6 +74,12 @@  rev_list_tests() {
 		test_cmp expect actual
 	'
 
+	test_expect_success "counting objects via bitmap ($state)" '
+		git rev-list --count --objects HEAD >expect &&
+		git rev-list --use-bitmap-index --count --objects HEAD >actual &&
+		test_cmp expect actual
+	'
+
 	test_expect_success "enumerate --objects ($state)" '
 		git rev-list --objects --use-bitmap-index HEAD >tmp &&
 		cut -d" " -f1 <tmp >tmp2 &&