{"thread":{"id":"48100","subject":"[PATCH] sha1_name: use bsearch_hash() for abbreviations","startedAt":"2018-03-20T20:04:02Z","lastAt":"2018-03-25T18:21:06Z","messageCount":12,"participants":["Derrick Stolee","Jonathan Tan","brian m. carlson","René Scharfe","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"342357","messageId":"20180320200325.168147-1-dstolee@microsoft.com","threadId":"48100","inReplyTo":null,"subject":"[PATCH] sha1_name: use bsearch_hash() for abbreviations","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-03-20T20:03:25Z","receivedAt":"2018-03-20T20:04:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"This patch updates the abbreviation code to use bsearch_hash() as defined\nin [1]. It gets a nice speedup since the old implementation did not use\nthe fanout table at all.\n\nOne caveat about the patch: there is a place where I cast a sha1 hash\ninto a struct object_id pointer. This is because the abbreviation code\nstill uses 'const unsigned char *' instead of structs. I wanted to avoid\na hashcpy() in these calls, but perhaps that is not too heavy a cost.\n\nI look forward to feedback on this.\n\nThanks,\n-Stolee\n\n[1] https://public-inbox.org/git/007f3a4c84cb1c07255404ad1ea9f797129c5cf0.1517609773.git.jonathantanmy@google.com/\n [PATCH 2/2] packfile: refactor hash search with fanout table\n\n-- >8 --\n\nWhen computing abbreviation lengths for an object ID against a single\npackfile, the method find_abbrev_len_for_pack() currently implements\nbinary search. This is one of several implementations. One issue with\nthis implementation is that it ignores the fanout table in the pack-\nindex.\n\nTranslate this binary search to use the existing bsearch_hash() method\nthat correctly uses a fanout table. To keep the details about pack-\nindex version 1 or 2 out of sha1_name.c, create a bsearch_pack() method\nin packfile.c.\n\nDue to the use of the fanout table, the abbreviation computation is\nslightly faster than before. For a fully-repacked copy of the Linux\nrepo, the following 'git log' commands improved:\n\n* git log --oneline --parents --raw\n Before: 66.83s\n After: 64.85s\n Rel %: -2.9%\n\n* git log --oneline --parents\n Before: 7.85s\n After: 7.29s\n Rel %: -7.1%\n\nSigned-off-by: Derrick Stolee \n---\n packfile.c | 23 +++++++++++++++++++++++\n packfile.h | 8 ++++++++\n sha1_name.c | 24 ++++--------------------\n 3 files changed, 35 insertions(+), 20 deletions(-)\n\ndiff --git a/packfile.c b/packfile.c\nindex 7c1a2519fc..ea0388f6dd 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1654,6 +1654,29 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n \treturn data;\n }\n \n+int bsearch_pack(const struct object_id *oid, const struct packed_git *p, uint32_t *result)\n+{\n+\tconst unsigned char *index_fanout = p->index_data;\n+\tconst unsigned char *index_lookup;\n+\tint index_lookup_width;\n+\n+\tif (!index_fanout)\n+\t\tBUG(\"bsearch_pack called without a valid pack-index\");\n+\n+\tindex_lookup = index_fanout + 4 * 256;\n+\tif (p->index_version == 1) {\n+\t\tindex_lookup_width = 24;\n+\t\tindex_lookup += 4;\n+\t} else {\n+\t\tindex_lookup_width = 20;\n+\t\tindex_fanout += 8;\n+\t\tindex_lookup += 8;\n+\t}\n+\n+\treturn bsearch_hash(oid->hash, (const uint32_t*)index_fanout,\n+\t\t\t index_lookup, index_lookup_width, result);\n+}\n+\n const unsigned char *nth_packed_object_sha1(struct packed_git *p,\n \t\t\t\t\t uint32_t n)\n {\ndiff --git a/packfile.h b/packfile.h\nindex a7fca598d6..ec08cb2bb0 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -78,6 +78,14 @@ extern struct packed_git *add_packed_git(const char *path, size_t path_len, int\n */\n extern void check_pack_index_ptr(const struct packed_git *p, const void *ptr);\n \n+/*\n+ * Perform binary search on a pack-index for a given oid. Packfile is expected to\n+ * have a valid pack-index.\n+ *\n+ * See 'bsearch_hash' for more information.\n+ */\n+int bsearch_pack(const struct object_id *oid, const struct packed_git *p, uint32_t *result);\n+\n /*\n * Return the SHA-1 of the nth object within the specified packfile.\n * Open the index if it is not already open. The return value points\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 735c1c0b8e..be3627b915 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -512,32 +512,16 @@ 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+\tuint32_t num, first = 0;\n \tstruct object_id oid;\n+\tconst struct object_id *mad_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+\tmad_oid = (const struct object_id *)mad->hash;\n+\tmatch = bsearch_pack(mad_oid, p, &first);\n \n \t/*\n \t * first is now the position in the packfile where we would insert\n-- \n2.17.0.rc0\n\n"},{"id":"342369","messageId":"20180320152505.bd66f0deaecf6d92fa6d62de@google.com","threadId":"48100","inReplyTo":"20180320200325.168147-1-dstolee@microsoft.com","subject":"Re: [PATCH] sha1_name: use bsearch_hash() for abbreviations","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2018-03-20T22:25:05Z","receivedAt":"2018-03-20T22:25:13Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Tue, 20 Mar 2018 16:03:25 -0400\nDerrick Stolee wrote:\n\n> This patch updates the abbreviation code to use bsearch_hash() as defined\n> in [1]. It gets a nice speedup since the old implementation did not use\n> the fanout table at all.\n\nYou can refer to the patch as:\n\n b4e00f7306a1 (\"packfile: refactor hash search with fanout table\",\n 2018-02-15)\n\nAlso, might be worth noting that this patch builds on\njt/binsearch-with-fanout.\n\n> One caveat about the patch: there is a place where I cast a sha1 hash\n> into a struct object_id pointer. This is because the abbreviation code\n> still uses 'const unsigned char *' instead of structs. I wanted to avoid\n> a hashcpy() in these calls, but perhaps that is not too heavy a cost.\n\nI recall a discussion that there were alignment issues with doing this,\nbut I might have be remembering wrongly - in my limited knowledge of C\nalignment, both \"unsigned char *\" and \"struct object_id *\" have the same\nconstraints, but I'm not sure.\n\n> +\tconst unsigned char *index_fanout = p->index_data;\n[snip]\n> +\treturn bsearch_hash(oid->hash, (const uint32_t*)index_fanout,\n> +\t\t\t index_lookup, index_lookup_width, result);\n\nThis cast to \"const uint32_t *\" is safe, because p->index_data points to\na mmap-ed region (which has very good alignment, as far as I know). I\nwonder if we should document alignment guarantees on p->index_data, and\nif yes, what guarantees to declare.\n"},{"id":"342408","messageId":"3527bd3a-a899-a909-5fda-1d7abeb0e158@gmail.com","threadId":"48100","inReplyTo":"20180320152505.bd66f0deaecf6d92fa6d62de@google.com","subject":"Re: [PATCH] sha1_name: use bsearch_hash() for abbreviations","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-03-21T13:24:06Z","receivedAt":"2018-03-21T13:24:19Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/20/2018 6:25 PM, Jonathan Tan wrote:\n> On Tue, 20 Mar 2018 16:03:25 -0400\n> Derrick Stolee wrote:\n>\n>> This patch updates the abbreviation code to use bsearch_hash() as defined\n>> in [1]. It gets a nice speedup since the old implementation did not use\n>> the fanout table at all.\n> You can refer to the patch as:\n>\n> b4e00f7306a1 (\"packfile: refactor hash search with fanout table\",\n> 2018-02-15)\n>\n> Also, might be worth noting that this patch builds on\n> jt/binsearch-with-fanout.\n\nThanks. That commit is in master and v2.17.0-rc0, so hopefully it isn't \ndifficult to apply the patch.\n\n>\n>> One caveat about the patch: there is a place where I cast a sha1 hash\n>> into a struct object_id pointer. This is because the abbreviation code\n>> still uses 'const unsigned char *' instead of structs. I wanted to avoid\n>> a hashcpy() in these calls, but perhaps that is not too heavy a cost.\n> I recall a discussion that there were alignment issues with doing this,\n> but I might have be remembering wrongly - in my limited knowledge of C\n> alignment, both \"unsigned char *\" and \"struct object_id *\" have the same\n> constraints, but I'm not sure.\n\nAdding Brian M. Carlson in the CC line for advice on how to do this \ntranslation between old sha1's and new object_ids. If it isn't safe, \nthen we could do a hashcpy() until the translation makes it unnecessary.\n\nI should have compared the two methods before sending the patch, but \nrunning the \"git log --oneline --parents\" test with a hashcpy() versus a \ncast has no measurable difference in performance for Linux. Probably \nbest to do the safest thing here if there is no cost to perf.\n\n>\n>> +\tconst unsigned char *index_fanout = p->index_data;\n> [snip]\n>> +\treturn bsearch_hash(oid->hash, (const uint32_t*)index_fanout,\n>> +\t\t\t index_lookup, index_lookup_width, result);\n> This cast to \"const uint32_t *\" is safe, because p->index_data points to\n> a mmap-ed region (which has very good alignment, as far as I know). I\n> wonder if we should document alignment guarantees on p->index_data, and\n> if yes, what guarantees to declare.\n\nThe existing application in find_pack_entry_one() [1] does similar \npack-index arithmetic before calling. A similar amount of arithmetic and \nalignment concerns appear in the commit-graph patch. Where is the right \nplace to declare these alignment requirements?\n\nIn v2, I'll have find_pack_entry_one() call bsearch_pack() so this logic \nis not duplicated.\n\nThanks,\n-Stolee\n\n[1] \nhttps://github.com/git/git/blob/c6284da4ff4afbde8211efe5d03f3604b1c6b9d6/packfile.c#L1721-L1749\n     find_pack_entry_one() in packfile.c\n"},{"id":"342482","messageId":"20180321224226.GA74743@genre.crustytoothpaste.net","threadId":"48100","inReplyTo":"3527bd3a-a899-a909-5fda-1d7abeb0e158@gmail.com","subject":"Re: [PATCH] sha1_name: use bsearch_hash() for abbreviations","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2018-03-21T22:42:26Z","receivedAt":"2018-03-21T22:42:38Z","isPatch":true,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On Wed, Mar 21, 2018 at 09:24:06AM -0400, Derrick Stolee wrote:\n> On 3/20/2018 6:25 PM, Jonathan Tan wrote:\n> > On Tue, 20 Mar 2018 16:03:25 -0400\n> > Derrick Stolee wrote:\n> > > One caveat about the patch: there is a place where I cast a sha1 hash\n> > > into a struct object_id pointer. This is because the abbreviation code\n> > > still uses 'const unsigned char *' instead of structs. I wanted to avoid\n> > > a hashcpy() in these calls, but perhaps that is not too heavy a cost.\n> > I recall a discussion that there were alignment issues with doing this,\n> > but I might have be remembering wrongly - in my limited knowledge of C\n> > alignment, both \"unsigned char *\" and \"struct object_id *\" have the same\n> > constraints, but I'm not sure.\n> \n> Adding Brian M. Carlson in the CC line for advice on how to do this\n> translation between old sha1's and new object_ids. If it isn't safe, then we\n> could do a hashcpy() until the translation makes it unnecessary.\n> \n> I should have compared the two methods before sending the patch, but running\n> the \"git log --oneline --parents\" test with a hashcpy() versus a cast has no\n> measurable difference in performance for Linux. Probably best to do the\n> safest thing here if there is no cost to perf.\n\nThere is no alignment difference. The alignment of struct object_id is\ngoing to be the same as the underlying hash. My concern in the past has\nbeen strict aliasing violations, which compilers can sometimes exploit\nto generate incorrect code.\n\nHowever, the bigger concern tends to be that when we switch to a new\nhash function, we may extend struct object_id with a hash type byte.\nThe current hash function transition plan certainly makes this a likely\nscenario. In such a case, a cast would end reading past the end of the\nunderlying array should we read the type byte.\n\nIf this isn't a performance critical path, I'd recommend simply making a\ncopy. I can clean up the definition of struct min_abbrev_data in a\nfuture series, or I can do something like the following on top of the\nlast series I sent, which is in next (only compile tested). If you're\nwilling to wait until it hits master, you can just drop the patch in.\n\n-- >8 --\nFrom 0000000000000000000000000000000000000000 Mon Sep 17 00:00:00 2001\nFrom: \"brian m. carlson\" \nDate: Wed, 21 Mar 2018 22:38:09 +0000\nSubject: [PATCH] sha1_name: convert struct min_abbrev_data to object_id\n\nThis structure is only written to in one place, where we already have a\nstruct object_id. Convert the struct to use a struct object_id instead.\n\nSigned-off-by: brian m. carlson \n---\n sha1_name.c | 6 +++---\n 1 file changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 39e911c8ba..16e0003396 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -480,7 +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+\tconst struct object_id *oid;\n };\n \n static inline char get_hex_char_from_oid(const struct object_id *oid,\n@@ -526,7 +526,7 @@ static void find_abbrev_len_for_pack(struct packed_git *p,\n \t\tint cmp;\n \n \t\tcurrent = nth_packed_object_sha1(p, mid);\n-\t\tcmp = hashcmp(mad->hash, current);\n+\t\tcmp = hashcmp(mad->oid->hash, current);\n \t\tif (!cmp) {\n \t\t\tmatch = 1;\n \t\t\tfirst = mid;\n@@ -603,7 +603,7 @@ int find_unique_abbrev_r(char *hex, const struct object_id *oid, int len)\n \tmad.init_len = len;\n \tmad.cur_len = len;\n \tmad.hex = hex;\n-\tmad.hash = oid->hash;\n+\tmad.oid = oid;\n \n \tfind_abbrev_len_packed(&mad);\n \n-- >8 --\n-- \nbrian m. carlson / brian with sandals: Houston, Texas, US\nhttps://www.crustytoothpaste.net/~bmc | My opinion only\nOpenPGP: https://keybase.io/bk2204\n"},{"id":"342527","messageId":"20180322174010.120117-1-dstolee@microsoft.com","threadId":"48100","inReplyTo":"20180321224226.GA74743@genre.crustytoothpaste.net","subject":"[PATCH v2 0/3] Use bsearch_hash() for abbreviations","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-03-22T17:40:07Z","receivedAt":"2018-03-22T17:40:33Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Thanks to Jonathan and Brian for the help with the proper way to handle\nOIDs and existing callers to bsearch_hash(). This patch includes one\ncommit that Brian sent in the previous discussion (included again here\nfor completeness).\n\nDerrick Stolee (2):\n packfile: define and use bsearch_pack()\n sha1_name: use bsearch_pack() for abbreviations\n\nbrian m. carlson (1):\n sha1_name: use bsearch_hash() for abbreviations\n\n packfile.c | 42 ++++++++++++++++++++++++++----------------\n packfile.h | 8 ++++++++\n sha1_name.c | 28 ++++++----------------------\n 3 files changed, 40 insertions(+), 38 deletions(-)\n\n\nbase-commit: 1a750441a7360b29fff7a414649ece1d35acaca6\n-- \n2.17.0.rc0\n\n"},{"id":"342528","messageId":"20180322174010.120117-3-dstolee@microsoft.com","threadId":"48100","inReplyTo":"20180322174010.120117-1-dstolee@microsoft.com","subject":"[PATCH v2 2/3] packfile: define and use bsearch_pack()","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-03-22T17:40:09Z","receivedAt":"2018-03-22T17:40:35Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"The method bsearch_hash() generalizes binary searches using a\nfanout table. The only consumer is currently find_pack_entry_one().\nIt requires a bit of pointer arithmetic to align the fanout table\nand the lookup table depending on the pack-index version.\n\nExtract the pack-index pointer arithmetic to a new method,\nbsearch_pack(), so this can be re-used in other code paths.\n\nSigned-off-by: Derrick Stolee \n---\n packfile.c | 42 ++++++++++++++++++++++++++----------------\n packfile.h | 8 ++++++++\n 2 files changed, 34 insertions(+), 16 deletions(-)\n\ndiff --git a/packfile.c b/packfile.c\nindex f26395ecab..69d3afda6c 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1654,6 +1654,29 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n \treturn data;\n }\n \n+int bsearch_pack(const struct object_id *oid, const struct packed_git *p, uint32_t *result)\n+{\n+\tconst unsigned char *index_fanout = p->index_data;\n+\tconst unsigned char *index_lookup;\n+\tint index_lookup_width;\n+\n+\tif (!index_fanout)\n+\t\tBUG(\"bsearch_pack called without a valid pack-index\");\n+\n+\tindex_lookup = index_fanout + 4 * 256;\n+\tif (p->index_version == 1) {\n+\t\tindex_lookup_width = 24;\n+\t\tindex_lookup += 4;\n+\t} else {\n+\t\tindex_lookup_width = 20;\n+\t\tindex_fanout += 8;\n+\t\tindex_lookup += 8;\n+\t}\n+\n+\treturn bsearch_hash(oid->hash, (const uint32_t*)index_fanout,\n+\t\t\t index_lookup, index_lookup_width, result);\n+}\n+\n const unsigned char *nth_packed_object_sha1(struct packed_git *p,\n \t\t\t\t\t uint32_t n)\n {\n@@ -1720,30 +1743,17 @@ off_t nth_packed_object_offset(const struct packed_git *p, uint32_t n)\n off_t find_pack_entry_one(const unsigned char *sha1,\n \t\t\t\t struct packed_git *p)\n {\n-\tconst uint32_t *level1_ofs = p->index_data;\n \tconst unsigned char *index = p->index_data;\n-\tunsigned stride;\n+\tstruct object_id oid;\n \tuint32_t result;\n \n \tif (!index) {\n \t\tif (open_pack_index(p))\n \t\t\treturn 0;\n-\t\tlevel1_ofs = p->index_data;\n-\t\tindex = p->index_data;\n-\t}\n-\tif (p->index_version > 1) {\n-\t\tlevel1_ofs += 2;\n-\t\tindex += 8;\n-\t}\n-\tindex += 4 * 256;\n-\tif (p->index_version > 1) {\n-\t\tstride = 20;\n-\t} else {\n-\t\tstride = 24;\n-\t\tindex += 4;\n \t}\n \n-\tif (bsearch_hash(sha1, level1_ofs, index, stride, &result))\n+\thashcpy(oid.hash, sha1);\n+\tif (bsearch_pack(&oid, p, &result))\n \t\treturn nth_packed_object_offset(p, result);\n \treturn 0;\n }\ndiff --git a/packfile.h b/packfile.h\nindex a7fca598d6..ec08cb2bb0 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -78,6 +78,14 @@ extern struct packed_git *add_packed_git(const char *path, size_t path_len, int\n */\n extern void check_pack_index_ptr(const struct packed_git *p, const void *ptr);\n \n+/*\n+ * Perform binary search on a pack-index for a given oid. Packfile is expected to\n+ * have a valid pack-index.\n+ *\n+ * See 'bsearch_hash' for more information.\n+ */\n+int bsearch_pack(const struct object_id *oid, const struct packed_git *p, uint32_t *result);\n+\n /*\n * Return the SHA-1 of the nth object within the specified packfile.\n * Open the index if it is not already open. The return value points\n-- \n2.17.0.rc0\n\n"},{"id":"342529","messageId":"20180322174010.120117-2-dstolee@microsoft.com","threadId":"48100","inReplyTo":"20180322174010.120117-1-dstolee@microsoft.com","subject":"[PATCH v2 1/3] sha1_name: convert struct min_abbrev_data to object_id","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-03-22T17:40:08Z","receivedAt":"2018-03-22T17:40:39Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: \"brian m. carlson\" \n\nThis structure is only written to in one place, where we already have a\nstruct object_id. Convert the struct to use a struct object_id instead.\n\nSigned-off-by: brian m. carlson \n---\n sha1_name.c | 6 +++---\n 1 file changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 39e911c8ba..16e0003396 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -480,7 +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+\tconst struct object_id *oid;\n };\n \n static inline char get_hex_char_from_oid(const struct object_id *oid,\n@@ -526,7 +526,7 @@ static void find_abbrev_len_for_pack(struct packed_git *p,\n \t\tint cmp;\n \n \t\tcurrent = nth_packed_object_sha1(p, mid);\n-\t\tcmp = hashcmp(mad->hash, current);\n+\t\tcmp = hashcmp(mad->oid->hash, current);\n \t\tif (!cmp) {\n \t\t\tmatch = 1;\n \t\t\tfirst = mid;\n@@ -603,7 +603,7 @@ int find_unique_abbrev_r(char *hex, const struct object_id *oid, int len)\n \tmad.init_len = len;\n \tmad.cur_len = len;\n \tmad.hex = hex;\n-\tmad.hash = oid->hash;\n+\tmad.oid = oid;\n \n \tfind_abbrev_len_packed(&mad);\n \n\nbase-commit: 1a750441a7360b29fff7a414649ece1d35acaca6\n-- \n2.17.0.rc0\n\n"},{"id":"342530","messageId":"20180322174010.120117-4-dstolee@microsoft.com","threadId":"48100","inReplyTo":"20180322174010.120117-1-dstolee@microsoft.com","subject":"[PATCH v2 3/3] sha1_name: use bsearch_pack() for abbreviations","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-03-22T17:40:10Z","receivedAt":"2018-03-22T17:40:43Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"When computing abbreviation lengths for an object ID against a single\npackfile, the method find_abbrev_len_for_pack() currently implements\nbinary search. This is one of several implementations. One issue with\nthis implementation is that it ignores the fanout table in the pack-\nindex.\n\nTranslate this binary search to use the existing bsearch_pack() method\nthat correctly uses a fanout table.\n\nDue to the use of the fanout table, the abbreviation computation is\nslightly faster than before. For a fully-repacked copy of the Linux\nrepo, the following 'git log' commands improved:\n\n* git log --oneline --parents --raw\n Before: 59.2s\n After: 56.9s\n Rel %: -3.8%\n\n* git log --oneline --parents\n Before: 6.48s\n After: 5.91s\n Rel %: -8.9%\n\nSigned-off-by: Derrick Stolee \n---\n sha1_name.c | 24 ++++--------------------\n 1 file changed, 4 insertions(+), 20 deletions(-)\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 16e0003396..24894b3dbe 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -512,32 +512,16 @@ 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+\tuint32_t num, first = 0;\n \tstruct object_id oid;\n+\tconst struct object_id *mad_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->oid->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+\tmad_oid = mad->oid;\n+\tmatch = bsearch_pack(mad_oid, p, &first);\n \n \t/*\n \t * first is now the position in the packfile where we would insert\n-- \n2.17.0.rc0\n\n"},{"id":"342824","messageId":"71b5cef0-abad-001f-6a23-3f2d874b9709@web.de","threadId":"48100","inReplyTo":"20180322174010.120117-1-dstolee@microsoft.com","subject":"[PATCH 4/3] sha1_name: use bsearch_pack() in unique_in_pack()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-03-24T16:41:08Z","receivedAt":"2018-03-24T16:41:26Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Replace the custom binary search in unique_in_pack() with a call to\nbsearch_pack(). This reduces code duplication and makes use of the\nfan-out table of packs.\n\nSigned-off-by: Rene Scharfe \n---\nThis is basically the same replacement as done by patch 3. Speed is\nless of a concern here -- at least I don't know a commonly used\ncommand that needs to resolve lots of short hashes.\n\n sha1_name.c | 21 ++-------------------\n 1 file changed, 2 insertions(+), 19 deletions(-)\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 24894b3dbe..0185c6081a 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -150,31 +150,14 @@ static int match_sha(unsigned len, const unsigned char *a, const unsigned char *\n static void unique_in_pack(struct packed_git *p,\n \t\t\t struct disambiguate_state *ds)\n {\n-\tuint32_t num, last, i, first = 0;\n+\tuint32_t num, i, first = 0;\n \tconst struct object_id *current = NULL;\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(ds->bin_pfx.hash, current);\n-\t\tif (!cmp) {\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+\tbsearch_pack(&ds->bin_pfx, p, &first);\n \n \t/*\n \t * At this point, \"first\" is the location of the lowest object\n-- \n2.16.3\n"},{"id":"342894","messageId":"xmqqvadkf7rd.fsf@gitster-ct.c.googlers.com","threadId":"48100","inReplyTo":"71b5cef0-abad-001f-6a23-3f2d874b9709@web.de","subject":"Re: [PATCH 4/3] sha1_name: use bsearch_pack() in unique_in_pack()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-03-25T16:19:02Z","receivedAt":"2018-03-25T16:19:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Replace the custom binary search in unique_in_pack() with a call to\n> bsearch_pack(). This reduces code duplication and makes use of the\n> fan-out table of packs.\n>\n> Signed-off-by: Rene Scharfe \n> ---\n> This is basically the same replacement as done by patch 3. Speed is\n> less of a concern here -- at least I don't know a commonly used\n> command that needs to resolve lots of short hashes.\n\nLooks correct. Did you find this by eyeballing, or do you have some\ninteresting tool you use?\n\n>\n> sha1_name.c | 21 ++-------------------\n> 1 file changed, 2 insertions(+), 19 deletions(-)\n>\n> diff --git a/sha1_name.c b/sha1_name.c\n> index 24894b3dbe..0185c6081a 100644\n> --- a/sha1_name.c\n> +++ b/sha1_name.c\n> @@ -150,31 +150,14 @@ static int match_sha(unsigned len, const unsigned char *a, const unsigned char *\n> static void unique_in_pack(struct packed_git *p,\n> \t\t\t struct disambiguate_state *ds)\n> {\n> -\tuint32_t num, last, i, first = 0;\n> +\tuint32_t num, i, first = 0;\n> \tconst struct object_id *current = NULL;\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(ds->bin_pfx.hash, current);\n> -\t\tif (!cmp) {\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> +\tbsearch_pack(&ds->bin_pfx, p, &first);\n> \n> \t/*\n> \t * At this point, \"first\" is the location of the lowest object\n"},{"id":"342897","messageId":"c56cd048-f0d1-3ed2-6e4e-5063d97071be@web.de","threadId":"48100","inReplyTo":"xmqqvadkf7rd.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 4/3] sha1_name: use bsearch_pack() in unique_in_pack()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-03-25T16:32:03Z","receivedAt":"2018-03-25T16:32:21Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 25.03.2018 um 18:19 schrieb Junio C Hamano:\n> René Scharfe writes:\n> \n>> Replace the custom binary search in unique_in_pack() with a call to\n>> bsearch_pack(). This reduces code duplication and makes use of the\n>> fan-out table of packs.\n>>\n>> Signed-off-by: Rene Scharfe \n>> ---\n>> This is basically the same replacement as done by patch 3. Speed is\n>> less of a concern here -- at least I don't know a commonly used\n>> command that needs to resolve lots of short hashes.\n> \n> Looks correct. Did you find this by eyeballing, or do you have some\n> interesting tool you use?\n\nI was looking for SHA1 binary searches using something like this:\n\n\tgit grep -e '/ 2' -e hashcmp -W --all-match\n\nRené\n"},{"id":"342917","messageId":"63f7e580-add1-2e5c-8720-c7982d993e00@gmail.com","threadId":"48100","inReplyTo":"71b5cef0-abad-001f-6a23-3f2d874b9709@web.de","subject":"Re: [PATCH 4/3] sha1_name: use bsearch_pack() in unique_in_pack()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-03-25T18:21:00Z","receivedAt":"2018-03-25T18:21:06Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/24/2018 12:41 PM, René Scharfe wrote:\n> Replace the custom binary search in unique_in_pack() with a call to\n> bsearch_pack(). This reduces code duplication and makes use of the\n> fan-out table of packs.\n>\n> Signed-off-by: Rene Scharfe \n> ---\n> This is basically the same replacement as done by patch 3. Speed is\n> less of a concern here -- at least I don't know a commonly used\n> command that needs to resolve lots of short hashes.\n\nThanks, René! Good teamwork on this patch series.\n\nReviewed-by: Derrick Stolee \n"}]}