{"thread":{"id":"46758","subject":"[PATCH 0/3] Improve abbreviation disambiguation","startedAt":"2017-09-15T16:58:22Z","lastAt":"2017-09-19T00:51:38Z","messageCount":8,"participants":["Derrick Stolee","Jonathan Nieder","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"328131","messageId":"20170915165750.198201-1-dstolee@microsoft.com","threadId":"46758","inReplyTo":null,"subject":"[PATCH 0/3] Improve abbreviation disambiguation","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-09-15T16:57:47Z","receivedAt":"2017-09-15T16:58:22Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Hello,\n\nMy name is Derrick Stolee and I just switched teams at Microsoft from\nthe VSTS Git Server to work on performance improvements in core Git.\n\nThis is my first patch submission, and I look forward to your feedback.\n\nThanks,\n Stolee\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 performance helper `test-abbrev` and performance test `p0008-abbrev.sh`\nare added to demonstrate this performance improvement. Here are some\nperformance results for the three included commits, using\nGIT_PERF_REPEAT_COUNT=10 since the first test is frequently an outlier\ndue to the file cache being cold.\n\nRunning git on a Linux VM, we see the following gains.\n\n| Repo    | Pack-Files | Loose Objs | Baseline | Patch 2 | Patch 3 |\n|---------|------------|------------|----------|---------|---------|\n| Git.git | 1          | 0          | 0.46 s   | -87.0%  | -87.0%  |\n| Git.git | 5          | 0          | 1.04 s   | -84.6%  | -85.6%  |\n| Git.git | 4          | 75852      | 0.88 s   | -86.4%  | -86.4%  |\n| Linux   | 1          | 0          | 0.63 s   | -38.1%  | -69.8%  |\n| Linux   | 24         | 0          | 5.41 s   | -69.3%  | -71.5%  |\n| Linux   | 23         | 323441     | 5.41 s   | -70.6%  | -73.4%  |\n\nRunning a similar patch on Git for Windows, we see the following gains.\n\n| Repo          | Pack-Files | Loose | Baseline | Patch 2 | Patch 3 |\n|---------------|------------|-------|----------|---------|---------|\n| GitForWindows | 6          | 319   | 7.19 s   | -91.1%  | -91.5%  |\n| VSTS          | 3          | 38    | 7.83 s   | -88.9%  | -90.9%  |\n| Linux         | 3          | 0     | 7.92 s   | -87.9%  | -90.2%  |\n| Windows       | 50         | 219   | 17.8 s   | -98.6%  | -98.6%  |\n\nNote that performance improves in all cases, but the performance gain\nis larger when there are multiple, large pack-files. This gain comes\nfrom the lack of in-memory caching of index files that have already been\ninspected.\n\n\nDerrick Stolee (3):\n  sha1_name: Create perf test for find_unique_abbrev()\n  sha1_name: Unroll len loop in find_unique_abbrev_r\n  sha1_name: Parse less while finding common prefix\n\n Makefile               |  1 +\n sha1_name.c            | 66 ++++++++++++++++++++++++++++++++++++++------------\n t/helper/.gitignore    |  1 +\n t/helper/test-abbrev.c | 22 +++++++++++++++++\n t/perf/p0008-abbrev.sh | 12 +++++++++\n 5 files changed, 87 insertions(+), 15 deletions(-)\n create mode 100644 t/helper/test-abbrev.c\n create mode 100755 t/perf/p0008-abbrev.sh\n\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"328132","messageId":"20170915165750.198201-3-dstolee@microsoft.com","threadId":"46758","inReplyTo":"20170915165750.198201-1-dstolee@microsoft.com","subject":"[PATCH 2/3] sha1_name: Unroll len loop in find_unique_abbrev_r","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-09-15T16:57:49Z","receivedAt":"2017-09-15T16:58:26Z","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\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\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":"328133","messageId":"20170915165750.198201-2-dstolee@microsoft.com","threadId":"46758","inReplyTo":"20170915165750.198201-1-dstolee@microsoft.com","subject":"[PATCH 1/3] sha1_name: Create perf test for find_unique_abbrev()","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-09-15T16:57:48Z","receivedAt":"2017-09-15T16:58:29Z","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 100,000 object ids. The ids are created\nby iterating an unsigned int hash_base by a constant hash_delta and\ncopying hash_base five times across the sha1. Iterating by hash_delta\ndoes not create a duplicate value for over 10,000,000 iterations.\n\ntest-abberv demonstrates the performance improvements that will be\nshown by later improvements to the find_unique_abberv(). The value of\n100,000 is large enough to show the significance of the later\nimprovements while only taking a few seconds on large repos.\n\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\n---\n Makefile               |  1 +\n t/helper/.gitignore    |  1 +\n t/helper/test-abbrev.c | 23 +++++++++++++++++++++++\n t/perf/p0008-abbrev.sh | 12 ++++++++++++\n 4 files changed, 37 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 f2bb7f2f6..081ca05e8 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 721650256..80ce7d836 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..cb3551df9\n--- /dev/null\n+++ b/t/helper/test-abbrev.c\n@@ -0,0 +1,23 @@\n+#include \"cache.h\"\n+\n+int cmd_main(int ac, const char **av)\n+{\n+\tsetup_git_directory();\n+\n+\tunsigned int hash_delt = 0x13579BDF;\n+\tunsigned int hash_base = 0x01020304;\n+\tstruct object_id oid;\n+\n+\tint i, count = 0;\n+\tint n = sizeof(struct object_id) / sizeof(int);\n+\twhile (count++ < 100000) {\n+\t\tfor (i = 0; i < n; i++)\n+\t\t\t((unsigned int*)oid.hash)[i] = hash_base;\n+\n+\t\tfind_unique_abbrev(oid.hash, MINIMUM_ABBREV);\n+\n+\t\thash_base += hash_delt;\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..7c3fad807\n--- /dev/null\n+++ b/t/perf/p0008-abbrev.sh\n@@ -0,0 +1,12 @@\n+#!/bin/sh\n+\n+test_description='Test object disambiguation through abbreviations'\n+. ./perf-lib.sh\n+\n+test_perf_large_repo\n+\n+test_perf 'find_unique_abbrev()' '\n+\ttest-abbrev\n+'\n+\n+test_done\n-- \n2.14.1.538.g56ec8fc98.dirty\n\n"},{"id":"328134","messageId":"20170915165750.198201-4-dstolee@microsoft.com","threadId":"46758","inReplyTo":"20170915165750.198201-1-dstolee@microsoft.com","subject":"[PATCH 3/3] sha1_name: Parse less while finding common prefix","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2017-09-15T16:57:50Z","receivedAt":"2017-09-15T16:58:30Z","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\nThis change decreases the time to run test-abbrev by up to 40% on\nlarge repos.\n\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\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":"328136","messageId":"20170915170857.GS27425@aiede.mtv.corp.google.com","threadId":"46758","inReplyTo":"20170915165750.198201-1-dstolee@microsoft.com","subject":"Re: [PATCH 0/3] Improve abbreviation disambiguation","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2017-09-15T17:08:57Z","receivedAt":"2017-09-15T17:09:09Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nDerrick Stolee wrote:\n\n> This is my first patch submission, and I look forward to your feedback.\n\nThanks for writing this.  Looks exciting.\n\n[...]\n> When displaying object ids, we frequently want to see an abbreviation\n[etc]\n> Note that performance improves in all cases, but the performance gain\n> is larger when there are multiple, large pack-files. This gain comes\n> from the lack of in-memory caching of index files that have already been\n> inspected.\n\nCan this (especially the performance information) go in the commit\nmessage for one of the patches?\n\nOtherwise it is harder for people to track down when looking at these\nchanges later with \"git log\".  In the worst case, if the mailing list\narchive is down, then people would not have access to this information\nat all.  For that reason, I try (though I often fail!) to restrict\ncover letters to giving hints at e.g. what changed since the patch\nseries last visited the list, and to make the commit messages in the\npatches themselves as self-contained as possible.\n\nThat aside, looking forward to reading the patches themselves in more\ndetail.  Thanks for working on this.\n\nSincerely,\nJonathan\n"},{"id":"328281","messageId":"xmqqa81su8v9.fsf@gitster.mtv.corp.google.com","threadId":"46758","inReplyTo":"20170915165750.198201-2-dstolee@microsoft.com","subject":"Re: [PATCH 1/3] sha1_name: Create perf test for find_unique_abbrev()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-09-18T00:51:38Z","receivedAt":"2017-09-18T00:51:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <dstolee@microsoft.com> writes:\n\n> +int cmd_main(int ac, const char **av)\n> +{\n> +\tsetup_git_directory();\n\nAs far as I recall, we do not (yet) allow declaration after\nstatement in our codebase.  Move this down to make it after all\ndecls.\n\n> +\n> +\tunsigned int hash_delt = 0x13579BDF;\n> +\tunsigned int hash_base = 0x01020304;\n> +\tstruct object_id oid;\n> +\n> +\tint i, count = 0;\n> +\tint n = sizeof(struct object_id) / sizeof(int);\n\nIt probably is technically OK to assume sizeof(int) always equals to\nsizeof(unsigned), but because you use 'n' _only_ to work with uint\nand never with int, it would make more sense to match.  \n\nBut I do not think we want this \"clever\" optimization that involves\n'n' in the first place.\n\n> +\twhile (count++ < 100000) {\n> +\t\tfor (i = 0; i < n; i++)\n> +\t\t\t((unsigned int*)oid.hash)[i] = hash_base;\n\nDoes it make sense to assume that uint is always 4-byte (so this\ncode won't work if it is 8-byte on your platform) and doing this is\nfaster than using platform-optimized memcpy()?\n\n> +\t\tfind_unique_abbrev(oid.hash, MINIMUM_ABBREV);\n> +\n> +\t\thash_base += hash_delt;\n> +\t}\n\nI also wonder if this is measuring the right thing.  I am guessing\nthat by making many queries for a unique abbreviation of \"random\"\n(well, it is deterministic, but my point is these queries are not\nbased on the names of objects that exist in the repository) hashes,\nthis test measures how much time it takes for us to decide that such\na random hash does not exist.  In the real life use, we make the\nopposite query far more frequently: we have an object that we _know_\nexists in the repository and we try to find a sufficient length to\ndisambiguate it from others, and I suspect that these two use\ndifferent logic.  Don't you need to be measuring the time it takes\nto compute the shortest abbreviation of an object that exists\ninstead?\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..7c3fad807\n> --- /dev/null\n> +++ b/t/perf/p0008-abbrev.sh\n> @@ -0,0 +1,12 @@\n> +#!/bin/sh\n> +\n> +test_description='Test object disambiguation through abbreviations'\n> +. ./perf-lib.sh\n> +\n> +test_perf_large_repo\n> +\n> +test_perf 'find_unique_abbrev()' '\n> +\ttest-abbrev\n> +'\n> +\n> +test_done\n"},{"id":"328283","messageId":"960c73e2-6909-6894-a9ab-a191426aeda9@gmail.com","threadId":"46758","inReplyTo":"xmqqa81su8v9.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/3] sha1_name: Create perf test for find_unique_abbrev()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2017-09-18T11:36:09Z","receivedAt":"2017-09-18T11:37:34Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/17/2017 5:51 PM, Junio C Hamano wrote:\n> Derrick Stolee <dstolee@microsoft.com> writes:\n> \n>> +int cmd_main(int ac, const char **av)\n>> +{\n>> +\tsetup_git_directory();\n> \n> As far as I recall, we do not (yet) allow declaration after\n> statement in our codebase.  Move this down to make it after all\n> decls.\n\nWill fix.\n\n>> +\n>> +\tunsigned int hash_delt = 0x13579BDF;\n>> +\tunsigned int hash_base = 0x01020304;\n>> +\tstruct object_id oid;\n>> +\n>> +\tint i, count = 0;\n>> +\tint n = sizeof(struct object_id) / sizeof(int);\n> \n> It probably is technically OK to assume sizeof(int) always equals to\n> sizeof(unsigned), but because you use 'n' _only_ to work with uint\n> and never with int, it would make more sense to match.\n\nWill fix. I also notice that \"n\" should be const.\n\n> But I do not think we want this \"clever\" optimization that involves\n> 'n' in the first place.\n >>> +\twhile (count++ < 100000) {\n>> +\t\tfor (i = 0; i < n; i++)\n>> +\t\t\t((unsigned int*)oid.hash)[i] = hash_base;\n> \n> Does it make sense to assume that uint is always 4-byte (so this\n> code won't work if it is 8-byte on your platform) and doing this is\n> faster than using platform-optimized memcpy()?\n\nI'm not sure what you mean by using memcpy to improve this, because\nit would require calling memcpy in the inner loop, such as\n\n\tfor (i = 0; i < n; i++)\n\t\tmemcpy(oid.hash + i * sizeof(unsigned), &hash_base,\n\t\t       sizeof(unsigned));\n\nI'm probably misunderstanding your intended use of memcpy().\n\n>> +\t\tfind_unique_abbrev(oid.hash, MINIMUM_ABBREV);\n>> +\n>> +\t\thash_base += hash_delt;\n>> +\t}\n> \n> I also wonder if this is measuring the right thing.  I am guessing\n> that by making many queries for a unique abbreviation of \"random\"\n> (well, it is deterministic, but my point is these queries are not\n> based on the names of objects that exist in the repository) hashes,\n> this test measures how much time it takes for us to decide that such\n> a random hash does not exist.  In the real life use, we make the\n> opposite query far more frequently: we have an object that we _know_\n> exists in the repository and we try to find a sufficient length to\n> disambiguate it from others, and I suspect that these two use\n> different logic.  Don't you need to be measuring the time it takes\n> to compute the shortest abbreviation of an object that exists\n> instead?\n\nFirst, this doesn't just measure the time it takes to determine non-\nexistence, because it finds the len required to disambiguate an\n\"incoming\" hash from all known hashes. When testing, I put in a\nsimple printf to report the result abbreviation so I could see how\noften it needed to be extended. In this sense, the test exposes the\nwhile loop that is removed by PATCH 2/3.\n\nSecond, your criticism about extant hashes is valid, and one I\nstruggled to reconcile. I see two issues with testing known hashes:\n\n1. By determining the hash exists, we have inspected the file that\n    contains it (either a .idx or the loose-object directory). This\n    has side-effects that warm up the file cache so the looped method\n    is artificially faster to find matching objects. The effect is\n    particularly significant on a repo with exactly one packfile.\n\n2. If we iterate over the entire set of objects, this test takes\n    O(N*t(N)) time, where t(N) is the average time to compute a\n    minimum abbreviation. For large repos, this can take several\n    minutes. Instead, even with the constant 100,000 test hashes, we\n    have an O(t(N)) test. We could avoid the asymptotic growth by\n    limiting the number of existing hashes we use, but how do we\n    find a sufficiently uniform sample from them?\n\nBy looking at some other perf tests, I see that we can add a pre-\nrequisite action. I will investigate making another helper that\nuniformly selects a set of hashes from the repo and writes them\nto stdout in a random order. p0008-abbrev.sh will run the helper as\na prerequisite, saving the data to a file. test-abbrev will read\nthe hashes from stdin to test find_unique_abbrev. This should avoid\nthe side-effects I mentioned (test-abbrev will not warm up indexes)\nwhile also testing abbreviation lengths for existing objects.\n\nI'll get started on these changes and send a new patch with new perf\ndata in a couple days. Please let me know if there is a better way\nto measure performance for this change.\n\nThanks,\n-Stolee\n\n"},{"id":"328327","messageId":"xmqqr2v3se7m.fsf@gitster.mtv.corp.google.com","threadId":"46758","inReplyTo":"960c73e2-6909-6894-a9ab-a191426aeda9@gmail.com","subject":"Re: [PATCH 1/3] sha1_name: Create perf test for find_unique_abbrev()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-09-19T00:51:25Z","receivedAt":"2017-09-19T00:51:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <stolee@gmail.com> writes:\n\n>> But I do not think we want this \"clever\" optimization that involves\n>> 'n' in the first place.\n>>>> +\twhile (count++ < 100000) {\n>>> +\t\tfor (i = 0; i < n; i++)\n>>> +\t\t\t((unsigned int*)oid.hash)[i] = hash_base;\n>>\n>> Does it make sense to assume that uint is always 4-byte (so this\n>> code won't work if it is 8-byte on your platform) and doing this is\n>> faster than using platform-optimized memcpy()?\n>\n> I'm not sure what you mean by using memcpy to improve this, because\n> it would require calling memcpy in the inner loop, such as\n>\n> \tfor (i = 0; i < n; i++)\n> \t\tmemcpy(oid.hash + i * sizeof(unsigned), &hash_base,\n> \t\t       sizeof(unsigned));\n\nSorry, I left it without saying as I thought it was obvious, but\nwhat I meant was to use a whole \"struct oid\", not just a single\nunsigned (repeated), as the hash that is tested.  If you have an\narray of object names you use in the test, then\n\n\tfor (count = 0; count < limit; count++) {\n\t\thashcpy(&oid.hash, &samples[count]);\n\n\t\t... do the probing ...\n\t}\n\n> First, this doesn't just measure the time it takes to determine non-\n> existence,\n\nSorry, my phrasing was indeed misleading.  I know the time we spend\nto see if we have or do not have the object is the largest cycle\nspender in these codepaths (and even if it were, I do not think that\nis what you are trying to optimize in these patches anyway).  \n\nBut if I recall correctly, the way we come up with the unique\nabbreviation for an object that exists and an object that does not\nexist are different?  And because most of the time (think: \"git log\n-p\" output) we would be finding abbreviation for objects that we do\nhave, benchmarking and tweaking the code that comes up with an\nobject that does not exist is not optimizing for the right case.\n\nBack when I wrote that initial response, I didn't check how\ndifferent the code was between the two cases, but now I did.  It\nseems that in both cases we start from the shortest-allowed length\nand then extend the same way, and the only difference between these\ntwo cases is that we return immediately when our candidate name is\nlong enough not to match any existing object when the full name\nrefers to an object we do not have, while we return only when\ndisambiguity is resolved.  I _think_ these amount to the same\ncomputation (i.e. when an object with the full name we have exists,\nthe amount of computation we need to come up with its unique\nabbreviation is the same as the computation we need to find the\nunique abbreviation for the same name in another repository that has\nidentical set of objects, minus that single object), so from that\npoint of view, throwing random hashes, most of which would not name\nany existing object, and measuring how much time it takes to run\nget_short_oid() to compute the minimum length of the unique prefix\nshould be sufficient.\n\nThanks.\n\n"}]}