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
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html