Derrick StoleeThis patch updates the abbreviation code to use bsearch_hash() as defined in [1]. It gets a nice speedup since the old implementation did not use the fanout table at all.
One caveat about the patch: there is a place where I cast a sha1 hash into a struct object_id pointer. This is because the abbreviation code still uses 'const unsigned char *' instead of structs. I wanted to avoid a hashcpy() in these calls, but perhaps that is not too heavy a cost.
I look forward to feedback on this.
Thanks, -Stolee
[1] https://public-inbox.org/git/007f3a4c84cb1c07255404ad1ea9f797129c5cf0.1517609773.git.jonathantanmy@google.com/
[PATCH 2/2] packfile: refactor hash search with fanout table-- >8 --
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_hash() method that correctly uses a fanout table. To keep the details about pack- index version 1 or 2 out of sha1_name.c, create a bsearch_pack() method in packfile.c.
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: 66.83s After: 64.85s Rel %: -2.9%
* git log --oneline --parents Before: 7.85s After: 7.29s Rel %: -7.1%
Signed-off-by: Derrick Stolee <dstolee@microsoft.com> --- packfile.c | 23 +++++++++++++++++++++++ packfile.h | 8 ++++++++ sha1_name.c | 24 ++++-------------------- 3 files changed, 35 insertions(+), 20 deletions(-)
Show changes to 3 files +35 −20
packfile.c, packfile.h, sha1_name.c
diff --git a/packfile.c b/packfile.c index 7c1a2519fc..ea0388f6dd 100644 --- a/packfile.c +++ b/packfile.c @@ -1654,6 +1654,29 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset, return data; } +int bsearch_pack(const struct object_id *oid, const struct packed_git *p, uint32_t *result) +{ + const unsigned char *index_fanout = p->index_data; + const unsigned char *index_lookup; + int index_lookup_width; + + if (!index_fanout) + BUG("bsearch_pack called without a valid pack-index"); + + index_lookup = index_fanout + 4 * 256; + if (p->index_version == 1) { + index_lookup_width = 24; + index_lookup += 4; + } else { + index_lookup_width = 20; + index_fanout += 8; + index_lookup += 8; + } + + return bsearch_hash(oid->hash, (const uint32_t*)index_fanout, + index_lookup, index_lookup_width, result); +} + const unsigned char *nth_packed_object_sha1(struct packed_git *p, uint32_t n) { diff --git a/packfile.h b/packfile.h index a7fca598d6..ec08cb2bb0 100644 --- a/packfile.h +++ b/packfile.h @@ -78,6 +78,14 @@ extern struct packed_git *add_packed_git(const char *path, size_t path_len, int */ extern void check_pack_index_ptr(const struct packed_git *p, const void *ptr); +/* + * Perform binary search on a pack-index for a given oid. Packfile is expected to + * have a valid pack-index. + * + * See 'bsearch_hash' for more information. + */ +int bsearch_pack(const struct object_id *oid, const struct packed_git *p, uint32_t *result); + /* * Return the SHA-1 of the nth object within the specified packfile. * Open the index if it is not already open. The return value points diff --git a/sha1_name.c b/sha1_name.c index 735c1c0b8e..be3627b915 100644 --- 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; - uint32_t num, last, first = 0; + uint32_t num, first = 0; struct object_id oid; + const struct object_id *mad_oid; 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->hash, current); - if (!cmp) { - match = 1; - first = mid; - break; - } - if (cmp > 0) { - first = mid + 1; - continue; - } - last = mid; - } + mad_oid = (const struct object_id *)mad->hash; + match = bsearch_pack(mad_oid, p, &first); /* * first is now the position in the packfile where we would insert
-- 2.17.0.rc0
