{"thread":{"id":"46935","subject":"[PATCH v4 1/4] p4211-line-log.sh: add log --online --raw --parents perf test","startedAt":"2017-10-08T18:50:09Z","lastAt":"2017-10-12T14:22:43Z","messageCount":22,"participants":["Derrick Stolee","Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":4,"patchTotal":4},"messages":[{"id":"329996","messageId":"20171008184942.69444-2-dstolee@microsoft.com","threadId":"46935","inReplyTo":"20171008184942.69444-1-dstolee@microsoft.com","subject":"[PATCH v4 1/4] p4211-line-log.sh: add log --online --raw --parents perf test","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-08T18:49:39Z","receivedAt":"2017-10-08T18:50:09Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Add a new perf test for testing the performance of log while computing\nOID abbreviations. Using --oneline --raw and --parents options maximizes\nthe number of OIDs to abbreviate while still spending some time computing\ndiffs.\n\nSigned-off-by: Derrick Stolee \n---\n t/perf/p4211-line-log.sh | 4 ++++\n 1 file changed, 4 insertions(+)\n\ndiff --git a/t/perf/p4211-line-log.sh b/t/perf/p4211-line-log.sh\nindex b7ff68d4f..e0ed05907 100755\n--- a/t/perf/p4211-line-log.sh\n+++ b/t/perf/p4211-line-log.sh\n@@ -31,4 +31,8 @@ test_perf 'git log -L (renames on)' '\n \tgit log -M -L 1:\"$file\" >/dev/null\n '\n \n+test_perf 'git log --oneline --raw --parents' '\n+\tgit log --oneline --raw --parents >/dev/null\n+'\n+\n test_done\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"329997","messageId":"20171008184942.69444-4-dstolee@microsoft.com","threadId":"46935","inReplyTo":"20171008184942.69444-1-dstolee@microsoft.com","subject":"[PATCH v4 3/4] sha1_name: parse less while finding common prefix","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-08T18:49:41Z","receivedAt":"2017-10-08T18:50:11Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Create get_hex_char_from_oid() to parse oids one hex character at a\ntime. This prevents unnecessary copying of hex characters in\nextend_abbrev_len() when finding the length of a common prefix.\n\nSigned-off-by: Derrick Stolee \n---\n sha1_name.c | 14 ++++++++++++--\n 1 file changed, 12 insertions(+), 2 deletions(-)\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex f2a1ebe49..5081aeb71 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -480,13 +480,23 @@ struct min_abbrev_data {\n \tchar *hex;\n };\n \n+static inline char get_hex_char_from_oid(const struct object_id *oid,\n+\t\t\t\t\t int pos)\n+{\n+\tstatic const char hex[] = \"0123456789abcdef\";\n+\n+\tif ((pos & 1) == 0)\n+\t\treturn hex[oid->hash[pos >> 1] >> 4];\n+\telse\n+\t\treturn hex[oid->hash[pos >> 1] & 0xf];\n+}\n+\n static int extend_abbrev_len(const struct object_id *oid, void *cb_data)\n {\n \tstruct min_abbrev_data *mad = cb_data;\n \n-\tchar *hex = oid_to_hex(oid);\n \tunsigned int i = mad->init_len;\n-\twhile (mad->hex[i] && mad->hex[i] == hex[i])\n+\twhile (mad->hex[i] && mad->hex[i] == get_hex_char_from_oid(oid, i))\n \t\ti++;\n \n \tif (i < GIT_MAX_RAWSZ && i >= mad->cur_len)\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"329998","messageId":"20171008184942.69444-5-dstolee@microsoft.com","threadId":"46935","inReplyTo":"20171008184942.69444-1-dstolee@microsoft.com","subject":"[PATCH v4 4/4] sha1_name: minimize OID comparisons during disambiguation","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-08T18:49:42Z","receivedAt":"2017-10-08T18:50:13Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Minimize OID comparisons during disambiguatiosn of packfile OIDs.\n\nTeach git to use binary search with the full OID to find the object's\nposition (or insertion position, if not present) in the pack-index.\nThe object before and immediately after (or the one at the insertion\nposition) give the maximum common prefix. No subsequent linear search\nis required.\n\nTake care of which two to inspect, in case the object id exists in the\npackfile.\n\nIf the input to find_unique_abbrev_r() is a partial prefix, then the\nOID used for the binary search is padded with zeroes so the object will\nnot exist in the repo (with high probability) and the same logic\napplies.\n\nThis commit completes a series of three changes to OID abbreviation\ncode, and the overall change can be seen using standard commands for\nlarge repos. Below we report performance statistics for perf test 4211.6\nfrom p4211-line-log.sh using three copies of the Linux repo:\n\n| Packs | Loose | HEAD~3 | HEAD | Rel% |\n|-------|--------|----------|----------|-------|\n| 1 | 0 | 41.27 s | 38.93 s | -4.8% |\n| 24 | 0 | 98.04 s | 91.35 s | -5.7% |\n| 23 | 323952 | 117.78 s | 112.18 s | -4.8% |\n\nSigned-off-by: Derrick Stolee \n---\n sha1_name.c | 70 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++----\n 1 file changed, 66 insertions(+), 4 deletions(-)\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 5081aeb71..49ba67955 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -478,6 +478,7 @@ struct min_abbrev_data {\n \tunsigned int init_len;\n \tunsigned int cur_len;\n \tchar *hex;\n+\tconst unsigned char *hash;\n };\n \n static inline char get_hex_char_from_oid(const struct object_id *oid,\n@@ -505,6 +506,65 @@ static int extend_abbrev_len(const struct object_id *oid, void *cb_data)\n \treturn 0;\n }\n \n+static void find_abbrev_len_for_pack(struct packed_git *p,\n+\t\t\t\t struct min_abbrev_data *mad)\n+{\n+\tint match = 0;\n+\tuint32_t num, last, first = 0;\n+\tstruct object_id oid;\n+\n+\topen_pack_index(p);\n+\tnum = p->num_objects;\n+\tlast = num;\n+\twhile (first < last) {\n+\t\tuint32_t mid = first + (last - first) / 2;\n+\t\tconst unsigned char *current;\n+\t\tint cmp;\n+\n+\t\tcurrent = nth_packed_object_sha1(p, mid);\n+\t\tcmp = hashcmp(mad->hash, current);\n+\t\tif (!cmp) {\n+\t\t\tmatch = 1;\n+\t\t\tfirst = mid;\n+\t\t\tbreak;\n+\t\t}\n+\t\tif (cmp > 0) {\n+\t\t\tfirst = mid + 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tlast = mid;\n+\t}\n+\n+\t/*\n+\t * first is now the position in the packfile where we would insert\n+\t * mad->hash if it does not exist (or the position of mad->hash if\n+\t * it does exist). Hence, we consider a maximum of three objects\n+\t * nearby for the abbreviation length.\n+\t */\n+\tmad->init_len = 0;\n+\tif (!match) {\n+\t\tnth_packed_object_oid(&oid, p, first);\n+\t\textend_abbrev_len(&oid, mad);\n+\t} else if (first < num - 1) {\n+\t\tnth_packed_object_oid(&oid, p, first + 1);\n+\t\textend_abbrev_len(&oid, mad);\n+\t}\n+\tif (first > 0) {\n+\t\tnth_packed_object_oid(&oid, p, first - 1);\n+\t\textend_abbrev_len(&oid, mad);\n+\t}\n+\tmad->init_len = mad->cur_len;\n+}\n+\n+static void find_abbrev_len_packed(struct min_abbrev_data *mad)\n+{\n+\tstruct packed_git *p;\n+\n+\tprepare_packed_git();\n+\tfor (p = packed_git; p; p = p->next)\n+\t\tfind_abbrev_len_for_pack(p, mad);\n+}\n+\n int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n {\n \tstruct disambiguate_state ds;\n@@ -536,19 +596,21 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n \tif (len == GIT_SHA1_HEXSZ || !len)\n \t\treturn GIT_SHA1_HEXSZ;\n \n-\tif (init_object_disambiguation(hex, len, &ds) < 0)\n-\t\treturn -1;\n-\n \tmad.init_len = len;\n \tmad.cur_len = len;\n \tmad.hex = hex;\n+\tmad.hash = sha1;\n+\n+\tfind_abbrev_len_packed(&mad);\n+\n+\tif (init_object_disambiguation(hex, mad.cur_len, &ds) < 0)\n+\t\treturn -1;\n \n \tds.fn = extend_abbrev_len;\n \tds.always_call_fn = 1;\n \tds.cb_data = (void*)&mad;\n \n \tfind_short_object_filename(&ds);\n-\tfind_short_packed_object(&ds);\n \t(void)finish_object_disambiguation(&ds, &oid_ret);\n \n \thex[mad.cur_len] = 0;\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"329999","messageId":"20171008184942.69444-3-dstolee@microsoft.com","threadId":"46935","inReplyTo":"20171008184942.69444-1-dstolee@microsoft.com","subject":"[PATCH v4 2/4] sha1_name: unroll len loop in find_unique_abbrev_r","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-08T18:49:40Z","receivedAt":"2017-10-08T18:50:14Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Unroll the while loop inside find_unique_abbrev_r to avoid iterating\nthrough all loose objects and packfiles multiple times when the short\nname is longer than the predicted length.\n\nInstead, inspect each object that collides with the estimated\nabbreviation to find the longest common prefix.\n\nThe focus of this change is to refactor the existing method in a way\nthat clearly does not change the current behavior. In some cases, the\nnew method is slower than the previous method. Later changes will\ncorrect all performance loss.\n\nSigned-off-by: Derrick Stolee \n---\n sha1_name.c | 57 ++++++++++++++++++++++++++++++++++++++++++---------------\n 1 file changed, 42 insertions(+), 15 deletions(-)\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 134ac9742..f2a1ebe49 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -474,10 +474,32 @@ static unsigned msb(unsigned long val)\n \treturn r;\n }\n \n-int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n+struct min_abbrev_data {\n+\tunsigned int init_len;\n+\tunsigned int cur_len;\n+\tchar *hex;\n+};\n+\n+static int extend_abbrev_len(const struct object_id *oid, void *cb_data)\n {\n-\tint status, exists;\n+\tstruct min_abbrev_data *mad = cb_data;\n+\n+\tchar *hex = oid_to_hex(oid);\n+\tunsigned int i = mad->init_len;\n+\twhile (mad->hex[i] && mad->hex[i] == hex[i])\n+\t\ti++;\n+\n+\tif (i < GIT_MAX_RAWSZ && i >= mad->cur_len)\n+\t\tmad->cur_len = i + 1;\n+\n+\treturn 0;\n+}\n \n+int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n+{\n+\tstruct disambiguate_state ds;\n+\tstruct min_abbrev_data mad;\n+\tstruct object_id oid_ret;\n \tif (len < 0) {\n \t\tunsigned long count = approximate_object_count();\n \t\t/*\n@@ -503,19 +525,24 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n \tsha1_to_hex_r(hex, sha1);\n \tif (len == GIT_SHA1_HEXSZ || !len)\n \t\treturn GIT_SHA1_HEXSZ;\n-\texists = has_sha1_file(sha1);\n-\twhile (len < GIT_SHA1_HEXSZ) {\n-\t\tstruct object_id oid_ret;\n-\t\tstatus = get_short_oid(hex, len, &oid_ret, GET_OID_QUIETLY);\n-\t\tif (exists\n-\t\t ? !status\n-\t\t : status == SHORT_NAME_NOT_FOUND) {\n-\t\t\thex[len] = 0;\n-\t\t\treturn len;\n-\t\t}\n-\t\tlen++;\n-\t}\n-\treturn len;\n+\n+\tif (init_object_disambiguation(hex, len, &ds) < 0)\n+\t\treturn -1;\n+\n+\tmad.init_len = len;\n+\tmad.cur_len = len;\n+\tmad.hex = hex;\n+\n+\tds.fn = extend_abbrev_len;\n+\tds.always_call_fn = 1;\n+\tds.cb_data = (void*)&mad;\n+\n+\tfind_short_object_filename(&ds);\n+\tfind_short_packed_object(&ds);\n+\t(void)finish_object_disambiguation(&ds, &oid_ret);\n+\n+\thex[mad.cur_len] = 0;\n+\treturn mad.cur_len;\n }\n \n const char *find_unique_abbrev(const unsigned char *sha1, int len)\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"330000","messageId":"20171008184942.69444-1-dstolee@microsoft.com","threadId":"46935","inReplyTo":null,"subject":"[PATCH v4 0/4] Improve abbreviation disambiguation","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-08T18:49:38Z","receivedAt":"2017-10-08T18:50:16Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Changes since previous version:\n\n* Fixed an overflow error in the binary search. I sent a separate patch\n to fix this error in existing searches; that patch should be applied\n before this one.\n\n* Removed test-list-objects and test-abbrev in favor of a new git log\n test in p4211-line-log.sh. Limited perf numbers for Linux repo are\n given in cover letter and commit 4/4.\n\n* Silently skip packfiles that fail to open with open_pack_index()\n\nThanks for all the comments from Jeff, Junio, Ramsey, and Stefan!\n\nThanks,\n Stolee\n\n---\n\nWhen displaying object ids, we frequently want to see an abbreviation\nfor easier typing. That abbreviation must be unambiguous among all\nobject ids.\n\nThe current implementation of find_unique_abbrev() performs a loop\nchecking if each abbreviation length is unambiguous until finding one\nthat works. This causes multiple round-trips to the disk when starting\nwith the default abbreviation length (usually 7) but needing up to 12\ncharacters for an unambiguous short-sha. For very large repos, this\neffect is pronounced and causes issues with several commands, from\nobvious consumers `status` and `log` to less obvious commands such as\n`fetch` and `push`.\n\nThis patch improves performance by iterating over objects matching the\nshort abbreviation only once, inspecting each object id, and reporting\nthe minimum length of an unambiguous abbreviation.\n\nAdd a new perf test for testing the performance of log while computing\nOID abbreviations. Using --oneline --raw and --parents options maximizes\nthe number of OIDs to abbreviate while still spending some time\ncomputing diffs. Below we report performance statistics for perf test\n4211.6 from p4211-line-log.sh using three copies of the Linux repo:\n\n| Packs | Loose | Base Time | New Time | Rel% |\n|-------|--------|-----------|----------|-------|\n| 1 | 0 | 41.27 s | 38.93 s | -4.8% |\n| 24 | 0 | 98.04 s | 91.35 s | -5.7% |\n| 23 | 323952 | 117.78 s | 112.18 s | -4.8% |\n\nDerrick Stolee (4):\n p4211-line-log.sh: add log --online --raw --parents perf test\n sha1_name: Unroll len loop in find_unique_abbrev_r\n sha1_name: Parse less while finding common prefix\n sha1_name: Minimize OID comparisons during disambiguation\n\n sha1_name.c | 129 +++++++++++++++++++++++++++++++++++++++++------\n t/perf/p4211-line-log.sh | 4 ++\n 2 files changed, 118 insertions(+), 15 deletions(-)\n\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"330038","messageId":"20171009134253.y2chrtd2hjaaaimm@sigill.intra.peff.net","threadId":"46935","inReplyTo":"20171008184942.69444-4-dstolee@microsoft.com","subject":"Re: [PATCH v4 3/4] sha1_name: parse less while finding common prefix","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-09T13:42:53Z","receivedAt":"2017-10-09T13:43:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Oct 08, 2017 at 02:49:41PM -0400, Derrick Stolee wrote:\n\n> +static inline char get_hex_char_from_oid(const struct object_id *oid,\n> +\t\t\t\t\t int pos)\n> +{\n> +\tstatic const char hex[] = \"0123456789abcdef\";\n> +\n> +\tif ((pos & 1) == 0)\n> +\t\treturn hex[oid->hash[pos >> 1] >> 4];\n> +\telse\n> +\t\treturn hex[oid->hash[pos >> 1] & 0xf];\n> +}\n\nShould \"pos\" be unsigned? I don't think it matters much in practice (as\nlong as it's not negative, the results are well defined by the standard,\nand this clearly will be between 0 and 40). But it seems funny that we\nconsistently use unsigned in the rest of the caller and then implicitly\nconvert to signed here.\n\n-Peff\n"},{"id":"330039","messageId":"20171009134933.vmba67adelqbkx4y@sigill.intra.peff.net","threadId":"46935","inReplyTo":"20171008184942.69444-5-dstolee@microsoft.com","subject":"Re: [PATCH v4 4/4] sha1_name: minimize OID comparisons during disambiguation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-09T13:49:33Z","receivedAt":"2017-10-09T13:49:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Oct 08, 2017 at 02:49:42PM -0400, Derrick Stolee wrote:\n\n> @@ -505,6 +506,65 @@ static int extend_abbrev_len(const struct object_id *oid, void *cb_data)\n> \treturn 0;\n> }\n> \n> +static void find_abbrev_len_for_pack(struct packed_git *p,\n> +\t\t\t\t struct min_abbrev_data *mad)\n> +{\n> +\tint match = 0;\n> +\tuint32_t num, last, first = 0;\n> +\tstruct object_id oid;\n> +\n> +\topen_pack_index(p);\n> +\tnum = p->num_objects;\n> +\tlast = num;\n> +\twhile (first < last) {\n> [...]\n\nYour cover letter lists:\n\n * Silently skip packfiles that fail to open with open_pack_index()\n\nas a change from the previous version. But this looks the same as the\nlast round. I think this _does_ end up skipping such packfiles because\np->num_objects will be zero. Is it worth having a comment to that\neffect (or even just an early return) to make it clear that the\nsituation is intentional?\n\nAlthough...\n\n> +\t/*\n> +\t * first is now the position in the packfile where we would insert\n> +\t * mad->hash if it does not exist (or the position of mad->hash if\n> +\t * it does exist). Hence, we consider a maximum of three objects\n> +\t * nearby for the abbreviation length.\n> +\t */\n> +\tmad->init_len = 0;\n> +\tif (!match) {\n> +\t\tnth_packed_object_oid(&oid, p, first);\n> +\t\textend_abbrev_len(&oid, mad);\n\nIf we have zero objects in the pack, what would nth_packed_object_oid()\nbe returning here?\n\nSo I actually think we do want an early return, not just when\nopen_packed_index() fails, but also when p->num_objects is zero.\n\n-Peff\n"},{"id":"330106","messageId":"338aab6a-1181-d740-1bf2-2ac86749a6b2@gmail.com","threadId":"46935","inReplyTo":"20171009134933.vmba67adelqbkx4y@sigill.intra.peff.net","subject":"Re: [PATCH v4 4/4] sha1_name: minimize OID comparisons during disambiguation","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2017-10-10T12:16:27Z","receivedAt":"2017-10-10T12:16:38Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/9/2017 9:49 AM, Jeff King wrote:\n> On Sun, Oct 08, 2017 at 02:49:42PM -0400, Derrick Stolee wrote:\n>\n>> @@ -505,6 +506,65 @@ static int extend_abbrev_len(const struct object_id *oid, void *cb_data)\n>> \treturn 0;\n>> }\n>> \n>> +static void find_abbrev_len_for_pack(struct packed_git *p,\n>> +\t\t\t\t struct min_abbrev_data *mad)\n>> +{\n>> +\tint match = 0;\n>> +\tuint32_t num, last, first = 0;\n>> +\tstruct object_id oid;\n>> +\n>> +\topen_pack_index(p);\n>> +\tnum = p->num_objects;\n>> +\tlast = num;\n>> +\twhile (first < last) {\n>> [...]\n> Your cover letter lists:\n>\n> * Silently skip packfiles that fail to open with open_pack_index()\n>\n> as a change from the previous version. But this looks the same as the\n> last round. I think this _does_ end up skipping such packfiles because\n> p->num_objects will be zero. Is it worth having a comment to that\n> effect (or even just an early return) to make it clear that the\n> situation is intentional?\n>\n> Although...\n>\n>> +\t/*\n>> +\t * first is now the position in the packfile where we would insert\n>> +\t * mad->hash if it does not exist (or the position of mad->hash if\n>> +\t * it does exist). Hence, we consider a maximum of three objects\n>> +\t * nearby for the abbreviation length.\n>> +\t */\n>> +\tmad->init_len = 0;\n>> +\tif (!match) {\n>> +\t\tnth_packed_object_oid(&oid, p, first);\n>> +\t\textend_abbrev_len(&oid, mad);\n> If we have zero objects in the pack, what would nth_packed_object_oid()\n> be returning here?\n>\n> So I actually think we do want an early return, not just when\n> open_packed_index() fails, but also when p->num_objects is zero.\n>\n> -Peff\n\nSorry about this. I caught this while I was writing my cover letter and \namended my last commit to include the following:\n\n     if (open_pack_index(p))\n         return;\n\nAfter I amended the commit, I forgot to 'format-patch' again. I can send \na diff between the commits after review has calmed.\n\nThanks,\n-Stolee\n"},{"id":"330107","messageId":"20171010123634.3hdqxpo6mbl6jhbx@sigill.intra.peff.net","threadId":"46935","inReplyTo":"338aab6a-1181-d740-1bf2-2ac86749a6b2@gmail.com","subject":"Re: [PATCH v4 4/4] sha1_name: minimize OID comparisons during disambiguation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-10T12:36:34Z","receivedAt":"2017-10-10T12:36:41Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Oct 10, 2017 at 08:16:27AM -0400, Derrick Stolee wrote:\n\n> > > +\tmad->init_len = 0;\n> > > +\tif (!match) {\n> > > +\t\tnth_packed_object_oid(&oid, p, first);\n> > > +\t\textend_abbrev_len(&oid, mad);\n> > If we have zero objects in the pack, what would nth_packed_object_oid()\n> > be returning here?\n> > \n> > So I actually think we do want an early return, not just when\n> > open_packed_index() fails, but also when p->num_objects is zero.\n> > \n> > -Peff\n> \n> Sorry about this. I caught this while I was writing my cover letter and\n> amended my last commit to include the following:\n> \n>     if (open_pack_index(p))\n>         return;\n> \n> After I amended the commit, I forgot to 'format-patch' again. I can send a\n> diff between the commits after review has calmed.\n\nOK, I think that makes more sense. But note the p->num_objects thing I\nmentioned. If I do:\n\n git pack-objects .git/objects/pack/pack num_objects)\n\treturn;\n\nTechnically that also covers open_pack_index() failure, too, but that's\na subtlety I don't think we should rely on.\n\n-Peff\n"},{"id":"330110","messageId":"xmqqbmlfp3eh.fsf@gitster.mtv.corp.google.com","threadId":"46935","inReplyTo":"20171010123634.3hdqxpo6mbl6jhbx@sigill.intra.peff.net","subject":"Re: [PATCH v4 4/4] sha1_name: minimize OID comparisons during disambiguation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-10T12:56:38Z","receivedAt":"2017-10-10T12:57:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> OK, I think that makes more sense. But note the p->num_objects thing I\n> mentioned. If I do:\n>\n> git pack-objects .git/objects/pack/pack \n> then I have a pack with zero objects, which I think we'd similarly want\n> to return early from. I.e., I think we need:\n>\n> if (p->num_objects)\n> \treturn;\n>\n> Technically that also covers open_pack_index() failure, too, but that's\n> a subtlety I don't think we should rely on.\n\nTrue. I notice that the early part of the two functions look almost\nidentical. Do we need error condition handling for the other one,\ntoo?\n"},{"id":"330113","messageId":"20171010130919.r4b5v4k7mdyuxllu@sigill.intra.peff.net","threadId":"46935","inReplyTo":"xmqqbmlfp3eh.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v4 4/4] sha1_name: minimize OID comparisons during disambiguation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-10T13:09:19Z","receivedAt":"2017-10-10T13:09:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Oct 10, 2017 at 09:56:38PM +0900, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > OK, I think that makes more sense. But note the p->num_objects thing I\n> > mentioned. If I do:\n> >\n> > git pack-objects .git/objects/pack/pack >\n> > then I have a pack with zero objects, which I think we'd similarly want\n> > to return early from. I.e., I think we need:\n> >\n> > if (p->num_objects)\n> > \treturn;\n> >\n> > Technically that also covers open_pack_index() failure, too, but that's\n> > a subtlety I don't think we should rely on.\n> \n> True. I notice that the early part of the two functions look almost\n> identical. Do we need error condition handling for the other one,\n> too?\n\nI'm not sure which two you mean. Do you mean find_pack_entry_one() in\npackfile.c as the other one? If so, I think it is fine in the\nzero-object case, because it does not do the \"this is the sha1 at the\nposition where it _would_ be found\" trick, which is what causes us to\npotentially dereference nonsense.\n\n-Peff\n"},{"id":"330114","messageId":"f9add2c3-5499-085e-e433-799427dda6d8@gmail.com","threadId":"46935","inReplyTo":"xmqqbmlfp3eh.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v4 4/4] sha1_name: minimize OID comparisons during disambiguation","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2017-10-10T13:11:15Z","receivedAt":"2017-10-10T13:11:22Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/10/2017 8:56 AM, Junio C Hamano wrote:\n> Jeff King writes:\n>\n>> OK, I think that makes more sense. But note the p->num_objects thing I\n>> mentioned. If I do:\n>>\n>> git pack-objects .git/objects/pack/pack >\n>> then I have a pack with zero objects, which I think we'd similarly want\n>> to return early from. I.e., I think we need:\n>>\n>> if (p->num_objects)\n>> \treturn;\n>>\n>> Technically that also covers open_pack_index() failure, too, but that's\n>> a subtlety I don't think we should rely on.\n> True. I notice that the early part of the two functions look almost\n> identical. Do we need error condition handling for the other one,\n> too?\n\nI prefer to fix the problem in all code clones when they cause review \nfriction, so I'll send a fifth commit showing just the diff for these \npackfile issues in sha1_name.c. See patch below.\n\nShould open_pack_index() return a non-zero status if the packfile is \nempty? Or, is there a meaningful reason to have empty packfiles?\n\nThanks,\n-Stolee\n\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 49ba67955..9f8a33e82 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -153,7 +153,9 @@ static void unique_in_pack(struct packed_git *p,\n         uint32_t num, last, i, first = 0;\n         const struct object_id *current = NULL;\n\n-       open_pack_index(p);\n+       if (open_pack_index(p) || !p->num_objects)\n+               return;\n+\n         num = p->num_objects;\n         last = num;\n         while (first < last) {\n@@ -513,7 +515,9 @@ static void find_abbrev_len_for_pack(struct \npacked_git *p,\n         uint32_t num, last, first = 0;\n         struct object_id oid;\n\n-       open_pack_index(p);\n+       if (open_pack_index(p) || !p->num_objects)\n+               return;\n+\n         num = p->num_objects;\n         last = num;\n         while (first < last) {\n\n"},{"id":"330115","messageId":"20171010133040.2j5wpgcvucquizpn@sigill.intra.peff.net","threadId":"46935","inReplyTo":"f9add2c3-5499-085e-e433-799427dda6d8@gmail.com","subject":"Re: [PATCH v4 4/4] sha1_name: minimize OID comparisons during disambiguation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-10T13:30:40Z","receivedAt":"2017-10-10T13:30:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Oct 10, 2017 at 09:11:15AM -0400, Derrick Stolee wrote:\n\n> On 10/10/2017 8:56 AM, Junio C Hamano wrote:\n> > Jeff King writes:\n> > \n> > > OK, I think that makes more sense. But note the p->num_objects thing I\n> > > mentioned. If I do:\n> > > \n> > > git pack-objects .git/objects/pack/pack > > \n> > > then I have a pack with zero objects, which I think we'd similarly want\n> > > to return early from. I.e., I think we need:\n> > > \n> > > if (p->num_objects)\n> > > \treturn;\n> > > \n> > > Technically that also covers open_pack_index() failure, too, but that's\n> > > a subtlety I don't think we should rely on.\n> > True. I notice that the early part of the two functions look almost\n> > identical. Do we need error condition handling for the other one,\n> > too?\n> \n> I prefer to fix the problem in all code clones when they cause review\n> friction, so I'll send a fifth commit showing just the diff for these\n> packfile issues in sha1_name.c. See patch below.\n\nAh, that answers my earlier question. Junio mean unique_in_pack(). And\nyeah, I think it suffers from the same problem.\n\n> Should open_pack_index() return a non-zero status if the packfile is empty?\n> Or, is there a meaningful reason to have empty packfiles?\n\nI can't think of a compelling reason to have an empty packfile. But nor\ndo I think we should consider them an error when we can handle them\nquietly (and returning non-zero status would cause Git to complain on\nmany operations in a repository that has such a file).\n\n-Peff\n"},{"id":"330178","messageId":"61168095-d392-39d2-ba65-823525239b5c@gmail.com","threadId":"46935","inReplyTo":"20171010133040.2j5wpgcvucquizpn@sigill.intra.peff.net","subject":"Re: [PATCH v4 4/4] sha1_name: minimize OID comparisons during disambiguation","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2017-10-11T13:58:38Z","receivedAt":"2017-10-11T13:58:47Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/10/2017 9:30 AM, Jeff King wrote:\n> On Tue, Oct 10, 2017 at 09:11:15AM -0400, Derrick Stolee wrote:\n>\n>> On 10/10/2017 8:56 AM, Junio C Hamano wrote:\n>>> Jeff King writes:\n>>>\n>>>> OK, I think that makes more sense. But note the p->num_objects thing I\n>>>> mentioned. If I do:\n>>>>\n>>>> git pack-objects .git/objects/pack/pack >>>\n>>>> then I have a pack with zero objects, which I think we'd similarly want\n>>>> to return early from. I.e., I think we need:\n>>>>\n>>>> if (p->num_objects)\n>>>> \treturn;\n>>>>\n>>>> Technically that also covers open_pack_index() failure, too, but that's\n>>>> a subtlety I don't think we should rely on.\n>>> True. I notice that the early part of the two functions look almost\n>>> identical. Do we need error condition handling for the other one,\n>>> too?\n>> I prefer to fix the problem in all code clones when they cause review\n>> friction, so I'll send a fifth commit showing just the diff for these\n>> packfile issues in sha1_name.c. See patch below.\n> Ah, that answers my earlier question. Junio mean unique_in_pack(). And\n> yeah, I think it suffers from the same problem.\n>\n>> Should open_pack_index() return a non-zero status if the packfile is empty?\n>> Or, is there a meaningful reason to have empty packfiles?\n> I can't think of a compelling reason to have an empty packfile. But nor\n> do I think we should consider them an error when we can handle them\n> quietly (and returning non-zero status would cause Git to complain on\n> many operations in a repository that has such a file).\n>\n> -Peff\n\nThanks for the comments. I found some typos in my commit messages, too.\n\nI plan to send a (hopefully) final version tomorrow (Thursday). It will \ninclude:\n\n* Make 'pos' unsigned in get_hex_char_from_oid()\n\n* Check response from open_pack_index()\n\n* Small typos in commit messages\n\nIf there are other issues, then please let me know.\n\nThanks,\n-Stolee\n"},{"id":"330270","messageId":"20171012120220.226427-1-dstolee@microsoft.com","threadId":"46935","inReplyTo":"61168095-d392-39d2-ba65-823525239b5c@gmail.com","subject":"[PATCH v5 0/4] Improve abbreviation disambiguation","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-12T12:02:16Z","receivedAt":"2017-10-12T12:02:47Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Changes since previous version:\n\n* Make 'pos' unsigned in get_hex_char_from_oid()\n\n* Check response from open_pack_index()\n\n* Small typos in commit messages \n\nThanks,\n Stolee\n\n---\n\nWhen displaying object ids, we frequently want to see an abbreviation\nfor easier typing. That abbreviation must be unambiguous among all\nobject ids.\n\nThe current implementation of find_unique_abbrev() performs a loop\nchecking if each abbreviation length is unambiguous until finding one\nthat works. This causes multiple round-trips to the disk when starting\nwith the default abbreviation length (usually 7) but needing up to 12\ncharacters for an unambiguous short-sha. For very large repos, this\neffect is pronounced and causes issues with several commands, from\nobvious consumers `status` and `log` to less obvious commands such as\n`fetch` and `push`.\n\nThis patch improves performance by iterating over objects matching the\nshort abbreviation only once, inspecting each object id, and reporting\nthe minimum length of an unambiguous abbreviation.\n\nAdd a new perf test for testing the performance of log while computing\nOID abbreviations. Using --oneline --raw and --parents options maximizes\nthe number of OIDs to abbreviate while still spending some time\ncomputing diffs. Below we report performance statistics for perf test\n4211.6 from p4211-line-log.sh using three copies of the Linux repo:\n\n| Packs | Loose | Base Time | New Time | Rel% |\n|-------|--------|-----------|----------|-------|\n| 1 | 0 | 41.27 s | 38.93 s | -4.8% |\n| 24 | 0 | 98.04 s | 91.35 s | -5.7% |\n| 23 | 323952 | 117.78 s | 112.18 s | -4.8% |\n\nDerrick Stolee (4):\n p4211-line-log.sh: add log --online --raw --parents perf test\n sha1_name: unroll len loop in find_unique_abbrev_r\n sha1_name: parse less while finding common prefix\n sha1_name: minimize OID comparisons during disambiguation\n sha1_name.c | 135 +++++++++++++++++++++++++++++++++++++++++------\n t/perf/p4211-line-log.sh | 4 ++\n 2 files changed, 123 insertions(+), 16 deletions(-)\n\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"330271","messageId":"20171012120220.226427-4-dstolee@microsoft.com","threadId":"46935","inReplyTo":"61168095-d392-39d2-ba65-823525239b5c@gmail.com","subject":"[PATCH v5 3/4] sha1_name: parse less while finding common prefix","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-12T12:02:19Z","receivedAt":"2017-10-12T12:02:51Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Create get_hex_char_from_oid() to parse oids one hex character at a\ntime. This prevents unnecessary copying of hex characters in\nextend_abbrev_len() when finding the length of a common prefix.\n\nSigned-off-by: Derrick Stolee \n---\n sha1_name.c | 14 ++++++++++++--\n 1 file changed, 12 insertions(+), 2 deletions(-)\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 19603713f..fdd2711a6 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -480,13 +480,23 @@ struct min_abbrev_data {\n \tchar *hex;\n };\n \n+static inline char get_hex_char_from_oid(const struct object_id *oid,\n+\t\t\t\t\t unsigned int pos)\n+{\n+\tstatic const char hex[] = \"0123456789abcdef\";\n+\n+\tif ((pos & 1) == 0)\n+\t\treturn hex[oid->hash[pos >> 1] >> 4];\n+\telse\n+\t\treturn hex[oid->hash[pos >> 1] & 0xf];\n+}\n+\n static int extend_abbrev_len(const struct object_id *oid, void *cb_data)\n {\n \tstruct min_abbrev_data *mad = cb_data;\n \n-\tchar *hex = oid_to_hex(oid);\n \tunsigned int i = mad->init_len;\n-\twhile (mad->hex[i] && mad->hex[i] == hex[i])\n+\twhile (mad->hex[i] && mad->hex[i] == get_hex_char_from_oid(oid, i))\n \t\ti++;\n \n \tif (i < GIT_MAX_RAWSZ && i >= mad->cur_len)\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"330272","messageId":"20171012120220.226427-3-dstolee@microsoft.com","threadId":"46935","inReplyTo":"61168095-d392-39d2-ba65-823525239b5c@gmail.com","subject":"[PATCH v5 2/4] sha1_name: unroll len loop in find_unique_abbrev_r","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-12T12:02:18Z","receivedAt":"2017-10-12T12:02:56Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Unroll the while loop inside find_unique_abbrev_r to avoid iterating\nthrough all loose objects and packfiles multiple times when the short\nname is longer than the predicted length.\n\nInstead, inspect each object that collides with the estimated\nabbreviation to find the longest common prefix.\n\nThe focus of this change is to refactor the existing method in a way\nthat clearly does not change the current behavior. In some cases, the\nnew method is slower than the previous method. Later changes will\ncorrect all performance loss.\n\nSigned-off-by: Derrick Stolee \n---\n sha1_name.c | 57 ++++++++++++++++++++++++++++++++++++++++++---------------\n 1 file changed, 42 insertions(+), 15 deletions(-)\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex c7c5ab376..19603713f 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -474,10 +474,32 @@ static unsigned msb(unsigned long val)\n \treturn r;\n }\n \n-int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n+struct min_abbrev_data {\n+\tunsigned int init_len;\n+\tunsigned int cur_len;\n+\tchar *hex;\n+};\n+\n+static int extend_abbrev_len(const struct object_id *oid, void *cb_data)\n {\n-\tint status, exists;\n+\tstruct min_abbrev_data *mad = cb_data;\n+\n+\tchar *hex = oid_to_hex(oid);\n+\tunsigned int i = mad->init_len;\n+\twhile (mad->hex[i] && mad->hex[i] == hex[i])\n+\t\ti++;\n+\n+\tif (i < GIT_MAX_RAWSZ && i >= mad->cur_len)\n+\t\tmad->cur_len = i + 1;\n+\n+\treturn 0;\n+}\n \n+int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n+{\n+\tstruct disambiguate_state ds;\n+\tstruct min_abbrev_data mad;\n+\tstruct object_id oid_ret;\n \tif (len < 0) {\n \t\tunsigned long count = approximate_object_count();\n \t\t/*\n@@ -503,19 +525,24 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n \tsha1_to_hex_r(hex, sha1);\n \tif (len == GIT_SHA1_HEXSZ || !len)\n \t\treturn GIT_SHA1_HEXSZ;\n-\texists = has_sha1_file(sha1);\n-\twhile (len < GIT_SHA1_HEXSZ) {\n-\t\tstruct object_id oid_ret;\n-\t\tstatus = get_short_oid(hex, len, &oid_ret, GET_OID_QUIETLY);\n-\t\tif (exists\n-\t\t ? !status\n-\t\t : status == SHORT_NAME_NOT_FOUND) {\n-\t\t\thex[len] = 0;\n-\t\t\treturn len;\n-\t\t}\n-\t\tlen++;\n-\t}\n-\treturn len;\n+\n+\tif (init_object_disambiguation(hex, len, &ds) < 0)\n+\t\treturn -1;\n+\n+\tmad.init_len = len;\n+\tmad.cur_len = len;\n+\tmad.hex = hex;\n+\n+\tds.fn = extend_abbrev_len;\n+\tds.always_call_fn = 1;\n+\tds.cb_data = (void*)&mad;\n+\n+\tfind_short_object_filename(&ds);\n+\tfind_short_packed_object(&ds);\n+\t(void)finish_object_disambiguation(&ds, &oid_ret);\n+\n+\thex[mad.cur_len] = 0;\n+\treturn mad.cur_len;\n }\n \n const char *find_unique_abbrev(const unsigned char *sha1, int len)\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"330273","messageId":"20171012120220.226427-2-dstolee@microsoft.com","threadId":"46935","inReplyTo":"61168095-d392-39d2-ba65-823525239b5c@gmail.com","subject":"[PATCH v5 1/4] p4211-line-log.sh: add log --online --raw --parents perf test","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-12T12:02:17Z","receivedAt":"2017-10-12T12:02:58Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Add a new perf test for testing the performance of log while computing\nOID abbreviations. Using --oneline --raw and --parents options maximizes\nthe number of OIDs to abbreviate while still spending some time computing\ndiffs.\n\nSigned-off-by: Derrick Stolee \n---\n t/perf/p4211-line-log.sh | 4 ++++\n 1 file changed, 4 insertions(+)\n\ndiff --git a/t/perf/p4211-line-log.sh b/t/perf/p4211-line-log.sh\nindex b7ff68d4f..e0ed05907 100755\n--- a/t/perf/p4211-line-log.sh\n+++ b/t/perf/p4211-line-log.sh\n@@ -31,4 +31,8 @@ test_perf 'git log -L (renames on)' '\n \tgit log -M -L 1:\"$file\" >/dev/null\n '\n \n+test_perf 'git log --oneline --raw --parents' '\n+\tgit log --oneline --raw --parents >/dev/null\n+'\n+\n test_done\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"330274","messageId":"20171012120220.226427-5-dstolee@microsoft.com","threadId":"46935","inReplyTo":"61168095-d392-39d2-ba65-823525239b5c@gmail.com","subject":"[PATCH v5 4/4] sha1_name: minimize OID comparisons during disambiguation","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-12T12:02:20Z","receivedAt":"2017-10-12T12:03:01Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Minimize OID comparisons during disambiguation of packfile OIDs.\n\nTeach git to use binary search with the full OID to find the object's\nposition (or insertion position, if not present) in the pack-index.\nThe object before and immediately after (or the one at the insertion\nposition) give the maximum common prefix. No subsequent linear search\nis required.\n\nTake care of which two to inspect, in case the object id exists in the\npackfile.\n\nIf the input to find_unique_abbrev_r() is a partial prefix, then the\nOID used for the binary search is padded with zeroes so the object will\nnot exist in the repo (with high probability) and the same logic\napplies.\n\nThis commit completes a series of three changes to OID abbreviation\ncode, and the overall change can be seen using standard commands for\nlarge repos. Below we report performance statistics for perf test 4211.6\nfrom p4211-line-log.sh using three copies of the Linux repo:\n\n| Packs | Loose | HEAD~3 | HEAD | Rel% |\n|-------|--------|----------|----------|-------|\n| 1 | 0 | 41.27 s | 38.93 s | -4.8% |\n| 24 | 0 | 98.04 s | 91.35 s | -5.7% |\n| 23 | 323952 | 117.78 s | 112.18 s | -4.8% |\n\nSigned-off-by: Derrick Stolee \n---\n sha1_name.c | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++----\n 1 file changed, 71 insertions(+), 5 deletions(-)\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex fdd2711a6..7fd5f5f71 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -153,7 +153,9 @@ static void unique_in_pack(struct packed_git *p,\n \tuint32_t num, last, i, first = 0;\n \tconst struct object_id *current = NULL;\n \n-\topen_pack_index(p);\n+\tif (open_pack_index(p) || !p->num_objects)\n+\t\treturn;\n+\n \tnum = p->num_objects;\n \tlast = num;\n \twhile (first < last) {\n@@ -478,6 +480,7 @@ struct min_abbrev_data {\n \tunsigned int init_len;\n \tunsigned int cur_len;\n \tchar *hex;\n+\tconst unsigned char *hash;\n };\n \n static inline char get_hex_char_from_oid(const struct object_id *oid,\n@@ -505,6 +508,67 @@ static int extend_abbrev_len(const struct object_id *oid, void *cb_data)\n \treturn 0;\n }\n \n+static void find_abbrev_len_for_pack(struct packed_git *p,\n+\t\t\t\t struct min_abbrev_data *mad)\n+{\n+\tint match = 0;\n+\tuint32_t num, last, first = 0;\n+\tstruct object_id oid;\n+\n+\tif (open_pack_index(p) || !p->num_objects)\n+\t\treturn;\n+\n+\tnum = p->num_objects;\n+\tlast = num;\n+\twhile (first < last) {\n+\t\tuint32_t mid = first + (last - first) / 2;\n+\t\tconst unsigned char *current;\n+\t\tint cmp;\n+\n+\t\tcurrent = nth_packed_object_sha1(p, mid);\n+\t\tcmp = hashcmp(mad->hash, current);\n+\t\tif (!cmp) {\n+\t\t\tmatch = 1;\n+\t\t\tfirst = mid;\n+\t\t\tbreak;\n+\t\t}\n+\t\tif (cmp > 0) {\n+\t\t\tfirst = mid + 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tlast = mid;\n+\t}\n+\n+\t/*\n+\t * first is now the position in the packfile where we would insert\n+\t * mad->hash if it does not exist (or the position of mad->hash if\n+\t * it does exist). Hence, we consider a maximum of three objects\n+\t * nearby for the abbreviation length.\n+\t */\n+\tmad->init_len = 0;\n+\tif (!match) {\n+\t\tnth_packed_object_oid(&oid, p, first);\n+\t\textend_abbrev_len(&oid, mad);\n+\t} else if (first < num - 1) {\n+\t\tnth_packed_object_oid(&oid, p, first + 1);\n+\t\textend_abbrev_len(&oid, mad);\n+\t}\n+\tif (first > 0) {\n+\t\tnth_packed_object_oid(&oid, p, first - 1);\n+\t\textend_abbrev_len(&oid, mad);\n+\t}\n+\tmad->init_len = mad->cur_len;\n+}\n+\n+static void find_abbrev_len_packed(struct min_abbrev_data *mad)\n+{\n+\tstruct packed_git *p;\n+\n+\tprepare_packed_git();\n+\tfor (p = packed_git; p; p = p->next)\n+\t\tfind_abbrev_len_for_pack(p, mad);\n+}\n+\n int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n {\n \tstruct disambiguate_state ds;\n@@ -536,19 +600,21 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n \tif (len == GIT_SHA1_HEXSZ || !len)\n \t\treturn GIT_SHA1_HEXSZ;\n \n-\tif (init_object_disambiguation(hex, len, &ds) < 0)\n-\t\treturn -1;\n-\n \tmad.init_len = len;\n \tmad.cur_len = len;\n \tmad.hex = hex;\n+\tmad.hash = sha1;\n+\n+\tfind_abbrev_len_packed(&mad);\n+\n+\tif (init_object_disambiguation(hex, mad.cur_len, &ds) < 0)\n+\t\treturn -1;\n \n \tds.fn = extend_abbrev_len;\n \tds.always_call_fn = 1;\n \tds.cb_data = (void*)&mad;\n \n \tfind_short_object_filename(&ds);\n-\tfind_short_packed_object(&ds);\n \t(void)finish_object_disambiguation(&ds, &oid_ret);\n \n \thex[mad.cur_len] = 0;\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"330275","messageId":"3261c086-01d9-42aa-5e82-002a4da37275@gmail.com","threadId":"46935","inReplyTo":"20171012120220.226427-1-dstolee@microsoft.com","subject":"Re: [PATCH v5 0/4] Improve abbreviation disambiguation","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2017-10-12T12:04:28Z","receivedAt":"2017-10-12T12:04:36Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/12/2017 8:02 AM, Derrick Stolee wrote:\n> Changes since previous version:\n>\n> * Make 'pos' unsigned in get_hex_char_from_oid()\n>\n> * Check response from open_pack_index()\n>\n> * Small typos in commit messages\n>\n> Thanks,\n> Stolee\n>\nI forgot to mention that I rebased on master this morning to be sure \nthis doesn't conflict with the binary-search patch that was queued this \nweek.\n\nThanks,\n  Stolee\n"},{"id":"330276","messageId":"xmqqr2u8y2tg.fsf@gitster.mtv.corp.google.com","threadId":"46935","inReplyTo":"3261c086-01d9-42aa-5e82-002a4da37275@gmail.com","subject":"Re: [PATCH v5 0/4] Improve abbreviation disambiguation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-12T12:21:15Z","receivedAt":"2017-10-12T12:21:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> On 10/12/2017 8:02 AM, Derrick Stolee wrote:\n>> Changes since previous version:\n>>\n>> * Make 'pos' unsigned in get_hex_char_from_oid()\n>>\n>> * Check response from open_pack_index()\n>>\n>> * Small typos in commit messages\n>>\n>> Thanks,\n>> Stolee\n>>\n> I forgot to mention that I rebased on master this morning to be sure\n> this doesn't conflict with the binary-search patch that was queued\n> this week.\n\nThanks for being extra careful. \n\nI've re-applied minor style fix s/(void\\*)/(void \\*)/ to 2/4 and 4/4\nbut other than that, the difference between this round and what has\nbeen queued looked all reasonable.\n\nWill replace.\n\n"},{"id":"330283","messageId":"20171012142236.dw64bovrmdvv5jn7@sigill.intra.peff.net","threadId":"46935","inReplyTo":"xmqqr2u8y2tg.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v5 0/4] Improve abbreviation disambiguation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-12T14:22:37Z","receivedAt":"2017-10-12T14:22:43Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 12, 2017 at 09:21:15PM +0900, Junio C Hamano wrote:\n\n> Derrick Stolee writes:\n> \n> > On 10/12/2017 8:02 AM, Derrick Stolee wrote:\n> >> Changes since previous version:\n> >>\n> >> * Make 'pos' unsigned in get_hex_char_from_oid()\n> >>\n> >> * Check response from open_pack_index()\n> >>\n> >> * Small typos in commit messages\n> >>\n> >> Thanks,\n> >> Stolee\n> >>\n> > I forgot to mention that I rebased on master this morning to be sure\n> > this doesn't conflict with the binary-search patch that was queued\n> > this week.\n> \n> Thanks for being extra careful. \n> \n> I've re-applied minor style fix s/(void\\*)/(void \\*)/ to 2/4 and 4/4\n> but other than that, the difference between this round and what has\n> been queued looked all reasonable.\n> \n> Will replace.\n\nThis looks good to me, too.\n\nAt first I was going to point out the nit that unique_in_pack() is\nquietly fixed in 4/4 for the empty-pack case. But I don't think it's\nactually buggy. The examination of nth_packed_object_oid() would never\nbe triggered if \"num\" is 0. So it probably is fine simply to fix it\nquietly along with adding the new function.\n\n-Peff\n"}]}