sha1_name: use bsearch_pack() for abbreviations

When computing abbreviation lengths for an object ID against a single
packfile, the method find_abbrev_len_for_pack() currently implements
binary search. This is one of several implementations. One issue with
this implementation is that it ignores the fanout table in the pack-
index.

Translate this binary search to use the existing bsearch_pack() method
that correctly uses a fanout table.

Due to the use of the fanout table, the abbreviation computation is
slightly faster than before. For a fully-repacked copy of the Linux
repo, the following 'git log' commands improved:

* git log --oneline --parents --raw
Before: 59.2s
After:  56.9s
Rel %:  -3.8%

* git log --oneline --parents
Before: 6.48s
After:  5.91s
Rel %: -8.9%

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/sha1_name.c b/sha1_name.c
index 16e0003396c3a169b33d3519d7f984d3b6e11228..24894b3dbedf024cfd2c63924c05219cbd1d356b 100644 (file)
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -512,32 +512,16 @@ static void find_abbrev_len_for_pack(struct packed_git *p,
                                     struct min_abbrev_data *mad)
 {
        int match = 0;
                                     struct min_abbrev_data *mad)
 {
        int match = 0;

-       uint32_t num, last, first = 0;
+       uint32_t num, first = 0;

        struct object_id oid;
        struct object_id oid;

+       const struct object_id *mad_oid;

 
        if (open_pack_index(p) || !p->num_objects)
                return;
 
        num = p->num_objects;
 
        if (open_pack_index(p) || !p->num_objects)
                return;
 
        num = p->num_objects;

-       last = num;
-       while (first < last) {
-               uint32_t mid = first + (last - first) / 2;
-               const unsigned char *current;
-               int cmp;
-
-               current = nth_packed_object_sha1(p, mid);
-               cmp = hashcmp(mad->oid->hash, current);
-               if (!cmp) {
-                       match = 1;
-                       first = mid;
-                       break;
-               }
-               if (cmp > 0) {
-                       first = mid + 1;
-                       continue;
-               }
-               last = mid;
-       }
+       mad_oid = mad->oid;
+       match = bsearch_pack(mad_oid, p, &first);

 
        /*
         * first is now the position in the packfile where we would insert
 
        /*
         * first is now the position in the packfile where we would insert