{"thread":{"id":"46826","subject":"[PATCH v2 0/5] Improve abbreviation disambiguation","startedAt":"2017-09-25T09:55:27Z","lastAt":"2017-10-09T13:33:26Z","messageCount":47,"participants":["Derrick Stolee","Stefan Beller","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":2,"patchTotal":5},"messages":[{"id":"328826","messageId":"20170925095452.66833-1-dstolee@microsoft.com","threadId":"46826","inReplyTo":null,"subject":"[PATCH v2 0/5] Improve abbreviation disambiguation","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-09-25T09:54:47Z","receivedAt":"2017-09-25T09:55:27Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Thanks for the feedback on my v1 patch. Thanks also to Jeff Hostetler\nfor helping me with this v2 patch, which includes an extra performance\nimprovement in commit 5.\n\nChanges since last version:\n\n* Added helper program test-list-objects to construct a list of\n existing object ids.\n\n* test-abbrev now disambiguates a list of OIDs from stdin.\n\n* p0008-abbrev.sh now has two tests:\n * 0008.1 tests 100,000 known OIDs\n * 0008.2 tests 100,000 missing OIDs\n\n* Added a third performance improvement that uses binary search within\n packfiles to inspect at most two object ids per packfile.\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\nA helper program `test-list-objects` outputs a sampling of object ids,\nwhich we reorder using `sort -R` before using them as input to a\nperformance test. \n\nA performance helper `test-abbrev` and performance test `p0008-abbrev.sh`\nare added to demonstrate performance improvements in this area.\n\nI include performance test numbers in the commit messages for each\nchange, but I also include the difference between the baseline and the\nfinal change here:\n\n\np0008.1: find_unique_abbrev() for existing objects\n--------------------------------------------------\n\nFor 10 repeated tests, each checking 100,000 known objects, we find the\nfollowing results when running in a Linux VM:\n\n| | Pack | Packed | Loose | Base | New | |\n| Repo | Files | Objects | Objects| Time | Time | Rel% |\n|-------|-------|---------|--------|--------|--------|--------|\n| Git | 1 | 230078 | 0 | 0.12 s | 0.05 s | -58.3% |\n| Git | 5 | 230162 | 0 | 0.25 s | 0.15 s | -40.0% |\n| Git | 4 | 154310 | 75852 | 0.18 s | 0.11 s | -38.9% |\n| Linux | 1 | 5606645 | 0 | 0.32 s | 0.10 s | -68.8% |\n| Linux | 24 | 5606645 | 0 | 2.77 s | 2.00 s | -27.8% |\n| Linux | 23 | 5283204 | 323441 | 2.86 s | 1.62 s | -43.4% |\n| VSTS | 1 | 4355923 | 0 | 0.27 s | 0.09 s | -66.7% |\n| VSTS | 32 | 4355923 | 0 | 2.41 s | 2.01 s | -16.6% |\n| VSTS | 31 | 4276829 | 79094 | 4.22 s | 3.02 s | -28.4% |\n\nFor the Windows repo running in Windows Subsystem for Linux:\n\n Pack Files: 50\nPacked Objects: 22,385,898\n Loose Objects: 492\n Base Time: 5.69 s\n New Time: 4.09 s\n Rel %: -28.1%\n\np0008.2: find_unique_abbrev() for missing objects\n-------------------------------------------------\n\nFor 10 repeated tests, each checking 100,000 missing objects, we find\nthe following results when running in a Linux VM:\n\n| | Pack | Packed | Loose | Base | New | |\n| Repo | Files | Objects | Objects| Time | Time | Rel% |\n|-------|-------|---------|--------|--------|--------|--------|\n| Git | 1 | 230078 | 0 | 0.61 s | 0.04 s | -93.4% |\n| Git | 5 | 230162 | 0 | 1.30 s | 0.15 s | -88.5% |\n| Git | 4 | 154310 | 75852 | 1.07 s | 0.12 s | -88.8% |\n| Linux | 1 | 5606645 | 0 | 0.65 s | 0.05 s | -92.3% |\n| Linux | 24 | 5606645 | 0 | 7.12 s | 1.28 s | -82.0% |\n| Linux | 23 | 5283204 | 323441 | 6.33 s | 0.96 s | -84.8% |\n| VSTS | 1 | 4355923 | 0 | 0.64 s | 0.05 s | -92.2% |\n| VSTS | 32 | 4355923 | 0 | 7.77 s | 1.36 s | -82.5% |\n| VSTS | 31 | 4276829 | 79094 | 7.76 s | 1.36 s | -82.5% |\n\nFor the Windows repo running in Windows Subsystem for Linux:\n\n Pack Files: 50\nPacked Objects: 22,385,898\n Loose Objects: 492\n Base Time: 38.9 s\n New Time: 2.7 s\n Rel %: -93.1%\n\nDerrick Stolee (5):\n test-list-objects: List a subset of object ids\n p0008-abbrev.sh: Test find_unique_abbrev() perf\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 Makefile | 2 +\n sha1_name.c | 128 ++++++++++++++++++++++++++++++++++++++-----\n t/helper/.gitignore | 2 +\n t/helper/test-abbrev.c | 19 +++++++\n t/helper/test-list-objects.c | 85 ++++++++++++++++++++++++++++\n t/perf/p0008-abbrev.sh | 22 ++++++++\n 6 files changed, 243 insertions(+), 15 deletions(-)\n create mode 100644 t/helper/test-abbrev.c\n create mode 100644 t/helper/test-list-objects.c\n create mode 100755 t/perf/p0008-abbrev.sh\n\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"328827","messageId":"20170925095452.66833-3-dstolee@microsoft.com","threadId":"46826","inReplyTo":"20170925095452.66833-1-dstolee@microsoft.com","subject":"[PATCH v2 2/5] p0008-abbrev.sh: Test find_unique_abbrev() perf","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-09-25T09:54:49Z","receivedAt":"2017-09-25T09:55:30Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Create helper program test-abbrev to compute the minimum length of a\ndisambiguating short-sha for an input list of object ids.\n\nPerf test p0008-abbrev.sh runs test-abbrev for 100,000 object ids. For\ntest 0008.1, these objects exist. For test 0008.2 these objects do not\nexist in the repo (with high probability). For each test, use `sort -R`\nto (deterministically) shuffle the sample of object ids to not check\nabbreviations in lexicographic order.\n\nSigned-off-by: Derrick Stolee \n---\n Makefile | 1 +\n t/helper/.gitignore | 1 +\n t/helper/test-abbrev.c | 19 +++++++++++++++++++\n t/perf/p0008-abbrev.sh | 22 ++++++++++++++++++++++\n 4 files changed, 43 insertions(+)\n create mode 100644 t/helper/test-abbrev.c\n create mode 100755 t/perf/p0008-abbrev.sh\n\ndiff --git a/Makefile b/Makefile\nindex af94b655a..75835c7c0 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -633,6 +633,7 @@ X =\n \n PROGRAMS += $(patsubst %.o,git-%$X,$(PROGRAM_OBJS))\n \n+TEST_PROGRAMS_NEED_X += test-abbrev\n TEST_PROGRAMS_NEED_X += test-chmtime\n TEST_PROGRAMS_NEED_X += test-ctype\n TEST_PROGRAMS_NEED_X += test-config\ndiff --git a/t/helper/.gitignore b/t/helper/.gitignore\nindex 9dd1c9f3c..ab9df8369 100644\n--- a/t/helper/.gitignore\n+++ b/t/helper/.gitignore\n@@ -1,3 +1,4 @@\n+/test-abbrev\n /test-chmtime\n /test-ctype\n /test-config\ndiff --git a/t/helper/test-abbrev.c b/t/helper/test-abbrev.c\nnew file mode 100644\nindex 000000000..6866896eb\n--- /dev/null\n+++ b/t/helper/test-abbrev.c\n@@ -0,0 +1,19 @@\n+#include \"cache.h\"\n+#include \n+\n+int cmd_main(int ac, const char **av)\n+{\n+\tstruct object_id oid;\n+\tchar hex[GIT_MAX_HEXSZ + 2];\n+\tconst char *end;\n+\n+\tsetup_git_directory();\n+\n+\twhile (fgets(hex, GIT_MAX_HEXSZ + 2, stdin)) {\n+\t\thex[GIT_MAX_HEXSZ] = 0;\n+\t\tif (!parse_oid_hex(hex, &oid, &end))\n+\t\t\tfind_unique_abbrev(oid.hash, MINIMUM_ABBREV);\n+\t}\n+\n+\texit(0);\n+}\ndiff --git a/t/perf/p0008-abbrev.sh b/t/perf/p0008-abbrev.sh\nnew file mode 100755\nindex 000000000..ba25e7824\n--- /dev/null\n+++ b/t/perf/p0008-abbrev.sh\n@@ -0,0 +1,22 @@\n+#!/bin/bash\n+\n+test_description='Test object disambiguation through abbreviations'\n+. ./perf-lib.sh\n+\n+test_perf_large_repo\n+\n+test-list-objects 100000 | sort -R > objs.txt\n+\n+test_perf 'find_unique_abbrev() for existing objects' '\n+\ttest-abbrev < objs.txt\n+'\n+\n+test-list-objects 100000 --missing | sort -R > objs.txt\n+\n+test_perf 'find_unique_abbrev() for missing objects' '\n+\ttest-abbrev < objs.txt\n+'\n+\n+rm objs.txt\n+\n+test_done\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"328828","messageId":"20170925095452.66833-6-dstolee@microsoft.com","threadId":"46826","inReplyTo":"20170925095452.66833-1-dstolee@microsoft.com","subject":"[PATCH v2 5/5] sha1_name: Minimize OID comparisons during disambiguation","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-09-25T09:54:52Z","receivedAt":"2017-09-25T09:55:34Z","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\np0008.1: find_unique_abbrev() for existing objects\n--------------------------------------------------\n\nFor 10 repeated tests, each checking 100,000 known objects, we find the\nfollowing results when running in a Linux VM:\n\n| | Pack | Packed | Loose | Base | New | |\n| Repo | Files | Objects | Objects| Time | Time | Rel% |\n|-------|-------|---------|--------|--------|--------|--------|\n| Git | 1 | 230078 | 0 | 0.08 s | 0.05 s | -37.5% |\n| Git | 5 | 230162 | 0 | 0.16 s | 0.15 s | - 6.3% |\n| Git | 4 | 154310 | 75852 | 0.12 s | 0.11 s | - 8.3% |\n| Linux | 1 | 5606645 | 0 | 0.25 s | 0.10 s | -60.0% |\n| Linux | 24 | 5606645 | 0 | 2.08 s | 2.00 s | - 3.8% |\n| Linux | 23 | 5283204 | 323441 | 1.69 s | 1.62 s | - 4.1% |\n| VSTS | 1 | 4355923 | 0 | 0.22 s | 0.09 s | -59.1% |\n| VSTS | 32 | 4355923 | 0 | 1.99 s | 2.01 s | + 1.0% |\n| VSTS | 31 | 4276829 | 79094 | 3.20 s | 3.02 s | - 5.6% |\n\nFor the Windows repo running in Windows Subsystem for Linux:\n\n Pack Files: 50\nPacked Objects: 22,385,898\n Loose Objects: 492\n Base Time: 4.62 s\n New Time: 4.09 s\n Rel %: -11.5%\n\np0008.2: find_unique_abbrev() for missing objects\n-------------------------------------------------\n\nFor 10 repeated tests, each checking 100,000 missing objects, we find\nthe following results when running in a Linux VM:\n\n| | Pack | Packed | Loose | Base | New | |\n| Repo | Files | Objects | Objects| Time | Time | Rel% |\n|-------|-------|---------|--------|--------|--------|--------|\n| Git | 1 | 230078 | 0 | 0.05 s | 0.04 s | -20.0% |\n| Git | 5 | 230162 | 0 | 0.15 s | 0.15 s | 0.0% |\n| Git | 4 | 154310 | 75852 | 0.12 s | 0.12 s | 0.0% |\n| Linux | 1 | 5606645 | 0 | 0.17 s | 0.05 s | -70.6% |\n| Linux | 24 | 5606645 | 0 | 1.30 s | 1.28 s | - 1.5% |\n| Linux | 23 | 5283204 | 323441 | 1.10 s | 0.96 s | -12.7% |\n| VSTS | 1 | 4355923 | 0 | 0.12 s | 0.05 s | -58.3% |\n| VSTS | 32 | 4355923 | 0 | 1.34 s | 1.36 s | + 1.5% |\n| VSTS | 31 | 4276829 | 79094 | 1.34 s | 1.36 s | + 1.5% |\n\nFor the Windows repo running in Windows Subsystem for Linux:\n\n Pack Files: 50\nPacked Objects: 22,385,898\n Loose Objects: 492\n Base Time: 3.08 s\n New Time: 2.72 s\n Rel %: -11.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 bb47b6702..1566cd4fc 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, int i)\n@@ -504,6 +505,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) / 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@@ -535,19 +595,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":"328829","messageId":"20170925095452.66833-2-dstolee@microsoft.com","threadId":"46826","inReplyTo":"20170925095452.66833-1-dstolee@microsoft.com","subject":"[PATCH v2 1/5] test-list-objects: List a subset of object ids","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-09-25T09:54:48Z","receivedAt":"2017-09-25T09:55:49Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Create test-list-objects helper program to output a random sample of\nOIDs present in the repo.\n\nIf no command line arguments are provided, all OIDs are output.\n\nThe first command line argument specifies how many samples to output.\nSamples are collected across the entire set of available OIDs to avoid\nclustering and therefore quite uniformly distributed.\n\nIf a second command line argument \"--missing\" is given, then a list of\nOIDs is generated without examining the repo.\n\nSigned-off-by: Derrick Stolee \n---\n Makefile | 1 +\n t/helper/.gitignore | 1 +\n t/helper/test-list-objects.c | 85 ++++++++++++++++++++++++++++++++++++++++++++\n 3 files changed, 87 insertions(+)\n create mode 100644 t/helper/test-list-objects.c\n\ndiff --git a/Makefile b/Makefile\nindex f2bb7f2f6..af94b655a 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -647,6 +647,7 @@ TEST_PROGRAMS_NEED_X += test-hashmap\n TEST_PROGRAMS_NEED_X += test-index-version\n TEST_PROGRAMS_NEED_X += test-lazy-init-name-hash\n TEST_PROGRAMS_NEED_X += test-line-buffer\n+TEST_PROGRAMS_NEED_X += test-list-objects\n TEST_PROGRAMS_NEED_X += test-match-trees\n TEST_PROGRAMS_NEED_X += test-mergesort\n TEST_PROGRAMS_NEED_X += test-mktemp\ndiff --git a/t/helper/.gitignore b/t/helper/.gitignore\nindex 721650256..9dd1c9f3c 100644\n--- a/t/helper/.gitignore\n+++ b/t/helper/.gitignore\n@@ -13,6 +13,7 @@\n /test-index-version\n /test-lazy-init-name-hash\n /test-line-buffer\n+/test-list-objects\n /test-match-trees\n /test-mergesort\n /test-mktemp\ndiff --git a/t/helper/test-list-objects.c b/t/helper/test-list-objects.c\nnew file mode 100644\nindex 000000000..83b1250fe\n--- /dev/null\n+++ b/t/helper/test-list-objects.c\n@@ -0,0 +1,85 @@\n+#include \"cache.h\"\n+#include \"packfile.h\"\n+#include \n+\n+struct count {\n+\tint total;\n+\tint select_mod;\n+};\n+\n+int count_loose(const struct object_id *oid,\n+\t\tconst char *path,\n+\t\tvoid *data)\n+{\n+\t((struct count*)data)->total++;\n+\treturn 0;\n+}\n+\n+int count_packed(const struct object_id *oid,\n+\t\t struct packed_git *pack,\n+\t\t uint32_t pos,\n+\t\t void* data)\n+{\n+\t((struct count*)data)->total++;\n+\treturn 0;\n+}\n+\n+void output(const struct object_id *oid,\n+\t struct count *c)\n+{\n+\tif (!(c->total % c->select_mod))\n+\t\tprintf(\"%s\\n\", oid_to_hex(oid));\n+\tc->total--;\n+}\n+\n+int output_loose(const struct object_id *oid,\n+\t\t const char *path,\n+\t\t void *data)\n+{\n+\toutput(oid, (struct count*)data);\n+\treturn 0;\n+}\n+\n+int output_packed(const struct object_id *oid,\n+\t\t struct packed_git *pack,\n+\t\t uint32_t pos,\n+\t\t void* data)\n+{\n+\toutput(oid, (struct count*)data);\n+\treturn 0;\n+}\n+\n+int cmd_main(int ac, const char **av)\n+{\n+\tunsigned int hash_delt = 0xFDB97531;\n+\tunsigned int hash_base = 0x01020304;\n+\tint i, n = 0;\n+\tstruct count c;\n+\tconst int u_per_oid = sizeof(struct object_id) / sizeof(unsigned int);\n+\n+\tc.total = 0;\n+\tif (ac > 1)\n+\t\tn = atoi(av[1]);\n+\n+\tif (ac > 2 && !strcmp(av[2], \"--missing\")) {\n+\t\twhile (c.total++ < n) {\n+\t\t\tfor (i = 0; i < u_per_oid; i++) {\n+\t\t\t\tprintf(\"%08x\", hash_base);\n+\t\t\t\thash_base += hash_delt;\n+\t\t\t}\n+\t\t\tprintf(\"\\n\");\n+\t\t}\n+\t} else {\n+\t\tsetup_git_directory();\n+\n+\t\tfor_each_loose_object(count_loose, &c, 0);\n+\t\tfor_each_packed_object(count_packed, &c, 0);\n+\n+\t\tc.select_mod = 1 + c.total / n;\n+\n+\t\tfor_each_loose_object(output_loose, &c, 0);\n+\t\tfor_each_packed_object(output_packed, &c, 0);\n+\t}\n+\n+\texit(0);\n+}\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"328830","messageId":"20170925095452.66833-5-dstolee@microsoft.com","threadId":"46826","inReplyTo":"20170925095452.66833-1-dstolee@microsoft.com","subject":"[PATCH v2 4/5] sha1_name: Parse less while finding common prefix","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-09-25T09:54:51Z","receivedAt":"2017-09-25T09:55: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\np0008.1: find_unique_abbrev() for existing objects\n--------------------------------------------------\n\nFor 10 repeated tests, each checking 100,000 known objects, we find the\nfollowing results when running in a Linux VM:\n\n| | Pack | Packed | Loose | Base | New | |\n| Repo | Files | Objects | Objects| Time | Time | Rel% |\n|-------|-------|---------|--------|--------|--------|--------|\n| Git | 1 | 230078 | 0 | 0.08 s | 0.08 s | 0.0% |\n| Git | 5 | 230162 | 0 | 0.17 s | 0.16 s | - 5.9% |\n| Git | 4 | 154310 | 75852 | 0.14 s | 0.12 s | -14.3% |\n| Linux | 1 | 5606645 | 0 | 0.50 s | 0.25 s | -50.0% |\n| Linux | 24 | 5606645 | 0 | 2.41 s | 2.08 s | -13.7% |\n| Linux | 23 | 5283204 | 323441 | 1.99 s | 1.69 s | -15.1% |\n| VSTS | 1 | 4355923 | 0 | 0.40 s | 0.22 s | -45.0% |\n| VSTS | 32 | 4355923 | 0 | 2.09 s | 1.99 s | - 4.8% |\n| VSTS | 31 | 4276829 | 79094 | 3.60 s | 3.20 s | -11.1% |\n\nFor the Windows repo running in Windows Subsystem for Linux:\n\n Pack Files: 50\nPacked Objects: 22,385,898\n Loose Objects: 492\n Base Time: 4.61 s\n New Time: 4.61 s\n Rel %: 0.0%\n\np0008.2: find_unique_abbrev() for missing objects\n-------------------------------------------------\n\nFor 10 repeated tests, each checking 100,000 missing objects, we find\nthe following results when running in a Linux VM:\n\n| | Pack | Packed | Loose | Base | New | |\n| Repo | Files | Objects | Objects| Time | Time | Rel% |\n|-------|-------|---------|--------|--------|--------|--------|\n| Git | 1 | 230078 | 0 | 0.06 s | 0.05 s | -16.7% |\n| Git | 5 | 230162 | 0 | 0.14 s | 0.15 s | + 7.1% |\n| Git | 4 | 154310 | 75852 | 0.12 s | 0.12 s | 0.0% |\n| Linux | 1 | 5606645 | 0 | 0.40 s | 0.17 s | -57.5% |\n| Linux | 24 | 5606645 | 0 | 1.59 s | 1.30 s | -18.2% |\n| Linux | 23 | 5283204 | 323441 | 1.23 s | 1.10 s | -10.6% |\n| VSTS | 1 | 4355923 | 0 | 0.25 s | 0.12 s | -52.0% |\n| VSTS | 32 | 4355923 | 0 | 1.45 s | 1.34 s | - 7.6% |\n| VSTS | 31 | 4276829 | 79094 | 1.59 s | 1.34 s | -15.7% |\n\nFor the Windows repo running in Windows Subsystem for Linux:\n\n Pack Files: 50\nPacked Objects: 22,385,898\n Loose Objects: 492\n Base Time: 3.91 s\n New Time: 3.08 s\n Rel %: -21.1%\n\nSigned-off-by: Derrick Stolee \n\nSigned-off-by: Derrick Stolee \n---\n sha1_name.c | 13 +++++++++++--\n 1 file changed, 11 insertions(+), 2 deletions(-)\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex f2a1ebe49..bb47b6702 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -480,13 +480,22 @@ struct min_abbrev_data {\n \tchar *hex;\n };\n \n+static inline char get_hex_char_from_oid(const struct object_id *oid, int i)\n+{\n+\tstatic const char hex[] = \"0123456789abcdef\";\n+\n+\tif ((i & 1) == 0)\n+\t\treturn hex[oid->hash[i >> 1] >> 4];\n+\telse\n+\t\treturn hex[oid->hash[i >> 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":"328831","messageId":"20170925095452.66833-4-dstolee@microsoft.com","threadId":"46826","inReplyTo":"20170925095452.66833-1-dstolee@microsoft.com","subject":"[PATCH v2 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-09-25T09:54:50Z","receivedAt":"2017-09-25T09:55:54Z","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\np0008.1: find_unique_abbrev() for existing objects\n--------------------------------------------------\n\nFor 10 repeated tests, each checking 100,000 known objects, we find the\nfollowing results when running in a Linux VM:\n\n| | Pack | Packed | Loose | Base | New | |\n| Repo | Files | Objects | Objects| Time | Time | Rel% |\n|-------|-------|---------|--------|--------|--------|--------|\n| Git | 1 | 230078 | 0 | 0.12 s | 0.08 s | -33.3% |\n| Git | 5 | 230162 | 0 | 0.25 s | 0.17 s | -32.0% |\n| Git | 4 | 154310 | 75852 | 0.18 s | 0.14 s | -22.2% |\n| Linux | 1 | 5606645 | 0 | 0.32 s | 0.50 s | +56.2% |\n| Linux | 24 | 5606645 | 0 | 2.77 s | 2.41 s | -13.0% |\n| Linux | 23 | 5283204 | 323441 | 2.86 s | 1.99 s | -30.4% |\n| VSTS | 1 | 4355923 | 0 | 0.27 s | 0.40 s | +48.1% |\n| VSTS | 32 | 4355923 | 0 | 2.41 s | 2.09 s | -13.3% |\n| VSTS | 31 | 4276829 | 79094 | 4.22 s | 3.60 s | -14.7% |\n\nFor the Windows repo running in Windows Subsystem for Linux:\n\n Pack Files: 50\nPacked Objects: 22,385,898\n Loose Objects: 492\n Base Time: 5.69 s\n New Time: 4.62 s\n Rel %: -18.9%\n\np0008.2: find_unique_abbrev() for missing objects\n-------------------------------------------------\n\nFor 10 repeated tests, each checking 100,000 missing objects, we find\nthe following results when running in a Linux VM:\n\n| | Pack | Packed | Loose | Base | New | |\n| Repo | Files | Objects | Objects| Time | Time | Rel% |\n|-------|-------|---------|--------|--------|--------|--------|\n| Git | 1 | 230078 | 0 | 0.61 s | 0.06 s | -90.2% |\n| Git | 5 | 230162 | 0 | 1.30 s | 0.14 s | -89.2% |\n| Git | 4 | 154310 | 75852 | 1.07 s | 0.12 s | -88.8% |\n| Linux | 1 | 5606645 | 0 | 0.65 s | 0.40 s | -38.5% |\n| Linux | 24 | 5606645 | 0 | 7.12 s | 1.59 s | -77.7% |\n| Linux | 23 | 5283204 | 323441 | 6.33 s | 1.23 s | -80.6% |\n| VSTS | 1 | 4355923 | 0 | 0.64 s | 0.25 s | -60.9% |\n| VSTS | 32 | 4355923 | 0 | 7.77 s | 1.45 s | -81.3% |\n| VSTS | 31 | 4276829 | 79094 | 7.76 s | 1.59 s | -79.5% |\n\nFor the Windows repo running in Windows Subsystem for Linux:\n\n Pack Files: 50\nPacked Objects: 22,385,898\n Loose Objects: 492\n Base Time: 39.0 s\n New Time: 3.9 s\n Rel %: -90.0%\n\nSigned-off-by: Derrick Stolee \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":"328900","messageId":"CAGZ79kaBGtgBv2OryCO+oc-0nvSyi0vXA2jsLS2=5Xweea1SNg@mail.gmail.com","threadId":"46826","inReplyTo":"20170925095452.66833-5-dstolee@microsoft.com","subject":"Re: [PATCH v2 4/5] sha1_name: Parse less while finding common prefix","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-09-25T23:42:03Z","receivedAt":"2017-09-25T23:42:09Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Mon, Sep 25, 2017 at 2:54 AM, Derrick Stolee wrote:\n> Create get_hex_char_from_oid() to parse oids one hex character at a\n> time. This prevents unnecessary copying of hex characters in\n> extend_abbrev_len() when finding the length of a common prefix.\n>\n> p0008.1: find_unique_abbrev() for existing objects\n> --------------------------------------------------\n>\n> For 10 repeated tests, each checking 100,000 known objects, we find the\n> following results when running in a Linux VM:\n>\n> | | Pack | Packed | Loose | Base | New | |\n> | Repo | Files | Objects | Objects| Time | Time | Rel% |\n> |-------|-------|---------|--------|--------|--------|--------|\n> | Git | 1 | 230078 | 0 | 0.08 s | 0.08 s | 0.0% |\n> | Git | 5 | 230162 | 0 | 0.17 s | 0.16 s | - 5.9% |\n> | Git | 4 | 154310 | 75852 | 0.14 s | 0.12 s | -14.3% |\n> | Linux | 1 | 5606645 | 0 | 0.50 s | 0.25 s | -50.0% |\n> | Linux | 24 | 5606645 | 0 | 2.41 s | 2.08 s | -13.7% |\n> | Linux | 23 | 5283204 | 323441 | 1.99 s | 1.69 s | -15.1% |\n> | VSTS | 1 | 4355923 | 0 | 0.40 s | 0.22 s | -45.0% |\n> | VSTS | 32 | 4355923 | 0 | 2.09 s | 1.99 s | - 4.8% |\n> | VSTS | 31 | 4276829 | 79094 | 3.60 s | 3.20 s | -11.1% |\n>\n> For the Windows repo running in Windows Subsystem for Linux:\n>\n> Pack Files: 50\n> Packed Objects: 22,385,898\n> Loose Objects: 492\n> Base Time: 4.61 s\n> New Time: 4.61 s\n> Rel %: 0.0%\n>\n> p0008.2: find_unique_abbrev() for missing objects\n> -------------------------------------------------\n>\n> For 10 repeated tests, each checking 100,000 missing objects, we find\n> the following results when running in a Linux VM:\n>\n> | | Pack | Packed | Loose | Base | New | |\n> | Repo | Files | Objects | Objects| Time | Time | Rel% |\n> |-------|-------|---------|--------|--------|--------|--------|\n> | Git | 1 | 230078 | 0 | 0.06 s | 0.05 s | -16.7% |\n> | Git | 5 | 230162 | 0 | 0.14 s | 0.15 s | + 7.1% |\n> | Git | 4 | 154310 | 75852 | 0.12 s | 0.12 s | 0.0% |\n> | Linux | 1 | 5606645 | 0 | 0.40 s | 0.17 s | -57.5% |\n> | Linux | 24 | 5606645 | 0 | 1.59 s | 1.30 s | -18.2% |\n> | Linux | 23 | 5283204 | 323441 | 1.23 s | 1.10 s | -10.6% |\n> | VSTS | 1 | 4355923 | 0 | 0.25 s | 0.12 s | -52.0% |\n> | VSTS | 32 | 4355923 | 0 | 1.45 s | 1.34 s | - 7.6% |\n> | VSTS | 31 | 4276829 | 79094 | 1.59 s | 1.34 s | -15.7% |\n>\n> For the Windows repo running in Windows Subsystem for Linux:\n>\n> Pack Files: 50\n> Packed Objects: 22,385,898\n> Loose Objects: 492\n> Base Time: 3.91 s\n> New Time: 3.08 s\n> Rel %: -21.1%\n>\n\nThese number look pretty cool!\n\n> Signed-off-by: Derrick Stolee \n>\n> Signed-off-by: Derrick Stolee \n\ndouble signoff?\n\n> ---\n> sha1_name.c | 13 +++++++++++--\n> 1 file changed, 11 insertions(+), 2 deletions(-)\n>\n> diff --git a/sha1_name.c b/sha1_name.c\n> index f2a1ebe49..bb47b6702 100644\n> --- a/sha1_name.c\n> +++ b/sha1_name.c\n> @@ -480,13 +480,22 @@ struct min_abbrev_data {\n> char *hex;\n> };\n>\n> +static inline char get_hex_char_from_oid(const struct object_id *oid, int i)\n\n'i' is not very descriptive, maybe add a comment?\n(I realize it is just walking through the char*s one by one)\n\nMaybe this function (together with the change in the while below)\ncould go into hex.c as \"int progressively_cmp_oids\" that returns\nthe position at which the given oids differ?\n\n> +{\n> + static const char hex[] = \"0123456789abcdef\";\n> +\n> + if ((i & 1) == 0)\n> + return hex[oid->hash[i >> 1] >> 4];\n> + else\n> + return hex[oid->hash[i >> 1] & 0xf];\n> +}\n\nsha1_to_hex_r has very similar code, though it iterates less\nand covers both cases in the loop body.\n\nThat is the actual reason I propose moving this function\n(or a variant thereof) to hex.c as there we can share code.\n"},{"id":"328934","messageId":"xmqqd16dak2s.fsf@gitster.mtv.corp.google.com","threadId":"46826","inReplyTo":"20170925095452.66833-2-dstolee@microsoft.com","subject":"Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-09-26T09:24:43Z","receivedAt":"2017-09-26T09:24:56Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> diff --git a/t/helper/test-list-objects.c b/t/helper/test-list-objects.c\n> new file mode 100644\n> index 000000000..83b1250fe\n> --- /dev/null\n> +++ b/t/helper/test-list-objects.c\n> @@ -0,0 +1,85 @@\n> +#include \"cache.h\"\n> +#include \"packfile.h\"\n> +#include \n\nIf you include \"cache.h\", like the ordinary \"git\" program, you\nshould not have to include any system headers like stdio.h\nyourself. The whole point of \"git-compat-util.h must be the first\nto be included (indirectly including it via cache.h and friends is\nalso OK)\" rule is to make sure that system headers are included at\nthe right place in the include sequence (e.g. defining feature\nmacros before including certain headers, etc.).\n\n> +int cmd_main(int ac, const char **av)\n> +{\n> +\tunsigned int hash_delt = 0xFDB97531;\n> +\tunsigned int hash_base = 0x01020304;\n> +...\n> +\tconst int u_per_oid = sizeof(struct object_id) / sizeof(unsigned int);\n\nBecause the above will not work as you expect, unless your uint is\n32-bit, you would probably want to make hash_delt and hash_base\nexplicitly uint32_t, I think.\n\nAlternatively, because you assume that uint is at least 8-hex-digit\nwide in the output loop, you can keep \"unsigned int\" above, but\nchange the divisor from sizeof(unsigned int) to a hardcoded 4.\n\nEither would fix the issue.\n\n> +\tc.total = 0;\n> +\tif (ac > 1)\n> +\t\tn = atoi(av[1]);\n\nOtherwise n will stay 0 as initialized. Not checking the result of\natoi() is probably permissible, as this is merely a test helper and\nwe can assume that the caller will not do anything silly, like\npassing \"-3\" in av[1]. But it certainly would be a good discipline\nto make sure av[1] is a reasonable number.\n\nI am afraid that I may be misreading the code, but the following\ncode seems to require that the caller must know roughly how many\nobjects there are (so that a large-enough value can be passed to\nav[1] to force c.select_mod to 1) when it wants to show everything,\nas the \"missing\" loop will run 0 times showing nothing, and\n\"listing\" case will divide by zero.\n\n\"Not passing anything will show everything\" the proposed log message\npromises is a better design than what the code actually seems to be\ndoing.\n\n> +\n> +\tif (ac > 2 && !strcmp(av[2], \"--missing\")) {\n> +\t\twhile (c.total++ < n) {\n\nWhen n==0, this does nothing. I am not sure what the desired\nbehaviour should be for \"When no count is given, we show everything\"\nin this codepath, though.\n\nAlso, doesn't \"test-list-objects 5 --missing\" look very wrong?\nShouldn't it be more like \"test-list-objects --missing 5\"?\n\n> +\t\t\tfor (i = 0; i < u_per_oid; i++) {\n> +\t\t\t\tprintf(\"%08x\", hash_base);\n> +\t\t\t\thash_base += hash_delt;\n> +\t\t\t}\n> +\t\t\tprintf(\"\\n\");\n> +\t\t}\n> +\t} else {\n> +\t\tsetup_git_directory();\n> +\n> +\t\tfor_each_loose_object(count_loose, &c, 0);\n> +\t\tfor_each_packed_object(count_packed, &c, 0);\n> +\n> +\t\tc.select_mod = 1 + c.total / n;\n\nWhen n==0, this would divide by zero.\nPerhaps\n\n\t\tc.select_mod = n ? (1 + c.total / n) : 1;\n\nor something to keep the promise of showing everything?\n\n> +\t\tfor_each_loose_object(output_loose, &c, 0);\n> +\t\tfor_each_packed_object(output_packed, &c, 0);\n> +\t}\n> +\n> +\texit(0);\n> +}\n\nThanks.\n"},{"id":"328935","messageId":"xmqq8th1ajy9.fsf@gitster.mtv.corp.google.com","threadId":"46826","inReplyTo":"20170925095452.66833-3-dstolee@microsoft.com","subject":"Re: [PATCH v2 2/5] p0008-abbrev.sh: Test find_unique_abbrev() perf","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-09-26T09:27:26Z","receivedAt":"2017-09-26T09:27:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> diff --git a/t/helper/test-abbrev.c b/t/helper/test-abbrev.c\n> new file mode 100644\n> index 000000000..6866896eb\n> --- /dev/null\n> +++ b/t/helper/test-abbrev.c\n> @@ -0,0 +1,19 @@\n> +#include \"cache.h\"\n> +#include \n\nSame comment on as [1/5] applies.\n\n> +\n> +int cmd_main(int ac, const char **av)\n> +{\n> +\tstruct object_id oid;\n> +\tchar hex[GIT_MAX_HEXSZ + 2];\n\nWhy +2 (as opposed to +1)?\n\n> +\tconst char *end;\n> +\n> +\tsetup_git_directory();\n> +\n> +\twhile (fgets(hex, GIT_MAX_HEXSZ + 2, stdin)) {\n> +\t\thex[GIT_MAX_HEXSZ] = 0;\n> +\t\tif (!parse_oid_hex(hex, &oid, &end))\n> +\t\t\tfind_unique_abbrev(oid.hash, MINIMUM_ABBREV);\n> +\t}\n> +\n> +\texit(0);\n> +}\n> diff --git a/t/perf/p0008-abbrev.sh b/t/perf/p0008-abbrev.sh\n> new file mode 100755\n> index 000000000..ba25e7824\n> --- /dev/null\n> +++ b/t/perf/p0008-abbrev.sh\n> @@ -0,0 +1,22 @@\n> +#!/bin/bash\n> +\n> +test_description='Test object disambiguation through abbreviations'\n> +. ./perf-lib.sh\n> +\n> +test_perf_large_repo\n> +\n> +test-list-objects 100000 | sort -R > objs.txt\n\nI thought \"sort randomly\" was a GNUism. Does it work across\nplatforms? I think not.\n\n> +\n> +test_perf 'find_unique_abbrev() for existing objects' '\n> +\ttest-abbrev < objs.txt\n> +'\n> +\n> +test-list-objects 100000 --missing | sort -R > objs.txt\n> +\n> +test_perf 'find_unique_abbrev() for missing objects' '\n> +\ttest-abbrev < objs.txt\n> +'\n> +\n> +rm objs.txt\n> +\n> +test_done\n"},{"id":"329449","messageId":"f255961b-754e-5cf1-7641-1951548db362@gmail.com","threadId":"46826","inReplyTo":"CAGZ79kaBGtgBv2OryCO+oc-0nvSyi0vXA2jsLS2=5Xweea1SNg@mail.gmail.com","subject":"Re: [PATCH v2 4/5] sha1_name: Parse less while finding common prefix","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2017-10-02T14:52:38Z","receivedAt":"2017-10-02T14:52:48Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"My v3 patch is incoming, but I wanted to respond directly to this message.\n\nOn 9/25/2017 7:42 PM, Stefan Beller wrote:\n> On Mon, Sep 25, 2017 at 2:54 AM, Derrick Stolee wrote:\n>> Create get_hex_char_from_oid() to parse oids one hex character at a\n>> time. This prevents unnecessary copying of hex characters in\n>> extend_abbrev_len() when finding the length of a common prefix.\n>>\n>> p0008.1: find_unique_abbrev() for existing objects\n>> --------------------------------------------------\n>>\n>> For 10 repeated tests, each checking 100,000 known objects, we find the\n>> following results when running in a Linux VM:\n>>\n>> | | Pack | Packed | Loose | Base | New | |\n>> | Repo | Files | Objects | Objects| Time | Time | Rel% |\n>> |-------|-------|---------|--------|--------|--------|--------|\n>> | Git | 1 | 230078 | 0 | 0.08 s | 0.08 s | 0.0% |\n>> | Git | 5 | 230162 | 0 | 0.17 s | 0.16 s | - 5.9% |\n>> | Git | 4 | 154310 | 75852 | 0.14 s | 0.12 s | -14.3% |\n>> | Linux | 1 | 5606645 | 0 | 0.50 s | 0.25 s | -50.0% |\n>> | Linux | 24 | 5606645 | 0 | 2.41 s | 2.08 s | -13.7% |\n>> | Linux | 23 | 5283204 | 323441 | 1.99 s | 1.69 s | -15.1% |\n>> | VSTS | 1 | 4355923 | 0 | 0.40 s | 0.22 s | -45.0% |\n>> | VSTS | 32 | 4355923 | 0 | 2.09 s | 1.99 s | - 4.8% |\n>> | VSTS | 31 | 4276829 | 79094 | 3.60 s | 3.20 s | -11.1% |\n>>\n>> For the Windows repo running in Windows Subsystem for Linux:\n>>\n>> Pack Files: 50\n>> Packed Objects: 22,385,898\n>> Loose Objects: 492\n>> Base Time: 4.61 s\n>> New Time: 4.61 s\n>> Rel %: 0.0%\n>>\n>> p0008.2: find_unique_abbrev() for missing objects\n>> -------------------------------------------------\n>>\n>> For 10 repeated tests, each checking 100,000 missing objects, we find\n>> the following results when running in a Linux VM:\n>>\n>> | | Pack | Packed | Loose | Base | New | |\n>> | Repo | Files | Objects | Objects| Time | Time | Rel% |\n>> |-------|-------|---------|--------|--------|--------|--------|\n>> | Git | 1 | 230078 | 0 | 0.06 s | 0.05 s | -16.7% |\n>> | Git | 5 | 230162 | 0 | 0.14 s | 0.15 s | + 7.1% |\n>> | Git | 4 | 154310 | 75852 | 0.12 s | 0.12 s | 0.0% |\n>> | Linux | 1 | 5606645 | 0 | 0.40 s | 0.17 s | -57.5% |\n>> | Linux | 24 | 5606645 | 0 | 1.59 s | 1.30 s | -18.2% |\n>> | Linux | 23 | 5283204 | 323441 | 1.23 s | 1.10 s | -10.6% |\n>> | VSTS | 1 | 4355923 | 0 | 0.25 s | 0.12 s | -52.0% |\n>> | VSTS | 32 | 4355923 | 0 | 1.45 s | 1.34 s | - 7.6% |\n>> | VSTS | 31 | 4276829 | 79094 | 1.59 s | 1.34 s | -15.7% |\n>>\n>> For the Windows repo running in Windows Subsystem for Linux:\n>>\n>> Pack Files: 50\n>> Packed Objects: 22,385,898\n>> Loose Objects: 492\n>> Base Time: 3.91 s\n>> New Time: 3.08 s\n>> Rel %: -21.1%\n>>\n> These number look pretty cool!\n>\n>> Signed-off-by: Derrick Stolee \n>>\n>> Signed-off-by: Derrick Stolee \n> double signoff?\n\nOops! I'll be more careful with my format-patch in the future.\n\n>\n>> ---\n>> sha1_name.c | 13 +++++++++++--\n>> 1 file changed, 11 insertions(+), 2 deletions(-)\n>>\n>> diff --git a/sha1_name.c b/sha1_name.c\n>> index f2a1ebe49..bb47b6702 100644\n>> --- a/sha1_name.c\n>> +++ b/sha1_name.c\n>> @@ -480,13 +480,22 @@ struct min_abbrev_data {\n>> char *hex;\n>> };\n>>\n>> +static inline char get_hex_char_from_oid(const struct object_id *oid, int i)\n> 'i' is not very descriptive, maybe add a comment?\n> (I realize it is just walking through the char*s one by one)\nI renamed 'i' to 'pos' in my v3.\n\n>\n> Maybe this function (together with the change in the while below)\n> could go into hex.c as \"int progressively_cmp_oids\" that returns\n> the position at which the given oids differ?\n>\n>> +{\n>> + static const char hex[] = \"0123456789abcdef\";\n>> +\n>> + if ((i & 1) == 0)\n>> + return hex[oid->hash[i >> 1] >> 4];\n>> + else\n>> + return hex[oid->hash[i >> 1] & 0xf];\n>> +}\n> sha1_to_hex_r has very similar code, though it iterates less\n> and covers both cases in the loop body.\n>\n> That is the actual reason I propose moving this function\n> (or a variant thereof) to hex.c as there we can share code.\n\nYou're right that sha1_to_hex_r is similar, in fact I based my work on \nit. There are a few reasons I didn't combine the two implementations:\n\n* I wanted to be sure my patch was only touching the code for \ndisambiguating short-shas. Modifying code in hex.c would touch many more \ncode paths.\n\n* I realize that the extra branch in my version is slower than the \nbranchless loop body in sha1_to_hex_r, so either I would slow that \nmethod or make the method call more complicated by returning two chars \nat a time.\n\n* I wanted to strongly hint that the method should be inlined, but I'm \nnot sure how to guarantee that happens across a linker boundary without \ndoing strange things in header files.\n\nI'm happy to revisit this after my patch is complete, since I think \nthere are interesting trade-offs to consider here. I'd prefer to keep \nthis discussion separate from the focus on disambiguation.\n\nThanks,\n-Stolee\n"},{"id":"329450","messageId":"20171002145651.204984-2-dstolee@microsoft.com","threadId":"46826","inReplyTo":"20170925095452.66833-1-dstolee@microsoft.com","subject":"[PATCH v3 1/5] test-list-objects: List a subset of object ids","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-02T14:56:47Z","receivedAt":"2017-10-02T14:57:11Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Create test-list-objects helper program to output a random sample of\nOIDs present in the repo.\n\nIf no command line arguments are provided, all OIDs are output.\n\nThe last command line argument specifies how many samples to output.\nSamples are collected across the entire set of available OIDs to avoid\nclustering and therefore quite uniformly distributed.\n\nIf a command line argument \"--missing\" is given before the sample count,\nthen a list of OIDs is generated without examining the repo.\n\n Signed-off-by: Derrick Stolee \n---\n Makefile | 1 +\n t/helper/.gitignore | 1 +\n t/helper/test-list-objects.c | 87 ++++++++++++++++++++++++++++++++++++++++++++\n 3 files changed, 89 insertions(+)\n create mode 100644 t/helper/test-list-objects.c\n\ndiff --git a/Makefile b/Makefile\nindex ed4ca438b..50a2eab80 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -652,6 +652,7 @@ TEST_PROGRAMS_NEED_X += test-hashmap\n TEST_PROGRAMS_NEED_X += test-index-version\n TEST_PROGRAMS_NEED_X += test-lazy-init-name-hash\n TEST_PROGRAMS_NEED_X += test-line-buffer\n+TEST_PROGRAMS_NEED_X += test-list-objects\n TEST_PROGRAMS_NEED_X += test-match-trees\n TEST_PROGRAMS_NEED_X += test-mergesort\n TEST_PROGRAMS_NEED_X += test-mktemp\ndiff --git a/t/helper/.gitignore b/t/helper/.gitignore\nindex 7c9d28a83..9696f54bb 100644\n--- a/t/helper/.gitignore\n+++ b/t/helper/.gitignore\n@@ -13,6 +13,7 @@\n /test-index-version\n /test-lazy-init-name-hash\n /test-line-buffer\n+/test-list-objects\n /test-match-trees\n /test-mergesort\n /test-mktemp\ndiff --git a/t/helper/test-list-objects.c b/t/helper/test-list-objects.c\nnew file mode 100644\nindex 000000000..22bc9b4e6\n--- /dev/null\n+++ b/t/helper/test-list-objects.c\n@@ -0,0 +1,87 @@\n+#include \"cache.h\"\n+#include \"packfile.h\"\n+\n+struct count {\n+\tint total;\n+\tint select_mod;\n+};\n+\n+int count_loose(const struct object_id *oid,\n+\t\tconst char *path,\n+\t\tvoid *data)\n+{\n+\t((struct count*)data)->total++;\n+\treturn 0;\n+}\n+\n+int count_packed(const struct object_id *oid,\n+\t\t struct packed_git *pack,\n+\t\t uint32_t pos,\n+\t\t void* data)\n+{\n+\t((struct count*)data)->total++;\n+\treturn 0;\n+}\n+\n+void output(const struct object_id *oid,\n+\t struct count *c)\n+{\n+\tif (!(c->total % c->select_mod))\n+\t\tprintf(\"%s\\n\", oid_to_hex(oid));\n+\tc->total--;\n+}\n+\n+int output_loose(const struct object_id *oid,\n+\t\t const char *path,\n+\t\t void *data)\n+{\n+\toutput(oid, (struct count*)data);\n+\treturn 0;\n+}\n+\n+int output_packed(const struct object_id *oid,\n+\t\t struct packed_git *pack,\n+\t\t uint32_t pos,\n+\t\t void* data)\n+{\n+\toutput(oid, (struct count*)data);\n+\treturn 0;\n+}\n+\n+int cmd_main(int ac, const char **av)\n+{\n+\tuint32_t hash_delt = 0xFDB97531;\n+\tuint32_t hash_base = 0x01020304;\n+\tint i, n = -1;\n+\tstruct count c;\n+\tconst int u_per_oid = sizeof(struct object_id) / sizeof(uint32_t);\n+\n+\tc.total = 0;\n+\tif (ac > 1)\n+\t\tn = atoi(av[ac - 1]);\n+\n+\tif (ac > 2 && !strcmp(av[1], \"--missing\")) {\n+\t\twhile (c.total++ < n) {\n+\t\t\tfor (i = 0; i < u_per_oid; i++) {\n+\t\t\t\tprintf(\"%08x\", hash_base);\n+\t\t\t\thash_base += hash_delt;\n+\t\t\t}\n+\t\t\tprintf(\"\\n\");\n+\t\t}\n+\t} else {\n+\t\tsetup_git_directory();\n+\n+\t\tif (n > 0) {\n+\t\t\tfor_each_loose_object(count_loose, &c, 0);\n+\t\t\tfor_each_packed_object(count_packed, &c, 0);\n+\t\t\tc.select_mod = 1 + c.total / n;\n+\t\t} else {\n+\t\t\tc.select_mod = 1;\n+\t\t}\n+\n+\t\tfor_each_loose_object(output_loose, &c, 0);\n+\t\tfor_each_packed_object(output_packed, &c, 0);\n+\t}\n+\n+\texit(0);\n+}\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"329451","messageId":"20171002145651.204984-3-dstolee@microsoft.com","threadId":"46826","inReplyTo":"20170925095452.66833-1-dstolee@microsoft.com","subject":"[PATCH v3 2/5] p0008-abbrev.sh: Test find_unique_abbrev() perf","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-02T14:56:48Z","receivedAt":"2017-10-02T14:57:13Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Create helper program test-abbrev to compute the minimum length of a\ndisambiguating short-sha for an input list of object ids.\n\nPerf test p0008-abbrev.sh runs test-abbrev for 100,000 object ids. For\ntest 0008.1, these objects exist. For test 0008.2 these objects do not\nexist in the repo (with high probability).\n\nSigned-off-by: Derrick Stolee \n---\n Makefile | 1 +\n t/helper/.gitignore | 1 +\n t/helper/test-abbrev.c | 18 ++++++++++++++++++\n t/perf/p0008-abbrev.sh | 22 ++++++++++++++++++++++\n 4 files changed, 42 insertions(+)\n create mode 100644 t/helper/test-abbrev.c\n create mode 100755 t/perf/p0008-abbrev.sh\n\ndiff --git a/Makefile b/Makefile\nindex 50a2eab80..63438a44e 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -638,6 +638,7 @@ X =\n \n PROGRAMS += $(patsubst %.o,git-%$X,$(PROGRAM_OBJS))\n \n+TEST_PROGRAMS_NEED_X += test-abbrev\n TEST_PROGRAMS_NEED_X += test-chmtime\n TEST_PROGRAMS_NEED_X += test-ctype\n TEST_PROGRAMS_NEED_X += test-config\ndiff --git a/t/helper/.gitignore b/t/helper/.gitignore\nindex 9696f54bb..2190781ff 100644\n--- a/t/helper/.gitignore\n+++ b/t/helper/.gitignore\n@@ -1,3 +1,4 @@\n+/test-abbrev\n /test-chmtime\n /test-ctype\n /test-config\ndiff --git a/t/helper/test-abbrev.c b/t/helper/test-abbrev.c\nnew file mode 100644\nindex 000000000..3ad88611a\n--- /dev/null\n+++ b/t/helper/test-abbrev.c\n@@ -0,0 +1,18 @@\n+#include \"cache.h\"\n+\n+int cmd_main(int ac, const char **av)\n+{\n+\tstruct object_id oid;\n+\tchar hex[GIT_MAX_HEXSZ + 2];\n+\tconst char *end;\n+\n+\tsetup_git_directory();\n+\n+\twhile (fgets(hex, GIT_MAX_HEXSZ + 2, stdin)) {\n+\t\thex[GIT_MAX_HEXSZ] = 0;\n+\t\tif (!parse_oid_hex(hex, &oid, &end))\n+\t\t\tfind_unique_abbrev(oid.hash, MINIMUM_ABBREV);\n+\t}\n+\n+\texit(0);\n+}\ndiff --git a/t/perf/p0008-abbrev.sh b/t/perf/p0008-abbrev.sh\nnew file mode 100755\nindex 000000000..5cbc8a888\n--- /dev/null\n+++ b/t/perf/p0008-abbrev.sh\n@@ -0,0 +1,22 @@\n+#!/bin/bash\n+\n+test_description='Test object disambiguation through abbreviations'\n+. ./perf-lib.sh\n+\n+test_perf_large_repo\n+\n+test-list-objects 100000 > objs.txt\n+\n+test_perf 'find_unique_abbrev() for existing objects' '\n+\ttest-abbrev < objs.txt\n+'\n+\n+test-list-objects --missing 100000 > objs.txt\n+\n+test_perf 'find_unique_abbrev() for missing objects' '\n+\ttest-abbrev < objs.txt\n+'\n+\n+rm objs.txt\n+\n+test_done\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"329452","messageId":"20171002145651.204984-1-dstolee@microsoft.com","threadId":"46826","inReplyTo":"20170925095452.66833-1-dstolee@microsoft.com","subject":"[PATCH v3 0/5] Improve abbreviation disambituation","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-02T14:56:46Z","receivedAt":"2017-10-02T14:57:16Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Thanks for the feedback on my previous versions, and for patience\nwith my inexperience on the mailing list. I tried to respond to all\nfeedback, but decided to not apply one suggestion:\n\n* Removed the \"sort -R\" from p0008-abbrev.sh, since it is a GNU-\n specific flag. The perf test now considers objects in \"discovery\"\n order, which improved performance all versions of the test as\n expected. New perf numbers are provided.\n\n* get_hex_char_from_oid(): renamed `i` to `pos`. I did not unify the\n code in this method with that in hex.c:sha1_to_hex_r due to the\n extra branch in get_hex_char_from_oid and wanting to inline the\n method. If we want to make this method available for other callers,\n then I would be happy to submit a separate patch for this change\n after the current patch is accepted.\n\n* Removed unecessary includes.\n\n* Use uint32_t instead of unsigned int in test-list-objects.c\n\n* Rearranged arguments in test-list-objects and fixed the n == 0 bug.\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\nA helper program `test-list-objects` outputs a sampling of object ids,\nwhich we reorder using `sort -R` before using them as input to a\nperformance test. \n\nA performance helper `test-abbrev` and performance test `p0008-abbrev.sh`\nare added to demonstrate performance improvements in this area.\n\nI include performance test numbers in the commit messages for each\nchange, but I also include the difference between the baseline and the\nfinal change here:\n\n\np0008.1: find_unique_abbrev() for existing objects\n--------------------------------------------------\n\nFor 10 repeated tests, each checking 100,000 known objects, we find the\nfollowing results when running in a Linux VM:\n\n| | Pack | Packed | Loose | Base | New | |\n| Repo | Files | Objects | Objects| Time | Time | Rel% |\n|-------|-------|---------|--------|--------|--------|--------|\n| Git | 1 | 230078 | 0 | 0.09 s | 0.05 s | -44.4% |\n| Git | 5 | 230162 | 0 | 0.11 s | 0.08 s | -27.3% |\n| Git | 4 | 154310 | 75852 | 0.09 s | 0.06 s | -33.3% |\n| Linux | 1 | 5606645 | 0 | 0.13 s | 0.05 s | -61.5% |\n| Linux | 24 | 5606645 | 0 | 1.13 s | 0.88 s | -22.1% |\n| Linux | 23 | 5283204 | 323441 | 1.08 s | 0.80 s | -25.9% |\n| VSTS | 1 | 4355923 | 0 | 0.12 s | 0.05 s | -58.3% |\n| VSTS | 32 | 4355923 | 0 | 1.02 s | 0.95 s | - 6.9% |\n| VSTS | 31 | 4276829 | 79094 | 2.25 s | 1.93 s | -14.2% |\n\nFor the Windows repo running in Windows Subsystem for Linux:\n\n Pack Files: 50\nPacked Objects: 22,385,898\n Loose Objects: 492\n Base Time: 5.69 s\n New Time: 4.09 s\n Rel %: -28.1%\n\np0008.2: find_unique_abbrev() for missing objects\n-------------------------------------------------\n\nFor 10 repeated tests, each checking 100,000 missing objects, we find\nthe following results when running in a Linux VM:\n\n| | Pack | Packed | Loose | Base | New | |\n| Repo | Files | Objects | Objects| Time | Time | Rel% |\n|-------|-------|---------|--------|--------|--------|--------|\n| Git | 1 | 230078 | 0 | 0.66 s | 0.07 s | -89.4% |\n| Git | 5 | 230162 | 0 | 0.90 s | 0.12 s | -86.7% |\n| Git | 4 | 154310 | 75852 | 0.79 s | 0.09 s | -88.6% |\n| Linux | 1 | 5606645 | 0 | 0.48 s | 0.04 s | -91.7% |\n| Linux | 24 | 5606645 | 0 | 4.41 s | 0.85 s | -80.7% |\n| Linux | 23 | 5283204 | 323441 | 4.11 s | 0.78 s | -81.0% |\n| VSTS | 1 | 4355923 | 0 | 0.46 s | 0.04 s | -91.3% |\n| VSTS | 32 | 4355923 | 0 | 5.40 s | 0.98 s | -81.9% |\n| VSTS | 31 | 4276829 | 79094 | 5.88 s | 1.04 s | -82.3% |\n\nFor the Windows repo running in Windows Subsystem for Linux:\n\n Pack Files: 50\nPacked Objects: 22,385,898\n Loose Objects: 492\n Base Time: 38.9 s\n New Time: 2.7 s\n Rel %: -93.1%\n\nDerrick Stolee (5):\n test-list-objects: List a subset of object ids\n p0008-abbrev.sh: Test find_unique_abbrev() perf\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 Makefile | 2 +\n sha1_name.c | 129 ++++++++++++++++++++++++++++++++++++++-----\n t/helper/.gitignore | 2 +\n t/helper/test-abbrev.c | 18 ++++++\n t/helper/test-list-objects.c | 87 +++++++++++++++++++++++++++++\n t/perf/p0008-abbrev.sh | 22 ++++++++\n 6 files changed, 245 insertions(+), 15 deletions(-)\n create mode 100644 t/helper/test-abbrev.c\n create mode 100644 t/helper/test-list-objects.c\n create mode 100755 t/perf/p0008-abbrev.sh\n\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"329453","messageId":"20171002145651.204984-5-dstolee@microsoft.com","threadId":"46826","inReplyTo":"20170925095452.66833-1-dstolee@microsoft.com","subject":"[PATCH v3 4/5] sha1_name: Parse less while finding common prefix","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-02T14:56:50Z","receivedAt":"2017-10-02T14:57:19Z","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\np0008.1: find_unique_abbrev() for existing objects\n--------------------------------------------------\n\nFor 10 repeated tests, each checking 100,000 known objects, we find the\nfollowing results when running in a Linux VM:\n\n| | Pack | Packed | Loose | Base | New | |\n| Repo | Files | Objects | Objects| Time | Time | Rel% |\n|-------|-------|---------|--------|--------|--------|--------|\n| Git | 1 | 230078 | 0 | 0.06 s | 0.05 s | -16.7% |\n| Git | 5 | 230162 | 0 | 0.08 s | 0.08 s | 0.0% |\n| Git | 4 | 154310 | 75852 | 0.07 s | 0.06 s | -14.3% |\n| Linux | 1 | 5606645 | 0 | 0.32 s | 0.14 s | -56.3% |\n| Linux | 24 | 5606645 | 0 | 1.12 s | 0.94 s | -16.1% |\n| Linux | 23 | 5283204 | 323441 | 1.05 s | 0.86 s | -18.1% |\n| VSTS | 1 | 4355923 | 0 | 0.23 s | 0.11 s | -52.2% |\n| VSTS | 32 | 4355923 | 0 | 1.08 s | 0.95 s | -12.0% |\n| VSTS | 31 | 4276829 | 79094 | 2.08 s | 1.82 s | -12.5% |\n\nFor the Windows repo running in Windows Subsystem for Linux:\n\n Pack Files: 50\nPacked Objects: 22,385,898\n Loose Objects: 492\n Base Time: 4.61 s\n New Time: 4.61 s\n Rel %: 0.0%\n\np0008.2: find_unique_abbrev() for missing objects\n-------------------------------------------------\n\nFor 10 repeated tests, each checking 100,000 missing objects, we find\nthe following results when running in a Linux VM:\n\n| | Pack | Packed | Loose | Base | New | |\n| Repo | Files | Objects | Objects| Time | Time | Rel% |\n|-------|-------|---------|--------|--------|--------|--------|\n| Git | 1 | 230078 | 0 | 0.08 s | 0.07 s | -12.5% |\n| Git | 5 | 230162 | 0 | 0.13 s | 0.12 s | - 7.7% |\n| Git | 4 | 154310 | 75852 | 0.10 s | 0.09 s | -10.0% |\n| Linux | 1 | 5606645 | 0 | 0.32 s | 0.13 s | -59.4% |\n| Linux | 24 | 5606645 | 0 | 1.09 s | 0.89 s | -18.3% |\n| Linux | 23 | 5283204 | 323441 | 0.99 s | 0.83 s | -16.2% |\n| VSTS | 1 | 4355923 | 0 | 0.25 s | 0.11 s | -56.0% |\n| VSTS | 32 | 4355923 | 0 | 1.15 s | 0.99 s | -13.9% |\n| VSTS | 31 | 4276829 | 79094 | 1.18 s | 1.02 s | -13.6% |\n\nFor the Windows repo running in Windows Subsystem for Linux:\n\n Pack Files: 50\nPacked Objects: 22,385,898\n Loose Objects: 492\n Base Time: 3.91 s\n New Time: 3.08 s\n Rel %: -21.1%\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":"329454","messageId":"20171002145651.204984-4-dstolee@microsoft.com","threadId":"46826","inReplyTo":"20170925095452.66833-1-dstolee@microsoft.com","subject":"[PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-02T14:56:49Z","receivedAt":"2017-10-02T14:57:24Z","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\np0008.1: find_unique_abbrev() for existing objects\n--------------------------------------------------\n\nFor 10 repeated tests, each checking 100,000 known objects, we find the\nfollowing results when running in a Linux VM:\n\n| | Pack | Packed | Loose | Base | New | |\n| Repo | Files | Objects | Objects| Time | Time | Rel% |\n|-------|-------|---------|--------|--------|--------|---------|\n| Git | 1 | 230078 | 0 | 0.09 s | 0.06 s | - 33.3% |\n| Git | 5 | 230162 | 0 | 0.11 s | 0.08 s | - 27.3% |\n| Git | 4 | 154310 | 75852 | 0.09 s | 0.07 s | - 22.2% |\n| Linux | 1 | 5606645 | 0 | 0.12 s | 0.32 s | +146.2% |\n| Linux | 24 | 5606645 | 0 | 1.12 s | 1.12 s | - 0.9% |\n| Linux | 23 | 5283204 | 323441 | 1.08 s | 1.05 s | - 2.8% |\n| VSTS | 1 | 4355923 | 0 | 0.12 s | 0.23 s | + 91.7% |\n| VSTS | 32 | 4355923 | 0 | 1.02 s | 1.08 s | + 5.9% |\n| VSTS | 31 | 4276829 | 79094 | 2.25 s | 2.08 s | - 7.6% |\n\nFor the Windows repo running in Windows Subsystem for Linux:\n\n Pack Files: 50\nPacked Objects: 22,385,898\n Loose Objects: 492\n Base Time: 5.69 s\n New Time: 4.62 s\n Rel %: -18.9%\n\np0008.2: find_unique_abbrev() for missing objects\n-------------------------------------------------\n\nFor 10 repeated tests, each checking 100,000 missing objects, we find\nthe following results when running in a Linux VM:\n\n| | Pack | Packed | Loose | Base | New | |\n| Repo | Files | Objects | Objects| Time | Time | Rel% |\n|-------|-------|---------|--------|--------|--------|--------|\n| Git | 1 | 230078 | 0 | 0.66 s | 0.08 s | -87.9% |\n| Git | 5 | 230162 | 0 | 0.90 s | 0.13 s | -85.6% |\n| Git | 4 | 154310 | 75852 | 0.79 s | 0.10 s | -87.3% |\n| Linux | 1 | 5606645 | 0 | 0.48 s | 0.32 s | -33.3% |\n| Linux | 24 | 5606645 | 0 | 4.41 s | 1.09 s | -75.3% |\n| Linux | 23 | 5283204 | 323441 | 4.11 s | 0.99 s | -75.9% |\n| VSTS | 1 | 4355923 | 0 | 0.46 s | 0.25 s | -45.7% |\n| VSTS | 32 | 4355923 | 0 | 5.40 s | 1.15 s | -78.7% |\n| VSTS | 31 | 4276829 | 79094 | 5.88 s | 1.18 s | -79.9% |\n\nFor the Windows repo running in Windows Subsystem for Linux:\n\n Pack Files: 50\nPacked Objects: 22,385,898\n Loose Objects: 492\n Base Time: 39.0 s\n New Time: 3.9 s\n Rel %: -90.0%\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":"329455","messageId":"20171002145651.204984-6-dstolee@microsoft.com","threadId":"46826","inReplyTo":"20170925095452.66833-1-dstolee@microsoft.com","subject":"[PATCH v3 5/5] sha1_name: Minimize OID comparisons during disambiguation","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-02T14:56:51Z","receivedAt":"2017-10-02T14:57:26Z","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\np0008.1: find_unique_abbrev() for existing objects\n--------------------------------------------------\n\nFor 10 repeated tests, each checking 100,000 known objects, we find the\nfollowing results when running in a Linux VM:\n\n| | Pack | Packed | Loose | Base | New | |\n| Repo | Files | Objects | Objects| Time | Time | Rel% |\n|-------|-------|---------|--------|--------|--------|--------|\n| Git | 1 | 230078 | 0 | 0.05 s | 0.05 s | 0.0% |\n| Git | 5 | 230162 | 0 | 0.08 s | 0.08 s | 0.0% |\n| Git | 4 | 154310 | 75852 | 0.06 s | 0.06 s | 0.0% |\n| Linux | 1 | 5606645 | 0 | 0.14 s | 0.05 s | -64.3% |\n| Linux | 24 | 5606645 | 0 | 0.94 s | 0.88 s | - 6.4% |\n| Linux | 23 | 5283204 | 323441 | 0.86 s | 0.80 s | - 7.0% |\n| VSTS | 1 | 4355923 | 0 | 0.11 s | 0.05 s | -54.5% |\n| VSTS | 32 | 4355923 | 0 | 0.95 s | 0.95 s | 0.0% |\n| VSTS | 31 | 4276829 | 79094 | 1.82 s | 1.93 s | + 6.0% |\n\nFor the Windows repo running in Windows Subsystem for Linux:\n\n Pack Files: 50\nPacked Objects: 22,385,898\n Loose Objects: 492\n Base Time: 4.62 s\n New Time: 4.09 s\n Rel %: -11.5%\n\np0008.2: find_unique_abbrev() for missing objects\n-------------------------------------------------\n\nFor 10 repeated tests, each checking 100,000 missing objects, we find\nthe following results when running in a Linux VM:\n\n| | Pack | Packed | Loose | Base | New | |\n| Repo | Files | Objects | Objects| Time | Time | Rel% |\n|-------|-------|---------|--------|--------|--------|--------|\n| Git | 1 | 230078 | 0 | 0.07 s | 0.07 s | 0.0% |\n| Git | 5 | 230162 | 0 | 0.12 s | 0.12 s | 0.0% |\n| Git | 4 | 154310 | 75852 | 0.09 s | 0.09 s | 0.0% |\n| Linux | 1 | 5606645 | 0 | 0.13 s | 0.04 s | -69.2% |\n| Linux | 24 | 5606645 | 0 | 0.89 s | 0.85 s | - 4.5% |\n| Linux | 23 | 5283204 | 323441 | 0.83 s | 0.78 s | - 6.0% |\n| VSTS | 1 | 4355923 | 0 | 0.11 s | 0.04 s | -63.6% |\n| VSTS | 32 | 4355923 | 0 | 0.99 s | 0.98 s | - 1.0% |\n| VSTS | 31 | 4276829 | 79094 | 1.02 s | 1.04 s | + 2.0% |\n\nFor the Windows repo running in Windows Subsystem for Linux:\n\n Pack Files: 50\nPacked Objects: 22,385,898\n Loose Objects: 492\n Base Time: 3.08 s\n New Time: 2.72 s\n Rel %: -11.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..54b3a37da 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) / 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":"329523","messageId":"xmqq1smklvca.fsf@gitster.mtv.corp.google.com","threadId":"46826","inReplyTo":"20171002145651.204984-2-dstolee@microsoft.com","subject":"Re: [PATCH v3 1/5] test-list-objects: List a subset of object ids","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-03T04:16:21Z","receivedAt":"2017-10-03T04:16:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> Subject: Re: [PATCH v3 1/5] test-list-objects: List a subset of object ids\n\nStyle nit: s/List/list/;\n\n>\n> Signed-off-by: Derrick Stolee \n\nThis should stick to the left hand side.\n\nNo need to resend, only to fix these two, as I'll tweak them when\nqueuing.\n\n"},{"id":"329551","messageId":"xmqqinfwh5g0.fsf@gitster.mtv.corp.google.com","threadId":"46826","inReplyTo":"20171002145651.204984-4-dstolee@microsoft.com","subject":"Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-03T10:49:19Z","receivedAt":"2017-10-03T10:49:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> p0008.1: find_unique_abbrev() for existing objects\n> --------------------------------------------------\n>\n> For 10 repeated tests, each checking 100,000 known objects, we find the\n> following results when running in a Linux VM:\n>\n> | | Pack | Packed | Loose | Base | New | |\n> | Repo | Files | Objects | Objects| Time | Time | Rel% |\n> |-------|-------|---------|--------|--------|--------|---------|\n> | Git | 1 | 230078 | 0 | 0.09 s | 0.06 s | - 33.3% |\n> | Git | 5 | 230162 | 0 | 0.11 s | 0.08 s | - 27.3% |\n> | Git | 4 | 154310 | 75852 | 0.09 s | 0.07 s | - 22.2% |\n> | Linux | 1 | 5606645 | 0 | 0.12 s | 0.32 s | +146.2% |\n> | Linux | 24 | 5606645 | 0 | 1.12 s | 1.12 s | - 0.9% |\n> | Linux | 23 | 5283204 | 323441 | 1.08 s | 1.05 s | - 2.8% |\n> | VSTS | 1 | 4355923 | 0 | 0.12 s | 0.23 s | + 91.7% |\n> | VSTS | 32 | 4355923 | 0 | 1.02 s | 1.08 s | + 5.9% |\n> | VSTS | 31 | 4276829 | 79094 | 2.25 s | 2.08 s | - 7.6% |\n\nThe above does not look so good, especially in cases where a\nrepository is well maintained by packing into smaller number of\npacks, we get much worse result?\n\n> p0008.2: find_unique_abbrev() for missing objects\n> -------------------------------------------------\n>\n> For 10 repeated tests, each checking 100,000 missing objects, we find\n> the following results when running in a Linux VM:\n>\n> | | Pack | Packed | Loose | Base | New | |\n> | Repo | Files | Objects | Objects| Time | Time | Rel% |\n> |-------|-------|---------|--------|--------|--------|--------|\n> | Git | 1 | 230078 | 0 | 0.66 s | 0.08 s | -87.9% |\n> | Git | 5 | 230162 | 0 | 0.90 s | 0.13 s | -85.6% |\n> | Git | 4 | 154310 | 75852 | 0.79 s | 0.10 s | -87.3% |\n> | Linux | 1 | 5606645 | 0 | 0.48 s | 0.32 s | -33.3% |\n> | Linux | 24 | 5606645 | 0 | 4.41 s | 1.09 s | -75.3% |\n> | Linux | 23 | 5283204 | 323441 | 4.11 s | 0.99 s | -75.9% |\n> | VSTS | 1 | 4355923 | 0 | 0.46 s | 0.25 s | -45.7% |\n> | VSTS | 32 | 4355923 | 0 | 5.40 s | 1.15 s | -78.7% |\n> | VSTS | 31 | 4276829 | 79094 | 5.88 s | 1.18 s | -79.9% |\n\nThe question is if this is even measuring a relevant workload. How\noften would we have a full 40-hex object name for which we actually\ndo not have the object, and ask its name to be abbreviated?\n\nCompared to it, the result from p0008.1 feels a lot more important.\nWe know we make tons of \"abbreviate the object name for this object\nwe have\" and we see them every day in our \"git log -p\" output.\n\nSeeing a lot more impressive result from p0008.2 than p0008.1 makes\nme unsure if this patch is optimizing for the right case.\n\nI'll have to see the code a bit deeper before I can comment on it.\n\nThanks.\n"},{"id":"329554","messageId":"6a3804a4-9728-d122-7fac-f297fc7977d1@gmail.com","threadId":"46826","inReplyTo":"xmqqinfwh5g0.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2017-10-03T11:26:02Z","receivedAt":"2017-10-03T11:26:11Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/3/2017 6:49 AM, Junio C Hamano wrote:\n> Derrick Stolee writes:\n>\n>> p0008.1: find_unique_abbrev() for existing objects\n>> --------------------------------------------------\n>>\n>> For 10 repeated tests, each checking 100,000 known objects, we find the\n>> following results when running in a Linux VM:\n>>\n>> | | Pack | Packed | Loose | Base | New | |\n>> | Repo | Files | Objects | Objects| Time | Time | Rel% |\n>> |-------|-------|---------|--------|--------|--------|---------|\n>> | Git | 1 | 230078 | 0 | 0.09 s | 0.06 s | - 33.3% |\n>> | Git | 5 | 230162 | 0 | 0.11 s | 0.08 s | - 27.3% |\n>> | Git | 4 | 154310 | 75852 | 0.09 s | 0.07 s | - 22.2% |\n>> | Linux | 1 | 5606645 | 0 | 0.12 s | 0.32 s | +146.2% |\n>> | Linux | 24 | 5606645 | 0 | 1.12 s | 1.12 s | - 0.9% |\n>> | Linux | 23 | 5283204 | 323441 | 1.08 s | 1.05 s | - 2.8% |\n>> | VSTS | 1 | 4355923 | 0 | 0.12 s | 0.23 s | + 91.7% |\n>> | VSTS | 32 | 4355923 | 0 | 1.02 s | 1.08 s | + 5.9% |\n>> | VSTS | 31 | 4276829 | 79094 | 2.25 s | 2.08 s | - 7.6% |\n> The above does not look so good, especially in cases where a\n> repository is well maintained by packing into smaller number of\n> packs, we get much worse result?\nI understand that this patch on its own does not have good numbers. I \nsplit the\npatches 3 and 4 specifically to highlight two distinct changes:\n\nPatch 3: Unroll the len loop that may inspect all files multiple times.\nPatch 4: Parse less while disambiguating.\n\nPatch 4 more than makes up for the performance hits in this patch.\n>\n>> p0008.2: find_unique_abbrev() for missing objects\n>> -------------------------------------------------\n>>\n>> For 10 repeated tests, each checking 100,000 missing objects, we find\n>> the following results when running in a Linux VM:\n>>\n>> | | Pack | Packed | Loose | Base | New | |\n>> | Repo | Files | Objects | Objects| Time | Time | Rel% |\n>> |-------|-------|---------|--------|--------|--------|--------|\n>> | Git | 1 | 230078 | 0 | 0.66 s | 0.08 s | -87.9% |\n>> | Git | 5 | 230162 | 0 | 0.90 s | 0.13 s | -85.6% |\n>> | Git | 4 | 154310 | 75852 | 0.79 s | 0.10 s | -87.3% |\n>> | Linux | 1 | 5606645 | 0 | 0.48 s | 0.32 s | -33.3% |\n>> | Linux | 24 | 5606645 | 0 | 4.41 s | 1.09 s | -75.3% |\n>> | Linux | 23 | 5283204 | 323441 | 4.11 s | 0.99 s | -75.9% |\n>> | VSTS | 1 | 4355923 | 0 | 0.46 s | 0.25 s | -45.7% |\n>> | VSTS | 32 | 4355923 | 0 | 5.40 s | 1.15 s | -78.7% |\n>> | VSTS | 31 | 4276829 | 79094 | 5.88 s | 1.18 s | -79.9% |\n> The question is if this is even measuring a relevant workload. How\n> often would we have a full 40-hex object name for which we actually\n> do not have the object, and ask its name to be abbreviated?\n>\n> Compared to it, the result from p0008.1 feels a lot more important.\n> We know we make tons of \"abbreviate the object name for this object\n> we have\" and we see them every day in our \"git log -p\" output.\n>\n> Seeing a lot more impressive result from p0008.2 than p0008.1 makes\n> me unsure if this patch is optimizing for the right case.\n>\n> I'll have to see the code a bit deeper before I can comment on it.\n>\n> Thanks.\nI agree that p0008.1 is more important. p0008.2 covers an important case \nof the\nprevious implementation. The line\n\n     exists = has_sha1_file(sha1);\n\nwill inspect all packfiles and scan the full loose-object directory that \nwould contain\nthe object. The only reason for this call is to determine how to inspect \nthe result of\nget_short_oid(), but is a significant portion of the time that is gained \nhere.\n\nThanks,\n-Stolee\n"},{"id":"329578","messageId":"CAGZ79kZz0EPUo=FpndxQMztQ=x-_c_CbvRB2NDmTLQXWapDBqQ@mail.gmail.com","threadId":"46826","inReplyTo":"20171002145651.204984-6-dstolee@microsoft.com","subject":"Re: [PATCH v3 5/5] sha1_name: Minimize OID comparisons during disambiguation","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-03T15:55:16Z","receivedAt":"2017-10-03T15:55:23Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"> @@ -505,6 +506,65 @@ static int extend_abbrev_len(const struct object_id *oid, void *cb_data)\n> return 0;\n> }\n>\n> +static void find_abbrev_len_for_pack(struct packed_git *p,\n> + struct min_abbrev_data *mad)\n> +{\n> + int match = 0;\n> + uint32_t num, last, first = 0;\n> + struct object_id oid;\n> +\n> + open_pack_index(p);\n\ncoverity complained here with\n Calling \"open_pack_index\" without checking return value\n (as is done elsewhere 13 out of 15 times).\n\nI think the easiest way out is just a\n\n if (open_pack_index(p))\n die(_(\"Cannot open existing pack idx file for '%s'\"), p);\n\nor is there another good approach?\n"},{"id":"329582","messageId":"8ddd2da9-2846-a4c8-f80a-55eb61e5925d@gmail.com","threadId":"46826","inReplyTo":"CAGZ79kZz0EPUo=FpndxQMztQ=x-_c_CbvRB2NDmTLQXWapDBqQ@mail.gmail.com","subject":"Re: [PATCH v3 5/5] sha1_name: Minimize OID comparisons during disambiguation","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2017-10-03T17:05:42Z","receivedAt":"2017-10-03T17:05:50Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/3/2017 11:55 AM, Stefan Beller wrote:\n>> @@ -505,6 +506,65 @@ static int extend_abbrev_len(const struct object_id *oid, void *cb_data)\n>> return 0;\n>> }\n>>\n>> +static void find_abbrev_len_for_pack(struct packed_git *p,\n>> + struct min_abbrev_data *mad)\n>> +{\n>> + int match = 0;\n>> + uint32_t num, last, first = 0;\n>> + struct object_id oid;\n>> +\n>> + open_pack_index(p);\n> coverity complained here with\n> Calling \"open_pack_index\" without checking return value\n> (as is done elsewhere 13 out of 15 times).\nGood catch! This same line is repeated in unique_in_pack() in this same \nfile, so if this is worth fixing then we should probably fix it there, too.\n> I think the easiest way out is just a\n>\n> if (open_pack_index(p))\n> die(_(\"Cannot open existing pack idx file for '%s'\"), p);\n>\n> or is there another good approach?\nYou probably intended to have p->pack_name in the die();\n\nUsing `cat *.c | grep -A 2 \"if (open_pack_index(\"` and `cat */*.c | grep \n-A 2 \"if (open_pack_index(\"` I see a few places that return error codes \nor quietly fail. The cases that use die() are inside builtin/ so I don't \nthink die() is the right choice here.\n\nSince find_abbrev_len_for_pack() is intended to extend the abbreviation \nlength when necessary, I think a silent return is best here:\n\n     if (open_pack_index(p))\n         return;\n\nThanks,\n-Stolee\n"},{"id":"329654","messageId":"xmqqtvzfcuoy.fsf@gitster.mtv.corp.google.com","threadId":"46826","inReplyTo":"20171002145651.204984-4-dstolee@microsoft.com","subject":"Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-04T06:07:25Z","receivedAt":"2017-10-04T06:07:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\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\nThe idea is to keep the target to be abbreviated in mad->hex[], and\nas the two functions find_short_{object_filename,packed_object}\ndiscover objects whose first 'len' letters of hexname are the same\nas the target, they'd call into the \"always_call_fn\" callback, which\nis this function, and it keeps track of the maximum of the common\nprefix it has seen. Which makes sense. Well, sort of.\n\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\nThe \"always_call_fn\" thing is a big sledgehammer that overrides\neverything else in update_candidates(). It bypasses the careful\nmachinery set up to avoid having to open ambiguous object to learn\ntheir types as much as possible. One narrow exception when it is OK\nto use is if we never limit our candidates with type.\n\nAnd it might appear that the conversion is safe (if only because we\ndo not see any type limitation in the get_short_oid() call above),\nbut I think there is one case where this patch changes the\nbehaviour: what happens if core.disambiguate was set to anything\nother than \"none\"? The new code does not know anything about type\nbased filtering, so it can end up reporting longer abbreviation than\nit was asked to produce. It may not be a problem in practice, though.\n\nI am not sure if setting core.disambiguate is generally a good idea\nin the first place, and if it is OK to break find_unique_abbrev()\nwith respect to the configuration variable like this patch does.\n\nI'd feel safe if we get extra input from Peff, who introduced the\nfeature in 5b33cb1f (\"get_short_sha1: make default disambiguation\nconfigurable\", 2016-09-27).\n\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"},{"id":"329655","messageId":"xmqqpoa3cujz.fsf@gitster.mtv.corp.google.com","threadId":"46826","inReplyTo":"6a3804a4-9728-d122-7fac-f297fc7977d1@gmail.com","subject":"Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-04T06:10:24Z","receivedAt":"2017-10-04T06:10:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> On 10/3/2017 6:49 AM, Junio C Hamano wrote:\n>> Derrick Stolee writes:\n>>\n>>> p0008.1: find_unique_abbrev() for existing objects\n>>> --------------------------------------------------\n>>>\n>>> For 10 repeated tests, each checking 100,000 known objects, we find the\n>>> following results when running in a Linux VM:\n>>>\n>>> | | Pack | Packed | Loose | Base | New | |\n>>> | Repo | Files | Objects | Objects| Time | Time | Rel% |\n>>> |-------|-------|---------|--------|--------|--------|---------|\n>>> | Git | 1 | 230078 | 0 | 0.09 s | 0.06 s | - 33.3% |\n>>> | Git | 5 | 230162 | 0 | 0.11 s | 0.08 s | - 27.3% |\n>>> | Git | 4 | 154310 | 75852 | 0.09 s | 0.07 s | - 22.2% |\n>>> | Linux | 1 | 5606645 | 0 | 0.12 s | 0.32 s | +146.2% |\n>>> | Linux | 24 | 5606645 | 0 | 1.12 s | 1.12 s | - 0.9% |\n>>> | Linux | 23 | 5283204 | 323441 | 1.08 s | 1.05 s | - 2.8% |\n>>> | VSTS | 1 | 4355923 | 0 | 0.12 s | 0.23 s | + 91.7% |\n>>> | VSTS | 32 | 4355923 | 0 | 1.02 s | 1.08 s | + 5.9% |\n>>> | VSTS | 31 | 4276829 | 79094 | 2.25 s | 2.08 s | - 7.6% |\n>>\n>> The above does not look so good, especially in cases where a\n>> repository is well maintained by packing into smaller number of\n>> packs, we get much worse result?\n>\n> I understand that this patch on its own does not have good numbers. I\n> split the\n> patches 3 and 4 specifically to highlight two distinct changes:\n>\n> Patch 3: Unroll the len loop that may inspect all files multiple times.\n> Patch 4: Parse less while disambiguating.\n>\n> Patch 4 more than makes up for the performance hits in this patch.\n\nNow you confused me even more. When we read the similar table that\nappears in [Patch 4/5], what does the \"Base Time\" column mean?\nVanilla Git with [Patch 3/5] applied? Vanillay Git with [Patch 4/5]\nalone applied? Something else?\n"},{"id":"329656","messageId":"xmqqlgkrcucj.fsf@gitster.mtv.corp.google.com","threadId":"46826","inReplyTo":"20171002145651.204984-5-dstolee@microsoft.com","subject":"Re: [PATCH v3 4/5] sha1_name: Parse less while finding common prefix","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-04T06:14:52Z","receivedAt":"2017-10-04T06:14:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> diff --git a/sha1_name.c b/sha1_name.c\n> index 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\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\nAssuming that [PATCH 3/5] makes sense, it is an obvious optimization\nto avoid writing the whole 20-byte out before comparing, and instead\nto grab hex digits as they become needed.\n\nI assume that the \"Base Time\" in the log message was with whatever\nversion of Git before [PATCH 3/5] and this one were applied\n(i.e. not comparing to \"vanilla Git plus 3/5\")?\n\nThanks.\n"},{"id":"329683","messageId":"ff54de0c-cd7c-bc3d-dd18-5fc248f3f573@gmail.com","threadId":"46826","inReplyTo":"xmqqpoa3cujz.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2017-10-04T13:06:32Z","receivedAt":"2017-10-04T13:06:39Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/4/2017 2:10 AM, Junio C Hamano wrote:\n> Derrick Stolee writes:\n> ...\n>> I understand that this patch on its own does not have good numbers. I\n>> split the\n>> patches 3 and 4 specifically to highlight two distinct changes:\n>>\n>> Patch 3: Unroll the len loop that may inspect all files multiple times.\n>> Patch 4: Parse less while disambiguating.\n>>\n>> Patch 4 more than makes up for the performance hits in this patch.\n> Now you confused me even more. When we read the similar table that\n> appears in [Patch 4/5], what does the \"Base Time\" column mean?\n> Vanilla Git with [Patch 3/5] applied? Vanillay Git with [Patch 4/5]\n> alone applied? Something else?\nIn PATCH 3, 4, and 5, I used the commit-by-commit diff for the perf \nnumbers, so the \"Base Time\" for PATCH 4 is the time calculated when \nPATCH 3 is applied. The table in the [PATCH 0/5] message includes the \nrelative change for all commits.\n\nI recalculated the relative change for each patch related to the \nbaseline (PATCH 2). Looking again, it appears I misspoke and PATCH 4 \ndoes include a +8% change for a fully-repacked Linux repo relative to \nPATCH 2. Since PATCH 5 includes an optimization targeted directly at \nlarge packfiles, the final performance gain is significant in the \nfully-packed cases.\n\nIt is also worth looking at the absolute times for these cases, since \nthe fully-packed case is significantly faster than the multiple-packfile \ncase, so the relative change impacts users less.\n\nOne final note: the improvement was clearer in test p0008.1 when the \ntest included \"sort -R\" to shuffle the known OIDs. Providing OIDs in \nlexicographic order has had a significant effect on the performance, \nwhich does not reflect real-world usage. I removed the \"sort -R\" because \nit is a GNU-ism, but if there is a good cross-platform alternative I \nwould be happy to replace it.\n\np0008.1: find_unique_abbrev() for existing objects\n--------------------------------------------------\n\nFor 10 repeated tests, each checking 100,000 known objects, we find the\nfollowing results when running in a Linux VM:\n\n| Repo  | Baseline | Patch 3 | Rel % | Patch 4 | Rel % | Patch 5 | Rel % |\n|-------|----------|---------|-------|---------|-------|---------|-------|\n| Git   | 0.09     | 0.06    | -33%  | 0.05    | -44%  | 0.05    | -44%  |\n| Git   | 0.11     | 0.08    | -27%  | 0.08    | -27%  | 0.08    | -27%  |\n| Git   | 0.09     | 0.07    | -22%  | 0.06    | -33%  | 0.06    | -33%  |\n| Linux | 0.13     | 0.32    | 146%  | 0.14    | + 8%  | 0.05    | -62%  |\n| Linux | 1.13     | 1.12    | - 1%  | 0.94    | -17%  | 0.88    | -22%  |\n| Linux | 1.08     | 1.05    | - 3%  | 0.86    | -20%  | 0.80    | -26%  |\n| VSTS  | 0.12     | 0.23    | +92%  | 0.11    | - 8%  | 0.05    | -58%  |\n| VSTS  | 1.02     | 1.08    | + 6%  | 0.95    | - 7%  | 0.95    | - 7%  |\n| VSTS  | 2.25     | 2.08    | - 8%  | 1.82    | -19%  | 1.93    | -14%  |\n\n(Each repo has three versions, in order: 1 packfile, multiple packfiles, \nand multiple packfiles and loose objects.)\n\nThanks,\n-Stolee\n\n"},{"id":"329684","messageId":"a6653525-94f2-fd7d-8c27-9334d473a556@gmail.com","threadId":"46826","inReplyTo":"xmqqtvzfcuoy.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2017-10-04T13:19:59Z","receivedAt":"2017-10-04T13:20:45Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/4/2017 2:07 AM, Junio C Hamano wrote:\n> Derrick Stolee writes:\n>\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> The \"always_call_fn\" thing is a big sledgehammer that overrides\n> everything else in update_candidates(). It bypasses the careful\n> machinery set up to avoid having to open ambiguous object to learn\n> their types as much as possible. One narrow exception when it is OK\n> to use is if we never limit our candidates with type.\n\nI do not modify get_short_oid, which uses these advanced options, \ndepending on the flags given. find_unique_abbrev_r() does not use these \nadvanced options.\n\n> And it might appear that the conversion is safe (if only because we\n> do not see any type limitation in the get_short_oid() call above),\n> but I think there is one case where this patch changes the\n> behaviour: what happens if core.disambiguate was set to anything\n> other than \"none\"? The new code does not know anything about type\n> based filtering, so it can end up reporting longer abbreviation than\n> it was asked to produce. It may not be a problem in practice, though.\n>\n> I am not sure if setting core.disambiguate is generally a good idea\n> in the first place, and if it is OK to break find_unique_abbrev()\n> with respect to the configuration variable like this patch does.\n\nI do not think that type-aware disambiguation goes through this code \npath, since it requires giving different parameters to get_short_oid(). \nTest t1512-rev-parse-disambituagion.sh has a test 'core.disambiguate \nconfig can prefer types' that verifies this behavior.\n\n> I'd feel safe if we get extra input from Peff, who introduced the\n> feature in 5b33cb1f (\"get_short_sha1: make default disambiguation\n> configurable\", 2016-09-27).\n\nI look forward to more feedback. Thanks for taking the time to look at \nmy patch series.\n\nThanks,\n-Stolee\n"},{"id":"329711","messageId":"xmqqfuay9ygs.fsf@gitster.mtv.corp.google.com","threadId":"46826","inReplyTo":"a6653525-94f2-fd7d-8c27-9334d473a556@gmail.com","subject":"Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-05T01:26:27Z","receivedAt":"2017-10-05T01:26:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> On 10/4/2017 2:07 AM, Junio C Hamano wrote:\n>> Derrick Stolee writes:\n>>\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>> The \"always_call_fn\" thing is a big sledgehammer that overrides\n>> everything else in update_candidates(). It bypasses the careful\n>> machinery set up to avoid having to open ambiguous object to learn\n>> their types as much as possible. One narrow exception when it is OK\n>> to use is if we never limit our candidates with type.\n>\n> I do not modify get_short_oid, which uses these advanced options,\n> depending on the flags given. find_unique_abbrev_r() does not use\n> these advanced options.\n\nIt is true that the function no longer even calls get_short_oid().\n\nWhen it called get_short_oid() before this patch, it not pass \"I\nwant to favor committish\" in the old code, as we can see in the\nabove removed code. In get_short_oid(), ds.fn would have been set\nto default_disambigutate_hint, and that would have been used in the\nupdate_candidates() function.\n\nNow, unless the user has core.disambiguate configuration set, this\n\"default\" thing becomes NULL, so overriding ds.fn like this patch\ndoes and bypass major parts of update_candidates() is probably fine.\nAfter all, update_candidates() wouldn't have inspected the object\ntypes and made the candidate management anyway with ds.fn set to\nNULL.\n\nBut having the configuration set would mean that the user wants to\nset default_disambigutate_hint to some non-default value, e.g.\ntelling us to find disambiguation only among committishes; the patch\nhowever overrides ds.fn and essentially makes the code ignore it\naltogether, no? That change in behaviour was what I was wondering\nabout.\n\n"},{"id":"329728","messageId":"20171005084249.sdkimglkxqh2vi4i@sigill.intra.peff.net","threadId":"46826","inReplyTo":"20170925095452.66833-2-dstolee@microsoft.com","subject":"Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-05T08:42:50Z","receivedAt":"2017-10-05T08:42:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Sep 25, 2017 at 05:54:48AM -0400, Derrick Stolee wrote:\n\n> Create test-list-objects helper program to output a random sample of\n> OIDs present in the repo.\n> \n> If no command line arguments are provided, all OIDs are output.\n\nThis is weirdly specific. Can we accomplish the same thing with existing\ntools?\n\nE.g., could:\n\n git cat-file --batch-all-objects --batch-check='%(objectname)' |\n shuffle |\n head -n 100\n\ndo the same thing?\n\nI know that \"shuffle\" isn't available everywhere, but I'd much rather\nsee us fill in portability gaps in a general way, rather than\nintroducing one-shot C code that needs to be maintained (and you\nwouldn't _think_ that t/helper programs need much maintenance, but try\nperusing \"git log t/helper\" output; they have to adapt to the same\ntree-wide changes as the rest of the code).\n\n-Peff\n"},{"id":"329729","messageId":"20171005085553.v3eqk73aaknt5fem@sigill.intra.peff.net","threadId":"46826","inReplyTo":"20170925095452.66833-3-dstolee@microsoft.com","subject":"Re: [PATCH v2 2/5] p0008-abbrev.sh: Test find_unique_abbrev() perf","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-05T08:55:53Z","receivedAt":"2017-10-05T08:56:02Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Sep 25, 2017 at 05:54:49AM -0400, Derrick Stolee wrote:\n\n> Create helper program test-abbrev to compute the minimum length of a\n> disambiguating short-sha for an input list of object ids.\n\nThis seems like something that Git ought to be able to do via real\ncommands.\n\nUsing \"log --stdin --no-walk --format=%h\" doesn't quite work, since it\nonly handles commits. We ought to be able to ask \"cat-file\" for this,\nthough. E.g., with the patch below you can do:\n\n git cat-file --batch-check='%(objectsize:short)' Perf test p0008-abbrev.sh runs test-abbrev for 100,000 object ids. For\n> test 0008.1, these objects exist. For test 0008.2 these objects do not\n> exist in the repo (with high probability). For each test, use `sort -R`\n> to (deterministically) shuffle the sample of object ids to not check\n> abbreviations in lexicographic order.\n\nI know you're not the first to add a test like this, but I'm somewhat\nnegative on these sorts of micro-benchmark perf tests. They're nice for\nshowing off an improvement, but there's little indication of how they\nimpact things that users actually do.\n\nWe know that this series makes finding abbreviations cheaper. But how\nmuch does it speed up \"git log --oneline\" on a real repository\n(including absurdly-sized ones)?\n\n-Peff\n"},{"id":"329730","messageId":"20171005085727.vdbli23n62xkiuq7@sigill.intra.peff.net","threadId":"46826","inReplyTo":"20171005085553.v3eqk73aaknt5fem@sigill.intra.peff.net","subject":"Re: [PATCH v2 2/5] p0008-abbrev.sh: Test find_unique_abbrev() perf","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-05T08:57:27Z","receivedAt":"2017-10-05T08:57:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 05, 2017 at 04:55:53AM -0400, Jeff King wrote:\n\n> On Mon, Sep 25, 2017 at 05:54:49AM -0400, Derrick Stolee wrote:\n> \n> > Create helper program test-abbrev to compute the minimum length of a\n> > disambiguating short-sha for an input list of object ids.\n> \n> This seems like something that Git ought to be able to do via real\n> commands.\n> \n> Using \"log --stdin --no-walk --format=%h\" doesn't quite work, since it\n> only handles commits. We ought to be able to ask \"cat-file\" for this,\n> though. E.g., with the patch below you can do:\n> \n> git cat-file --batch-check='%(objectsize:short)' \n> Or even just dispense with your earlier randomization helper and do:\n> \n> git cat-file --batch-all-objects --batch-check='%(objectsize:short)'\n> \n> to compute the abbreviation for every object.\n\nOf course it would help if I bothered to include the patch. Here it is.\n\ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex f5fa4fd75a..a5f911a632 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -225,6 +225,9 @@ static void expand_atom(struct strbuf *sb, const char *atom, int len,\n \tif (is_atom(\"objectname\", atom, len)) {\n \t\tif (!data->mark_query)\n \t\t\tstrbuf_addstr(sb, oid_to_hex(&data->oid));\n+\t} else if (is_atom(\"objectname:short\", atom, len)) {\n+\t\tif (!data->mark_query)\n+\t\t\tstrbuf_add_unique_abbrev(sb, data->oid.hash, MINIMUM_ABBREV);\n \t} else if (is_atom(\"objecttype\", atom, len)) {\n \t\tif (data->mark_query)\n \t\t\tdata->info.typep = &data->type;\n\n-Peff\n"},{"id":"329732","messageId":"20171005091334.7oyjaco432l5p6ft@sigill.intra.peff.net","threadId":"46826","inReplyTo":"xmqqtvzfcuoy.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-05T09:13:34Z","receivedAt":"2017-10-05T09:13:41Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 04, 2017 at 03:07:25PM +0900, Junio C Hamano wrote:\n\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> The \"always_call_fn\" thing is a big sledgehammer that overrides\n> everything else in update_candidates(). It bypasses the careful\n> machinery set up to avoid having to open ambiguous object to learn\n> their types as much as possible. One narrow exception when it is OK\n> to use is if we never limit our candidates with type.\n> \n> And it might appear that the conversion is safe (if only because we\n> do not see any type limitation in the get_short_oid() call above),\n> but I think there is one case where this patch changes the\n> behaviour: what happens if core.disambiguate was set to anything\n> other than \"none\"? The new code does not know anything about type\n> based filtering, so it can end up reporting longer abbreviation than\n> it was asked to produce. It may not be a problem in practice, though.\n> \n> I am not sure if setting core.disambiguate is generally a good idea\n> in the first place, and if it is OK to break find_unique_abbrev()\n> with respect to the configuration variable like this patch does.\n> \n> I'd feel safe if we get extra input from Peff, who introduced the\n> feature in 5b33cb1f (\"get_short_sha1: make default disambiguation\n> configurable\", 2016-09-27).\n\nRegarding core.disambiguate, I _do_ think it's reasonable to set it to\n\"commit\" or \"committish\". And in fact I have meant to revisit the idea\nof doing so by default (the reason it was made into config at all was to\nlet people play around with it and gain experience).\n\nThat said, I think it's entirely reasonable for find_unique_abbrev() to\nignore type-based disambiguation entirely.\n\nThe type disambiguation is really a property of the context in which we\ndo a lookup. And that context is not necessarily known to the generating\nside. Even core.disambiguate is not universal, as command-specific\ncontext overrides it.\n\nSo I think on the generating side we are better off creating a slightly\nlonger abbreviation that is unambiguous no matter what context it is\nused in. I.e., I'd argue that it's actually more _correct_ to ignore\nthe disambiguation code entirely on the generating side.\n\nAnd it should also be faster, because it turns the abbreviation search\ninto a purely textual one that never has to look at extra objects. And\nthat speed matters a lot more on the generating side, where we tend to\noutput long lists of abbreviated sha1s in commands like \"git log\" (as\nopposed to the lookup side, where we're asked to find some particular\nitem of interest).\n\n-Peff\n"},{"id":"329737","messageId":"20171005094418.irm6omly67bgyvo7@sigill.intra.peff.net","threadId":"46826","inReplyTo":"20171002145651.204984-6-dstolee@microsoft.com","subject":"Re: [PATCH v3 5/5] sha1_name: Minimize OID comparisons during disambiguation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-05T09:44:18Z","receivedAt":"2017-10-05T09:44:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Oct 02, 2017 at 10:56:51AM -0400, Derrick Stolee wrote:\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) / 2;\n\nThis can overflow if we are looking past 2^31. Probably not very common\n(things seem to get pretty painful at hundreds of millions of objects).\nBut it can be written as:\n\n uint32_t mid = lo + (hi - lo) / 2;\n\nSadly, this overflow case seems to be present in many of our binary\nsearches.\n\n> +\t\tconst unsigned char *current;\n> +\t\tint cmp;\n> +\n> +\t\tcurrent = nth_packed_object_sha1(p, mid);\n\nnth_packed_object_sha1() has to do some minor computation to come up\nwith the correct pointer. The normal packfile lookup precomputes the\ninitial offset and stride outside the loop. I have no idea if that\nmicro-optimization is actually noticeable, but I thought I'd mention it\nas a possible avenue for investigation since you're obviously interested\nin squeezing out performance. ;)\n\n-Peff\n"},{"id":"329738","messageId":"xmqqvaju6i3p.fsf@gitster.mtv.corp.google.com","threadId":"46826","inReplyTo":"20171005084249.sdkimglkxqh2vi4i@sigill.intra.peff.net","subject":"Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-05T09:48:10Z","receivedAt":"2017-10-05T09:48:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> This is weirdly specific. Can we accomplish the same thing with existing\n> tools?\n>\n> E.g., could:\n>\n> git cat-file --batch-all-objects --batch-check='%(objectname)' |\n> shuffle |\n> head -n 100\n>\n> do the same thing?\n>\n> I know that \"shuffle\" isn't available everywhere, but I'd much rather\n> see us fill in portability gaps in a general way, rather than\n> introducing one-shot C code that needs to be maintained (and you\n> wouldn't _think_ that t/helper programs need much maintenance, but try\n> perusing \"git log t/helper\" output; they have to adapt to the same\n> tree-wide changes as the rest of the code).\n\nI was thinking about this a bit more, and came to the conclusion\nthat \"sort -R\" and \"shuf\" are wrong tools to use. We would want to\nmeasure with something close to real world workload. for example,\nletting\n\n\tgit rev-list --all --objects\n\nproduce the listof objects in traversal order (i.e. this is very\nsimilar to the order in which \"git log -p\" needs to access the\nobjects) and chomping at the number of sample objects you need in\nyour test would give you such a list.\n"},{"id":"329739","messageId":"20171005094939.uzizbh6dfhapkqho@sigill.intra.peff.net","threadId":"46826","inReplyTo":"20171002145651.204984-1-dstolee@microsoft.com","subject":"Re: [PATCH v3 0/5] Improve abbreviation disambituation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-05T09:49:39Z","receivedAt":"2017-10-05T09:49:46Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Oct 02, 2017 at 10:56:46AM -0400, Derrick Stolee wrote:\n\n> Thanks for the feedback on my previous versions, and for patience\n> with my inexperience on the mailing list. I tried to respond to all\n> feedback, but decided to not apply one suggestion:\n\nFor what it's worth, the optimizations here look sound overall. Like\nJunio, I was concerned at the loss of performance from patch 3 at first.\nAfter looking at your numbers, though, I think it really is just the\ncost of oid_to_hex() that is then eliminated in patch 4.\n\nI had a few nits to pick on the perf-test setup, but I stupidly sent\nthem in response to v2 (and so missed cc-ing several folks involved in\nreview). I think they apply equally to v3, though.\n\n-Peff\n"},{"id":"329740","messageId":"xmqqr2uh7wjs.fsf@gitster.mtv.corp.google.com","threadId":"46826","inReplyTo":"20171005091334.7oyjaco432l5p6ft@sigill.intra.peff.net","subject":"Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-05T09:50:47Z","receivedAt":"2017-10-05T09:50:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> So I think on the generating side we are better off creating a slightly\n> longer abbreviation that is unambiguous no matter what context it is\n> used in. I.e., I'd argue that it's actually more _correct_ to ignore\n> the disambiguation code entirely on the generating side.\n\nOK. Thanks for sanity checking.\n"},{"id":"329742","messageId":"20171005100001.do5m4zhexcsltvw7@sigill.intra.peff.net","threadId":"46826","inReplyTo":"xmqqvaju6i3p.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-05T10:00:02Z","receivedAt":"2017-10-05T10:00:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 05, 2017 at 06:48:10PM +0900, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > This is weirdly specific. Can we accomplish the same thing with existing\n> > tools?\n> >\n> > E.g., could:\n> >\n> > git cat-file --batch-all-objects --batch-check='%(objectname)' |\n> > shuffle |\n> > head -n 100\n> >\n> > do the same thing?\n> >\n> > I know that \"shuffle\" isn't available everywhere, but I'd much rather\n> > see us fill in portability gaps in a general way, rather than\n> > introducing one-shot C code that needs to be maintained (and you\n> > wouldn't _think_ that t/helper programs need much maintenance, but try\n> > perusing \"git log t/helper\" output; they have to adapt to the same\n> > tree-wide changes as the rest of the code).\n> \n> I was thinking about this a bit more, and came to the conclusion\n> that \"sort -R\" and \"shuf\" are wrong tools to use. We would want to\n> measure with something close to real world workload. for example,\n> letting\n> \n> \tgit rev-list --all --objects\n> \n> produce the listof objects in traversal order (i.e. this is very\n> similar to the order in which \"git log -p\" needs to access the\n> objects) and chomping at the number of sample objects you need in\n> your test would give you such a list.\n\nActually, I'd just as soon see timings for \"git log --format=%h\" or \"git\nlog --raw\", as opposed to patches 1 and 2.\n\nYou won't see a 90% speedup there, but you will see the actual\nimprovement that real-world users are going to experience, which is way\nmore important, IMHO.\n\n-Peff\n"},{"id":"329745","messageId":"CAPc5daVKNgU8XsUnBDYYutFqZt_RmTomKGCV5GEsFN6+6==jmA@mail.gmail.com","threadId":"46826","inReplyTo":"20171005100001.do5m4zhexcsltvw7@sigill.intra.peff.net","subject":"Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-05T10:16:14Z","receivedAt":"2017-10-05T10:16:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"On Thu, Oct 5, 2017 at 7:00 PM, Jeff King wrote:\n>\n>> Jeff King writes:\n>>\n> Actually, I'd just as soon see timings for \"git log --format=%h\" or \"git\n> log --raw\", as opposed to patches 1 and 2.\n>\n> You won't see a 90% speedup there, but you will see the actual\n> improvement that real-world users are going to experience, which is way\n> more important, IMHO.\n\nYup, \"log --raw -r\" would really exercise the abbreviation machinery\nwithout spending time on the diff machinery, and it would be a good\ntest.\n"},{"id":"329763","messageId":"6222f65a-c518-74a4-9df4-89bf997425cb@gmail.com","threadId":"46826","inReplyTo":"20171005100001.do5m4zhexcsltvw7@sigill.intra.peff.net","subject":"Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2017-10-05T12:39:42Z","receivedAt":"2017-10-05T12:39:51Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"\n\nOn 10/5/2017 6:00 AM, Jeff King wrote:\n> On Thu, Oct 05, 2017 at 06:48:10PM +0900, Junio C Hamano wrote:\n>\n>> Jeff King writes:\n>>\n>>> This is weirdly specific. Can we accomplish the same thing with existing\n>>> tools?\n>>>\n>>> E.g., could:\n>>>\n>>> git cat-file --batch-all-objects --batch-check='%(objectname)' |\n>>> shuffle |\n>>> head -n 100\n>>>\n>>> do the same thing?\n>>>\n>>> I know that \"shuffle\" isn't available everywhere, but I'd much rather\n>>> see us fill in portability gaps in a general way, rather than\n>>> introducing one-shot C code that needs to be maintained (and you\n>>> wouldn't _think_ that t/helper programs need much maintenance, but try\n>>> perusing \"git log t/helper\" output; they have to adapt to the same\n>>> tree-wide changes as the rest of the code).\n>> I was thinking about this a bit more, and came to the conclusion\n>> that \"sort -R\" and \"shuf\" are wrong tools to use. We would want to\n>> measure with something close to real world workload. for example,\n>> letting\n>>\n>> \tgit rev-list --all --objects\n>>\n>> produce the listof objects in traversal order (i.e. this is very\n>> similar to the order in which \"git log -p\" needs to access the\n>> objects) and chomping at the number of sample objects you need in\n>> your test would give you such a list.\n> Actually, I'd just as soon see timings for \"git log --format=%h\" or \"git\n> log --raw\", as opposed to patches 1 and 2.\n>\n> You won't see a 90% speedup there, but you will see the actual\n> improvement that real-world users are going to experience, which is way\n> more important, IMHO.\n>\n> -Peff\nThanks for thinking hard about this.\n\nFor some real-user context: Some engineers using Git for the Windows \nrepo were seeing extremely slow commands, such as 'fetch' or 'commit', \nand when we took a trace we saw most of the time spinning in this \nabbreviation code. Our workaround so far has been to set core.abbrev=40.\n\nI'll run some perf numbers for these commands you recommend, and also \nsee if I can replicate some of the pain points that triggered this \nchange using the Linux repo.\n\nThanks,\n-Stolee\n"},{"id":"329887","messageId":"20171006135231.239232-1-dstolee@microsoft.com","threadId":"46826","inReplyTo":"20171005094418.irm6omly67bgyvo7@sigill.intra.peff.net","subject":"[PATCH] cleanup: fix possible overflow errors in binary search","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-06T13:52:31Z","receivedAt":"2017-10-06T13:53:03Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"A common mistake when writing binary search is to allow possible\ninteger overflow by using the simple average:\n\n\tmid = (min + max) / 2;\n\nInstead, use the overflow-safe version:\n\n\tmid = min + (max - min) / 2;\n\nThe included changes were found using the following two greps:\n\n\tgrep \"/ 2;\" *.c\n\tgrep \"/ 2;\" */*.c\n\tgrep \"/2;\" */*.c\n\nMaking this cleanup will prevent future review friction when a new\nbinary search is contructed based on existing code.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/index-pack.c | 4 ++--\n builtin/pack-objects.c | 2 +-\n builtin/unpack-objects.c | 2 +-\n cache-tree.c | 2 +-\n packfile.c | 2 +-\n sha1-lookup.c | 2 +-\n sha1_name.c | 2 +-\n string-list.c | 2 +-\n utf8.c | 2 +-\n xdiff/xpatience.c | 2 +-\n 10 files changed, 11 insertions(+), 11 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex f2be145e1..8ec459f52 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -633,7 +633,7 @@ static int find_ofs_delta(const off_t offset, enum object_type type)\n \tint first = 0, last = nr_ofs_deltas;\n \n \twhile (first < last) {\n-\t\tint next = (first + last) / 2;\n+\t\tint next = first + (last - first) / 2;\n \t\tstruct ofs_delta_entry *delta = &ofs_deltas[next];\n \t\tint cmp;\n \n@@ -687,7 +687,7 @@ static int find_ref_delta(const unsigned char *sha1, enum object_type type)\n \tint first = 0, last = nr_ref_deltas;\n \n \twhile (first < last) {\n-\t\tint next = (first + last) / 2;\n+\t\tint next = first + (last - first) / 2;\n \t\tstruct ref_delta_entry *delta = &ref_deltas[next];\n \t\tint cmp;\n \ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 5ee2c48ff..6e77dfd44 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1277,7 +1277,7 @@ static int done_pbase_path_pos(unsigned hash)\n \tint lo = 0;\n \tint hi = done_pbase_paths_num;\n \twhile (lo < hi) {\n-\t\tint mi = (hi + lo) / 2;\n+\t\tint mi = lo + (hi - lo) / 2;\n \t\tif (done_pbase_paths[mi] == hash)\n \t\t\treturn mi;\n \t\tif (done_pbase_paths[mi] < hash)\ndiff --git a/builtin/unpack-objects.c b/builtin/unpack-objects.c\nindex 689a29fac..62ea264c4 100644\n--- a/builtin/unpack-objects.c\n+++ b/builtin/unpack-objects.c\n@@ -394,7 +394,7 @@ static void unpack_delta_entry(enum object_type type, unsigned long delta_size,\n \t\tlo = 0;\n \t\thi = nr;\n \t\twhile (lo < hi) {\n-\t\t\tmid = (lo + hi)/2;\n+\t\t\tmid = lo + (hi - lo) / 2;\n \t\t\tif (base_offset < obj_list[mid].offset) {\n \t\t\t\thi = mid;\n \t\t\t} else if (base_offset > obj_list[mid].offset) {\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 71d092ed5..d3f740127 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -49,7 +49,7 @@ static int subtree_pos(struct cache_tree *it, const char *path, int pathlen)\n \tlo = 0;\n \thi = it->subtree_nr;\n \twhile (lo < hi) {\n-\t\tint mi = (lo + hi) / 2;\n+\t\tint mi = lo + (hi - lo) / 2;\n \t\tstruct cache_tree_sub *mdl = down[mi];\n \t\tint cmp = subtree_name_cmp(path, pathlen,\n \t\t\t\t\t mdl->name, mdl->namelen);\ndiff --git a/packfile.c b/packfile.c\nindex eab754248..4a5fe7ab1 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1743,7 +1743,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \t\t sha1[0], sha1[1], sha1[2], lo, hi, p->num_objects);\n \n \twhile (lo < hi) {\n-\t\tunsigned mi = (lo + hi) / 2;\n+\t\tunsigned mi = lo + (hi - lo) / 2;\n \t\tint cmp = hashcmp(index + mi * stride, sha1);\n \n \t\tif (debug_lookup)\ndiff --git a/sha1-lookup.c b/sha1-lookup.c\nindex 2552b7902..df08f8355 100644\n--- a/sha1-lookup.c\n+++ b/sha1-lookup.c\n@@ -95,7 +95,7 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr,\n \t\t\thi = mi;\n \t\telse\n \t\t\tlo = mi + 1;\n-\t\tmi = (hi + lo) / 2;\n+\t\tmi = lo + (hi - lo) / 2;\n \t} while (lo < hi);\n \treturn -lo-1;\n }\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 134ac9742..c7c5ab376 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -157,7 +157,7 @@ static void unique_in_pack(struct packed_git *p,\n \tnum = p->num_objects;\n \tlast = num;\n \twhile (first < last) {\n-\t\tuint32_t mid = (first + last) / 2;\n+\t\tuint32_t mid = first + (last - first) / 2;\n \t\tconst unsigned char *current;\n \t\tint cmp;\n \ndiff --git a/string-list.c b/string-list.c\nindex 806b4c872..a0cf0cfe8 100644\n--- a/string-list.c\n+++ b/string-list.c\n@@ -16,7 +16,7 @@ static int get_entry_index(const struct string_list *list, const char *string,\n \tcompare_strings_fn cmp = list->cmp ? list->cmp : strcmp;\n \n \twhile (left + 1 < right) {\n-\t\tint middle = (left + right) / 2;\n+\t\tint middle = left + (right - left) / 2;\n \t\tint compare = cmp(string, list->items[middle].string);\n \t\tif (compare < 0)\n \t\t\tright = middle;\ndiff --git a/utf8.c b/utf8.c\nindex 47a42047c..2c27ce013 100644\n--- a/utf8.c\n+++ b/utf8.c\n@@ -32,7 +32,7 @@ static int bisearch(ucs_char_t ucs, const struct interval *table, int max)\n \tif (ucs < table[0].first || ucs > table[max].last)\n \t\treturn 0;\n \twhile (max >= min) {\n-\t\tmid = (min + max) / 2;\n+\t\tmid = min + (max - min) / 2;\n \t\tif (ucs > table[mid].last)\n \t\t\tmin = mid + 1;\n \t\telse if (ucs < table[mid].first)\ndiff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\nindex a613efc70..9f91702de 100644\n--- a/xdiff/xpatience.c\n+++ b/xdiff/xpatience.c\n@@ -166,7 +166,7 @@ static int binary_search(struct entry **sequence, int longest,\n \tint left = -1, right = longest;\n \n \twhile (left + 1 < right) {\n-\t\tint middle = (left + right) / 2;\n+\t\tint middle = left + (right - left) / 2;\n \t\t/* by construction, no two entries can be equal */\n \t\tif (sequence[middle]->line2 > entry->line2)\n \t\t\tright = middle;\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"329888","messageId":"20171006141128.rkuhd4m7hp2f7vvx@sigill.intra.peff.net","threadId":"46826","inReplyTo":"6222f65a-c518-74a4-9df4-89bf997425cb@gmail.com","subject":"Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-06T14:11:28Z","receivedAt":"2017-10-06T14:11:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 05, 2017 at 08:39:42AM -0400, Derrick Stolee wrote:\n\n> > Actually, I'd just as soon see timings for \"git log --format=%h\" or \"git\n> > log --raw\", as opposed to patches 1 and 2.\n> > \n> > You won't see a 90% speedup there, but you will see the actual\n> > improvement that real-world users are going to experience, which is way\n> > more important, IMHO.\n> > \n> Thanks for thinking hard about this.\n> \n> For some real-user context: Some engineers using Git for the Windows repo\n> were seeing extremely slow commands, such as 'fetch' or 'commit', and when\n> we took a trace we saw most of the time spinning in this abbreviation code.\n\nThat's surprising to me. I'd expect fetch to generate up to two\nabbreviations per fetched ref (for the status table). And for commit to\ngenerate only one for the summary. But maybe it was just so painfully\nslow on your repo that it was noticeable.\n\nIf there's a case where we're generating a bunch of abbreviated oids,\nthat might be worth looking into. Do you happen to have a stack trace of\none of the slow cases showing who is calling into the function?\n\n> Our workaround so far has been to set core.abbrev=40.\n\nI actually wondered about this. With the new auto-scaling, we'd\ntypically jump straight to 12 or 13 hex-chars on a large repo, and that\nwould be sufficient. So we'd really only need one iteration of the loop.\n\n> I'll run some perf numbers for these commands you recommend, and also see if\n> I can replicate some of the pain points that triggered this change using the\n> Linux repo.\n\nThanks!\n\n-Peff\n"},{"id":"329889","messageId":"20171006141820.6vd3qt6iosxcgebm@sigill.intra.peff.net","threadId":"46826","inReplyTo":"20171006135231.239232-1-dstolee@microsoft.com","subject":"Re: [PATCH] cleanup: fix possible overflow errors in binary search","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-06T14:18:20Z","receivedAt":"2017-10-06T14:18:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Oct 06, 2017 at 09:52:31AM -0400, Derrick Stolee wrote:\n\n> A common mistake when writing binary search is to allow possible\n> integer overflow by using the simple average:\n> \n> \tmid = (min + max) / 2;\n> \n> Instead, use the overflow-safe version:\n> \n> \tmid = min + (max - min) / 2;\n\nGreat, thank you for picking this up!\n\n> The included changes were found using the following two greps:\n> \n> \tgrep \"/ 2;\" *.c\n> \tgrep \"/ 2;\" */*.c\n> \tgrep \"/2;\" */*.c\n\nYou can use[1]:\n\n git grep '/ 2;' '*.c'\n\nto have Git expand the wildcard. That catches a few extra cases in\ncompat/regex/*.c. Even though it's imported code, it might be\nnice to cover those, too (since it's a possible bug, and also as a good\nexample).\n\n[1] I'd actually write:\n\n git grep '/ *2;' '*.c'\n\n to do it all in one grep. :)\n\n> ---\n> builtin/index-pack.c | 4 ++--\n> builtin/pack-objects.c | 2 +-\n> builtin/unpack-objects.c | 2 +-\n> cache-tree.c | 2 +-\n> packfile.c | 2 +-\n> sha1-lookup.c | 2 +-\n> sha1_name.c | 2 +-\n> string-list.c | 2 +-\n> utf8.c | 2 +-\n> xdiff/xpatience.c | 2 +-\n> 10 files changed, 11 insertions(+), 11 deletions(-)\n\nThese all look good to me (really the only way the conversion could be\nbad is if \"min\" was higher than \"max\", and each case is just inside a\nloop condition which makes sure that is not the case).\n\n-Peff\n"},{"id":"329895","messageId":"bd3c5fe2-ac6a-b978-163b-da07208b879c@gmail.com","threadId":"46826","inReplyTo":"20171006141820.6vd3qt6iosxcgebm@sigill.intra.peff.net","subject":"Re: [PATCH] cleanup: fix possible overflow errors in binary search","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2017-10-06T14:41:12Z","receivedAt":"2017-10-06T14:41:19Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/6/2017 10:18 AM, Jeff King wrote:\n> On Fri, Oct 06, 2017 at 09:52:31AM -0400, Derrick Stolee wrote:\n>\n>> A common mistake when writing binary search is to allow possible\n>> integer overflow by using the simple average:\n>>\n>> \tmid = (min + max) / 2;\n>>\n>> Instead, use the overflow-safe version:\n>>\n>> \tmid = min + (max - min) / 2;\n> Great, thank you for picking this up!\n>\n>> The included changes were found using the following two greps:\n>>\n>> \tgrep \"/ 2;\" *.c\n>> \tgrep \"/ 2;\" */*.c\n>> \tgrep \"/2;\" */*.c\n> You can use[1]:\n>\n> git grep '/ 2;' '*.c'\n>\n> to have Git expand the wildcard. That catches a few extra cases in\n> compat/regex/*.c. Even though it's imported code, it might be\n> nice to cover those, too (since it's a possible bug, and also as a good\n> example).\n>\n> [1] I'd actually write:\n>\n> git grep '/ *2;' '*.c'\n>\n> to do it all in one grep. :)\n\nThanks for the grep lesson! I knew there would be a simpler way to do \nwhat I wanted.\n\n>> ---\n>> builtin/index-pack.c | 4 ++--\n>> builtin/pack-objects.c | 2 +-\n>> builtin/unpack-objects.c | 2 +-\n>> cache-tree.c | 2 +-\n>> packfile.c | 2 +-\n>> sha1-lookup.c | 2 +-\n>> sha1_name.c | 2 +-\n>> string-list.c | 2 +-\n>> utf8.c | 2 +-\n>> xdiff/xpatience.c | 2 +-\n>> 10 files changed, 11 insertions(+), 11 deletions(-)\n> These all look good to me (really the only way the conversion could be\n> bad is if \"min\" was higher than \"max\", and each case is just inside a\n> loop condition which makes sure that is not the case).\n>\n> -Peff\nI thought this should be simple enough. When we are all happy with the \nidea of this cleanup, I'll re-roll with the missed examples.\n\nThanks,\n-Stolee\n"},{"id":"329966","messageId":"d5b3107f-76ec-8e8c-d7f5-d0f1ec75b1c9@gmail.com","threadId":"46826","inReplyTo":"20171006141128.rkuhd4m7hp2f7vvx@sigill.intra.peff.net","subject":"Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2017-10-07T19:12:08Z","receivedAt":"2017-10-07T19:12:21Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/6/2017 10:11 AM, Jeff King wrote:\n> On Thu, Oct 05, 2017 at 08:39:42AM -0400, Derrick Stolee wrote:\n>> I'll run some perf numbers for these commands you recommend, and also see if\n>> I can replicate some of the pain points that triggered this change using the\n>> Linux repo.\n> \n> Thanks!\n> \n> -Peff\n> \n\nIn my local copy, I added a test to p4211-line-log.sh that runs \"git log \n--raw -r\" and tested it on three copies of the Linux repo. In order, \nthey have 1 packfile (0 loose), 24 packfiles (0 loose), and 23 packfiles \n(~324,000 loose).\n\n4211.6: git log --raw -r 43.34(42.62+0.65) 40.47(40.16+0.27) -6.6%\n4211.6: git log --raw -r 88.77(86.54+2.12) 82.44(81.87+0.52) -7.1%\n4211.6: git log --raw -r 108.86(103.97+4.81) 103.92(100.63+3.19) -4.5%\n\nWe have moderate performance gains for this command, despite the command \ndoing many more things than just checking abbreviations.\n\nI plan to re-roll my patch on Monday including the following feedback items:\n\n* Remove test-list-objects and test-abbrev in favor of a new \"git log\"\n performance test.\n\n* Fix binary search overflow error.\n\n* Check response from open_pack_index(p) in find_abbrev_len_for_pack().\n I plan to return without failure on non-zero result, which results in\n no failure on a bad pack and the abbreviation length will be the\n minimum required among all valid packs. (Thanks Stefan!)\n\nI made note of a few things, but will not include them in my re-roll. \nI'll revisit them later if they are valuable:\n\n- nth_packed_object_sha1() could be simplified in\n find_abbrev_len_for_pack().\n\n- Teach 'cat-file' to --batch-check='%(objectsize:short)'. (Peff already\n included a patch, perhaps that could be reviewed separately.)\n\n- Ramsay caught my lack of \"static\" in test-list-objects.c, but that\n file will be removed in the next patch. I'll make sure to use \"static\"\n in the future.\n\nI'm not re-rolling immediately to allow for some extra review over the \nweekend, if anyone is so inclined.\n\nThanks,\n-Stolee\n"},{"id":"329969","messageId":"20171007193311.c2izgofpyh357yi7@sigill.intra.peff.net","threadId":"46826","inReplyTo":"d5b3107f-76ec-8e8c-d7f5-d0f1ec75b1c9@gmail.com","subject":"Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-07T19:33:11Z","receivedAt":"2017-10-07T19:33:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Oct 07, 2017 at 03:12:08PM -0400, Derrick Stolee wrote:\n\n> In my local copy, I added a test to p4211-line-log.sh that runs \"git log\n> --raw -r\" and tested it on three copies of the Linux repo. In order, they\n> have 1 packfile (0 loose), 24 packfiles (0 loose), and 23 packfiles\n> (~324,000 loose).\n> \n> 4211.6: git log --raw -r 43.34(42.62+0.65) 40.47(40.16+0.27) -6.6%\n> 4211.6: git log --raw -r 88.77(86.54+2.12) 82.44(81.87+0.52) -7.1%\n> 4211.6: git log --raw -r 108.86(103.97+4.81) 103.92(100.63+3.19) -4.5%\n> \n> We have moderate performance gains for this command, despite the command\n> doing many more things than just checking abbreviations.\n\nYeah, while it's less exciting than seeing the 90% numbers for a\nmicro-benchmark, I think this represents real-world gains (and 5-7% is\nnothing to sneeze at).\n\nYou might also try adding \"--format=%h\" or --oneline to your invocation,\nwhich would compute abbreviations for each commit (making your workload\nmore abbrev-heavy and possibly showing off the difference more).\n\nI also think \"-r\" isn't doing anything. Recursive diffs are the default\nfor the \"log\" porcelain (even for --raw).\n\n> I plan to re-roll my patch on Monday including the following feedback items:\n> \n> * Remove test-list-objects and test-abbrev in favor of a new \"git log\"\n> performance test.\n> \n> * Fix binary search overflow error.\n> \n> * Check response from open_pack_index(p) in find_abbrev_len_for_pack().\n> I plan to return without failure on non-zero result, which results in\n> no failure on a bad pack and the abbreviation length will be the\n> minimum required among all valid packs. (Thanks Stefan!)\n\nThat all sounds reasonable to me.\n\n> - Teach 'cat-file' to --batch-check='%(objectsize:short)'. (Peff already\n> included a patch, perhaps that could be reviewed separately.)\n\nI think I'll let it lie in the list archive for now unless somebody has\na real use case for it (though I'm tempted to add it purely for\ncompletionism, since it's so easy).\n\n-Peff\n"},{"id":"329977","messageId":"xmqqh8vatnr2.fsf@gitster.mtv.corp.google.com","threadId":"46826","inReplyTo":"20171007193311.c2izgofpyh357yi7@sigill.intra.peff.net","subject":"Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-08T01:46:41Z","receivedAt":"2017-10-08T01:46:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Sat, Oct 07, 2017 at 03:12:08PM -0400, Derrick Stolee wrote:\n>\n>> In my local copy, I added a test to p4211-line-log.sh that runs \"git log\n>> --raw -r\" and tested it on three copies of the Linux repo. In order, they\n>> have 1 packfile (0 loose), 24 packfiles (0 loose), and 23 packfiles\n>> (~324,000 loose).\n>> \n>> 4211.6: git log --raw -r 43.34(42.62+0.65) 40.47(40.16+0.27) -6.6%\n>> 4211.6: git log --raw -r 88.77(86.54+2.12) 82.44(81.87+0.52) -7.1%\n>> 4211.6: git log --raw -r 108.86(103.97+4.81) 103.92(100.63+3.19) -4.5%\n>> \n>> We have moderate performance gains for this command, despite the command\n>> doing many more things than just checking abbreviations.\n>\n> Yeah, while it's less exciting than seeing the 90% numbers for a\n> micro-benchmark, I think this represents real-world gains (and 5-7% is\n> nothing to sneeze at).\n\nYes! I would even say 5-7% is much better than \"nothing to sneeze\nat\". We do prefer workload closer to the real-world usage over\nmicro benchmarks, and consider changes that gain by a few percent as\nreal improvements.\n\n> You might also try adding \"--format=%h\" or --oneline to your invocation,\n> which would compute abbreviations for each commit (making your workload\n> more abbrev-heavy and possibly showing off the difference more).\n\nAgain, agreed, and I would not consider it would be inflating the\nbenchmark artificially in favor of the change. \"log --oneline\" is\nnot something people use rarely---I'd think it would be quite a\nnormal thing to do.\n\n> I also think \"-r\" isn't doing anything. Recursive diffs are the default\n> for the \"log\" porcelain (even for --raw).\n\nThat's my fault writing \"-r\" ;-) Together with your \"log --oneline\"\nsuggestion,\n\n\tgit log --oneline --raw\n\nwould be a reasonable thing to measure.\n\nThanks, both.\n"},{"id":"329994","messageId":"20171008182937.69205-1-dstolee@microsoft.com","threadId":"46826","inReplyTo":"bd3c5fe2-ac6a-b978-163b-da07208b879c@gmail.com","subject":"[PATCH v2] cleanup: fix possible overflow errors in binary search","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-10-08T18:29:37Z","receivedAt":"2017-10-08T18:29:57Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"A common mistake when writing binary search is to allow possible\ninteger overflow by using the simple average:\n\n\tmid = (min + max) / 2;\n\nInstead, use the overflow-safe version:\n\n\tmid = min + (max - min) / 2;\n\nThis translation is safe since the operation occurs inside a loop\nconditioned on \"min < max\". The included changes were found using\nthe following git grep:\n\n\tgit grep '/ *2;' '*.c'\n\nMaking this cleanup will prevent future review friction when a new\nbinary search is contructed based on existing code.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/index-pack.c | 4 ++--\n builtin/pack-objects.c | 2 +-\n builtin/unpack-objects.c | 2 +-\n cache-tree.c | 2 +-\n compat/regex/regex_internal.c | 4 ++--\n compat/regex/regexec.c | 2 +-\n packfile.c | 2 +-\n sha1-lookup.c | 4 ++--\n sha1_name.c | 2 +-\n string-list.c | 2 +-\n utf8.c | 2 +-\n xdiff/xpatience.c | 2 +-\n 12 files changed, 15 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex f2be145e1..8ec459f52 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -633,7 +633,7 @@ static int find_ofs_delta(const off_t offset, enum object_type type)\n \tint first = 0, last = nr_ofs_deltas;\n \n \twhile (first < last) {\n-\t\tint next = (first + last) / 2;\n+\t\tint next = first + (last - first) / 2;\n \t\tstruct ofs_delta_entry *delta = &ofs_deltas[next];\n \t\tint cmp;\n \n@@ -687,7 +687,7 @@ static int find_ref_delta(const unsigned char *sha1, enum object_type type)\n \tint first = 0, last = nr_ref_deltas;\n \n \twhile (first < last) {\n-\t\tint next = (first + last) / 2;\n+\t\tint next = first + (last - first) / 2;\n \t\tstruct ref_delta_entry *delta = &ref_deltas[next];\n \t\tint cmp;\n \ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 5ee2c48ff..6e77dfd44 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1277,7 +1277,7 @@ static int done_pbase_path_pos(unsigned hash)\n \tint lo = 0;\n \tint hi = done_pbase_paths_num;\n \twhile (lo < hi) {\n-\t\tint mi = (hi + lo) / 2;\n+\t\tint mi = lo + (hi - lo) / 2;\n \t\tif (done_pbase_paths[mi] == hash)\n \t\t\treturn mi;\n \t\tif (done_pbase_paths[mi] < hash)\ndiff --git a/builtin/unpack-objects.c b/builtin/unpack-objects.c\nindex 689a29fac..62ea264c4 100644\n--- a/builtin/unpack-objects.c\n+++ b/builtin/unpack-objects.c\n@@ -394,7 +394,7 @@ static void unpack_delta_entry(enum object_type type, unsigned long delta_size,\n \t\tlo = 0;\n \t\thi = nr;\n \t\twhile (lo < hi) {\n-\t\t\tmid = (lo + hi)/2;\n+\t\t\tmid = lo + (hi - lo) / 2;\n \t\t\tif (base_offset < obj_list[mid].offset) {\n \t\t\t\thi = mid;\n \t\t\t} else if (base_offset > obj_list[mid].offset) {\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 71d092ed5..d3f740127 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -49,7 +49,7 @@ static int subtree_pos(struct cache_tree *it, const char *path, int pathlen)\n \tlo = 0;\n \thi = it->subtree_nr;\n \twhile (lo < hi) {\n-\t\tint mi = (lo + hi) / 2;\n+\t\tint mi = lo + (hi - lo) / 2;\n \t\tstruct cache_tree_sub *mdl = down[mi];\n \t\tint cmp = subtree_name_cmp(path, pathlen,\n \t\t\t\t\t mdl->name, mdl->namelen);\ndiff --git a/compat/regex/regex_internal.c b/compat/regex/regex_internal.c\nindex d4121f2f4..98342b831 100644\n--- a/compat/regex/regex_internal.c\n+++ b/compat/regex/regex_internal.c\n@@ -613,7 +613,7 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags)\n \t int low = 0, high = pstr->valid_len, mid;\n \t do\n \t\t{\n-\t\t mid = (high + low) / 2;\n+\t\t mid = low + (high - low) / 2;\n \t\t if (pstr->offsets[mid] > offset)\n \t\t high = mid;\n \t\t else if (pstr->offsets[mid] < offset)\n@@ -1394,7 +1394,7 @@ re_node_set_contains (const re_node_set *set, int elem)\n right = set->nelem - 1;\n while (idx < right)\n {\n- mid = (idx + right) / 2;\n+ mid = idx + (right - idx) / 2;\n if (set->elems[mid] < elem)\n \tidx = mid + 1;\n else\ndiff --git a/compat/regex/regexec.c b/compat/regex/regexec.c\nindex 0a745d9c3..6f2b48a78 100644\n--- a/compat/regex/regexec.c\n+++ b/compat/regex/regexec.c\n@@ -4284,7 +4284,7 @@ search_cur_bkref_entry (const re_match_context_t *mctx, int str_idx)\n last = right = mctx->nbkref_ents;\n for (left = 0; left < right;)\n {\n- mid = (left + right) / 2;\n+ mid = left + (right - left) / 2;\n if (mctx->bkref_ents[mid].str_idx < str_idx)\n \tleft = mid + 1;\n else\ndiff --git a/packfile.c b/packfile.c\nindex eab754248..4a5fe7ab1 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1743,7 +1743,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \t\t sha1[0], sha1[1], sha1[2], lo, hi, p->num_objects);\n \n \twhile (lo < hi) {\n-\t\tunsigned mi = (lo + hi) / 2;\n+\t\tunsigned mi = lo + (hi - lo) / 2;\n \t\tint cmp = hashcmp(index + mi * stride, sha1);\n \n \t\tif (debug_lookup)\ndiff --git a/sha1-lookup.c b/sha1-lookup.c\nindex 2552b7902..4cf3ebd92 100644\n--- a/sha1-lookup.c\n+++ b/sha1-lookup.c\n@@ -10,7 +10,7 @@ static uint32_t take2(const unsigned char *sha1)\n * Conventional binary search loop looks like this:\n *\n * do {\n- * int mi = (lo + hi) / 2;\n+ * int mi = lo + (hi - lo) / 2;\n * int cmp = \"entry pointed at by mi\" minus \"target\";\n * if (!cmp)\n * return (mi is the wanted one)\n@@ -95,7 +95,7 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr,\n \t\t\thi = mi;\n \t\telse\n \t\t\tlo = mi + 1;\n-\t\tmi = (hi + lo) / 2;\n+\t\tmi = lo + (hi - lo) / 2;\n \t} while (lo < hi);\n \treturn -lo-1;\n }\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 134ac9742..c7c5ab376 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -157,7 +157,7 @@ static void unique_in_pack(struct packed_git *p,\n \tnum = p->num_objects;\n \tlast = num;\n \twhile (first < last) {\n-\t\tuint32_t mid = (first + last) / 2;\n+\t\tuint32_t mid = first + (last - first) / 2;\n \t\tconst unsigned char *current;\n \t\tint cmp;\n \ndiff --git a/string-list.c b/string-list.c\nindex 806b4c872..a0cf0cfe8 100644\n--- a/string-list.c\n+++ b/string-list.c\n@@ -16,7 +16,7 @@ static int get_entry_index(const struct string_list *list, const char *string,\n \tcompare_strings_fn cmp = list->cmp ? list->cmp : strcmp;\n \n \twhile (left + 1 < right) {\n-\t\tint middle = (left + right) / 2;\n+\t\tint middle = left + (right - left) / 2;\n \t\tint compare = cmp(string, list->items[middle].string);\n \t\tif (compare < 0)\n \t\t\tright = middle;\ndiff --git a/utf8.c b/utf8.c\nindex 47a42047c..2c27ce013 100644\n--- a/utf8.c\n+++ b/utf8.c\n@@ -32,7 +32,7 @@ static int bisearch(ucs_char_t ucs, const struct interval *table, int max)\n \tif (ucs < table[0].first || ucs > table[max].last)\n \t\treturn 0;\n \twhile (max >= min) {\n-\t\tmid = (min + max) / 2;\n+\t\tmid = min + (max - min) / 2;\n \t\tif (ucs > table[mid].last)\n \t\t\tmin = mid + 1;\n \t\telse if (ucs < table[mid].first)\ndiff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\nindex a613efc70..9f91702de 100644\n--- a/xdiff/xpatience.c\n+++ b/xdiff/xpatience.c\n@@ -166,7 +166,7 @@ static int binary_search(struct entry **sequence, int longest,\n \tint left = -1, right = longest;\n \n \twhile (left + 1 < right) {\n-\t\tint middle = (left + right) / 2;\n+\t\tint middle = left + (right - left) / 2;\n \t\t/* by construction, no two entries can be equal */\n \t\tif (sequence[middle]->line2 > entry->line2)\n \t\t\tright = middle;\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"330036","messageId":"20171009133309.lslwg2uorbhnygqp@sigill.intra.peff.net","threadId":"46826","inReplyTo":"20171008182937.69205-1-dstolee@microsoft.com","subject":"Re: [PATCH v2] cleanup: fix possible overflow errors in binary search","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-09T13:33:10Z","receivedAt":"2017-10-09T13:33:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Oct 08, 2017 at 02:29:37PM -0400, Derrick Stolee wrote:\n\n> A common mistake when writing binary search is to allow possible\n> integer overflow by using the simple average:\n> \n> \tmid = (min + max) / 2;\n> \n> Instead, use the overflow-safe version:\n> \n> \tmid = min + (max - min) / 2;\n> \n> This translation is safe since the operation occurs inside a loop\n> conditioned on \"min < max\". The included changes were found using\n> the following git grep:\n> \n> \tgit grep '/ *2;' '*.c'\n> \n> Making this cleanup will prevent future review friction when a new\n> binary search is contructed based on existing code.\n\nThanks, this version looks good to me.\n\n> diff --git a/compat/regex/regex_internal.c b/compat/regex/regex_internal.c\n> index d4121f2f4..98342b831 100644\n> --- a/compat/regex/regex_internal.c\n> +++ b/compat/regex/regex_internal.c\n> @@ -613,7 +613,7 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags)\n> \t int low = 0, high = pstr->valid_len, mid;\n> \t do\n> \t\t{\n> -\t\t mid = (high + low) / 2;\n> +\t\t mid = low + (high - low) / 2;\n> \t\t if (pstr->offsets[mid] > offset)\n> \t\t high = mid;\n> \t\t else if (pstr->offsets[mid] < offset)\n\nThis one is a do-while, so it's less obvious that \"high\" is always more\nthan \"low\" when entering the loop. But one assumes it is so, since the\nbinary search wouldn't work otherwise.\n\n-Peff\n"}]}