rev-list: add bitmap mode to speed up object lists

The bitmap reachability index used to speed up the counting objects
phase during `pack-objects` can also be used to optimize a normal
rev-list if the only thing required are the SHA1s of the objects during
the list (i.e., not the path names at which trees and blobs were found).

Calling `git rev-list --objects --use-bitmap-index [committish]` will
perform an object iteration based on a bitmap result instead of actually
walking the object graph.

These are some example timings for `torvalds/linux` (warm cache,
best-of-five):

$ time git rev-list --objects master > /dev/null

real    0m34.191s
user    0m33.904s
sys     0m0.268s

$ time git rev-list --objects --use-bitmap-index master > /dev/null

real    0m1.041s
user    0m0.976s
sys     0m0.064s

Likewise, using `git rev-list --count --use-bitmap-index` will speed up
the counting operation by building the resulting bitmap and performing a
fast popcount (number of bits set on the bitmap) on the result.

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

$ time git rev-list master | wc -l
399882

real    0m6.524s
user    0m6.060s
sys     0m3.284s

$ time git rev-list --count master
399882

real    0m4.318s
user    0m4.236s
sys     0m0.076s

$ time git rev-list --use-bitmap-index --count master
399882

real    0m0.217s
user    0m0.176s
sys     0m0.040s

This also respects negative refs, so you can use it to count
a slice of history:

$ time git rev-list --count v3.0..master
144843

real    0m1.971s
user    0m1.932s
sys     0m0.036s

$ time git rev-list --use-bitmap-index --count v3.0..master
real    0m0.280s
user    0m0.220s
sys     0m0.056s

Though note that the closer the endpoints, the less it helps. In the
traversal case, we have fewer commits to cross, so we take less time.
But the bitmap time is dominated by generating the pack revindex, which
is constant with respect to the refs given.

Note that you cannot yet get a fast --left-right count of a symmetric
difference (e.g., "--count --left-right master...topic"). The slow part
of that walk actually happens during the merge-base determination when
we parse "master...topic". Even though a count does not actually need to
know the real merge base (it only needs to take the symmetric difference
of the bitmaps), the revision code would require some refactoring to
handle this case.

Additionally, a `--test-bitmap` flag has been added that will perform
the same rev-list manually (i.e. using a normal revwalk) and using
bitmaps, and verify that the results are the same. This can be used to
exercise the bitmap code, and also to verify that the contents of the
.bitmap file are sane.

Signed-off-by: Vicent Marti <tanoku@gmail.com>
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt
index 045b37b82e7544ddb753cdec7ead2bc8d97ad1c8..7a1585def0ce0c0ca78a2735f619f0e8bdf3506c 100644 (file)
--- a/Documentation/git-rev-list.txt
+++ b/Documentation/git-rev-list.txt
@@ -55,6 +55,7 @@ SYNOPSIS
             [ \--reverse ]
             [ \--walk-reflogs ]
             [ \--no-walk ] [ \--do-walk ]
             [ \--reverse ]
             [ \--walk-reflogs ]
             [ \--no-walk ] [ \--do-walk ]

+            [ \--use-bitmap-index ]

             <commit>... [ \-- <paths>... ]
 
 DESCRIPTION
             <commit>... [ \-- <paths>... ]
 
 DESCRIPTION

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 5bdfb4285247770722434541700b0f7547e3a113..c236b857b0f1ae10eb2993b1703f7c9f4faa2152 100644 (file)
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -274,6 +274,14 @@ See also linkgit:git-reflog[1].
        Output excluded boundary commits. Boundary commits are
        prefixed with `-`.
 
        Output excluded boundary commits. Boundary commits are
        prefixed with `-`.
 

+ifdef::git-rev-list[]
+--use-bitmap-index::
+
+       Try to speed up the traversal using the pack bitmap index (if
+       one is available). Note that when traversing with `--objects`,
+       trees and blobs will not have their associated path printed.
+endif::git-rev-list[]
+

 --
 
 History Simplification
 --
 
 History Simplification

diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index 4fc16166374b86927e605ccbfe341aebe0e3240f..5209255f28c66049b2ec6dc539ceaa7fe339133c 100644 (file)
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -3,6 +3,8 @@
 #include "diff.h"
 #include "revision.h"
 #include "list-objects.h"
 #include "diff.h"
 #include "revision.h"
 #include "list-objects.h"

+#include "pack.h"
+#include "pack-bitmap.h"

 #include "builtin.h"
 #include "log-tree.h"
 #include "graph.h"
 #include "builtin.h"
 #include "log-tree.h"
 #include "graph.h"


@@ -257,6 +259,18 @@ static int show_bisect_vars(struct rev_list_info *info, int reaches, int all)
        return 0;
 }
 
        return 0;
 }
 

+static int show_object_fast(
+       const unsigned char *sha1,
+       enum object_type type,
+       int exclude,
+       uint32_t name_hash,
+       struct packed_git *found_pack,
+       off_t found_offset)
+{
+       fprintf(stdout, "%s\n", sha1_to_hex(sha1));
+       return 1;
+}
+

 int cmd_rev_list(int argc, const char **argv, const char *prefix)
 {
        struct rev_info revs;
 int cmd_rev_list(int argc, const char **argv, const char *prefix)
 {
        struct rev_info revs;


@@ -265,6 +279,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
        int bisect_list = 0;
        int bisect_show_vars = 0;
        int bisect_find_all = 0;
        int bisect_list = 0;
        int bisect_show_vars = 0;
        int bisect_find_all = 0;

+       int use_bitmap_index = 0;

 
        git_config(git_default_config, NULL);
        init_revisions(&revs, prefix);
 
        git_config(git_default_config, NULL);
        init_revisions(&revs, prefix);


@@ -306,6 +321,14 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
                        bisect_show_vars = 1;
                        continue;
                }
                        bisect_show_vars = 1;
                        continue;
                }

+               if (!strcmp(arg, "--use-bitmap-index")) {
+                       use_bitmap_index = 1;
+                       continue;
+               }
+               if (!strcmp(arg, "--test-bitmap")) {
+                       test_bitmap_walk(&revs);
+                       return 0;
+               }

                usage(rev_list_usage);
 
        }
                usage(rev_list_usage);
 
        }


@@ -333,6 +356,22 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
        if (bisect_list)
                revs.limited = 1;
 
        if (bisect_list)
                revs.limited = 1;
 

+       if (use_bitmap_index) {
+               if (revs.count && !revs.left_right && !revs.cherry_mark) {
+                       uint32_t commit_count;
+                       if (!prepare_bitmap_walk(&revs)) {
+                               count_bitmap_commit_list(&commit_count, NULL, NULL, NULL);
+                               printf("%d\n", commit_count);
+                               return 0;
+                       }
+               } else if (revs.tag_objects && revs.tree_objects && revs.blob_objects) {
+                       if (!prepare_bitmap_walk(&revs)) {
+                               traverse_bitmap_commit_list(&show_object_fast);
+                               return 0;
+                       }
+               }
+       }
+

        if (prepare_revision_walk(&revs))
                die("revision walk setup failed");
        if (revs.tree_objects)
        if (prepare_revision_walk(&revs))
                die("revision walk setup failed");
        if (revs.tree_objects)