From 5b20ace6a81e5fe1366b07c51b1f577f356a20ff Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Sun, 8 Oct 2017 14:49:40 -0400 Subject: sha1_name: unroll len loop in find_unique_abbrev_r() Unroll the while loop inside find_unique_abbrev_r to avoid iterating through all loose objects and packfiles multiple times when the short name is longer than the predicted length. Instead, inspect each object that collides with the estimated abbreviation to find the longest common prefix. The focus of this change is to refactor the existing method in a way that clearly does not change the current behavior. In some cases, the new method is slower than the previous method. Later changes will correct all performance loss. Signed-off-by: Derrick Stolee Reviewed-by: Jeff King Signed-off-by: Junio C Hamano --- sha1_name.c | 57 ++++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 42 insertions(+), 15 deletions(-) (limited to 'sha1_name.c') diff --git a/sha1_name.c b/sha1_name.c index 134ac9742..4b6c08975 100644 --- a/sha1_name.c +++ b/sha1_name.c @@ -474,10 +474,32 @@ static unsigned msb(unsigned long val) return r; } -int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len) +struct min_abbrev_data { + unsigned int init_len; + unsigned int cur_len; + char *hex; +}; + +static int extend_abbrev_len(const struct object_id *oid, void *cb_data) { - int status, exists; + struct min_abbrev_data *mad = cb_data; + + char *hex = oid_to_hex(oid); + unsigned int i = mad->init_len; + while (mad->hex[i] && mad->hex[i] == hex[i]) + i++; + + if (i < GIT_MAX_RAWSZ && i >= mad->cur_len) + mad->cur_len = i + 1; + + return 0; +} +int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len) +{ + struct disambiguate_state ds; + struct min_abbrev_data mad; + struct object_id oid_ret; if (len < 0) { unsigned long count = approximate_object_count(); /* @@ -503,19 +525,24 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len) sha1_to_hex_r(hex, sha1); if (len == GIT_SHA1_HEXSZ || !len) return GIT_SHA1_HEXSZ; - exists = has_sha1_file(sha1); - while (len < GIT_SHA1_HEXSZ) { - struct object_id oid_ret; - status = get_short_oid(hex, len, &oid_ret, GET_OID_QUIETLY); - if (exists - ? !status - : status == SHORT_NAME_NOT_FOUND) { - hex[len] = 0; - return len; - } - len++; - } - return len; + + if (init_object_disambiguation(hex, len, &ds) < 0) + return -1; + + mad.init_len = len; + mad.cur_len = len; + mad.hex = hex; + + ds.fn = extend_abbrev_len; + ds.always_call_fn = 1; + ds.cb_data = (void *)&mad; + + find_short_object_filename(&ds); + find_short_packed_object(&ds); + (void)finish_object_disambiguation(&ds, &oid_ret); + + hex[mad.cur_len] = 0; + return mad.cur_len; } const char *find_unique_abbrev(const unsigned char *sha1, int len) -- cgit v1.2.1 From a42d6fd274940be9c0fa6ada738e7611d011a1fc Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Thu, 12 Oct 2017 08:02:19 -0400 Subject: sha1_name: parse less while finding common prefix Create get_hex_char_from_oid() to parse oids one hex character at a time. This prevents unnecessary copying of hex characters in extend_abbrev_len() when finding the length of a common prefix. Signed-off-by: Derrick Stolee Reviewed-by: Jeff King Signed-off-by: Junio C Hamano --- sha1_name.c | 14 ++++++++++++-- 1 file changed, 12 insertions(+), 2 deletions(-) (limited to 'sha1_name.c') diff --git a/sha1_name.c b/sha1_name.c index 4b6c08975..733815f1d 100644 --- a/sha1_name.c +++ b/sha1_name.c @@ -480,13 +480,23 @@ struct min_abbrev_data { char *hex; }; +static inline char get_hex_char_from_oid(const struct object_id *oid, + unsigned int pos) +{ + static const char hex[] = "0123456789abcdef"; + + if ((pos & 1) == 0) + return hex[oid->hash[pos >> 1] >> 4]; + else + return hex[oid->hash[pos >> 1] & 0xf]; +} + static int extend_abbrev_len(const struct object_id *oid, void *cb_data) { struct min_abbrev_data *mad = cb_data; - char *hex = oid_to_hex(oid); unsigned int i = mad->init_len; - while (mad->hex[i] && mad->hex[i] == hex[i]) + while (mad->hex[i] && mad->hex[i] == get_hex_char_from_oid(oid, i)) i++; if (i < GIT_MAX_RAWSZ && i >= mad->cur_len) -- cgit v1.2.1 From 0e87b85683df145007862d23b5f0773368d66464 Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Thu, 12 Oct 2017 08:02:20 -0400 Subject: sha1_name: minimize OID comparisons during disambiguation Minimize OID comparisons during disambiguation of packfile OIDs. Teach git to use binary search with the full OID to find the object's position (or insertion position, if not present) in the pack-index. The object before and immediately after (or the one at the insertion position) give the maximum common prefix. No subsequent linear search is required. Take care of which two to inspect, in case the object id exists in the packfile. If the input to find_unique_abbrev_r() is a partial prefix, then the OID used for the binary search is padded with zeroes so the object will not exist in the repo (with high probability) and the same logic applies. This commit completes a series of three changes to OID abbreviation code, and the overall change can be seen using standard commands for large repos. Below we report performance statistics for perf test 4211.6 from p4211-line-log.sh using three copies of the Linux repo: | Packs | Loose | HEAD~3 | HEAD | Rel% | |-------|--------|----------|----------|-------| | 1 | 0 | 41.27 s | 38.93 s | -4.8% | | 24 | 0 | 98.04 s | 91.35 s | -5.7% | | 23 | 323952 | 117.78 s | 112.18 s | -4.8% | Signed-off-by: Derrick Stolee Reviewed-by: Jeff King Signed-off-by: Junio C Hamano --- sha1_name.c | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 71 insertions(+), 5 deletions(-) (limited to 'sha1_name.c') diff --git a/sha1_name.c b/sha1_name.c index 733815f1d..05a635911 100644 --- a/sha1_name.c +++ b/sha1_name.c @@ -153,7 +153,9 @@ static void unique_in_pack(struct packed_git *p, uint32_t num, last, i, first = 0; const struct object_id *current = NULL; - open_pack_index(p); + if (open_pack_index(p) || !p->num_objects) + return; + num = p->num_objects; last = num; while (first < last) { @@ -478,6 +480,7 @@ struct min_abbrev_data { unsigned int init_len; unsigned int cur_len; char *hex; + const unsigned char *hash; }; static inline char get_hex_char_from_oid(const struct object_id *oid, @@ -505,6 +508,67 @@ static int extend_abbrev_len(const struct object_id *oid, void *cb_data) return 0; } +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; + struct object_id 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; + } + + /* + * first is now the position in the packfile where we would insert + * mad->hash if it does not exist (or the position of mad->hash if + * it does exist). Hence, we consider a maximum of three objects + * nearby for the abbreviation length. + */ + mad->init_len = 0; + if (!match) { + nth_packed_object_oid(&oid, p, first); + extend_abbrev_len(&oid, mad); + } else if (first < num - 1) { + nth_packed_object_oid(&oid, p, first + 1); + extend_abbrev_len(&oid, mad); + } + if (first > 0) { + nth_packed_object_oid(&oid, p, first - 1); + extend_abbrev_len(&oid, mad); + } + mad->init_len = mad->cur_len; +} + +static void find_abbrev_len_packed(struct min_abbrev_data *mad) +{ + struct packed_git *p; + + prepare_packed_git(); + for (p = packed_git; p; p = p->next) + find_abbrev_len_for_pack(p, mad); +} + int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len) { struct disambiguate_state ds; @@ -536,19 +600,21 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len) if (len == GIT_SHA1_HEXSZ || !len) return GIT_SHA1_HEXSZ; - if (init_object_disambiguation(hex, len, &ds) < 0) - return -1; - mad.init_len = len; mad.cur_len = len; mad.hex = hex; + mad.hash = sha1; + + find_abbrev_len_packed(&mad); + + if (init_object_disambiguation(hex, mad.cur_len, &ds) < 0) + return -1; ds.fn = extend_abbrev_len; ds.always_call_fn = 1; ds.cb_data = (void *)&mad; find_short_object_filename(&ds); - find_short_packed_object(&ds); (void)finish_object_disambiguation(&ds, &oid_ret); hex[mad.cur_len] = 0; -- cgit v1.2.1