[PATCH 16/16] rev-list: Optimize --count using bitmaps too

[Vicent Marti <tanoku@gmail.com>]

If bitmap indexes are available, the process of counting reachable
commits with `git rev-list --count` can be greatly sped up. Instead of
having to use callbacks that yield each object in the revision list, we
can build the reachable bitmap for the list and then use an efficient
popcount to find the number of bits set in the bitmap.

This commit implements a `count_bitmap_commit_list` that can be used
after `prepare_bitmap_walk` has returned successfully to return the
number of commits, trees, blobs or tags that have been found to be
reachable during the walk.

`git rev-list` is taught to use this function call when bitmaps are
enabled instead of going through the old rev-list machinery. Do note,
however, that counts with `left_right` and `cherry_mark` are not
optimized by this patch.

Here are some sample timings of different ways to count commits in
`torvalds/linux`:

	$ time ../git/git rev-list master | wc -l
	376549

	real    0m6.973s
	user    0m3.216s
	sys     0m5.316s

	$ time ../git/git rev-list --count master
	376549

	real    0m1.933s
	user    0m1.744s
	sys     0m0.188s

	$ time ../git/git rev-list --use-bitmaps --count master
	376549

	real    0m0.005s
	user    0m0.000s
	sys     0m0.004s

Note that the time in the `--use-bitmaps` invocation is basically noise.
In my machine it ranges from 2ms to 6ms.
---
 builtin/rev-list.c |   11 +++++++++--
 pack-bitmap.c      |   37 +++++++++++++++++++++++++++++++++++++
 pack-bitmap.h      |    2 ++
 3 files changed, 48 insertions(+), 2 deletions(-)

diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index 905ed08..097adb8 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -354,8 +354,15 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 		revs.limited = 1;
 
 	if (use_bitmaps && !prepare_bitmap_walk(&revs, NULL)) {
-		traverse_bitmap_commit_list(&show_object_fast);
-		return 0;
+		if (revs.count && !revs.left_right && !revs.cherry_mark) {
+			uint32_t commit_count;
+			count_bitmap_commit_list(&commit_count, NULL, NULL, NULL);
+			printf("%d\n", commit_count);
+			return 0;
+		} else {
+			traverse_bitmap_commit_list(&show_object_fast);
+			return 0;
+		}
 	}
 
 	if (prepare_revision_walk(&revs))
diff --git a/pack-bitmap.c b/pack-bitmap.c
index 090db15..65fdce7 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -720,6 +720,43 @@ void traverse_bitmap_commit_list(show_reachable_fn show_reachable)
 	bitmap_git.result = NULL;
 }
 
+static uint32_t count_object_type(
+	struct bitmap *objects,
+	struct ewah_bitmap *type_filter)
+{
+	size_t i = 0, count = 0;
+	struct ewah_iterator it;
+	eword_t filter;
+
+	ewah_iterator_init(&it, type_filter);
+
+	while (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {
+		eword_t word = objects->words[i++] & filter;
+		count += __builtin_popcountll(word);
+	}
+
+	return count;
+}
+
+void count_bitmap_commit_list(
+	uint32_t *commits, uint32_t *trees, uint32_t *blobs, uint32_t *tags)
+{
+	if (!bitmap_git.result)
+		die("Tried to count bitmap without setting it up first");
+
+	if (commits)
+		*commits = count_object_type(bitmap_git.result, bitmap_git.commits);
+
+	if (trees)
+		*trees = count_object_type(bitmap_git.result, bitmap_git.trees);
+
+	if (blobs)
+		*blobs = count_object_type(bitmap_git.result, bitmap_git.blobs);
+
+	if (tags)
+		*tags = count_object_type(bitmap_git.result, bitmap_git.tags);
+}
+
 struct bitmap_test_data {
 	struct bitmap *base;
 	struct progress *prg;
diff --git a/pack-bitmap.h b/pack-bitmap.h
index 8e7e3dc..816da6d 100644
--- a/pack-bitmap.h
+++ b/pack-bitmap.h
@@ -47,6 +47,8 @@ typedef int (*show_reachable_fn)(
 	struct packed_git *found_pack,
 	off_t found_offset);
 
+void count_bitmap_commit_list(
+	uint32_t *commits, uint32_t *trees, uint32_t *blobs, uint32_t *tags);
 void traverse_bitmap_commit_list(show_reachable_fn show_reachable);
 int prepare_bitmap_walk(struct rev_info *revs, uint32_t *result_size);
 void test_bitmap_walk(struct rev_info *revs);
-- 
1.7.9.5