{"thread":{"id":"40743","subject":"[PATCH] receive-pack: avoid sending duplicate \"have\" lines","startedAt":"2015-11-06T23:16:13Z","lastAt":"2015-11-07T09:04:31Z","messageCount":3,"participants":["Lukas Fleischer","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"273034","messageId":"1446851773-32390-1-git-send-email-lfleischer@lfos.de","threadId":"40743","inReplyTo":null,"subject":"[PATCH] receive-pack: avoid sending duplicate \"have\" lines","fromName":"Lukas Fleischer","fromEmail":"lfleischer@lfos.de","sentAt":"2015-11-06T23:16:13Z","receivedAt":"2015-11-06T23:16:13Z","isPatch":true,"sender":{"key":"lfleischer@lfos.de","avatar":"https://avatars.githubusercontent.com/u/5530842?v=4"},"body":"Alternates and refs outside the current namespace are advertised as\n\"have\" lines. To this end, the object identifiers of alternates are\ncollected in an array and repeated hashes are omitted before\ntransmission. In contrast, refs outside the used namespace are currently\nconverted into \"have\" lines and transmitted immediately, without\nchecking for duplicate lines. This means that exactly the same \"have\"\nline might be transmitted several times.\n\nOptimize this by using a single pool to collect all object identifiers\nto be converted into \"have\" lines (including both alternates and refs\noutside the namespace) first and transmit them later, omitting any\nduplicates.\n\nSuggested-by: Junio C Hamano <gitster@pobox.com>\nSigned-off-by: Lukas Fleischer <lfleischer@lfos.de>\n---\nThis is based on pu. I am not sure whether we should also change the\nname of show_one_alternate_sha1() in this patch since it is now used\nto transmit refs outside the current namespace as well...\n\n builtin/receive-pack.c | 25 +++++++++++++------------\n 1 file changed, 13 insertions(+), 12 deletions(-)\n\ndiff --git a/builtin/receive-pack.c b/builtin/receive-pack.c\nindex f06f70a..548d4ce 100644\n--- a/builtin/receive-pack.c\n+++ b/builtin/receive-pack.c\n@@ -217,23 +217,24 @@ static void show_ref(const char *path, const unsigned char *sha1)\n }\n \n static int show_ref_cb(const char *path_full, const struct object_id *oid,\n-\t\t       int flag, void *unused)\n+\t\t       int flag, void *data)\n {\n \tconst char *path = strip_namespace(path_full);\n \n \tif (ref_is_hidden(path, path_full))\n \t\treturn 0;\n \n-\t/*\n-\t * Advertise refs outside our current namespace as \".have\"\n-\t * refs, so that the client can use them to minimize data\n-\t * transfer but will otherwise ignore them. This happens to\n-\t * cover \".have\" that are thrown in by add_one_alternate_ref()\n-\t * to mark histories that are complete in our alternates as\n-\t * well.\n-\t */\n-\tif (!path)\n-\t\tpath = \".have\";\n+\tif (!path) {\n+\t\t/*\n+\t\t * Advertise refs outside our current namespace as \".have\"\n+\t\t * refs, so that the client can use them to minimize data\n+\t\t * transfer but will otherwise ignore them.\n+\t\t */\n+\t\tstruct sha1_array *sa = data;\n+\t\tsha1_array_append(sa, oid->hash);\n+\t\treturn 0;\n+\t}\n+\n \tshow_ref(path, oid->hash);\n \treturn 0;\n }\n@@ -254,9 +255,9 @@ static void write_head_info(void)\n \tstruct sha1_array sa = SHA1_ARRAY_INIT;\n \n \tfor_each_alternate_ref(collect_one_alternate_ref, &sa);\n+\tfor_each_ref(show_ref_cb, &sa);\n \tsha1_array_for_each_unique(&sa, show_one_alternate_sha1, NULL);\n \tsha1_array_clear(&sa);\n-\tfor_each_ref(show_ref_cb, NULL);\n \tif (!sent_capabilities)\n \t\tshow_ref(\"capabilities^{}\", null_sha1);\n \n-- \n2.6.2\n"},{"id":"273037","messageId":"xmqq8u6a3dif.fsf@gitster.mtv.corp.google.com","threadId":"40743","inReplyTo":"1446851773-32390-1-git-send-email-lfleischer@lfos.de","subject":"Re: [PATCH] receive-pack: avoid sending duplicate \"have\" lines","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-11-06T23:38:00Z","receivedAt":"2015-11-06T23:38:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Lukas Fleischer <lfleischer@lfos.de> writes:\n\n> @@ -254,9 +255,9 @@ static void write_head_info(void)\n>  \tstruct sha1_array sa = SHA1_ARRAY_INIT;\n>  \n>  \tfor_each_alternate_ref(collect_one_alternate_ref, &sa);\n> +\tfor_each_ref(show_ref_cb, &sa);\n>  \tsha1_array_for_each_unique(&sa, show_one_alternate_sha1, NULL);\n\nHeh, I didn't realize that we already have half a support for this\ndeduping.  Good find.\n\nWe used to show \".have\" from alternates first and then our own, but\nnow we show the refs that matter and then \".have\"s from alternates\nand \".have\"s for our repository outside the current namespace.  That\nshouldn't cause problems and the result would probably make more\nsense from aesthetics point of view ;-)\n\nI suspect that many of these that turn into \".have\"s point the same\nobject as those sit at the tip of our refs (e.g. tags in alternates\nwe borrow from, which are the folks of the same project that copy\nthe same tags from the same upstream).  I wonder if it easy to filter\nthem out?  After all, if we say object X sits at refs/tags/v1.0\nthere is no point showing \".have\" for that same object X.\n\n>  \tsha1_array_clear(&sa);\n> -\tfor_each_ref(show_ref_cb, NULL);\n>  \tif (!sent_capabilities)\n>  \t\tshow_ref(\"capabilities^{}\", null_sha1);\n"},{"id":"273047","messageId":"20151107090431.576.3746@typhoon.lan","threadId":"40743","inReplyTo":"xmqq8u6a3dif.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] receive-pack: avoid sending duplicate \"have\" lines","fromName":"Lukas Fleischer","fromEmail":"lfleischer@lfos.de","sentAt":"2015-11-07T09:04:31Z","receivedAt":"2015-11-07T09:04:31Z","isPatch":true,"sender":{"key":"lfleischer@lfos.de","avatar":"https://avatars.githubusercontent.com/u/5530842?v=4"},"body":"On Sat, 07 Nov 2015 at 00:38:00, Junio C Hamano wrote:\n> [...]\n> I suspect that many of these that turn into \".have\"s point the same\n> object as those sit at the tip of our refs (e.g. tags in alternates\n> we borrow from, which are the folks of the same project that copy\n> the same tags from the same upstream).  I wonder if it easy to filter\n> them out?  After all, if we say object X sits at refs/tags/v1.0\n> there is no point showing \".have\" for that same object X.\n> [...]\n\nIt is certainly doable but we would need a better infrastructure. The\neasiest implementation (i.e. the one that is closest to what we\ncurrently do) is adding a second SHA1 array to collect all the hashes we\nalready advertised. We could then pass a struct of both SHA1 arrays as\nsecond parameter to for_each_ref() and always insert the object\nidentifier into either of the arrays in show_ref_cb(), depending on\nwhether we immediately advertise it as a ref or decide convert it into a\n\"have\" line. To transmit \"have\" lines, instead of calling\nsha1_array_for_each_unique(), we would then call some function that\nprints unique entries from the first array that do not appear in the\nsecond array. Something like this (fully untested):\n\n-- 8< --\nvoid sha1_array_for_each_diff(struct sha1_array *array1,\n\t\t\t      struct sha1_array *array2,\n\t\t\t      for_each_sha1_fn fn,\n\t\t\t      void *data)\n{\n\tint i, j;\n\n\tif (!array1->sorted)\n\t\tsha1_array_sort(array1);\n\tif (!array2->sorted)\n\t\tsha1_array_sort(array2);\n\n\tfor (i = j = 0; i < array1->nr; i++) {\n\t\tif (i > 0 && !hashcmp(array1->sha1[i], array1->sha1[i - 1]))\n\t\t\tcontinue;\n\t\twhile (j < array2->nr && hashcmp(array1->sha1[i], array2->sha1[j]) > 0)\n\t\t\tj++;\n\t\tif (j < array2->nr && !hashcmp(array1->sha1[i], array2->sha1[j]))\n\t\t\tcontinue;\n\t\tfn(array1->sha1[i], data);\n\t}\n}\n-- >8 --\n\nIf we decide to implement all that, however, I wonder whether we should\nuse a more sophisticated data structure instead. Currently, if there are\nn refs outside the current namespace pointing all to the same object, we\nappend n entries to the SHA1 array and sort them afterwards which\nrequires O(n) space. If we would maintain a set of hashes instead of an\narray in the first place, we could reduce space usage significantly by\nonly storing what is needed (O(1) in the scenario I mentioned). We could\nalso add markers to those object identifiers we already advertised\ninstead of maintaining two separate lists.\n\nUnfortunately, in order to keep the running time of O(n log n), we would\nprobably need something like self-balancing binary search trees.\nAlternatively, a hash map based approach could be taken. Is something\nlike this already used anywhere in the Git source tree such that we can\nborrow the required data structures and functions?\n"}]}