{"thread":{"id":"26734","subject":"[PATCH 2/2] upload-pack: More aggressively send 'ACK %s ready'","startedAt":"2011-03-14T23:48:38Z","lastAt":"2011-03-17T15:51:29Z","messageCount":5,"participants":["Shawn O. Pearce","Jeff King","Shawn Pearce"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"163356","messageId":"1300146519-26508-1-git-send-email-spearce@spearce.org","threadId":"26734","inReplyTo":null,"subject":"[PATCH 1/2] fetch-pack: Finish negotation if remote replies \"ACK %s ready\"","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-03-14T23:48:38Z","receivedAt":"2011-03-14T23:48:38Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"If multi_ack_detailed was selected in the protocol capabilities\n(both client and server are >= Git 1.6.6) the upload-pack side will\nsend \"ACK %s ready\" when it knows how to safely cut the graph and\nproduce a reasonable pack for the want list that was already sent\non the connection.\n\nUpon receiving \"ACK %s ready\" there is no point in looking at\nthe remaining commits inside of rev_list.  Sending additional\n\"have %s\" lines to the remote will not construct a smaller pack.\nIt is unlikely a commit older than the current cut point will have\na better delta base than the cut point itself has.\n\nThe original design of this code had fetch-pack empty rev_list by\nmarking a commit and its transitive ancestors COMMON whenever the\nremote side said \"ACK %s {continue,common}\" and skipping over any\nalready COMMON commits during get_rev().  This approach does not\nwork when most of rev_list is actually COMMON_REF, commits that\nare pointed to by a reference on the remote, which exist locally,\nand which have not yet been sent to the remote as a \"have %s\" line.\n\nMost of the common references are tags in the ref/tags namespace,\nusing points in the commit graph that are more than 1 commit apart.\nIn git.git itself, this is currently 340 tags, 339 of which point to\ncommits in the commit graph.  fetch-pack pushes all of these into\nrev_list, but is unable to mark them COMMON and discard during a\nremote's \"ACK %s {continue,common}\" because it does not parse through\nthe entire parent chain.  Not parsing the entire parent chain is\nan optimization to avoid walking back to the roots of the repository.\n\nAssuming the client is only following the remote (and does not make\nits own local commits), the client needs 11 rounds to spin through\nthe entire list of tags (32 commits per round, ceil(339/32) == 11).\nUnfortunately the server knows on the first \"have %s\" line that\nit can produce a good pack, and does not need to see the remaining\n320 tags in the other 10 rounds.\n\nOver git:// and ssh:// this isn't as bad as it sounds, the client is\nonly transmitting an extra 16,000 bytes that it doesn't need to send.\n\nOver smart HTTP, the client must do an additional 10 HTTP POST\nrequests, each of which incurs round-trip latency, and must upload\nthe entire state vector of all known common objects.  On the final\nPOST request, this is 16 KiB worth of data.\n\nFix all of this by clearing rev_list as soon as the remote side\nsays it can construct a pack.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n builtin/fetch-pack.c |    2 ++\n 1 files changed, 2 insertions(+), 0 deletions(-)\n\ndiff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c\nindex b999413..dfacfdf 100644\n--- a/builtin/fetch-pack.c\n+++ b/builtin/fetch-pack.c\n@@ -379,6 +379,8 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t\t\t\tretval = 0;\n \t\t\t\t\tin_vain = 0;\n \t\t\t\t\tgot_continue = 1;\n+\t\t\t\t\tif (ack == ACK_ready)\n+\t\t\t\t\t  rev_list = NULL;\n \t\t\t\t\tbreak;\n \t\t\t\t\t}\n \t\t\t\t}\n-- \n1.7.0.9.5.g6bd7.dirty\n"},{"id":"163355","messageId":"1300146519-26508-2-git-send-email-spearce@spearce.org","threadId":"26734","inReplyTo":"1300146519-26508-1-git-send-email-spearce@spearce.org","subject":"[PATCH 2/2] upload-pack: More aggressively send 'ACK %s ready'","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-03-14T23:48:39Z","receivedAt":"2011-03-14T23:48:39Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"If a client is merely following the remote (and has not made any\nnew commits itself), all \"have %s\" lines sent by the client will be\ncommon to the server.  As all lines are common upload-pack never\ncalls ok_to_give_up() and does not compute if it has a good cut\npoint in the commit graph.\n\nWithout this computation the following client is going to send all\ntagged commits, as these were determined to be COMMON_REF during the\ninitial advertisement, but the client does not parse their history\nto transitively pass the COMMON flag and empty its queue of commits.\n\nFor git.git with 339 commit tags, it takes clients 11 rounds of\nnegotation to fully send all tagged commits and exhaust its queue\nof things to send as common.  This is pretty slow for a client that\nhas not done any local development activity.\n\nForce computing ok_to_give_up() and send \"ACK %s ready\" at the end\nof the current round if this round only contained common objects\nand ok_to_give_up() was therefore not called.  This may allow the\nclient to break early, avoiding transmission of the COMMON_REFs.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n upload-pack.c |    9 +++++++++\n 1 files changed, 9 insertions(+), 0 deletions(-)\n\ndiff --git a/upload-pack.c b/upload-pack.c\nindex b40a43f..2a0f19e 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -429,6 +429,8 @@ static int get_common_commits(void)\n \tstatic char line[1000];\n \tunsigned char sha1[20];\n \tchar last_hex[41];\n+\tint got_common = 0;\n+\tint got_other = 0;\n \n \tsave_commit_buffer = 0;\n \n@@ -437,16 +439,22 @@ static int get_common_commits(void)\n \t\treset_timeout();\n \n \t\tif (!len) {\n+\t\t\tif (multi_ack == 2 && got_common\n+\t\t\t\t\t&& !got_other && ok_to_give_up())\n+\t\t\t\tpacket_write(1, \"ACK %s ready\\n\", last_hex);\n \t\t\tif (have_obj.nr == 0 || multi_ack)\n \t\t\t\tpacket_write(1, \"NAK\\n\");\n \t\t\tif (stateless_rpc)\n \t\t\t\texit(0);\n+\t\t\tgot_common = 0;\n+\t\t\tgot_other = 0;\n \t\t\tcontinue;\n \t\t}\n \t\tstrip(line, len);\n \t\tif (!prefixcmp(line, \"have \")) {\n \t\t\tswitch (got_sha1(line+5, sha1)) {\n \t\t\tcase -1: /* they have what we do not */\n+\t\t\t\tgot_other = 1;\n \t\t\t\tif (multi_ack && ok_to_give_up()) {\n \t\t\t\t\tconst char *hex = sha1_to_hex(sha1);\n \t\t\t\t\tif (multi_ack == 2)\n@@ -456,6 +464,7 @@ static int get_common_commits(void)\n \t\t\t\t}\n \t\t\t\tbreak;\n \t\t\tdefault:\n+\t\t\t\tgot_common = 1;\n \t\t\t\tmemcpy(last_hex, sha1_to_hex(sha1), 41);\n \t\t\t\tif (multi_ack == 2)\n \t\t\t\t\tpacket_write(1, \"ACK %s common\\n\", last_hex);\n-- \n1.7.0.9.5.g6bd7.dirty\n"},{"id":"163532","messageId":"20110317071512.GF11931@sigill.intra.peff.net","threadId":"26734","inReplyTo":"1300146519-26508-1-git-send-email-spearce@spearce.org","subject":"Re: [PATCH 1/2] fetch-pack: Finish negotation if remote replies \"ACK %s ready\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-03-17T07:15:12Z","receivedAt":"2011-03-17T07:15:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Mar 14, 2011 at 04:48:38PM -0700, Shawn O. Pearce wrote:\n\n> Upon receiving \"ACK %s ready\" there is no point in looking at\n> the remaining commits inside of rev_list.  Sending additional\n> \"have %s\" lines to the remote will not construct a smaller pack.\n> It is unlikely a commit older than the current cut point will have\n> a better delta base than the cut point itself has.\n> [...]\n> Assuming the client is only following the remote (and does not make\n> its own local commits), the client needs 11 rounds to spin through\n> the entire list of tags (32 commits per round, ceil(339/32) == 11).\n> Unfortunately the server knows on the first \"have %s\" line that\n> it can produce a good pack, and does not need to see the remaining\n> 320 tags in the other 10 rounds.\n\nDoes this optimization help in that case? From looking at the code, it\nseems that we offer \"ACK %s ready\" only in the case that the client\nhas something we do not. I.e., they _are_ building local commits on top.\n\n> Over smart HTTP, the client must do an additional 10 HTTP POST\n> requests, each of which incurs round-trip latency, and must upload\n> the entire state vector of all known common objects.  On the final\n> POST request, this is 16 KiB worth of data.\n\nThis optimization aside, I wonder if it is worth bumping up the number\nof haves we send in a chunk from 32 to something higher.\n\n-Peff\n"},{"id":"163533","messageId":"20110317071600.GG11931@sigill.intra.peff.net","threadId":"26734","inReplyTo":"20110317071512.GF11931@sigill.intra.peff.net","subject":"Re: [PATCH 1/2] fetch-pack: Finish negotation if remote replies \"ACK %s ready\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-03-17T07:16:01Z","receivedAt":"2011-03-17T07:16:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Mar 17, 2011 at 03:15:12AM -0400, Jeff King wrote:\n\n> > Assuming the client is only following the remote (and does not make\n> > its own local commits), the client needs 11 rounds to spin through\n> > the entire list of tags (32 commits per round, ceil(339/32) == 11).\n> > Unfortunately the server knows on the first \"have %s\" line that\n> > it can produce a good pack, and does not need to see the remaining\n> > 320 tags in the other 10 rounds.\n> \n> Does this optimization help in that case? From looking at the code, it\n> seems that we offer \"ACK %s ready\" only in the case that the client\n> has something we do not. I.e., they _are_ building local commits on top.\n\nOK, never mind, I just read your 2/2. ;)\n\nSorry for the noise.\n\n-Peff\n"},{"id":"163565","messageId":"AANLkTinKudDokLkZQhcMbzXuO8UeY9r74V_dqgyyV2YA@mail.gmail.com","threadId":"26734","inReplyTo":"20110317071512.GF11931@sigill.intra.peff.net","subject":"Re: [PATCH 1/2] fetch-pack: Finish negotation if remote replies \"ACK %s ready\"","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-03-17T15:51:29Z","receivedAt":"2011-03-17T15:51:29Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Mar 17, 2011 at 00:15, Jeff King <peff@peff.net> wrote:\n>> Over smart HTTP, the client must do an additional 10 HTTP POST\n>> requests, each of which incurs round-trip latency, and must upload\n>> the entire state vector of all known common objects.  On the final\n>> POST request, this is 16 KiB worth of data.\n>\n> This optimization aside, I wonder if it is worth bumping up the number\n> of haves we send in a chunk from 32 to something higher.\n\nI have been considering that myself. 32 isn't a good number here. Its\n1604 bytes per round (32 have lines, and flush-pkt). Ethernet's\ndefault MTU is 1500 bytes, so stopping at 32 causes us to need more\nthan one packet, and the last one isn't full. In native git:// or\nssh:// where its bi-directional the client does \"race ahead\" and send\nanother 1604 bytes, but now we're at 3208 bytes which still doesn't\nfit well within the MTU. :-\\\n\nI've thought about increasing this to 64. On git:// or ssh:// that can\nbe wasteful as the remote should be able to stop us earlier,\nespecially if we are common very early (e.g. infrequent contributor\nwho is only 1 commit ahead). The same is true for smart HTTP, boosting\nit to 64 would help the maintainer pull from a lieutenant with fewer\nrounds, but it hurts the infrequent contributor as his only round is\nlarger for no good reason.\n\nThe better approach might be to automatically double the round size on\neach successive round, until we reach an upper limit of say 1024. For\nthe infrequent contributor we might even consider cutting the initial\nround to 16, as it would allow the entire initial round to fit into a\nsingle Ethernet MTU over git://, and with the no-done capability, the\nentire exchange is over in that single packet. :-)\n\nFor the maintainer, 16 is way too small, but they will then try 32,\n64, 128, 256, 512... and should pick up the common point quickly.\nAssuming the maintainer is already 600 commits ahead when he pulls,\nwe'll find the common point in 6 rounds, vs. the current approach that\nrequires 19 rounds.\n\n\nBut we should really cap the size at something sane like 1024 to\nprevent HTTP POST payloads from being more than 64 KiB. But\npractically this is <32 KiB because we gzip the POST body, and there\nonly content is hex digits and the word \"have\". It should be deflating\nto smaller than 50% of the original size. For various selfish reasons\nI wish I could keep this under 8192 bytes for the entire HTTP headers\nand POST body, but this is under 64 \"have\" lines, and that's useless.\n\nI'll try putting together this exponential round size patch today, I\nhave a few other git things to do today.\n\n-- \nShawn.\n"}]}