{"thread":{"id":"15569","subject":"[RFC] log(n)-transmissions common commit handshake","startedAt":"2008-09-17T23:00:30Z","lastAt":"2008-12-06T23:20:21Z","messageCount":13,"participants":["Thomas Rast","Nicolas Pitre","Nanako Shiraishi","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"90979","messageId":"200809180100.32626.trast@student.ethz.ch","threadId":"15569","inReplyTo":null,"subject":"[RFC] log(n)-transmissions common commit handshake","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2008-09-17T23:00:30Z","receivedAt":"2008-09-17T23:00:30Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Hi *\n\nThis is a fairly long mail, so here's a brief abstract:\n\n  Using two passes, first exponential stride through history, then\n  bisection on the \"right\" windows, we implement the find_common\n  handshake in log(history_size) many transmissions.  The followup\n  patch partially achieves that, but a few points are open and strict\n  backwards compatibility is missing (but its absence is Mostly\n  Harmless).\n\nTerminology\n===========\n\nThe sending side (running upload-pack) is called server, and the\nreceiving side (running fetch-pack) is the client.  Commits fall into\nthe following categories:\n\n'want':\n\tRequested by the client for transmission.\n\n'have':\n\tIn the client's object storage.\n\n'common':\n\tIn both client's and server's object storage.\n\n'private':\n\thave, but not in the server's storage.\n\n'required':\n\tPart of the history graph \"between\" commons and wants; minimal\n\tsubset that needs to be sent over the wire as part of the\n\ttransmission.\n\n(\"Verbing weirds language.\" -- Calvin)\n\nWhen I say \"a commit is not _yet_ X\", I mean \"it is not yet known to\nbe X\", usually from the client's POV.\n\n\nMotivation\n==========\n\nThis spawned out of the O(#haves*#wants*#history) analysis late last\nweek.  As a brief summary, the server uses the fairly expensive test\nok_to_give_up() to check whether it can cut the handshake short since\nit knows enough commons to cover all wants.  The thread is here:\n\n  http://article.gmane.org/gmane.comp.version-control.git/95787\n\n(Be sure to read the follow-up regarding the first '*' bullet point.)\n\nIt does this shortcut because the client risks getting side-tracked on\na private chunk of history leading to a private root.  (According to\nthe commit message.  I'm not sure how effective it really is.)\n\nThis check by far dominates the rest of the server's work, which is\nmostly lookup_object(): it only has to take each \"have\" line sha1, see\nif it is present, and if so, ACK it.  The client announces when it\nconsiders the handshake finished, so there is no other requirement to\ntest for it.\n\nA more efficient handshake could -- in addition to being more\nefficient :-) -- solve this problem simply by hitting the private root\nvery quickly and proceeding elsewhere, avoiding the server-side check.\n\n\nOutline of current algorithm\n============================\n\nThe client sends all its 'have' sha1s, ordered by date, in chunks of\n32.  The server replies with an ACK for each 'common', i.e., for any\nsha1 it finds in its own object store.\n\n[This is complicated a bit by the exchange of refs, see \"Open\nquestions\".]\n\nAs it goes, the client marks the commons, and as soon as it runs out\nof unmarket commits, it sends a \"done\".  The server then knows the\nentire set of commons too, and can proceed to generate a pack file of\nthe requireds.\n\nThere is a hard limit of 256 commits that go un-ACKed until the client\ngives up and declares that there are no common commits.\n\n\nIdea\n====\n\nThe proposed algorithm scans the haves in a different order, using two\nstages: exponential stride and bisection.\n\n(1) Exponential stride:\n-----------------------\n\nEmit the first commit, then the 2nd from that, then the 4th from that,\nand so on.  As a boundary case, always emit the root.\n\nIf the history has \"bounded width\" (the meaning should be fairly\nobvious), then this stage emits O(log(n)) commits up to the root.\n\n(2) Bisection:\n--------------\n\nCall a pair of (A,B) where A is an ancestor of B \"interesting\" if B is\nnot yet common and A is not yet private.\n\nThen the bisection step is: between any interesting pair of commits\n(A,B) emitted so far, emit the one in the middle M=M(A,B).\n\n[\"Cut points\" between last common and first private commits clearly\nlie only between such pairs.]\n\nAssuming for a moment that the server responds immediately, this also\ntakes only O(log(n)) commits since M must be either common or private,\nand thus A..M or M..B is no longer interesting, respectively.\n\nTo deal with the delayed responses in the actual protocol, at each\npass 'i' emit M(A,B) for all (A,B) in pairs(i) only if the pair is\nstill interesting.  Add both (A,M) and (M,B) to pairs(i+1).  Iterate.\npairs(0) is constructed from pass (1).\n\nIntuitively, this means we emit more than log(n) only if we have\nnothing else left to do.\n\n----\n\nBetween the two stages, we achieve O(log(n)) complexity.  (This\nnotably means that we hit private roots in far less transmitted sha1s\nthan the chunk size of 32.)\n\nUnfortunately, this ordering sometimes conflicts with the server's\nok_to_give_up() shortcut mentioned in \"Motivation\": Consider a linear\nbranch 'master', and suppose the only 'common' sent out in the first\nbatch was the root.  ok_to_give_up() detects that it has a common on\nthe only ancestry line of the want, and trigger a fake ACK for all\nfurther commits.  This becomes a problem when we later emit, say,\n'master~1' and the server ACKs it even though it is private.  (It does\nnot affect correctness, but can increase the depth of history\ntransmitted by a factor of 2 at worst.)\n\n\nRFC Implementation\n==================\n\nI'll just highlight a few design decisions.  It's my first serious C\ncoding in years, so warm up the flamethrowers...\n\n* The work_list (replacing rev_list) is the \"recursion stack\" for\n  get_rev().  New \"frames\" are inserted such that the order of emitted\n  commits is\n   (a) refs\n   (b) stage (1) in date order\n   (b) stage (2) in bisection depth order\n\n  get_rev() is split across functions for each case.\n\n  Refs are moved to front because the current code emits them anyway\n  (see \"Open questions\" below), mostly to help fill the first 64\n  \"have\" lines with things we are going to send anyway, as opposed to\n  the \"real\" walk where we make choices.\n\n* The bisection does not actually remember pairs, but flags commits\n  with the directions it has already started a bisection from them.\n  Combined with the existing POPPED flag for commits that were\n  emitted, the pair (A,B) can be determined from (A,direction) by a\n  parent/children search through the history.  This simplifies the\n  implementation.\n\n  The idea is then to scan with two pointers 'half' and 'full' in\n  parallel, where the first one makes only half as many steps, until\n  we hit a POPPED commit.  This must then be the interval we want to\n  bisect, and we can check whether it is still interesting, emit M,\n  and queue it for recursion at one level deeper.\n\n* We maintain a list 'outstanding' of all commits that have been sent,\n  so that an \"implied not-ACK\" can be inferred from the next ACK.\n  This is used to do a child-recursive NOTCOMMON flagging, analogous\n  to the parent-recursive COMMON flagging on an ACK.  The bisection\n  uses these flags to determine ranges.\n\n* Yes, commit_info is a pointless level of indirection.  I had more\n  tracking information in it before the last draft, and left it in for\n  the time being.\n\n[Hint: when playing with the patch, command lines such as\n\n   git fetch-pack -v -k <url> <head> 2>&1 | git name-rev --stdin\n\nhelp see the effects.]\n\n\nOpen Problems\n=============\n\n* Effect of branch/merge points\n\n  I do not see a better solution to deal with branch/merge points than\n  recursing into them.  There may be examples of history where this\n  extra level of recursion spoils the log(n) bound.  Carefully\n  choosing which side to scan first might help.\n\n* Impact/clever use of refs\n\n  For some reason, current git sends all refs to the server, even if\n  the server should already know about lots of them.  For example, in\n  git.git, emitting v1.6.0.2 covers almost all tags in the repository\n  by simple ancestor scanning.\n\n  Is there a reason for this behaviour?  Otherwise it would be better\n  to emit them in date order and intelligently handle commons.  (In\n  fact this does not depend on the discussed change.)\n\n* Backwards compatibility\n\n  As mentioned above, ok_to_give_up() is not really compatible with\n  this algorithm.  I suppose we should introduce a new capability\n  identifier that has the client enable the log(n) walker, and the\n  server disable ok_to_give_up()?  Is there a better approach, or are\n  there problems with it?  (I haven't worked with the protocol enough\n  to say, though it seems harmless.)\n\n... and of course everything that I missed. ;-)\n\n\nI'd greatly appreciate comments, especially from people who know the\nprotocol side of git.\n\n- Thomas\n\n\n-- \nThomas Rast\ntrast@student.ethz.ch\n\n\n\n\n"},{"id":"90980","messageId":"1221692484-21977-1-git-send-email-trast@student.ethz.ch","threadId":"15569","inReplyTo":"200809180100.32626.trast@student.ethz.ch","subject":"[RFC PATCH] fetch-pack: log(n)-transmission find_common()","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2008-09-17T23:01:24Z","receivedAt":"2008-09-17T23:01:24Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"See thread starter for discussion.\n\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n\n---\n builtin-fetch-pack.c |  333 +++++++++++++++++++++++++++++++++++++++++++------\n upload-pack.c        |    4 +-\n 2 files changed, 294 insertions(+), 43 deletions(-)\n\ndiff --git a/builtin-fetch-pack.c b/builtin-fetch-pack.c\nindex 4dfef29..9f010fe 100644\n--- a/builtin-fetch-pack.c\n+++ b/builtin-fetch-pack.c\n@@ -25,6 +25,11 @@ static const char fetch_pack_usage[] =\n #define COMMON_REF\t(1U << 2)\n #define SEEN\t\t(1U << 3)\n #define POPPED\t\t(1U << 4)\n+#define BISECTED_FW\t(1U << 5)\n+#define BISECTED_BW\t(1U << 6)\n+#define NOTCOMMON       (1U << 7)\n+#define HAS_INFO        (1U << 8)\n+#define CLEAN_MARKS     (COMMON | COMMON_REF | SEEN | POPPED | BISECTED_FW | BISECTED_BW | NOTCOMMON)\n \n static int marked;\n \n@@ -34,19 +39,78 @@ static int marked;\n  */\n #define MAX_IN_VAIN 256\n \n-static struct commit_list *rev_list;\n+struct work_list\n+{\n+\tstruct work_list *next;\n+\tstruct commit *commit;\n+\tunsigned int stride;    /* current stride length between commits */\n+\tunsigned int steps;     /* steps left to go before emitting again */\n+\tunsigned int bisect;\n+\tunsigned int is_ref :1; /* prioritise refs */\n+};\n+\n+static struct work_list *work_list = NULL;\n+\n+static struct commit_list *outstanding = NULL; /* list of commits not ACKed yet */\n+static struct commit_list *outstanding_end = NULL;\n+\n+struct commit_info\n+{\n+\tstruct commit_list *children;\n+};\n+\n+\n static int non_common_revs, multi_ack, use_sideband;\n \n-static void rev_list_push(struct commit *commit, int mark)\n+static struct commit_info *get_commit_info(struct commit *commit)\n+{\n+\tif (commit->object.flags & HAS_INFO)\n+\t\treturn commit->util;\n+\n+\tstruct commit_info *info = xmalloc(sizeof(struct commit_info));\n+\tinfo->children = NULL;\n+\tcommit->util = info;\n+\tcommit->object.flags |= HAS_INFO;\n+\treturn info;\n+}\n+\n+static void work_list_insert(struct work_list *work_item)\n {\n+\tstruct work_list **pp = &work_list;\n+\tstruct work_list *p;\n+\n+\twhile ((p = *pp)) {\n+\t\tif ((work_item->is_ref && (!p->is_ref || p->commit->date < work_item->commit->date))\n+\t\t    || (!work_item->bisect && (p->bisect || p->commit->date < work_item->commit->date))\n+\t\t    || p->bisect > work_item->bisect)\n+\t\t\tbreak;\n+\t\tpp = &p->next;\n+\t}\n+\n+\twork_item->next = p;\n+\t*pp = work_item;\n+}\n+\n+\n+static void rev_list_push(struct commit *commit, int mark, unsigned int stride, unsigned int steps, unsigned int is_ref)\n+{\n+\tstruct work_list *work_item;\n+\n \tif (!(commit->object.flags & mark)) {\n \t\tcommit->object.flags |= mark;\n \n-\t\tif (!(commit->object.parsed))\n+\t\tif (!(commit->object.parsed)) {\n \t\t\tif (parse_commit(commit))\n \t\t\t\treturn;\n+\t\t}\n \n-\t\tinsert_by_date(commit, &rev_list);\n+\t\twork_item = xmalloc(sizeof(struct work_list));\n+\t\twork_item->commit = commit;\n+\t\twork_item->stride = stride;\n+\t\twork_item->steps = steps;\n+\t\twork_item->bisect = 0;\n+\t\twork_item->is_ref = is_ref;\n+\t\twork_list_insert(work_item);\n \n \t\tif (!(commit->object.flags & COMMON))\n \t\t\tnon_common_revs++;\n@@ -58,7 +122,7 @@ static int rev_list_insert_ref(const char *path, const unsigned char *sha1, int\n \tstruct object *o = deref_tag(parse_object(sha1), path, 0);\n \n \tif (o && o->type == OBJ_COMMIT)\n-\t\trev_list_push((struct commit *)o, SEEN);\n+\t\trev_list_push((struct commit *)o, SEEN, 1, 1, 1);\n \n \treturn 0;\n }\n@@ -68,8 +132,7 @@ static int clear_marks(const char *path, const unsigned char *sha1, int flag, vo\n \tstruct object *o = deref_tag(parse_object(sha1), path, 0);\n \n \tif (o && o->type == OBJ_COMMIT)\n-\t\tclear_commit_marks((struct commit *)o,\n-\t\t\t\t   COMMON | COMMON_REF | SEEN | POPPED);\n+\t\tclear_commit_marks((struct commit *)o, CLEAN_MARKS);\n \treturn 0;\n }\n \n@@ -89,7 +152,7 @@ static void mark_common(struct commit *commit,\n \t\t\to->flags |= COMMON;\n \n \t\tif (!(o->flags & SEEN))\n-\t\t\trev_list_push(commit, SEEN);\n+\t\t\trev_list_push(commit, SEEN, 1, 1, 0);\n \t\telse {\n \t\t\tstruct commit_list *parents;\n \n@@ -111,49 +174,216 @@ static void mark_common(struct commit *commit,\n   Get the next rev to send, ignoring the common.\n */\n \n-static const unsigned char* get_rev(void)\n+\n+static void get_rev_queue_parents(struct commit *commit, int mark, unsigned int stride, unsigned int steps)\n+{\n+\tstruct commit_list *parents = commit->parents;\n+\n+\twhile (parents) {\n+\t\tstruct commit_info *info = get_commit_info(parents->item);\n+\t\tstruct commit_list *entry;\n+\t\tfor (entry = info->children; entry; entry = entry->next)\n+\t\t\tif (entry->item == commit)\n+\t\t\t\tbreak;\n+\t\tif (!entry)\n+\t\t\tcommit_list_insert(commit, &(info->children));\n+\t\tif (!(parents->item->object.flags & SEEN))\n+\t\t\trev_list_push(parents->item, mark, stride, steps, 0);\n+\t\tif (mark & COMMON)\n+\t\t\tmark_common(parents->item, 1, 0);\n+\t\tparents = parents->next;\n+\t}\n+}\n+\n+\n+static struct commit* get_rev_stride_skip(struct work_list *work_item)\n+{\n+\tget_rev_queue_parents(work_item->commit, SEEN, work_item->stride,\n+\t\t\t      work_item->steps + 1);\n+\n+\tfree(work_item);\n+\treturn NULL;\n+}\n+\n+static void setup_bisect(struct commit *commit, int depth)\n+{\n+\tstruct work_list *work_item = xmalloc(sizeof(struct work_list));\n+\n+\twork_item->commit = commit;\n+\twork_item->bisect = 1+depth;\n+\twork_item->is_ref = 0;\n+\twork_list_insert(work_item);\n+}\n+\n+static void setup_bisect_all (struct commit_list* list, int depth)\n+{\n+\twhile (list) {\n+\t\tsetup_bisect(list->item, depth);\n+\t\tlist = list->next;\n+\t}\n+}\n+\n+static struct commit* get_rev_stride_emit(struct work_list *work_item)\n+{\n+\tstruct commit *commit = work_item->commit;\n+\tunsigned int mark;\n+\n+\tcommit->object.flags |= POPPED;\n+\n+\t/* This one got hit by our walk! */\n+\tif (!(commit->object.flags & COMMON))\n+\t\tnon_common_revs--;\n+\n+\tif (commit->object.flags & COMMON) {\n+\t\t/* do not send \"have\", and ignore ancestors */\n+\t\tcommit = NULL;\n+\t\tmark = COMMON | SEEN;\n+\t} else if (commit->object.flags & COMMON_REF) {\n+\t\t/* send \"have\", and ignore ancestors */\n+\t\tmark = COMMON | SEEN;\n+\t} else {\n+\t\t/* send \"have\", also for its ancestors */\n+\t\tmark = SEEN;\n+\t\tsetup_bisect(commit, 0);\n+\t}\n+\n+\tif (commit)\n+\t\tget_rev_queue_parents(commit, mark, work_item->stride*2, 0);\n+\n+\tfree(work_item);\n+\n+\treturn commit;\n+}\n+\n+static struct commit* get_rev_bisect(struct work_list *work_item)\n+{\n+\tstruct commit *full;\n+\tstruct commit *half;\n+\tint half_step;\n+\tstruct commit_info *info;\n+\tunsigned int flags = work_item->commit->object.flags;\n+\n+\tif (flags & NOTCOMMON) {\n+\t\t/* we inferred that this side of the bisection is not\n+\t\t * interesting any longer */\n+\t\tfree(work_item);\n+\t\treturn NULL;\n+\t}\n+\n+\n+\tif (!(flags & (COMMON|BISECTED_BW))) {\n+\t\t/* Server does not have this. Search backward in history */\n+\n+\t\tfull = work_item->commit;\n+\t\tfull->object.flags |= BISECTED_BW;\n+\t\thalf = work_item->commit;\n+\t\thalf_step = 0;\n+\n+\t\twhile (full && full->parents) {\n+\t\t\tsetup_bisect_all(full->parents->next, work_item->bisect);\n+\t\t\tfull = full->parents->item;\n+\t\t\thalf_step ^= 1;\n+\t\t\tif (half_step)\n+\t\t\t\thalf = half->parents->item;\n+\t\t\tif (full->object.flags & (POPPED|COMMON))\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\t/* also insert the same bisection again so we can try forward too */\n+\t\twork_list_insert(work_item);\n+\n+\t\tif (full->object.flags & POPPED\n+\t\t    && !(full->object.flags & NOTCOMMON)\n+\t\t    && !(half->object.flags & (COMMON|POPPED))) {\n+\t\t\tsetup_bisect(half, work_item->bisect);\n+\t\t\thalf->object.flags |= POPPED;\n+\t\t\tinfo = get_commit_info(half);\n+\t\t\treturn half;\n+\t\t} else {\n+\t\t\treturn NULL;\n+\t\t}\n+\t}\n+\n+\tif (!(flags & (NOTCOMMON|BISECTED_FW))) {\n+\t\t/* We have not seen this yet when bisecting, search forward */\n+\n+\t\tfull = work_item->commit;\n+\t\tfull->object.flags |= BISECTED_FW;\n+\t\thalf = work_item->commit;\n+\t\thalf_step = 0;\n+\n+\t\twhile (full && (info=get_commit_info(full))->children) {\n+\t\t\tsetup_bisect_all(info->children->next, work_item->bisect);\n+\t\t\tfull = info->children->item;\n+\t\t\thalf_step ^= 1;\n+\t\t\tif (half_step) {\n+\t\t\t\tinfo = get_commit_info(half);\n+\t\t\t\thalf = info->children->item;\n+\t\t\t}\n+\t\t\tif (full->object.flags & (POPPED|NOTCOMMON))\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\tif (full->object.flags & POPPED\n+\t\t    && !(full->object.flags & COMMON)\n+\t\t    && !(half->object.flags & POPPED)) {\n+\t\t\tsetup_bisect(half, work_item->bisect);\n+\t\t\thalf->object.flags |= POPPED;\n+\t\t\tinfo = get_commit_info(half);\n+\t\t\tfree(work_item);\n+\t\t\treturn half;\n+\t\t}\n+\t}\n+\n+\tfree(work_item);\n+\treturn NULL;\n+}\n+\n+\n+static void mark_not_common(struct commit *commit)\n+{\n+\tstruct commit_info *info = get_commit_info(commit);\n+\tstruct commit_list *child;\n+\n+\tif (commit->object.flags & COMMON)\n+\t\t/* this has already been acked earlier */\n+\t\treturn;\n+\n+\tcommit->object.flags |= NOTCOMMON;\n+\n+\tfor (child = info->children; child; child = child->next)\n+\t\tmark_not_common(child->item);\n+}\n+\n+static struct commit *get_rev(void)\n {\n \tstruct commit *commit = NULL;\n \n \twhile (commit == NULL) {\n-\t\tunsigned int mark;\n-\t\tstruct commit_list *parents;\n+\t\tstruct work_list *work_item = NULL;\n \n-\t\tif (rev_list == NULL || non_common_revs == 0)\n+\t\tif (work_list == NULL || non_common_revs == 0)\n \t\t\treturn NULL;\n \n-\t\tcommit = rev_list->item;\n-\t\tif (!commit->object.parsed)\n+\t\twork_item = work_list;\n+\t\twork_list = work_item->next;\n+\n+\t\tcommit = work_item->commit;\n+\n+\t\tif (commit && !commit->object.parsed)\n \t\t\tparse_commit(commit);\n-\t\tparents = commit->parents;\n \n-\t\tcommit->object.flags |= POPPED;\n-\t\tif (!(commit->object.flags & COMMON))\n-\t\t\tnon_common_revs--;\n-\n-\t\tif (commit->object.flags & COMMON) {\n-\t\t\t/* do not send \"have\", and ignore ancestors */\n-\t\t\tcommit = NULL;\n-\t\t\tmark = COMMON | SEEN;\n-\t\t} else if (commit->object.flags & COMMON_REF)\n-\t\t\t/* send \"have\", and ignore ancestors */\n-\t\t\tmark = COMMON | SEEN;\n-\t\telse\n-\t\t\t/* send \"have\", also for its ancestors */\n-\t\t\tmark = SEEN;\n-\n-\t\twhile (parents) {\n-\t\t\tif (!(parents->item->object.flags & SEEN))\n-\t\t\t\trev_list_push(parents->item, mark);\n-\t\t\tif (mark & COMMON)\n-\t\t\t\tmark_common(parents->item, 1, 0);\n-\t\t\tparents = parents->next;\n+\t\tif (work_item->bisect) {\n+\t\t\tcommit = get_rev_bisect(work_item);\n+\t\t} else if (work_item->steps >= work_item->stride-1\n+\t\t\t   || (commit && !commit->parents)) {\n+\t\t\tcommit = get_rev_stride_emit(work_item);\n+\t\t} else {\n+\t\t\tcommit = get_rev_stride_skip(work_item);\n \t\t}\n-\n-\t\trev_list = rev_list->next;\n \t}\n \n-\treturn commit->object.sha1;\n+\treturn commit;\n }\n \n static int find_common(int fd[2], unsigned char *result_sha1,\n@@ -161,6 +391,7 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n {\n \tint fetching;\n \tint count = 0, flushes = 0, retval;\n+\tstruct commit *commit;\n \tconst unsigned char *sha1;\n \tunsigned in_vain = 0;\n \tint got_continue = 0;\n@@ -243,11 +474,21 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \n \tflushes = 0;\n \tretval = -1;\n-\twhile ((sha1 = get_rev())) {\n+\twhile ((commit = get_rev())) {\n+\t\tsha1 = commit->object.sha1;\n \t\tpacket_write(fd[1], \"have %s\\n\", sha1_to_hex(sha1));\n \t\tif (args.verbose)\n \t\t\tfprintf(stderr, \"have %s\\n\", sha1_to_hex(sha1));\n \t\tin_vain++;\n+\n+\t\tif (outstanding) {\n+\t\t\tcommit_list_insert(commit, &(outstanding_end->next));\n+\t\t\toutstanding_end = outstanding_end->next;\n+\t\t} else {\n+\t\t\tcommit_list_insert(commit, &outstanding);\n+\t\t\toutstanding_end = outstanding;\n+\t\t}\n+\n \t\tif (!(31 & ++count)) {\n \t\t\tint ack;\n \n@@ -274,6 +515,16 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t\t\t} else if (ack == 2) {\n \t\t\t\t\tstruct commit *commit =\n \t\t\t\t\t\tlookup_commit(result_sha1);\n+\t\t\t\t\tstruct commit_list *item;\n+\t\t\t\t\twhile (commit != outstanding->item) {\n+\t\t\t\t\t\tmark_not_common(commit);\n+\t\t\t\t\t\titem = outstanding;\n+\t\t\t\t\t\toutstanding = item->next;\n+\t\t\t\t\t\tfree(item);\n+\t\t\t\t\t}\n+\t\t\t\t\titem = outstanding;\n+\t\t\t\t\toutstanding = item->next;\n+\t\t\t\t\tfree(item);\n \t\t\t\t\tmark_common(commit, 0, 1);\n \t\t\t\t\tretval = 0;\n \t\t\t\t\tin_vain = 0;\n@@ -445,7 +696,7 @@ static int everything_local(struct ref **refs, int nr_match, char **match)\n \t\t\tcontinue;\n \n \t\tif (!(o->flags & SEEN)) {\n-\t\t\trev_list_push((struct commit *)o, COMMON_REF | SEEN);\n+\t\t\trev_list_push((struct commit *)o, COMMON_REF | SEEN, 1, 1, 1);\n \n \t\t\tmark_common((struct commit *)o, 1, 1);\n \t\t}\ndiff --git a/upload-pack.c b/upload-pack.c\nindex e5adbc0..c6dfb32 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -414,9 +414,9 @@ static int get_common_commits(void)\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\tif (multi_ack && ok_to_give_up())\n+/*\t\t\t\tif (multi_ack && ok_to_give_up())\n \t\t\t\t\tpacket_write(1, \"ACK %s continue\\n\",\n-\t\t\t\t\t\t     sha1_to_hex(sha1));\n+\t\t\t\t\tsha1_to_hex(sha1));*/\n \t\t\t\tbreak;\n \t\t\tdefault:\n \t\t\t\tmemcpy(hex, sha1_to_hex(sha1), 41);\n-- \ntg: (1293c95..) t/fetch-pack-speedup (depends on: origin/master)\n"},{"id":"91011","messageId":"200809181018.52811.trast@student.ethz.ch","threadId":"15569","inReplyTo":"200809180100.32626.trast@student.ethz.ch","subject":"Re: [RFC] log(n)-transmissions common commit handshake","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2008-09-18T08:18:18Z","receivedAt":"2008-09-18T08:18:18Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"I wrote:\n> * Impact/clever use of refs\n> \n>   For some reason, current git sends all refs to the server, even if\n>   the server should already know about lots of them.  For example, in\n>   git.git, emitting v1.6.0.2 covers almost all tags in the repository\n>   by simple ancestor scanning.\n> \n>   Is there a reason for this behaviour?  Otherwise it would be better\n>   to emit them in date order and intelligently handle commons.  (In\n>   fact this does not depend on the discussed change.)\n\nAs an addendum, I think the following would be a good way to cleverly\nuse refs to reduce work:\n\nCache a \"reduced\" DAG which just maps the ref'd commit relationships,\ni.e., shows the reachability of refs only.  This needs to be written\nout to disk between invocations.\n\nAt the start of the protocol, the server announces all its refs.  We\ncan use the reduced DAG to infer the minimal set of ref heads we need\nto announce to have the server know all common ones.  We can also mark\nall the other refs as \"common but not announced yet\", so that the\nbackwards marking and searching routines know to stop there.\n\nThis should reduce the number of refs listed back to the server to\nonly a handful, and at the same time, stop the client from searching\nbackwards through _all_ history (which can take a bit of time, and is\none of the weaknesses of my proposal) in most cases.\n\n- Thomas\n\n-- \nThomas Rast\ntrast@student.ethz.ch\n\n\n"},{"id":"91445","messageId":"1222217303-29792-1-git-send-email-trast@student.ethz.ch","threadId":"15569","inReplyTo":"1221692484-21977-1-git-send-email-trast@student.ethz.ch","subject":"[RFC PATCH v2] fetch-pack: log(n)-transmission find_common()","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2008-09-24T00:48:23Z","receivedAt":"2008-09-24T00:48:23Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Replaces the existing simple history search with a more sophisticated\nalgorithm:\n\n1) Walk history with exponentially increasing stride lengths; i.e.,\n   send the 1st commit, then the 2nd after that, then the 4th after\n   that, and so on.\n\n2) Bisect the resulting intervals.\n\nCombined with tracking the \"outstanding haves\" so that we can detect\nwhich sha1s were never ACKed by upload-pack (and hence not common),\nthis gives O(log(n)) required \"have\" lines.\n\nUnfortunately this cannot work if the server sends fake ACKs, so we\nintroduce a capability 'exp-stride' which instructs upload-pack to\ndisable ok_to_give_up().  (Which incidentally saves the server a lot\nof work.)\n\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n\n---\n\nSo, after the resounding success that v1 of this patch was, I went\nthrough and actually made it work, or at least I hope so.\n\nI eventually gave up on trying to understand the exact interaction of\nmark_common(), which sometimes pushes, and rev_list_push(), which\nsometimes marks, and just rewrote them to each only do one thing.  I\nalso rewrote the old strategy in terms of the new get_rev_stride\n(always keeping stride length at 1) because that was far less work\nthan integrating the existing code with the new one.\n\nFor the timings below, I ran the (new) daemon locally, with two repos:\n\n- a 'clone --mirror' of my own git.git, with a branch 'next' 525\n  commits from the above cc185a6\n\n- a 'clone --mirror' of the completely unrelated adps.git, which\n  shares no objects with git.git\n\nSome not really statistically sound timings, usually best of 3-5:\n\n  ## A stripped down git.git, with only one branch and no tags\n  $ git branch -a\n  * master\n  $ git tag\n  $ git log -1 --pretty=oneline master\n  cc185a6a8ac24737a26ec4b40cc401c2db8b2e97 Start draft release notes for 1.6.0.3\n  \n  ## I still have the old (dashed) forms in /usr/bin from RPMs\n  $ /usr/bin/git --version\n  git version 1.5.6\n\n  ## (1a) \"Updating\" from the git.git that is further ahead (OLD)\n  $ time /usr/bin/git-fetch-pack -k git://localhost/git next\n  [...]\n  real    0m1.004s\n  user    0m0.228s\n  sys     0m0.028s\n\n  ## (1b) \"Updating\" from the git.git that is further ahead (NEW)\n  $ time git fetch-pack -k git://localhost/git next\n  [...]\n  real    0m0.977s\n  user    0m0.208s\n  sys     0m0.068s\n\n  ## (2a) Fetching the unrelated repo from scratch (OLD)\n  $ time /usr/bin/git-fetch-pack -k git://localhost/adps master\n  [...]\n  real    0m9.560s\n  user    0m0.720s\n  sys     0m0.128s\n\n  ## (2b) Fetching the unrelated repo from scratch (NEW)\n  $ time git fetch-pack -k git://localhost/adps master\n  [...]\n  real    0m0.596s\n  user    0m0.372s\n  sys     0m0.008s\n\n  ## (3a) Fetching over the network from real repo (OLD)\n  $ time /usr/bin/git-fetch-pack git://git.kernel.org/pub/scm/git/git.git next\n  [...]\n  user    0m0.528s\n  sys     0m0.136s\n\n  ## (3b) Fetching over the network from real repo (NEW)\n  $ time git fetch-pack git://git.kernel.org/pub/scm/git/git.git next\n  [...]\n  user    0m0.540s\n  sys     0m0.180s\n\n  ## Add more refs to make it more interesting\n  $ git remote add origin ~/dev/git\n  $ git fetch --tags origin\n\n  ## (4a) like 1a, but with lots of tags\n  $ time /usr/bin/git-fetch-pack -k git://localhost/git next\n  [...]\n  real    0m1.075s\n  user    0m0.452s\n  sys     0m0.048s\n\n  ## (4b) like 1b, but with lots of tags\n  $ time git fetch-pack -k git://localhost/git next\n  [...]\n  real    0m0.837s\n  user    0m0.236s\n  sys     0m0.040s\n\nClearly, this approach does solve the issue I mentioned in the\nmotivation earlier in the thread, where the initial fetch of\ncompletely disjoint repositories takes _ages_.  Somewhat to my own\nsurprise, it seems to do quite well in _all_ cases even though it\naggressively digs through history.\n\nNote, however, that the timings aren't really solid; the final write\nof the pack, which I assume is fsync()ed, seems to have a big impact\non the execution time.  Test (3) obviously depends more on network\nperformance than anything else; and it uses the old (linear)\nalgorithm, but in the new implementation.\n\nI'd appreciate testers and eyeballs on the patch.  I'll think about\nthe ref heads \"reduced DAG\" again, to possibly shave off some more\n(client side cpu) time when I get the time, but that likely won't be\nin the next few days.\n\n- Thomas\n\n\nPS: Thanks drizzd for the discussion of the topic on IRC.\n\nPPS: Junio, enjoy your holidays :-)\n\n\n\n builtin-fetch-pack.c |  477 +++++++++++++++++++++++++++++++++++++++++---------\n upload-pack.c        |    7 +-\n 2 files changed, 400 insertions(+), 84 deletions(-)\n\ndiff --git a/builtin-fetch-pack.c b/builtin-fetch-pack.c\nindex 4dfef29..721fe08 100644\n--- a/builtin-fetch-pack.c\n+++ b/builtin-fetch-pack.c\n@@ -25,6 +25,12 @@ static const char fetch_pack_usage[] =\n #define COMMON_REF\t(1U << 2)\n #define SEEN\t\t(1U << 3)\n #define POPPED\t\t(1U << 4)\n+#define BISECTED_FW\t(1U << 5)\n+#define BISECTED_BW\t(1U << 6)\n+#define NOTCOMMON       (1U << 7)\n+#define HAS_INFO        (1U << 8)\n+#define CLEAN_MARKS     (COMMON | COMMON_REF | SEEN | POPPED | BISECTED_FW \\\n+\t\t\t | BISECTED_BW | NOTCOMMON)\n \n static int marked;\n \n@@ -34,133 +40,412 @@ static int marked;\n  */\n #define MAX_IN_VAIN 256\n \n-static struct commit_list *rev_list;\n-static int non_common_revs, multi_ack, use_sideband;\n+struct work_list\n+{\n+\tstruct work_list *next;\n+\tstruct commit *commit;\n+\tunsigned int stride;    /* current stride length between commits */\n+\tunsigned int steps;     /* steps left to go before emitting again */\n+\tunsigned int depth;     /* sideline depth */\n+\tunsigned int bisect;\n+};\n+\n+/* \"recursion stack\" of our strategy of choosing sha1s to transmit */\n+static struct work_list *work_list = NULL;\n \n-static void rev_list_push(struct commit *commit, int mark)\n+/* list of commits not ACKed yet */\n+static struct commit_list *outstanding = NULL;\n+static struct commit_list *outstanding_end = NULL;\n+\n+struct commit_info\n {\n-\tif (!(commit->object.flags & mark)) {\n-\t\tcommit->object.flags |= mark;\n+\tstruct commit_list *children;\n+};\n \n-\t\tif (!(commit->object.parsed))\n-\t\t\tif (parse_commit(commit))\n-\t\t\t\treturn;\n \n-\t\tinsert_by_date(commit, &rev_list);\n+static int non_common_revs = 1, multi_ack, use_sideband, exp_stride_algorithm;\n \n-\t\tif (!(commit->object.flags & COMMON))\n-\t\t\tnon_common_revs++;\n+static struct commit_info *get_commit_info(struct commit *commit)\n+{\n+\tif (commit->object.flags & HAS_INFO)\n+\t\treturn commit->util;\n+\n+\tstruct commit_info *info = xmalloc(sizeof(struct commit_info));\n+\tinfo->children = NULL;\n+\tcommit->util = info;\n+\tcommit->object.flags |= HAS_INFO;\n+\treturn info;\n+}\n+\n+static void work_list_insert(struct work_list *work_item)\n+{\n+\tstruct work_list **pp = &work_list;\n+\tstruct work_list *p;\n+\n+\twhile ((p = *pp)) {\n+\t\tif (p->bisect || work_item->bisect) {\n+\t\t\tif (p->bisect > work_item->bisect)\n+\t\t\t\tbreak;\n+\t\t} else {\n+\t\t\tif (p->depth > work_item->depth)\n+\t\t\t\tbreak;\n+\t\t\telse if (p->commit->date < work_item->commit->date)\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\tpp = &p->next;\n \t}\n+\n+\twork_item->next = p;\n+\t*pp = work_item;\n }\n \n-static int rev_list_insert_ref(const char *path, const unsigned char *sha1, int flag, void *cb_data)\n+static void add_child(struct commit *parent, struct commit *child)\n+{\n+\tstruct commit_info *info = get_commit_info(parent);\n+\tstruct commit_list *item;\n+\tfor (item = info->children; item; item = item->next)\n+\t\tif (item->item == child)\n+\t\t\tbreak;\n+\tif (!item)\n+\t\tcommit_list_insert(child, &(info->children));\n+}\n+\n+\n+/*\n+  Marks all (known) children of this commit NOTCOMMON.  We call this\n+  for all sha1s the server did not ACK.\n+*/\n+\n+static void mark_not_common(struct commit *commit)\n+{\n+\tstruct commit_info *info = get_commit_info(commit);\n+\tstruct commit_list *child;\n+\n+\tassert(!(commit->object.flags & COMMON));\n+\n+\tif (commit->object.flags & NOTCOMMON)\n+\t\treturn;\n+\n+\tcommit->object.flags |= NOTCOMMON;\n+\n+\tfor (child = info->children; child; child = child->next)\n+\t\tmark_not_common(child->item);\n+}\n+\n+\n+static void check_parsed_and_mark(struct commit *commit)\n+{\n+\tstruct commit_list *parent;\n+\n+\tif (!commit && commit->object.parsed)\n+\t\treturn;\n+\n+\tparse_commit(commit);\n+\n+\tfor (parent = commit->parents; parent; parent = parent->next) {\n+\t\tadd_child(parent->item, commit);\n+\t\tif (parent->item->object.flags & NOTCOMMON)\n+\t\t\tmark_not_common(commit);\n+\t}\n+}\n+\n+\n+static void rev_list_push(struct commit *commit, unsigned int stride,\n+\t\t\t  unsigned int steps, unsigned int depth)\n+{\n+\tstruct work_list *work_item;\n+\n+\tcheck_parsed_and_mark(commit);\n+\n+\twork_item = xmalloc(sizeof(struct work_list));\n+\twork_item->commit = commit;\n+\twork_item->stride = stride;\n+\twork_item->steps = steps;\n+\twork_item->depth = depth;\n+\twork_item->bisect = 0;\n+\twork_list_insert(work_item);\n+}\n+\n+static int rev_list_insert_ref(const char *path, const unsigned char *sha1,\n+\t\t\t       int flag, void *cb_data)\n {\n \tstruct object *o = deref_tag(parse_object(sha1), path, 0);\n \n-\tif (o && o->type == OBJ_COMMIT)\n-\t\trev_list_push((struct commit *)o, SEEN);\n+\tif (o && o->type == OBJ_COMMIT && !(o->flags & SEEN))\n+\t\trev_list_push((struct commit *)o, 1, 1, 0);\n \n \treturn 0;\n }\n \n-static int clear_marks(const char *path, const unsigned char *sha1, int flag, void *cb_data)\n+static int clear_marks(const char *path, const unsigned char *sha1, int flag,\n+\t\t       void *cb_data)\n {\n \tstruct object *o = deref_tag(parse_object(sha1), path, 0);\n \n \tif (o && o->type == OBJ_COMMIT)\n-\t\tclear_commit_marks((struct commit *)o,\n-\t\t\t\t   COMMON | COMMON_REF | SEEN | POPPED);\n+\t\tclear_commit_marks((struct commit *)o, CLEAN_MARKS);\n \treturn 0;\n }\n \n+\n /*\n-   This function marks a rev and its ancestors as common.\n-   In some cases, it is desirable to mark only the ancestors (for example\n-   when only the server does not yet know that they are common).\n+  Mark commits backwards through history as COMMON.\n */\n \n-static void mark_common(struct commit *commit,\n-\t\tint ancestors_only, int dont_parse)\n+static void mark_common(struct commit *commit, int ancestors_only, int dont_parse)\n {\n-\tif (commit != NULL && !(commit->object.flags & COMMON)) {\n-\t\tstruct object *o = (struct object *)commit;\n+\tstruct commit_list *parents;\n+\tstruct object *o;\n \n-\t\tif (!ancestors_only)\n-\t\t\to->flags |= COMMON;\n+\tif (commit == NULL || commit->object.flags & (COMMON_REF|COMMON))\n+\t\treturn;\n \n-\t\tif (!(o->flags & SEEN))\n-\t\t\trev_list_push(commit, SEEN);\n-\t\telse {\n-\t\t\tstruct commit_list *parents;\n-\n-\t\t\tif (!ancestors_only && !(o->flags & POPPED))\n-\t\t\t\tnon_common_revs--;\n-\t\t\tif (!o->parsed && !dont_parse)\n-\t\t\t\tif (parse_commit(commit))\n-\t\t\t\t\treturn;\n-\n-\t\t\tfor (parents = commit->parents;\n-\t\t\t\t\tparents;\n-\t\t\t\t\tparents = parents->next)\n-\t\t\t\tmark_common(parents->item, 0, dont_parse);\n-\t\t}\n+\tif (!dont_parse && !(commit->object.parsed))\n+\t\tcheck_parsed_and_mark(commit);\n+\n+\to = (struct object *)commit;\n+\n+\tif (!ancestors_only)\n+\t\to->flags |= COMMON;\n+\n+\tfor (parents = commit->parents; parents; parents = parents->next) {\n+\t\tadd_child(parents->item, commit);\n+\t\tmark_common(parents->item, 0, dont_parse);\n \t}\n }\n \n+\n+\n /*\n-  Get the next rev to send, ignoring the common.\n+  Queue all revs in the list for simple backward search. Does not\n+  requeue already SEEN commits.\n */\n \n-static const unsigned char* get_rev(void)\n+static void queue_list(struct commit *child, struct commit_list *list,\n+\t\t       unsigned int stride, unsigned int steps,\n+\t\t       unsigned int depth)\n {\n-\tstruct commit *commit = NULL;\n+\twhile (list) {\n+\t\tadd_child(list->item, child);\n+\t\tif (!(list->item->object.flags & SEEN))\n+\t\t\trev_list_push(list->item, stride, steps, depth);\n+\t\tlist = list->next;\n+\t}\n+}\n+\n+\n+/*\n+  Queues a commit for bisection\n+*/\n+\n+static void setup_bisect(struct commit *commit, int depth)\n+{\n+\tstruct work_list *work_item = xmalloc(sizeof(struct work_list));\n+\n+\twork_item->commit = commit;\n+\twork_item->bisect = 1+depth;\n+\twork_item->depth = 0;\n+\twork_list_insert(work_item);\n+}\n+\n+\n+/*\n+  Queues a list of commits for bisection\n+*/\n+\n+static void setup_bisect_all (struct commit_list* list, int depth)\n+{\n+\twhile (list) {\n+\t\tsetup_bisect(list->item, depth);\n+\t\tlist = list->next;\n+\t}\n+}\n+\n+\n+/*\n+  Backwards search. If we use exp_stride_algorithm, it takes\n+  exponential strides between commits chosen.\n+*/\n+\n+static struct commit* get_rev_stride(struct work_list *work_item)\n+{\n+\tstruct commit *commit = work_item->commit;\n+\tunsigned int steps = work_item->steps;\n+\n+\twhile (steps++ < work_item->stride-1 && commit->parents\n+\t       && !(commit->object.flags & (SEEN|COMMON|COMMON_REF))) {\n+\t\t/* all but the first parent line are queued for later */\n+\t\tif (commit->parents)\n+\t\t\tqueue_list(commit, commit->parents->next,\n+\t\t\t\t   work_item->stride, steps,\n+\t\t\t\t   work_item->depth+1);\n+\n+\t\t/* follow the first parent line directly */\n+\t\tcommit->object.flags |= SEEN;\n+\t\tadd_child(commit->parents->item, commit);\n+\t\tcommit = commit->parents->item;\n+\t\tcheck_parsed_and_mark(commit);\n+\t}\n+\n+\tif (commit->object.flags & (SEEN|COMMON)) {\n+\t\t/* already been here! */\n+\t\tcommit = NULL;\n+\t} else if (commit->object.flags & COMMON_REF) {\n+\t\t/* this came from a ref; we stop here, but need to\n+\t\t * emit it so the server knows too */\n+\t\tcommit->object.flags |= POPPED|SEEN|BISECTED_BW;\n+\t\tif (exp_stride_algorithm)\n+\t\t\tsetup_bisect(commit, 0);\n+\t} else {\n+\t\t/* usual case: this is news to us, so we scan further\n+\t\t * back.  note that the first-depth bisection only\n+\t\t * needs to go forward */\n+\t\tcommit->object.flags |= POPPED|SEEN|BISECTED_BW;\n+\t\tqueue_list(commit, commit->parents,\n+\t\t\t   exp_stride_algorithm ? work_item->stride*2 : 1,\n+\t\t\t   0, work_item->depth);\n+\t\tif (exp_stride_algorithm)\n+\t\t\tsetup_bisect(commit, 0);\n+\t}\n+\n+\tfree(work_item);\n+\n+\treturn commit;\n+}\n \n-\twhile (commit == NULL) {\n-\t\tunsigned int mark;\n-\t\tstruct commit_list *parents;\n \n-\t\tif (rev_list == NULL || non_common_revs == 0)\n+/*\n+  Bisection state of the exponential stride algorithm: scans forward\n+  (backward) for a non-common/already-sent (common/already-sent,\n+  resp.) commit, then emits the middle of that range, and re-queues.\n+\n+  This means we bisect the discovered range in log(n) transmissions,\n+  although we do make O(n) steps through history.\n+*/\n+\n+static struct commit* get_rev_bisect(struct work_list *work_item)\n+{\n+\tstruct commit *full;\n+\tstruct commit *half;\n+\tint half_step;\n+\tstruct commit_info *info;\n+\tunsigned int flags = work_item->commit->object.flags;\n+\n+\tif (!(flags & (COMMON|BISECTED_BW))) {\n+\t\t/* We don't know anything about the history _backward_\n+\t\t * from this, so search it */\n+\n+\t\tfull = work_item->commit;\n+\t\tfull->object.flags |= BISECTED_BW;\n+\t\thalf = work_item->commit;\n+\t\thalf_step = 0;\n+\n+\t\twhile (full && full->parents) {\n+\t\t\tfull = full->parents->item;\n+\t\t\thalf_step ^= 1;\n+\t\t\tif (half_step)\n+\t\t\t\thalf = half->parents->item;\n+\t\t\tif (full->object.flags & (POPPED|COMMON))\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\t/* also insert the same bisection again so we can try\n+\t\t * forward too */\n+\t\twork_list_insert(work_item);\n+\n+\t\tif (full->object.flags & POPPED\n+\t\t    && !(full->object.flags & NOTCOMMON)\n+\t\t    && !(half->object.flags & (COMMON|POPPED))) {\n+\t\t\tsetup_bisect(half, work_item->bisect);\n+\t\t\thalf->object.flags |= POPPED;\n+\t\t\treturn half;\n+\t\t} else {\n \t\t\treturn NULL;\n+\t\t}\n+\t}\n \n-\t\tcommit = rev_list->item;\n-\t\tif (!commit->object.parsed)\n-\t\t\tparse_commit(commit);\n-\t\tparents = commit->parents;\n-\n-\t\tcommit->object.flags |= POPPED;\n-\t\tif (!(commit->object.flags & COMMON))\n-\t\t\tnon_common_revs--;\n-\n-\t\tif (commit->object.flags & COMMON) {\n-\t\t\t/* do not send \"have\", and ignore ancestors */\n-\t\t\tcommit = NULL;\n-\t\t\tmark = COMMON | SEEN;\n-\t\t} else if (commit->object.flags & COMMON_REF)\n-\t\t\t/* send \"have\", and ignore ancestors */\n-\t\t\tmark = COMMON | SEEN;\n-\t\telse\n-\t\t\t/* send \"have\", also for its ancestors */\n-\t\t\tmark = SEEN;\n-\n-\t\twhile (parents) {\n-\t\t\tif (!(parents->item->object.flags & SEEN))\n-\t\t\t\trev_list_push(parents->item, mark);\n-\t\t\tif (mark & COMMON)\n-\t\t\t\tmark_common(parents->item, 1, 0);\n-\t\t\tparents = parents->next;\n+\tif (!(flags & (NOTCOMMON|BISECTED_FW))) {\n+\t\t/* We don't know anything about the history _forward_\n+\t\t * from this, so search it */\n+\n+\t\tfull = work_item->commit;\n+\t\tfull->object.flags |= BISECTED_FW;\n+\t\thalf = work_item->commit;\n+\t\thalf_step = 0;\n+\n+\t\twhile (full && (info=get_commit_info(full))->children) {\n+\t\t\tsetup_bisect_all(info->children->next, work_item->bisect);\n+\t\t\tfull = info->children->item;\n+\t\t\thalf_step ^= 1;\n+\t\t\tif (half_step) {\n+\t\t\t\tinfo = get_commit_info(half);\n+\t\t\t\thalf = info->children->item;\n+\t\t\t}\n+\t\t\tif (full->object.flags & (POPPED|NOTCOMMON))\n+\t\t\t\tbreak;\n \t\t}\n \n-\t\trev_list = rev_list->next;\n+\t\tif (full->object.flags & POPPED\n+\t\t    && !(full->object.flags & COMMON)\n+\t\t    && !(half->object.flags & (NOTCOMMON|POPPED))) {\n+\t\t\tsetup_bisect(half, work_item->bisect);\n+\t\t\thalf->object.flags |= POPPED;\n+\t\t\tfree(work_item);\n+\t\t\treturn half;\n+\t\t}\n \t}\n \n-\treturn commit->object.sha1;\n+\tfree(work_item);\n+\treturn NULL;\n }\n \n+\n+/*\n+  Get the next revision to send.\n+*/\n+\n+static struct commit *get_rev(void)\n+{\n+\tstruct commit *commit = NULL;\n+\n+\twhile (commit == NULL && work_list) {\n+\t\tstruct work_list *work_item = NULL;\n+\n+\t\twork_item = work_list;\n+\t\t/* we update the pointer early so the get_rev\n+\t\t * functions can free() or reuse the work_item as\n+\t\t * required */\n+\t\twork_list = work_item->next;\n+\n+\t\tcommit = work_item->commit;\n+\n+\t\tcheck_parsed_and_mark(commit);\n+\n+\t\tif (work_item->bisect) {\n+\t\t\tcommit = get_rev_bisect(work_item);\n+\t\t} else {\n+\t\t\tcommit = get_rev_stride(work_item);\n+\t\t}\n+\t}\n+\n+\treturn commit;\n+}\n+\n+static void pop_outstanding()\n+{\n+\tstruct commit_list *item = outstanding;\n+\toutstanding = item->next;\n+\tfree(item);\n+}\n+\n+\n static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t       struct ref *refs)\n {\n \tint fetching;\n \tint count = 0, flushes = 0, retval;\n+\tstruct commit *commit;\n \tconst unsigned char *sha1;\n \tunsigned in_vain = 0;\n \tint got_continue = 0;\n@@ -192,7 +477,7 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t}\n \n \t\tif (!fetching)\n-\t\t\tpacket_write(fd[1], \"want %s%s%s%s%s%s%s%s\\n\",\n+\t\t\tpacket_write(fd[1], \"want %s%s%s%s%s%s%s%s%s\\n\",\n \t\t\t\t     sha1_to_hex(remote),\n \t\t\t\t     (multi_ack ? \" multi_ack\" : \"\"),\n \t\t\t\t     (use_sideband == 2 ? \" side-band-64k\" : \"\"),\n@@ -200,6 +485,7 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t\t\t     (args.use_thin_pack ? \" thin-pack\" : \"\"),\n \t\t\t\t     (args.no_progress ? \" no-progress\" : \"\"),\n \t\t\t\t     (args.include_tag ? \" include-tag\" : \"\"),\n+\t\t\t\t     (exp_stride_algorithm ? \" exp-stride\" : \"\"),\n \t\t\t\t     \" ofs-delta\");\n \t\telse\n \t\t\tpacket_write(fd[1], \"want %s\\n\", sha1_to_hex(remote));\n@@ -243,13 +529,25 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \n \tflushes = 0;\n \tretval = -1;\n-\twhile ((sha1 = get_rev())) {\n+\twhile ((commit = get_rev())) {\n+\t\tsha1 = commit->object.sha1;\n \t\tpacket_write(fd[1], \"have %s\\n\", sha1_to_hex(sha1));\n \t\tif (args.verbose)\n \t\t\tfprintf(stderr, \"have %s\\n\", sha1_to_hex(sha1));\n \t\tin_vain++;\n+\n+\t\tif (outstanding) {\n+\t\t\tcommit_list_insert(commit, &(outstanding_end->next));\n+\t\t\toutstanding_end = outstanding_end->next;\n+\t\t} else {\n+\t\t\tcommit_list_insert(commit, &outstanding);\n+\t\t\toutstanding_end = outstanding;\n+\t\t}\n+\n \t\tif (!(31 & ++count)) {\n \t\t\tint ack;\n+\t\t\tint unwound = 0;\n+\t\t\tstruct commit_list *item;\n \n \t\t\tpacket_flush(fd[1]);\n \t\t\tflushes++;\n@@ -274,12 +572,23 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t\t\t} else if (ack == 2) {\n \t\t\t\t\tstruct commit *commit =\n \t\t\t\t\t\tlookup_commit(result_sha1);\n+\t\t\t\t\twhile (commit != outstanding->item) {\n+\t\t\t\t\t\tmark_not_common(outstanding->item);\n+\t\t\t\t\t\tpop_outstanding();\n+\t\t\t\t\t\tunwound++;\n+\t\t\t\t\t}\n+\t\t\t\t\tpop_outstanding();\n+\t\t\t\t\tunwound++;\n \t\t\t\t\tmark_common(commit, 0, 1);\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}\n \t\t\t} while (ack);\n+\t\t\twhile (unwound++ < 32) {\n+\t\t\t\tmark_not_common(outstanding->item);\n+\t\t\t\tpop_outstanding();\n+\t\t\t}\n \t\t\tflushes--;\n \t\t\tif (got_continue && MAX_IN_VAIN < in_vain) {\n \t\t\t\tif (args.verbose)\n@@ -445,9 +754,8 @@ static int everything_local(struct ref **refs, int nr_match, char **match)\n \t\t\tcontinue;\n \n \t\tif (!(o->flags & SEEN)) {\n-\t\t\trev_list_push((struct commit *)o, COMMON_REF | SEEN);\n-\n-\t\t\tmark_common((struct commit *)o, 1, 1);\n+\t\t\trev_list_push((struct commit *)o, 1, 0, 0);\n+\t\t\to->flags |= COMMON_REF;\n \t\t}\n \t}\n \n@@ -597,6 +905,11 @@ static struct ref *do_fetch_pack(int fd[2],\n \t\t\tfprintf(stderr, \"Server supports side-band\\n\");\n \t\tuse_sideband = 1;\n \t}\n+\tif (server_supports(\"exp-stride\")) {\n+\t\tif (args.verbose)\n+\t\t\tfprintf(stderr, \"Server supports exp-stride\\n\");\n+\t\texp_stride_algorithm = 1;\n+\t}\n \tif (everything_local(&ref, nr_match, match)) {\n \t\tpacket_flush(fd[1]);\n \t\tgoto all_done;\ndiff --git a/upload-pack.c b/upload-pack.c\nindex e5adbc0..14012ee 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -37,6 +37,7 @@ static unsigned int timeout;\n  */\n static int use_sideband;\n static int debug_fd;\n+static int exp_stride_algorithm;\n \n static void reset_timeout(void)\n {\n@@ -414,7 +415,7 @@ static int get_common_commits(void)\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\tif (multi_ack && ok_to_give_up())\n+\t\t\t\tif (multi_ack && !exp_stride_algorithm && ok_to_give_up())\n \t\t\t\t\tpacket_write(1, \"ACK %s continue\\n\",\n \t\t\t\t\t\t     sha1_to_hex(sha1));\n \t\t\t\tbreak;\n@@ -501,6 +502,8 @@ static void receive_needs(void)\n \t\t\tno_progress = 1;\n \t\tif (strstr(line+45, \"include-tag\"))\n \t\t\tuse_include_tag = 1;\n+\t\tif (strstr(line+45, \"exp-stride\"))\n+\t\t\texp_stride_algorithm = 1;\n \n \t\t/* We have sent all our refs already, and the other end\n \t\t * should have chosen out of them; otherwise they are\n@@ -573,7 +576,7 @@ static int send_ref(const char *refname, const unsigned char *sha1, int flag, vo\n {\n \tstatic const char *capabilities = \"multi_ack thin-pack side-band\"\n \t\t\" side-band-64k ofs-delta shallow no-progress\"\n-\t\t\" include-tag\";\n+\t\t\" include-tag exp-stride\";\n \tstruct object *o = parse_object(sha1);\n \n \tif (!o)\n-- \ntg: (1293c95..) t/fetch-pack-speedup (depends on: origin/master)\n"},{"id":"93802","messageId":"1224790716-20551-1-git-send-email-trast@student.ethz.ch","threadId":"15569","inReplyTo":"1222217303-29792-1-git-send-email-trast@student.ethz.ch","subject":"[RFC PATCH v2] fetch-pack: log(n)-transmission find_common()","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2008-10-23T19:38:36Z","receivedAt":"2008-10-23T19:38:36Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Replaces the existing simple history search with a more sophisticated\nalgorithm:\n\n1) Walk history with exponentially increasing stride lengths; i.e.,\n   send the 1st commit, then the 2nd after that, then the 4th after\n   that, and so on.\n\n2) Bisect the resulting intervals.\n\nCombined with tracking the \"outstanding haves\" so that we can detect\nwhich sha1s were never ACKed by upload-pack (and hence not common),\nthis gives O(log(n)) required \"have\" lines.\n\nUnfortunately this cannot work if the server sends fake ACKs, so we\nintroduce a capability 'exp-stride' which instructs upload-pack to\ndisable ok_to_give_up().  (Which incidentally saves the server a lot\nof work.)\n\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n\n---\n\nThis is a simple resend of v2, in the hope of attracting some\ndiscussion or at least encouraging words this time around.\n\nHere are the timings I took when I wrote the last mail:\n\n-- 8< --\nFor the timings below, I ran the (new) daemon locally, with two repos:\n\n- a 'clone --mirror' of my own git.git, with a branch 'next' 525\n  commits from the above cc185a6\n\n- a 'clone --mirror' of the completely unrelated adps.git, which\n  shares no objects with git.git\n\nSome not really statistically sound timings, usually best of 3-5:\n\n  ## A stripped down git.git, with only one branch and no tags\n  $ git branch -a\n  * master\n  $ git tag\n  $ git log -1 --pretty=oneline master\n  cc185a6a8ac24737a26ec4b40cc401c2db8b2e97 Start draft release notes for 1.6.0.3\n  \n  ## I still have the old (dashed) forms in /usr/bin from RPMs\n  $ /usr/bin/git --version\n  git version 1.5.6\n\n  ## (1a) \"Updating\" from the git.git that is further ahead (OLD)\n  $ time /usr/bin/git-fetch-pack -k git://localhost/git next\n  [...]\n  real    0m1.004s\n  user    0m0.228s\n  sys     0m0.028s\n\n  ## (1b) \"Updating\" from the git.git that is further ahead (NEW)\n  $ time git fetch-pack -k git://localhost/git next\n  [...]\n  real    0m0.977s\n  user    0m0.208s\n  sys     0m0.068s\n\n  ## (2a) Fetching the unrelated repo from scratch (OLD)\n  $ time /usr/bin/git-fetch-pack -k git://localhost/adps master\n  [...]\n  real    0m9.560s\n  user    0m0.720s\n  sys     0m0.128s\n\n  ## (2b) Fetching the unrelated repo from scratch (NEW)\n  $ time git fetch-pack -k git://localhost/adps master\n  [...]\n  real    0m0.596s\n  user    0m0.372s\n  sys     0m0.008s\n\n  ## (3a) Fetching over the network from real repo (OLD)\n  $ time /usr/bin/git-fetch-pack git://git.kernel.org/pub/scm/git/git.git next\n  [...]\n  user    0m0.528s\n  sys     0m0.136s\n\n  ## (3b) Fetching over the network from real repo (NEW)\n  $ time git fetch-pack git://git.kernel.org/pub/scm/git/git.git next\n  [...]\n  user    0m0.540s\n  sys     0m0.180s\n\n  ## Add more refs to make it more interesting\n  $ git remote add origin ~/dev/git\n  $ git fetch --tags origin\n\n  ## (4a) like 1a, but with lots of tags\n  $ time /usr/bin/git-fetch-pack -k git://localhost/git next\n  [...]\n  real    0m1.075s\n  user    0m0.452s\n  sys     0m0.048s\n\n  ## (4b) like 1b, but with lots of tags\n  $ time git fetch-pack -k git://localhost/git next\n  [...]\n  real    0m0.837s\n  user    0m0.236s\n  sys     0m0.040s\n\nClearly, this approach does solve the issue I mentioned in the\nmotivation earlier in the thread, where the initial fetch of\ncompletely disjoint repositories takes _ages_.  Somewhat to my own\nsurprise, it seems to do quite well in _all_ cases even though it\naggressively digs through history.\n\nNote, however, that the timings aren't really solid; the final write\nof the pack, which I assume is fsync()ed, seems to have a big impact\non the execution time.  Test (3) obviously depends more on network\nperformance than anything else; and it uses the old (linear)\nalgorithm, but in the new implementation.\n-- >8 --\n\n builtin-fetch-pack.c |  477 +++++++++++++++++++++++++++++++++++++++++---------\n upload-pack.c        |    7 +-\n 2 files changed, 400 insertions(+), 84 deletions(-)\n\ndiff --git a/builtin-fetch-pack.c b/builtin-fetch-pack.c\nindex 372bfa2..9ab84ab 100644\n--- a/builtin-fetch-pack.c\n+++ b/builtin-fetch-pack.c\n@@ -25,6 +25,12 @@ static const char fetch_pack_usage[] =\n #define COMMON_REF\t(1U << 2)\n #define SEEN\t\t(1U << 3)\n #define POPPED\t\t(1U << 4)\n+#define BISECTED_FW\t(1U << 5)\n+#define BISECTED_BW\t(1U << 6)\n+#define NOTCOMMON       (1U << 7)\n+#define HAS_INFO        (1U << 8)\n+#define CLEAN_MARKS     (COMMON | COMMON_REF | SEEN | POPPED | BISECTED_FW \\\n+\t\t\t | BISECTED_BW | NOTCOMMON)\n \n static int marked;\n \n@@ -34,133 +40,412 @@ static int marked;\n  */\n #define MAX_IN_VAIN 256\n \n-static struct commit_list *rev_list;\n-static int non_common_revs, multi_ack, use_sideband;\n+struct work_list\n+{\n+\tstruct work_list *next;\n+\tstruct commit *commit;\n+\tunsigned int stride;    /* current stride length between commits */\n+\tunsigned int steps;     /* steps left to go before emitting again */\n+\tunsigned int depth;     /* sideline depth */\n+\tunsigned int bisect;\n+};\n+\n+/* \"recursion stack\" of our strategy of choosing sha1s to transmit */\n+static struct work_list *work_list = NULL;\n \n-static void rev_list_push(struct commit *commit, int mark)\n+/* list of commits not ACKed yet */\n+static struct commit_list *outstanding = NULL;\n+static struct commit_list *outstanding_end = NULL;\n+\n+struct commit_info\n {\n-\tif (!(commit->object.flags & mark)) {\n-\t\tcommit->object.flags |= mark;\n+\tstruct commit_list *children;\n+};\n \n-\t\tif (!(commit->object.parsed))\n-\t\t\tif (parse_commit(commit))\n-\t\t\t\treturn;\n \n-\t\tinsert_by_date(commit, &rev_list);\n+static int non_common_revs = 1, multi_ack, use_sideband, exp_stride_algorithm;\n \n-\t\tif (!(commit->object.flags & COMMON))\n-\t\t\tnon_common_revs++;\n+static struct commit_info *get_commit_info(struct commit *commit)\n+{\n+\tif (commit->object.flags & HAS_INFO)\n+\t\treturn commit->util;\n+\n+\tstruct commit_info *info = xmalloc(sizeof(struct commit_info));\n+\tinfo->children = NULL;\n+\tcommit->util = info;\n+\tcommit->object.flags |= HAS_INFO;\n+\treturn info;\n+}\n+\n+static void work_list_insert(struct work_list *work_item)\n+{\n+\tstruct work_list **pp = &work_list;\n+\tstruct work_list *p;\n+\n+\twhile ((p = *pp)) {\n+\t\tif (p->bisect || work_item->bisect) {\n+\t\t\tif (p->bisect > work_item->bisect)\n+\t\t\t\tbreak;\n+\t\t} else {\n+\t\t\tif (p->depth > work_item->depth)\n+\t\t\t\tbreak;\n+\t\t\telse if (p->commit->date < work_item->commit->date)\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\tpp = &p->next;\n \t}\n+\n+\twork_item->next = p;\n+\t*pp = work_item;\n }\n \n-static int rev_list_insert_ref(const char *path, const unsigned char *sha1, int flag, void *cb_data)\n+static void add_child(struct commit *parent, struct commit *child)\n+{\n+\tstruct commit_info *info = get_commit_info(parent);\n+\tstruct commit_list *item;\n+\tfor (item = info->children; item; item = item->next)\n+\t\tif (item->item == child)\n+\t\t\tbreak;\n+\tif (!item)\n+\t\tcommit_list_insert(child, &(info->children));\n+}\n+\n+\n+/*\n+  Marks all (known) children of this commit NOTCOMMON.  We call this\n+  for all sha1s the server did not ACK.\n+*/\n+\n+static void mark_not_common(struct commit *commit)\n+{\n+\tstruct commit_info *info = get_commit_info(commit);\n+\tstruct commit_list *child;\n+\n+\tassert(!(commit->object.flags & COMMON));\n+\n+\tif (commit->object.flags & NOTCOMMON)\n+\t\treturn;\n+\n+\tcommit->object.flags |= NOTCOMMON;\n+\n+\tfor (child = info->children; child; child = child->next)\n+\t\tmark_not_common(child->item);\n+}\n+\n+\n+static void check_parsed_and_mark(struct commit *commit)\n+{\n+\tstruct commit_list *parent;\n+\n+\tif (!commit && commit->object.parsed)\n+\t\treturn;\n+\n+\tparse_commit(commit);\n+\n+\tfor (parent = commit->parents; parent; parent = parent->next) {\n+\t\tadd_child(parent->item, commit);\n+\t\tif (parent->item->object.flags & NOTCOMMON)\n+\t\t\tmark_not_common(commit);\n+\t}\n+}\n+\n+\n+static void rev_list_push(struct commit *commit, unsigned int stride,\n+\t\t\t  unsigned int steps, unsigned int depth)\n+{\n+\tstruct work_list *work_item;\n+\n+\tcheck_parsed_and_mark(commit);\n+\n+\twork_item = xmalloc(sizeof(struct work_list));\n+\twork_item->commit = commit;\n+\twork_item->stride = stride;\n+\twork_item->steps = steps;\n+\twork_item->depth = depth;\n+\twork_item->bisect = 0;\n+\twork_list_insert(work_item);\n+}\n+\n+static int rev_list_insert_ref(const char *path, const unsigned char *sha1,\n+\t\t\t       int flag, void *cb_data)\n {\n \tstruct object *o = deref_tag(parse_object(sha1), path, 0);\n \n-\tif (o && o->type == OBJ_COMMIT)\n-\t\trev_list_push((struct commit *)o, SEEN);\n+\tif (o && o->type == OBJ_COMMIT && !(o->flags & SEEN))\n+\t\trev_list_push((struct commit *)o, 1, 1, 0);\n \n \treturn 0;\n }\n \n-static int clear_marks(const char *path, const unsigned char *sha1, int flag, void *cb_data)\n+static int clear_marks(const char *path, const unsigned char *sha1, int flag,\n+\t\t       void *cb_data)\n {\n \tstruct object *o = deref_tag(parse_object(sha1), path, 0);\n \n \tif (o && o->type == OBJ_COMMIT)\n-\t\tclear_commit_marks((struct commit *)o,\n-\t\t\t\t   COMMON | COMMON_REF | SEEN | POPPED);\n+\t\tclear_commit_marks((struct commit *)o, CLEAN_MARKS);\n \treturn 0;\n }\n \n+\n /*\n-   This function marks a rev and its ancestors as common.\n-   In some cases, it is desirable to mark only the ancestors (for example\n-   when only the server does not yet know that they are common).\n+  Mark commits backwards through history as COMMON.\n */\n \n-static void mark_common(struct commit *commit,\n-\t\tint ancestors_only, int dont_parse)\n+static void mark_common(struct commit *commit, int ancestors_only, int dont_parse)\n {\n-\tif (commit != NULL && !(commit->object.flags & COMMON)) {\n-\t\tstruct object *o = (struct object *)commit;\n+\tstruct commit_list *parents;\n+\tstruct object *o;\n \n-\t\tif (!ancestors_only)\n-\t\t\to->flags |= COMMON;\n+\tif (commit == NULL || commit->object.flags & (COMMON_REF|COMMON))\n+\t\treturn;\n \n-\t\tif (!(o->flags & SEEN))\n-\t\t\trev_list_push(commit, SEEN);\n-\t\telse {\n-\t\t\tstruct commit_list *parents;\n-\n-\t\t\tif (!ancestors_only && !(o->flags & POPPED))\n-\t\t\t\tnon_common_revs--;\n-\t\t\tif (!o->parsed && !dont_parse)\n-\t\t\t\tif (parse_commit(commit))\n-\t\t\t\t\treturn;\n-\n-\t\t\tfor (parents = commit->parents;\n-\t\t\t\t\tparents;\n-\t\t\t\t\tparents = parents->next)\n-\t\t\t\tmark_common(parents->item, 0, dont_parse);\n-\t\t}\n+\tif (!dont_parse && !(commit->object.parsed))\n+\t\tcheck_parsed_and_mark(commit);\n+\n+\to = (struct object *)commit;\n+\n+\tif (!ancestors_only)\n+\t\to->flags |= COMMON;\n+\n+\tfor (parents = commit->parents; parents; parents = parents->next) {\n+\t\tadd_child(parents->item, commit);\n+\t\tmark_common(parents->item, 0, dont_parse);\n \t}\n }\n \n+\n+\n /*\n-  Get the next rev to send, ignoring the common.\n+  Queue all revs in the list for simple backward search. Does not\n+  requeue already SEEN commits.\n */\n \n-static const unsigned char* get_rev(void)\n+static void queue_list(struct commit *child, struct commit_list *list,\n+\t\t       unsigned int stride, unsigned int steps,\n+\t\t       unsigned int depth)\n {\n-\tstruct commit *commit = NULL;\n+\twhile (list) {\n+\t\tadd_child(list->item, child);\n+\t\tif (!(list->item->object.flags & SEEN))\n+\t\t\trev_list_push(list->item, stride, steps, depth);\n+\t\tlist = list->next;\n+\t}\n+}\n+\n+\n+/*\n+  Queues a commit for bisection\n+*/\n+\n+static void setup_bisect(struct commit *commit, int depth)\n+{\n+\tstruct work_list *work_item = xmalloc(sizeof(struct work_list));\n+\n+\twork_item->commit = commit;\n+\twork_item->bisect = 1+depth;\n+\twork_item->depth = 0;\n+\twork_list_insert(work_item);\n+}\n+\n+\n+/*\n+  Queues a list of commits for bisection\n+*/\n+\n+static void setup_bisect_all (struct commit_list* list, int depth)\n+{\n+\twhile (list) {\n+\t\tsetup_bisect(list->item, depth);\n+\t\tlist = list->next;\n+\t}\n+}\n+\n+\n+/*\n+  Backwards search. If we use exp_stride_algorithm, it takes\n+  exponential strides between commits chosen.\n+*/\n+\n+static struct commit* get_rev_stride(struct work_list *work_item)\n+{\n+\tstruct commit *commit = work_item->commit;\n+\tunsigned int steps = work_item->steps;\n+\n+\twhile (steps++ < work_item->stride-1 && commit->parents\n+\t       && !(commit->object.flags & (SEEN|COMMON|COMMON_REF))) {\n+\t\t/* all but the first parent line are queued for later */\n+\t\tif (commit->parents)\n+\t\t\tqueue_list(commit, commit->parents->next,\n+\t\t\t\t   work_item->stride, steps,\n+\t\t\t\t   work_item->depth+1);\n+\n+\t\t/* follow the first parent line directly */\n+\t\tcommit->object.flags |= SEEN;\n+\t\tadd_child(commit->parents->item, commit);\n+\t\tcommit = commit->parents->item;\n+\t\tcheck_parsed_and_mark(commit);\n+\t}\n+\n+\tif (commit->object.flags & (SEEN|COMMON)) {\n+\t\t/* already been here! */\n+\t\tcommit = NULL;\n+\t} else if (commit->object.flags & COMMON_REF) {\n+\t\t/* this came from a ref; we stop here, but need to\n+\t\t * emit it so the server knows too */\n+\t\tcommit->object.flags |= POPPED|SEEN|BISECTED_BW;\n+\t\tif (exp_stride_algorithm)\n+\t\t\tsetup_bisect(commit, 0);\n+\t} else {\n+\t\t/* usual case: this is news to us, so we scan further\n+\t\t * back.  note that the first-depth bisection only\n+\t\t * needs to go forward */\n+\t\tcommit->object.flags |= POPPED|SEEN|BISECTED_BW;\n+\t\tqueue_list(commit, commit->parents,\n+\t\t\t   exp_stride_algorithm ? work_item->stride*2 : 1,\n+\t\t\t   0, work_item->depth);\n+\t\tif (exp_stride_algorithm)\n+\t\t\tsetup_bisect(commit, 0);\n+\t}\n+\n+\tfree(work_item);\n+\n+\treturn commit;\n+}\n \n-\twhile (commit == NULL) {\n-\t\tunsigned int mark;\n-\t\tstruct commit_list *parents;\n \n-\t\tif (rev_list == NULL || non_common_revs == 0)\n+/*\n+  Bisection state of the exponential stride algorithm: scans forward\n+  (backward) for a non-common/already-sent (common/already-sent,\n+  resp.) commit, then emits the middle of that range, and re-queues.\n+\n+  This means we bisect the discovered range in log(n) transmissions,\n+  although we do make O(n) steps through history.\n+*/\n+\n+static struct commit* get_rev_bisect(struct work_list *work_item)\n+{\n+\tstruct commit *full;\n+\tstruct commit *half;\n+\tint half_step;\n+\tstruct commit_info *info;\n+\tunsigned int flags = work_item->commit->object.flags;\n+\n+\tif (!(flags & (COMMON|BISECTED_BW))) {\n+\t\t/* We don't know anything about the history _backward_\n+\t\t * from this, so search it */\n+\n+\t\tfull = work_item->commit;\n+\t\tfull->object.flags |= BISECTED_BW;\n+\t\thalf = work_item->commit;\n+\t\thalf_step = 0;\n+\n+\t\twhile (full && full->parents) {\n+\t\t\tfull = full->parents->item;\n+\t\t\thalf_step ^= 1;\n+\t\t\tif (half_step)\n+\t\t\t\thalf = half->parents->item;\n+\t\t\tif (full->object.flags & (POPPED|COMMON))\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\t/* also insert the same bisection again so we can try\n+\t\t * forward too */\n+\t\twork_list_insert(work_item);\n+\n+\t\tif (full->object.flags & POPPED\n+\t\t    && !(full->object.flags & NOTCOMMON)\n+\t\t    && !(half->object.flags & (COMMON|POPPED))) {\n+\t\t\tsetup_bisect(half, work_item->bisect);\n+\t\t\thalf->object.flags |= POPPED;\n+\t\t\treturn half;\n+\t\t} else {\n \t\t\treturn NULL;\n+\t\t}\n+\t}\n \n-\t\tcommit = rev_list->item;\n-\t\tif (!commit->object.parsed)\n-\t\t\tparse_commit(commit);\n-\t\tparents = commit->parents;\n-\n-\t\tcommit->object.flags |= POPPED;\n-\t\tif (!(commit->object.flags & COMMON))\n-\t\t\tnon_common_revs--;\n-\n-\t\tif (commit->object.flags & COMMON) {\n-\t\t\t/* do not send \"have\", and ignore ancestors */\n-\t\t\tcommit = NULL;\n-\t\t\tmark = COMMON | SEEN;\n-\t\t} else if (commit->object.flags & COMMON_REF)\n-\t\t\t/* send \"have\", and ignore ancestors */\n-\t\t\tmark = COMMON | SEEN;\n-\t\telse\n-\t\t\t/* send \"have\", also for its ancestors */\n-\t\t\tmark = SEEN;\n-\n-\t\twhile (parents) {\n-\t\t\tif (!(parents->item->object.flags & SEEN))\n-\t\t\t\trev_list_push(parents->item, mark);\n-\t\t\tif (mark & COMMON)\n-\t\t\t\tmark_common(parents->item, 1, 0);\n-\t\t\tparents = parents->next;\n+\tif (!(flags & (NOTCOMMON|BISECTED_FW))) {\n+\t\t/* We don't know anything about the history _forward_\n+\t\t * from this, so search it */\n+\n+\t\tfull = work_item->commit;\n+\t\tfull->object.flags |= BISECTED_FW;\n+\t\thalf = work_item->commit;\n+\t\thalf_step = 0;\n+\n+\t\twhile (full && (info=get_commit_info(full))->children) {\n+\t\t\tsetup_bisect_all(info->children->next, work_item->bisect);\n+\t\t\tfull = info->children->item;\n+\t\t\thalf_step ^= 1;\n+\t\t\tif (half_step) {\n+\t\t\t\tinfo = get_commit_info(half);\n+\t\t\t\thalf = info->children->item;\n+\t\t\t}\n+\t\t\tif (full->object.flags & (POPPED|NOTCOMMON))\n+\t\t\t\tbreak;\n \t\t}\n \n-\t\trev_list = rev_list->next;\n+\t\tif (full->object.flags & POPPED\n+\t\t    && !(full->object.flags & COMMON)\n+\t\t    && !(half->object.flags & (NOTCOMMON|POPPED))) {\n+\t\t\tsetup_bisect(half, work_item->bisect);\n+\t\t\thalf->object.flags |= POPPED;\n+\t\t\tfree(work_item);\n+\t\t\treturn half;\n+\t\t}\n \t}\n \n-\treturn commit->object.sha1;\n+\tfree(work_item);\n+\treturn NULL;\n }\n \n+\n+/*\n+  Get the next revision to send.\n+*/\n+\n+static struct commit *get_rev(void)\n+{\n+\tstruct commit *commit = NULL;\n+\n+\twhile (commit == NULL && work_list) {\n+\t\tstruct work_list *work_item = NULL;\n+\n+\t\twork_item = work_list;\n+\t\t/* we update the pointer early so the get_rev\n+\t\t * functions can free() or reuse the work_item as\n+\t\t * required */\n+\t\twork_list = work_item->next;\n+\n+\t\tcommit = work_item->commit;\n+\n+\t\tcheck_parsed_and_mark(commit);\n+\n+\t\tif (work_item->bisect) {\n+\t\t\tcommit = get_rev_bisect(work_item);\n+\t\t} else {\n+\t\t\tcommit = get_rev_stride(work_item);\n+\t\t}\n+\t}\n+\n+\treturn commit;\n+}\n+\n+static void pop_outstanding()\n+{\n+\tstruct commit_list *item = outstanding;\n+\toutstanding = item->next;\n+\tfree(item);\n+}\n+\n+\n static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t       struct ref *refs)\n {\n \tint fetching;\n \tint count = 0, flushes = 0, retval;\n+\tstruct commit *commit;\n \tconst unsigned char *sha1;\n \tunsigned in_vain = 0;\n \tint got_continue = 0;\n@@ -192,7 +477,7 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t}\n \n \t\tif (!fetching)\n-\t\t\tpacket_write(fd[1], \"want %s%s%s%s%s%s%s%s\\n\",\n+\t\t\tpacket_write(fd[1], \"want %s%s%s%s%s%s%s%s%s\\n\",\n \t\t\t\t     sha1_to_hex(remote),\n \t\t\t\t     (multi_ack ? \" multi_ack\" : \"\"),\n \t\t\t\t     (use_sideband == 2 ? \" side-band-64k\" : \"\"),\n@@ -200,6 +485,7 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t\t\t     (args.use_thin_pack ? \" thin-pack\" : \"\"),\n \t\t\t\t     (args.no_progress ? \" no-progress\" : \"\"),\n \t\t\t\t     (args.include_tag ? \" include-tag\" : \"\"),\n+\t\t\t\t     (exp_stride_algorithm ? \" exp-stride\" : \"\"),\n \t\t\t\t     \" ofs-delta\");\n \t\telse\n \t\t\tpacket_write(fd[1], \"want %s\\n\", sha1_to_hex(remote));\n@@ -243,13 +529,25 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \n \tflushes = 0;\n \tretval = -1;\n-\twhile ((sha1 = get_rev())) {\n+\twhile ((commit = get_rev())) {\n+\t\tsha1 = commit->object.sha1;\n \t\tpacket_write(fd[1], \"have %s\\n\", sha1_to_hex(sha1));\n \t\tif (args.verbose)\n \t\t\tfprintf(stderr, \"have %s\\n\", sha1_to_hex(sha1));\n \t\tin_vain++;\n+\n+\t\tif (outstanding) {\n+\t\t\tcommit_list_insert(commit, &(outstanding_end->next));\n+\t\t\toutstanding_end = outstanding_end->next;\n+\t\t} else {\n+\t\t\tcommit_list_insert(commit, &outstanding);\n+\t\t\toutstanding_end = outstanding;\n+\t\t}\n+\n \t\tif (!(31 & ++count)) {\n \t\t\tint ack;\n+\t\t\tint unwound = 0;\n+\t\t\tstruct commit_list *item;\n \n \t\t\tpacket_flush(fd[1]);\n \t\t\tflushes++;\n@@ -274,12 +572,23 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t\t\t} else if (ack == 2) {\n \t\t\t\t\tstruct commit *commit =\n \t\t\t\t\t\tlookup_commit(result_sha1);\n+\t\t\t\t\twhile (commit != outstanding->item) {\n+\t\t\t\t\t\tmark_not_common(outstanding->item);\n+\t\t\t\t\t\tpop_outstanding();\n+\t\t\t\t\t\tunwound++;\n+\t\t\t\t\t}\n+\t\t\t\t\tpop_outstanding();\n+\t\t\t\t\tunwound++;\n \t\t\t\t\tmark_common(commit, 0, 1);\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}\n \t\t\t} while (ack);\n+\t\t\twhile (unwound++ < 32) {\n+\t\t\t\tmark_not_common(outstanding->item);\n+\t\t\t\tpop_outstanding();\n+\t\t\t}\n \t\t\tflushes--;\n \t\t\tif (got_continue && MAX_IN_VAIN < in_vain) {\n \t\t\t\tif (args.verbose)\n@@ -445,9 +754,8 @@ static int everything_local(struct ref **refs, int nr_match, char **match)\n \t\t\tcontinue;\n \n \t\tif (!(o->flags & SEEN)) {\n-\t\t\trev_list_push((struct commit *)o, COMMON_REF | SEEN);\n-\n-\t\t\tmark_common((struct commit *)o, 1, 1);\n+\t\t\trev_list_push((struct commit *)o, 1, 0, 0);\n+\t\t\to->flags |= COMMON_REF;\n \t\t}\n \t}\n \n@@ -597,6 +905,11 @@ static struct ref *do_fetch_pack(int fd[2],\n \t\t\tfprintf(stderr, \"Server supports side-band\\n\");\n \t\tuse_sideband = 1;\n \t}\n+\tif (server_supports(\"exp-stride\")) {\n+\t\tif (args.verbose)\n+\t\t\tfprintf(stderr, \"Server supports exp-stride\\n\");\n+\t\texp_stride_algorithm = 1;\n+\t}\n \tif (everything_local(&ref, nr_match, match)) {\n \t\tpacket_flush(fd[1]);\n \t\tgoto all_done;\ndiff --git a/upload-pack.c b/upload-pack.c\nindex e5adbc0..14012ee 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -37,6 +37,7 @@ static unsigned int timeout;\n  */\n static int use_sideband;\n static int debug_fd;\n+static int exp_stride_algorithm;\n \n static void reset_timeout(void)\n {\n@@ -414,7 +415,7 @@ static int get_common_commits(void)\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\tif (multi_ack && ok_to_give_up())\n+\t\t\t\tif (multi_ack && !exp_stride_algorithm && ok_to_give_up())\n \t\t\t\t\tpacket_write(1, \"ACK %s continue\\n\",\n \t\t\t\t\t\t     sha1_to_hex(sha1));\n \t\t\t\tbreak;\n@@ -501,6 +502,8 @@ static void receive_needs(void)\n \t\t\tno_progress = 1;\n \t\tif (strstr(line+45, \"include-tag\"))\n \t\t\tuse_include_tag = 1;\n+\t\tif (strstr(line+45, \"exp-stride\"))\n+\t\t\texp_stride_algorithm = 1;\n \n \t\t/* We have sent all our refs already, and the other end\n \t\t * should have chosen out of them; otherwise they are\n@@ -573,7 +576,7 @@ static int send_ref(const char *refname, const unsigned char *sha1, int flag, vo\n {\n \tstatic const char *capabilities = \"multi_ack thin-pack side-band\"\n \t\t\" side-band-64k ofs-delta shallow no-progress\"\n-\t\t\" include-tag\";\n+\t\t\" include-tag exp-stride\";\n \tstruct object *o = parse_object(sha1);\n \n \tif (!o)\n-- \ntg: (759ad19..) t/fetch-pack-speedup (depends on: origin/master)\n"},{"id":"93860","messageId":"alpine.LFD.2.00.0810241144260.3061@xanadu.home","threadId":"15569","inReplyTo":"1224790716-20551-1-git-send-email-trast@student.ethz.ch","subject":"Re: [RFC PATCH v2] fetch-pack: log(n)-transmission find_common()","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-10-24T15:49:56Z","receivedAt":"2008-10-24T15:49:56Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 23 Oct 2008, Thomas Rast wrote:\n\n> Replaces the existing simple history search with a more sophisticated\n> algorithm:\n> \n> 1) Walk history with exponentially increasing stride lengths; i.e.,\n>    send the 1st commit, then the 2nd after that, then the 4th after\n>    that, and so on.\n> \n> 2) Bisect the resulting intervals.\n> \n> Combined with tracking the \"outstanding haves\" so that we can detect\n> which sha1s were never ACKed by upload-pack (and hence not common),\n> this gives O(log(n)) required \"have\" lines.\n> \n> Unfortunately this cannot work if the server sends fake ACKs, so we\n> introduce a capability 'exp-stride' which instructs upload-pack to\n> disable ok_to_give_up().  (Which incidentally saves the server a lot\n> of work.)\n> \n> Signed-off-by: Thomas Rast <trast@student.ethz.ch>\n> \n> ---\n> \n> This is a simple resend of v2, in the hope of attracting some\n> discussion or at least encouraging words this time around.\n\nOK, I gave this a quick try, and fetch operations appear to make their \nmind about what to do quicker.  Some fetch requests which used to take \nup to 5 seconds are somewhat faster.  I have no formal measurements \nthough.\n\n\nNicolas\n"},{"id":"94039","messageId":"20081027192923.6117@nanako3.lavabit.com","threadId":"15569","inReplyTo":"1224790716-20551-1-git-send-email-trast@student.ethz.ch","subject":"Re: [RFC PATCH v2] fetch-pack: log(n)-transmission find_common()","fromName":"Nanako Shiraishi","fromEmail":"nanako3@lavabit.com","sentAt":"2008-10-27T10:29:23Z","receivedAt":"2008-10-27T10:29:23Z","isPatch":true,"sender":{"key":"nanako3@lavabit.com","avatar":"https://gravatar.com/avatar/3777b9e201c5883a62b1a6fdf7c53f2d712d1d80989146063ea861e33aad72a8?d=mp&s=160"},"body":"Quoting Thomas Rast <trast@student.ethz.ch>:\n\n> Replaces the existing simple history search with a more sophisticated\n> algorithm:\n> \n> 1) Walk history with exponentially increasing stride lengths; i.e.,\n>    send the 1st commit, then the 2nd after that, then the 4th after\n>    that, and so on.\n> \n> 2) Bisect the resulting intervals.\n\nJunio, may I ask what the status of this patch is? I see Nicolas responded and said \"I gave this a quick try\". Wasn't it a good enough review?\n\n-- \nNanako Shiraishi\nhttp://ivory.ap.teacup.com/nanako3/\n"},{"id":"94088","messageId":"7vljw9h061.fsf@gitster.siamese.dyndns.org","threadId":"15569","inReplyTo":"20081027192923.6117@nanako3.lavabit.com","subject":"Re: [RFC PATCH v2] fetch-pack: log(n)-transmission find_common()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-10-28T03:24:22Z","receivedAt":"2008-10-28T03:24:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nanako Shiraishi <nanako3@lavabit.com> writes:\n\n> Quoting Thomas Rast <trast@student.ethz.ch>:\n>\n>> Replaces the existing simple history search with a more sophisticated\n>> algorithm:\n>> \n>> 1) Walk history with exponentially increasing stride lengths; i.e.,\n>>    send the 1st commit, then the 2nd after that, then the 4th after\n>>    that, and so on.\n>> \n>> 2) Bisect the resulting intervals.\n>\n> Junio, may I ask what the status of this patch is? I see Nicolas responded and said \"I gave this a quick try\". Wasn't it a good enough review?\n\nI took the \"quick try\" more about \"first feel in performance\" and not\n\"code review concentrating on correctness and trying to catch mistakes\".\n\nI like what the patch tries to solve, and the approach it takes to solve\nit.  I haven't had a chance to have a block of time for me to concentrate\non this patch to assess where it could go wrong yet.\n"},{"id":"94112","messageId":"alpine.LFD.2.00.0810281034500.13034@xanadu.home","threadId":"15569","inReplyTo":"7vljw9h061.fsf@gitster.siamese.dyndns.org","subject":"Re: [RFC PATCH v2] fetch-pack: log(n)-transmission find_common()","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-10-28T14:46:02Z","receivedAt":"2008-10-28T14:46:02Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 27 Oct 2008, Junio C Hamano wrote:\n\n> Nanako Shiraishi <nanako3@lavabit.com> writes:\n> \n> > Quoting Thomas Rast <trast@student.ethz.ch>:\n> >\n> >> Replaces the existing simple history search with a more sophisticated\n> >> algorithm:\n> >> \n> >> 1) Walk history with exponentially increasing stride lengths; i.e.,\n> >>    send the 1st commit, then the 2nd after that, then the 4th after\n> >>    that, and so on.\n> >> \n> >> 2) Bisect the resulting intervals.\n> >\n> > Junio, may I ask what the status of this patch is? I see Nicolas responded and said \"I gave this a quick try\". Wasn't it a good enough review?\n> \n> I took the \"quick try\" more about \"first feel in performance\" and not\n> \"code review concentrating on correctness and trying to catch mistakes\".\n\nExact.\n\nFWIW, I had to back this patch out from my version as things seemed to \nfall into an infinite loop of ref negotiation while fetching the Linux \nkernel repository at some point.  Doing a \"git fetch -v -v\" turned up an \nendless stream of \"got\" and \"have\" lines.  I was in a hurry for $work so \ndidn't think of preserving my local refs for reproduction of the \nproblem.\n\nSorry for not being more helpful.  This is some part of git that I know \nf-all about.\n\n\nNicolas\n"},{"id":"94131","messageId":"200810282037.36275.trast@student.ethz.ch","threadId":"15569","inReplyTo":"alpine.LFD.2.00.0810281034500.13034@xanadu.home","subject":"Re: [RFC PATCH v2] fetch-pack: log(n)-transmission find_common()","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2008-10-28T19:37:33Z","receivedAt":"2008-10-28T19:37:33Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Nicolas Pitre wrote:\n> \n> FWIW, I had to back this patch out from my version as things seemed to \n> fall into an infinite loop of ref negotiation while fetching the Linux \n> kernel repository at some point.  Doing a \"git fetch -v -v\" turned up an \n> endless stream of \"got\" and \"have\" lines.  I was in a hurry for $work so \n> didn't think of preserving my local refs for reproduction of the \n> problem.\n\nAh.  Thanks for the report, though having a test case would be great.\nI've been running it without problems since I completed v2 more than a\nmonth ago, so I don't expect it to be an obvious mistake.\n\n- Thomas\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n\n"},{"id":"97288","messageId":"1228605621-29685-1-git-send-email-trast@student.ethz.ch","threadId":"15569","inReplyTo":"alpine.LFD.2.00.0810281034500.13034@xanadu.home","subject":"[RFC PATCH v3 0/2] fetch-pack: log(n)-transmission find_common()","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2008-12-06T23:20:19Z","receivedAt":"2008-12-06T23:20:19Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"If you still know what this was about, you can skip ahead to the \"==\"\nmarker below.\n\n\nThe mail that started it all was\n\n  http://kerneltrap.org/mailarchive/git/2008/9/17/3328364\n\n  [Abstract:]\n  Using two passes, first exponential stride through history, then\n  bisection on the \"right\" windows, we implement the find_common\n  handshake in log(history_size) many transmissions.  The followup\n  patch partially achieves that, but a few points are open and strict\n  backwards compatibility is missing (but its absence is Mostly\n  Harmless).\n\nThis spawned out of a problem originally reported on IRC where pulling\nseveral disjoint histories together takes ages (due to the load on the\nserver caused by ok_to_give_up()).  Apparently this is a common\nworkflow in the Ruby-on-Rails.  The bound on the number of\ntransmissions holds in other cases too, of course.\n\nThe idea attracted some interest, but to my knowledge nobody actually\nreviewed the code, and it eventually died because of Nicholas's\nfinding:\n\nNicolas Pitre wrote:\n> FWIW, I had to back this patch out from my version as things seemed to \n> fall into an infinite loop of ref negotiation while fetching the Linux \n> kernel repository at some point.  Doing a \"git fetch -v -v\" turned up an \n> endless stream of \"got\" and \"have\" lines.  I was in a hurry for $work so \n> didn't think of preserving my local refs for reproduction of the \n> problem.\n\nUnfortunately, I was never able to reliably reproduce this problem.\n(IIRC I did once when running an automated hammering script but it\nvanished when I tried again manually.)\n\n\n\n==\n\nAfter a long break, I decided to pick this up again.  I'm not sure\nthis is the best time to do so, but I had the time to spare, and\n(unless there are more serious bugs, and Gods and Junio willing) we\nmight get it into 'next' sometime early in the next cycle for better\ntesting.\n\nI rewrote the core of the algorithm, though some helpers and most of\nthe glue to surrounding routines are still the same.  I took the\nfollowing design decisions that weren't in v2:\n\n0. Lots of comments.  Well, by my standards in any case.\n\n1. The old code stays.  I mostly want to make it (far) easier to be\n   certain that it behaves exactly as before if the server does not\n   support disabling ok_to_give_up().  [The idea is that it should be\n   easy to verify that 1/2 is a no-change refactoring and 2/2 only\n   does something if the server supports it.]\n\n2. The work list now uses a Fibonacci heap to order jobs.  I'm not\n   religious about the specific flavour of heap, but I had the\n   description of these handy.  (The work list can get rather large.)\n\n3. The bisection is essentially precomputed.  By staring at the binary\n   representation of the distance from the starting commit hard\n   enough, it can be constructed during the stride pass.  Barring a\n   circular bisection \"tree\", the algorithm is now guaranteed to\n   terminate even if it, say, emits too many or too few sha1s due to\n   some other bug.\n\nThe last point of course means that the main work is now in the\ntangled mess that is get_rev_new_stride(), and \"staring hard enough\"\nfrequently enough meant grabbing a notepad.  YMMV.\n\nWhile I did run a lot of tests, including 'make test' and some\nautomated hammering, it seems quite hard to make sure it _really_\nbisects correctly (except manually in toy examples, such as two linear\nhistories with a common base).  Suggestions for automated tests\nwelcome.\n\nTo see the effects of the patch, try\n\n  git fetch-pack -v -k <url> <head> 2>&1 \\\n    | git name-rev --stdin refs/heads/master\n\nwith a daemon that supports the feature.\n"},{"id":"97287","messageId":"1228605621-29685-2-git-send-email-trast@student.ethz.ch","threadId":"15569","inReplyTo":"1228605621-29685-1-git-send-email-trast@student.ethz.ch","subject":"[RFC PATCH v3 1/2] fetch-pack: rearrange main loop","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2008-12-06T23:20:20Z","receivedAt":"2008-12-06T23:20:20Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"This patch does not change the results (nor any of the semantics\nexcept for the get_rev return type), but we need the changed layout\nfor the exponential-stride feature.\n\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n\n---\n builtin-fetch-pack.c |  108 +++++++++++++++++++++++++++++--------------------\n 1 files changed, 64 insertions(+), 44 deletions(-)\n\ndiff --git a/builtin-fetch-pack.c b/builtin-fetch-pack.c\nindex 372bfa2..ae0a67a 100644\n--- a/builtin-fetch-pack.c\n+++ b/builtin-fetch-pack.c\n@@ -111,7 +111,7 @@ static void mark_common(struct commit *commit,\n   Get the next rev to send, ignoring the common.\n */\n \n-static const unsigned char* get_rev(void)\n+static struct commit* get_rev(void)\n {\n \tstruct commit *commit = NULL;\n \n@@ -153,15 +153,41 @@ static const unsigned char* get_rev(void)\n \t\trev_list = rev_list->next;\n \t}\n \n-\treturn commit->object.sha1;\n+\treturn commit;\n }\n \n+/*\n+ * Send 'have' for the next batch of revisions.  Returns 0 if we ran\n+ * out of commits to send, 1 otherwise.\n+ */\n+\n+static int send_have_lines(int fd[2], int *flushes, unsigned *in_vain)\n+{\n+\tstruct commit *commit;\n+\tint i;\n+\n+\tfor (i = 0; i < 32; i++) {\n+\t\tcommit = get_rev();\n+\t\tif (!commit)\n+\t\t\treturn 0;\n+\t\tpacket_write(fd[1], \"have %s\\n\",\n+\t\t\t     sha1_to_hex(commit->object.sha1));\n+\t\tif (args.verbose)\n+\t\t\tfprintf(stderr, \"have %s\\n\",\n+\t\t\t\tsha1_to_hex(commit->object.sha1));\n+\t}\n+\tpacket_flush(fd[1]);\n+\t*flushes += 1;\n+\t*in_vain += 32;\n+\treturn 1;\n+}\n+\n+\n static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t       struct ref *refs)\n {\n \tint fetching;\n \tint count = 0, flushes = 0, retval;\n-\tconst unsigned char *sha1;\n \tunsigned in_vain = 0;\n \tint got_continue = 0;\n \n@@ -243,51 +269,45 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \n \tflushes = 0;\n \tretval = -1;\n-\twhile ((sha1 = get_rev())) {\n-\t\tpacket_write(fd[1], \"have %s\\n\", sha1_to_hex(sha1));\n-\t\tif (args.verbose)\n-\t\t\tfprintf(stderr, \"have %s\\n\", sha1_to_hex(sha1));\n-\t\tin_vain++;\n-\t\tif (!(31 & ++count)) {\n-\t\t\tint ack;\n \n-\t\t\tpacket_flush(fd[1]);\n-\t\t\tflushes++;\n+\t/*\n+\t * We keep one window \"ahead\" of the other side, and\n+\t * will wait for an ACK only on the next one\n+\t */\n+\tif (!send_have_lines(fd, &flushes, &in_vain))\n+\t\tgoto done;\n \n-\t\t\t/*\n-\t\t\t * We keep one window \"ahead\" of the other side, and\n-\t\t\t * will wait for an ACK only on the next one\n-\t\t\t */\n-\t\t\tif (count == 32)\n-\t\t\t\tcontinue;\n+\twhile (send_have_lines(fd, &flushes, &in_vain)) {\n+\t\tint ack;\n+\t\tint unwound = 0;\n \n-\t\t\tdo {\n-\t\t\t\tack = get_ack(fd[0], result_sha1);\n-\t\t\t\tif (args.verbose && ack)\n-\t\t\t\t\tfprintf(stderr, \"got ack %d %s\\n\", ack,\n-\t\t\t\t\t\t\tsha1_to_hex(result_sha1));\n-\t\t\t\tif (ack == 1) {\n-\t\t\t\t\tflushes = 0;\n-\t\t\t\t\tmulti_ack = 0;\n-\t\t\t\t\tretval = 0;\n-\t\t\t\t\tgoto done;\n-\t\t\t\t} else if (ack == 2) {\n-\t\t\t\t\tstruct commit *commit =\n-\t\t\t\t\t\tlookup_commit(result_sha1);\n-\t\t\t\t\tmark_common(commit, 0, 1);\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}\n-\t\t\t} while (ack);\n-\t\t\tflushes--;\n-\t\t\tif (got_continue && MAX_IN_VAIN < in_vain) {\n-\t\t\t\tif (args.verbose)\n-\t\t\t\t\tfprintf(stderr, \"giving up\\n\");\n-\t\t\t\tbreak; /* give up */\n+\t\tdo {\n+\t\t\tack = get_ack(fd[0], result_sha1);\n+\t\t\tif (args.verbose && ack)\n+\t\t\t\tfprintf(stderr, \"got ack %d %s\\n\", ack,\n+\t\t\t\t\tsha1_to_hex(result_sha1));\n+\t\t\tif (ack == 1) {\n+\t\t\t\tflushes = 0;\n+\t\t\t\tmulti_ack = 0;\n+\t\t\t\tretval = 0;\n+\t\t\t\tgoto done;\n+\t\t\t} else if (ack == 2) {\n+\t\t\t\tstruct commit *commit =\n+\t\t\t\t\tlookup_commit(result_sha1);\n+\t\t\t\tmark_common(commit, 0, 1);\n+\t\t\t\tretval = 0;\n+\t\t\t\tin_vain = 0;\n+\t\t\t\tgot_continue = 1;\n \t\t\t}\n+\t\t} while (ack);\n+\t\tflushes--;\n+\t\tif (got_continue && MAX_IN_VAIN < in_vain) {\n+\t\t\tif (args.verbose)\n+\t\t\t\tfprintf(stderr, \"giving up\\n\");\n+\t\t\tbreak; /* give up */\n \t\t}\n \t}\n+\n done:\n \tpacket_write(fd[1], \"done\\n\");\n \tif (args.verbose)\n-- \ntg: (7f705dc..) t/fp-refactor (depends on: origin/master)\n"},{"id":"97289","messageId":"1228605621-29685-3-git-send-email-trast@student.ethz.ch","threadId":"15569","inReplyTo":"1228605621-29685-2-git-send-email-trast@student.ethz.ch","subject":"[RFC PATCH v3 2/2] fetch-pack: log(n)-transmission find_common()","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2008-12-06T23:20:21Z","receivedAt":"2008-12-06T23:20:21Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Replaces the existing simple history search with a more sophisticated\nalgorithm:\n\n1) Walk history with exponentially increasing stride lengths; i.e.,\n   send the 1st commit, then the 2nd after that, then the 4th after\n   that, and so on.\n\n2) Bisect the resulting intervals.\n\nCombined with tracking the \"outstanding haves\" so that we can detect\nwhich sha1s were never ACKed by upload-pack (and hence not common),\nthis gives O(log(n)) required \"have\" lines.\n\nUnfortunately this cannot work if the server sends fake ACKs, so we\nintroduce a capability 'no-giveup' which instructs upload-pack to\ndisable ok_to_give_up().  (Which incidentally saves the server a lot\nof work.)\n\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n\n---\n builtin-fetch-pack.c |  789 +++++++++++++++++++++++++++++++++++++++++++++++++-\n upload-pack.c        |    7 +-\n 2 files changed, 787 insertions(+), 9 deletions(-)\n\ndiff --git a/builtin-fetch-pack.c b/builtin-fetch-pack.c\nindex ae0a67a..ea88e28 100644\n--- a/builtin-fetch-pack.c\n+++ b/builtin-fetch-pack.c\n@@ -9,6 +9,7 @@\n #include \"fetch-pack.h\"\n #include \"remote.h\"\n #include \"run-command.h\"\n+#include <string.h>\n \n static int transfer_unpack_limit = -1;\n static int fetch_unpack_limit = -1;\n@@ -25,6 +26,14 @@ static const char fetch_pack_usage[] =\n #define COMMON_REF\t(1U << 2)\n #define SEEN\t\t(1U << 3)\n #define POPPED\t\t(1U << 4)\n+#define BISECTED_FW\t(1U << 5)\n+#define BISECTED_BW\t(1U << 6)\n+#define NOTCOMMON       (1U << 7)\n+#define HAS_INFO        (1U << 8)\n+#define PARSED_WITH_PARENTS (1U << 9)\n+#define CLEAN_MARKS     (COMMON | COMMON_REF | SEEN | POPPED | BISECTED_FW \\\n+\t\t\t | BISECTED_BW | NOTCOMMON | HAS_INFO \\\n+\t\t\t | PARSED_WITH_PARENTS)\n \n static int marked;\n \n@@ -34,8 +43,61 @@ static int marked;\n  */\n #define MAX_IN_VAIN 256\n \n+struct work_heap\n+{\n+\tstruct work_heap *next;\n+\tstruct work_heap *prev;\n+\tstruct work_item *item;\n+};\n+\n+struct work_item\n+{\n+\t/* Fibonacci heap data */\n+\t/* we don't need a parent pointer because we don't support changing keys */\n+\tstruct work_item *child;\n+\tstruct work_item *sibling;\n+\tint rank;\n+\tint marked;\n+\n+\t/* actual content */\n+\tstruct commit *commit;\n+\tunsigned int stride;  /* for stride mode */\n+\tunsigned int steps;\n+\tunsigned int depth;\n+\tunsigned int bisect;  /* for bisection mode */\n+\n+\t/*\n+\t * Helper array to generate the bisection order.  A size of 32\n+\t * is ok as long as the history length is less than 2**32.\n+\t */\n+\tstruct commit **ladder;\n+};\n+\n+/*\n+ * \"Recursion stack\" of the exponential-stride algorithm\n+ *\n+ * This is a priority queue implemented as a Fibonacci heap since we\n+ * expect to stuff a lot of commits into it.\n+ */\n+static struct work_heap *work_heap = NULL;\n+static struct work_heap *work_min = NULL;\n+\n+/* list of commits not ACKed yet */\n+static struct commit_list *outstanding = NULL;\n+static struct commit_list *outstanding_end = NULL;\n+\n+struct commit_info\n+{\n+\tstruct commit_list *children;\n+\tstruct commit_list *bisect_forward;\n+\tstruct commit_list *bisect_backward;\n+\tstruct commit_list *forward_bound;\n+\tstruct commit_list *backward_bound;\n+};\n+\n static struct commit_list *rev_list;\n static int non_common_revs, multi_ack, use_sideband;\n+static int exp_stride_algorithm;\n \n static void rev_list_push(struct commit *commit, int mark)\n {\n@@ -68,8 +130,7 @@ static int clear_marks(const char *path, const unsigned char *sha1, int flag, vo\n \tstruct object *o = deref_tag(parse_object(sha1), path, 0);\n \n \tif (o && o->type == OBJ_COMMIT)\n-\t\tclear_commit_marks((struct commit *)o,\n-\t\t\t\t   COMMON | COMMON_REF | SEEN | POPPED);\n+\t\tclear_commit_marks((struct commit *)o, CLEAN_MARKS);\n \treturn 0;\n }\n \n@@ -107,6 +168,354 @@ static void mark_common(struct commit *commit,\n \t}\n }\n \n+static struct commit_info *get_commit_info(struct commit *commit)\n+{\n+\tif (commit->object.flags & HAS_INFO)\n+\t\treturn commit->util;\n+\n+\tstruct commit_info *info = xmalloc(sizeof(struct commit_info));\n+\tinfo->children = NULL;\n+\tinfo->bisect_forward = NULL;\n+\tinfo->bisect_backward = NULL;\n+\tinfo->forward_bound = NULL;\n+\tinfo->backward_bound = NULL;\n+\tcommit->util = info;\n+\tcommit->object.flags |= HAS_INFO;\n+\treturn info;\n+}\n+\n+static void add_child(struct commit *parent, struct commit *child)\n+{\n+\tstruct commit_info *info = get_commit_info(parent);\n+\tstruct commit_list *item;\n+\tfor (item = info->children; item; item = item->next)\n+\t\tif (item->item == child)\n+\t\t\tbreak;\n+\tif (!item)\n+\t\tcommit_list_insert(child, &(info->children));\n+}\n+\n+/* implemented further below */\n+static void mark_not_common(struct commit *commit);\n+\n+static void check_parsed_and_mark(struct commit *commit)\n+{\n+\tstruct commit_list *parent;\n+\n+\tif (!commit || commit->object.flags & PARSED_WITH_PARENTS)\n+\t\treturn;\n+\n+\tparse_commit(commit);\n+\n+\tcommit->object.flags |= PARSED_WITH_PARENTS;\n+\n+\tfor (parent = commit->parents; parent; parent = parent->next) {\n+\t\tadd_child(parent->item, commit);\n+\t\tif (parent->item->object.flags & NOTCOMMON)\n+\t\t\tmark_not_common(commit);\n+\t}\n+}\n+\n+static void work_item_free(struct work_item *item)\n+{\n+\tif (!item->bisect)\n+\t\tfree(item->ladder);\n+\tfree(item);\n+}\n+\n+/*\n+ * Ordering imposed on the \"recursion\" that generates the commits.\n+ * The smallest item is processed first.  To maintain the O(log n)\n+ * transmissions bound we want to achieve, bisections must come after\n+ * (compare >0) strides.\n+ */\n+\n+static int work_item_cmp(struct work_item *a, struct work_item *b)\n+{\n+\tif (a->bisect || b->bisect) {\n+\t\t/* bisections last */\n+\t\tif (a->bisect > b->bisect)\n+\t\t\treturn 1;\n+\t\telse if (a->bisect < b->bisect)\n+\t\t\treturn -1;\n+\n+\t\t/* older commits later */\n+\t\tif (a->commit->date < b->commit->date)\n+\t\t\treturn 1;\n+\t\telse if (a->commit->date == b->commit->date)\n+\t\t\treturn 0;\n+\t\telse\n+\t\t\treturn -1;\n+\t} else {\n+\t\t/* deeper sidelines of history later */\n+\t\tif (a->depth > b->depth)\n+\t\t\treturn 1;\n+\t\telse if (a->depth < b->depth)\n+\t\t\treturn -1;\n+\n+\t\t/* older commits later */\n+\t\tif (a->commit->date < b->commit->date)\n+\t\t\treturn 1;\n+\t\telse if (a->commit->date == b->commit->date)\n+\t\t\treturn 0;\n+\t\telse\n+\t\t\treturn -1;\n+\t}\n+}\n+\n+/*\n+ * Insert/remove items from the work_heap.  _pop() always returns the\n+ * smallest one.\n+ */\n+\n+static void work_heap_insert_internal(struct work_item *item)\n+{\n+\tstruct work_heap *entry = xmalloc(sizeof(struct work_heap));\n+\tentry->item = item;\n+\n+\tif (!work_heap) {\n+\t\tentry->prev = entry;\n+\t\tentry->next = entry;\n+\t\twork_heap = entry;\n+\t\twork_min = work_heap;\n+\t\treturn;\n+\t}\n+\n+\tentry->next = work_heap;\n+\tentry->prev = work_heap->prev;\n+\twork_heap->prev = entry;\n+\tentry->prev->next = entry;\n+\tif (!work_min || work_item_cmp(item, work_min->item) < 0)\n+\t\twork_min = entry;\n+\twork_heap = entry;\n+}\n+\n+static void work_heap_insert(struct work_item *item)\n+{\n+\titem->marked = 0;\n+\titem->child = NULL;\n+\titem->sibling = NULL;\n+\titem->rank = 0;\n+\n+\twork_heap_insert_internal(item);\n+}\n+\n+static struct work_item *work_heap_pop(void)\n+{\n+\tstruct work_heap *entry = work_min;\n+\tstruct work_item *x, *y, *t;\n+\tstruct work_item *child, *item;\n+\t/* The rank of any child in a Fib heap of size n can be at\n+\t * most log_{3/2}(n), and we only support 2**32 items\n+\t * anyway */\n+\tstruct work_item *ranks[55] = {0,};\n+\tint i;\n+\n+\tif (!entry)\n+\t\treturn NULL;\n+\n+\tif (entry == entry->prev) {\n+\t\twork_heap = NULL;\n+\t\twork_min = NULL;\n+\t\titem = entry->item;\n+\t\tfree(entry);\n+\t\tfor (child = item->child; child; child = child->sibling) {\n+\t\t\tchild->marked = 0;\n+\t\t\twork_heap_insert_internal(child);\n+\t\t}\n+\t\treturn item;\n+\t}\n+\n+\twork_heap = entry->next;\n+\tentry->next->prev = entry->prev;\n+\tentry->prev->next = entry->next;\n+\titem = entry->item;\n+\tfree(entry);\n+\twork_min = NULL;\n+\n+\tfor (child = item->child; child; child = child->sibling) {\n+\t\tchild->marked = 0;\n+\t\twork_heap_insert_internal(child);\n+\t}\n+\n+\twhile (work_heap) {\n+\t\tentry = work_heap;\n+\t\tif (entry == entry->prev) {\n+\t\t\twork_heap = NULL;\n+\t\t} else {\n+\t\t\twork_heap = entry->next;\n+\t\t\tentry->next->prev = entry->prev;\n+\t\t\tentry->prev->next = entry->next;\n+\t\t}\n+\t\tx = entry->item;\n+\t\tfree(entry);\n+\t\twhile ((y = ranks[x->rank])) {\n+\t\t\tranks[x->rank] = NULL;\n+\t\t\tif (work_item_cmp(x, y) > 0) {\n+\t\t\t\tt = x;\n+\t\t\t\tx = y;\n+\t\t\t\ty = t;\n+\t\t\t}\n+\t\t\ty->sibling = x->child;\n+\t\t\tx->child = y;\n+\t\t\tx->rank++;\n+\t\t}\n+\t\tranks[x->rank] = x;\n+\t}\n+\n+\tfor (i = 0; i < 55; i++)\n+\t\tif (ranks[i])\n+\t\t\twork_heap_insert_internal(ranks[i]);\n+\n+\treturn item;\n+}\n+\n+static void work_insert_stride(struct commit *commit, int stride,\n+\t\t\t       int steps, int depth, struct commit **ladder)\n+{\n+\tstruct work_item *item = xmalloc(sizeof(struct work_item));\n+\tcheck_parsed_and_mark(commit);\n+\titem->commit = commit;\n+\titem->stride = stride;\n+\titem->steps = steps;\n+\titem->depth = depth;\n+\titem->bisect = 0;\n+\titem->ladder = xmalloc(32*sizeof(struct commit *));\n+\tif (ladder)\n+\t\tmemcpy(item->ladder, ladder, 32*sizeof(struct commit *));\n+\twork_heap_insert(item);\n+}\n+\n+static void work_insert_bisect(struct commit *commit, int bisect)\n+{\n+\tstruct work_item *item = xmalloc(sizeof(struct work_item));\n+\titem->commit = commit;\n+\titem->stride = 0;\n+\titem->steps = 0;\n+\titem->depth = 0;\n+\titem->bisect = bisect;\n+\titem->ladder = NULL;\n+\twork_heap_insert(item);\n+}\n+\n+static void work_insert_strides(struct commit_list *commits,\n+\t\t\t\tint stride, int steps, int depth, int depth2,\n+\t\t\t\tstruct commit **ladder,\n+\t\t\t\tstruct work_item *reusable_item)\n+{\n+\tstruct work_item *item = reusable_item;\n+\n+\twhile (commits) {\n+\t\tif (!(commits->item->object.flags &= SEEN)) {\n+\t\t\tif (!item)\n+\t\t\t\titem = xmalloc(sizeof(struct work_item));\n+\n+\t\t\titem->commit = commits->item;\n+\t\t\titem->stride = stride;\n+\t\t\titem->steps = steps;\n+\t\t\titem->depth = depth;\n+\t\t\titem->bisect = 0;\n+\t\t\titem->ladder = xmalloc(32*sizeof(struct commit *));\n+\t\t\tif (ladder)\n+\t\t\t\tmemcpy(item->ladder, ladder, 32*sizeof(struct commit *));\n+\t\t\twork_heap_insert(item);\n+\t\t}\n+\t\tcommits = commits->next;\n+\t\titem = NULL;\n+\t\tdepth = depth2;\n+\t}\n+\n+\tif (item)\n+\t\twork_item_free(item);\n+}\n+\n+static void work_insert_bisects(struct commit_list *commits,\n+\t\t\t\tint bisect,\n+\t\t\t\tstruct work_item *reusable_item)\n+{\n+\tstruct work_item *item = reusable_item;\n+\n+\twhile (commits) {\n+\t\tif (!item)\n+\t\t\titem = xmalloc(sizeof(struct work_item));\n+\n+\t\titem->commit = commits->item;\n+\t\titem->stride = 0;\n+\t\titem->steps = 0;\n+\t\titem->depth = 0;\n+\t\titem->bisect = bisect;\n+\t\twork_heap_insert(item);\n+\n+\t\tcommits = commits->next;\n+\t\titem = NULL;\n+\t}\n+\n+\tif (item)\n+\t\twork_item_free(item);\n+}\n+\n+static int work_heap_insert_ref(const char *path, const unsigned char *sha1,\n+\t\t\t       int flag, void *cb_data)\n+{\n+\tstruct object *o = deref_tag(parse_object(sha1), path, 0);\n+\n+\tif (o && o->type == OBJ_COMMIT && !(o->flags & SEEN))\n+\t\twork_insert_stride((struct commit *)o, 0, 0, 0, NULL);\n+\n+\treturn 0;\n+}\n+\n+\n+/*\n+ * Marks all (known) children of this commit NOTCOMMON.  We call this\n+ * for all sha1s the server did not ACK.\n+ */\n+\n+static void mark_not_common(struct commit *commit)\n+{\n+\tstruct commit_info *info = get_commit_info(commit);\n+\tstruct commit_list *child;\n+\n+\tassert(!(commit->object.flags & COMMON));\n+\n+\tif (commit->object.flags & NOTCOMMON)\n+\t\treturn;\n+\n+\tcommit->object.flags |= NOTCOMMON;\n+\n+\tfor (child = info->children; child; child = child->next)\n+\t\tmark_not_common(child->item);\n+}\n+\n+/*\n+ * Similar for the ACKed ones.  We have a _new() version because the\n+ * old one interacts with the work queue.\n+ */\n+\n+static void mark_common_new(struct commit *commit, int ancestors_only, int dont_parse)\n+{\n+\tstruct commit_list *parents;\n+\tstruct object *o;\n+\n+\tif (commit == NULL || commit->object.flags & (COMMON_REF|COMMON))\n+\t\treturn;\n+\n+\tif (!dont_parse && !(commit->object.parsed))\n+\t\tcheck_parsed_and_mark(commit);\n+\n+\to = (struct object *)commit;\n+\n+\tif (!ancestors_only)\n+\t\to->flags |= COMMON;\n+\n+\tfor (parents = commit->parents; parents; parents = parents->next) {\n+\t\tadd_child(parents->item, commit);\n+\t\tmark_common_new(parents->item, 0, dont_parse);\n+\t}\n+}\n+\n+\n+\n /*\n   Get the next rev to send, ignoring the common.\n */\n@@ -156,6 +565,330 @@ static struct commit* get_rev(void)\n \treturn commit;\n }\n \n+\n+int flag_in_list(int flag, struct commit_list *list)\n+{\n+\twhile (list) {\n+\t\tif (list->item->object.flags & flag)\n+\t\t\treturn 1;\n+\t\tlist = list->next;\n+\t}\n+\treturn 0;\n+}\n+\n+\n+/*\n+ * Find the second bit set in x, similar to ffs() from string.h.\n+ * Assumes that x>0.\n+ */\n+\n+int fss(int x)\n+{\n+\treturn ffs(x - (1<<(ffs(x)-1)));\n+}\n+\n+/*\n+ * The exponential-stride algorithm, part 1 and 1.5.\n+ *\n+ * We take exponential strides through history, that is we emit the\n+ * 1st commit, the 2nd, the 4th, etc.  But we also simultaneously\n+ * build pointers that help us bisect later: Every commit has a\n+ * bisect_forward and bisect_backward list (if history is linear, both\n+ * have at most 1 element) that tells us where to continue bisection\n+ * after this.\n+ *\n+ * To achieve this with good running time, we think of the commits in\n+ * a line of history as being numbered in binary:\n+ *\n+ *        o 1000\n+ *        o  111\n+ *        o  110   <- current   [1]\n+ *        o  101                [0]\n+ *  t |\t  o  100                [2]\n+ *  i |\t  o   11\n+ *  m |\t  o   10\n+ *  e v\t  o    1\n+ *\n+ * Every commit of the form 10...0 is emitted, since it is an\n+ * exponential step.  Between that, we want to have\n+ * (100).bisect_backward=[110], (110).bisect_forward=[101],\n+ * (110).bisect_backward=[111], etc.  Define the lowest bit set (as\n+ * per ffs()-1) in a commit as its \"order\", then we can achieve this\n+ * by keeping track of the last commit of every order (marked with [n]\n+ * in the diagram) as we go through history.  Then [n] must be on\n+ * [n+1].bisect_backward and [n-1] must be on [n].bisect_forward.\n+ *\n+ * Similarly, we track the boundaries forward_bound and\n+ * backward_bound, which indicate the furthest commit(s) that can be\n+ * reached by bisecting this one.  We use them to detect when it\n+ * becomes pointless to pursue this branch of the bisection because\n+ * the far end is already COMMON (NOTCOMMON) in forward (backward)\n+ * mode.  In the scheme chosen, a current commit [n] numbered N is a\n+ * backward boundary of [i] for all i=0..n, and [fss(N)-1] is a\n+ * forward boundary of the current [n].\n+ *\n+ * The tough problem is if we stop (because we hit a root, or a part\n+ * of history that we've already seen) at a non-exp-stride commit.\n+ * Then we must ensure that all history up to the current commit can\n+ * be reached by bisecting.  Consider\n+ *\n+ *        o 1000\n+ *        o  111\n+ *        o  110\n+ *        o  101   <- current   [0]\n+ *  t |\t  o  100                [2]\n+ *  i |\t  o   11\n+ *  m |\t  o   10                [1]\n+ *  e v\t  o    1\n+ *\n+ * then stopping at the commit 101 without any corrective measures\n+ * would leave it unreachable because the intermediate step 110 has\n+ * not been seen yet.\n+ *\n+ * Observe that any given commit x10z, where x is arbitrary and z only\n+ * zeros, has outgoing pointers to x01z (forward) and x11z (backward).\n+ * Conversely this means x01z needs an incoming forward pointer from\n+ * x10z, even if we haven't seen it yet.  So there are two cases:\n+ *\n+ * SEEN CASE: We stopped because we hit a SEEN commit.  Assume that\n+ * the last commit not SEEN is numbered x1y1z, where x is arbitrary\n+ * and y and z are only zeros (z possibly empty).  Then unless y is\n+ * empty, x1y'01z needs an incoming forward pointer from x1y'10z\n+ * (where y'0=y), which we haven't seen yet.  Repeat until y is empty.\n+ * Note that during this repetition, we might hit a root commit.\n+ *\n+ * ROOT CASE: We cannot fix this with forward pointers since there are\n+ * no commits left to put them in.  Assume that the root commit is\n+ * numbered x1y1z as in the SEEN case.  Then we fix by pointing a\n+ * backwards pointer from x1y'00z to x1y'01z, then iterate with\n+ * x1y'00z.  Note that x1y'00z is the last seen commit of order\n+ * fss(x1y1z).\n+ *\n+ * Note that we only need to bisect (first level) exp-stride commits\n+ * in one direction.  We choose backward.  This choice needs to be\n+ * consistent among get_rev_new_stride() and get_rev_new(), and it\n+ * happens to match the faster code path of get_rev_new_bisect().\n+ */\n+\n+static struct commit *get_rev_new_stride(struct work_item *item)\n+{\n+\tstruct commit_info *info;\n+\tstruct commit *commit = item->commit;\n+\tint steps = item->steps;\n+\tint stride = item->stride;\n+\tint depth = item->depth;\n+\tint order = -1;\n+\tstruct commit **ladder = item->ladder;\n+\tint i;\n+\t/* The next two are for the pointer-fixing iterations */\n+\tint order2;\n+\tstruct commit *commit2;\n+\n+\twhile (!(commit->object.flags & SEEN)) {\n+\t\tsteps++;\n+\t\torder = ffs(steps)-1;\n+\n+\t\tcommit->object.flags |= SEEN;\n+\n+\t\tif (order > 0 && stride == order) {\n+\t\t\tinfo = get_commit_info(ladder[order-1]);\n+\t\t\tcommit_list_insert(commit, &info->backward_bound);\n+\t\t\tfor (i = order-2; i>=0; i--) {\n+\t\t\t\tinfo = get_commit_info(ladder[i]);\n+\t\t\t\tcommit_list_insert(commit, &info->backward_bound);\n+\t\t\t}\n+\t\t}\n+\n+\t\tladder[order] = commit;\n+\n+\t\tif (stride == order) {\n+\t\t\t/* this is precisely a 2**k'th commit, emit it */\n+\t\t\twork_insert_strides(commit->parents, stride+1, steps,\n+\t\t\t\t\t    depth, depth+1, ladder, item);\n+\t\t\treturn commit;\n+\t\t}\n+\n+\t\t/*\n+\t\t * We are the next step in the higher-order commit's\n+\t\t * backward (in time) bisection\n+\t\t */\n+\t\tinfo = get_commit_info(ladder[order+1]);\n+\t\tcommit_list_insert(commit, &info->bisect_backward);\n+\t\tinfo = get_commit_info(commit);\n+\t\tcommit_list_insert(ladder[fss(steps)-1], &info->forward_bound);\n+\n+\t\tif (order > 0) {\n+\t\t\t/*\n+\t\t\t * The lower-order commit is our next step for\n+\t\t\t * forward (in time) bisection\n+\t\t\t */\n+\t\t\tinfo = get_commit_info(commit);\n+\t\t\tcommit_list_insert(ladder[order-1], &info->bisect_forward);\n+\t\t\tfor (i = order-1; i >= 0; i--) {\n+\t\t\t\tinfo = get_commit_info(ladder[i]);\n+\t\t\t\tcommit_list_insert(commit, &info->backward_bound);\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (commit->parents) {\n+\t\t\twork_insert_strides(commit->parents->next, stride,\n+\t\t\t\t\t    steps, depth+1, depth+1, ladder,\n+\t\t\t\t\t    NULL);\n+\t\t\tcommit = commit->parents->item;\n+\t\t\tcheck_parsed_and_mark(commit);\n+\t\t} else {\n+\t\t\t/* ROOT CASE: fix missing pointers */\n+\t\t\torder2 = fss(steps)-1;\n+\t\t\tcommit2 = commit;\n+\t\t\twhile (order != order2-1 && order2 > 0) {\n+\t\t\t\tinfo = get_commit_info(ladder[order2]);\n+\t\t\t\tcommit_list_insert(commit2, &info->bisect_backward);\n+\t\t\t\tinfo = get_commit_info(commit2);\n+\t\t\t\tcommit_list_insert(ladder[order2], &info->forward_bound);\n+\t\t\t\tcommit2 = ladder[order2];\n+\t\t\t\tsteps -= 1 << order;\n+\t\t\t\torder = order2;\n+\t\t\t\torder2 = fss(steps)-1;\n+\t\t\t}\n+\t\t\twork_item_free(item);\n+\t\t\treturn commit;\n+\t\t}\n+\t}\n+\n+\tif (order == -1) {\n+\t\t/* this just means we hit a SEEN commit immediately */\n+\t\twork_item_free(item);\n+\t\treturn  NULL;\n+\t}\n+\n+\t/* SEEN CASE: fix missing pointers w.r.t. the _last_ commit\n+\t * before this */\n+\n+\t/* unless/until we hit a root, 'commit' tracks the steps\n+\t * backward through the SEEN commits that we stick the\n+\t * pointers in.  'order2' only serves to figure out if the 'y'\n+\t * (see comment at function head) of 'commit' is empty. */\n+\torder2 = fss(steps)-1;\n+\tassert(order2 > order || order2 == 0);\n+\twhile (order != order2-1 && order2 > 0) {\n+\t\tint i;\n+\t\t/* skip ahead to the next commit2 of order 'order+1' */\n+\t\tfor (i = (1<<order); i > 0; i--) {\n+\t\t\tsteps++;\n+\t\t\tassert (steps < (1<<stride));\n+\t\t\tif (commit->parents) {\n+\t\t\t\tcommit = commit->parents->item;\n+\t\t\t\tcheck_parsed_and_mark(commit);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\t/* we hit a root commit! use the root strategy\n+\t\t\t * for the rest */\n+\t\t\torder2 = fss(steps)-1;\n+\t\t\tcommit2 = commit;\n+\t\t\twhile (order != order2-1 && order2 > 0) {\n+\t\t\t\tinfo = get_commit_info(ladder[order2]);\n+\t\t\t\tcommit_list_insert(commit2, &info->bisect_backward);\n+\t\t\t\tinfo = get_commit_info(commit2);\n+\t\t\t\tcommit_list_insert(ladder[order2], &info->forward_bound);\n+\t\t\t\tcommit2 = ladder[order2];\n+\t\t\t\tsteps -= 1 << order;\n+\t\t\t\torder = order2;\n+\t\t\t\torder2 = fss(steps)-1;\n+\t\t\t}\n+\t\t\t/* short-cut out of the big loop */\n+\t\t\twork_item_free(item);\n+\t\t\treturn NULL;\n+\t\t}\n+\t\tinfo = get_commit_info(commit);\n+\t\tcommit_list_insert(ladder[order], &info->bisect_forward);\n+\t\tfor (i = order; i >= 0; i--) {\n+\t\t\tinfo = get_commit_info(ladder[i]);\n+\t\t\tcommit_list_insert(commit, &info->backward_bound);\n+\t\t}\n+\t\torder++;\n+\t\t/* this has not changed order2.  we still keep track\n+\t\t * of 'steps' carefully in case we hit a root\n+\t\t * commit. */\n+\t}\n+\n+\twork_item_free(item);\n+\treturn NULL;\n+}\n+\n+/*\n+ * The exponential-stride algorithm, part 2.\n+ *\n+ * Bisecting is now easy: just follow the forward/backward pointers,\n+ * stopping when we already know enough to not search any further.\n+ */\n+\n+static struct commit *get_rev_new_bisect(struct work_item *item)\n+{\n+\tstruct commit *commit = item->commit;\n+\tstruct commit_info *info = get_commit_info(commit);\n+\tint flags = commit->object.flags;\n+\n+\tif (!(flags & (BISECTED_FW|NOTCOMMON))\n+\t    && !flag_in_list(COMMON, info->forward_bound)) {\n+\t\tcommit->object.flags |= BISECTED_FW;\n+\t\twork_insert_bisects(info->bisect_forward, item->bisect+1, NULL);\n+\t\tif (!(flags & (POPPED|COMMON))) {\n+\t\t\t/* re-queue for backward bisection */\n+\t\t\twork_heap_insert(item);\n+\t\t\titem = NULL;\n+\t\t\treturn commit;\n+\t\t}\n+\t}\n+\n+\tif (!(flags & (BISECTED_BW|COMMON))\n+\t    && !flag_in_list(NOTCOMMON, info->backward_bound)) {\n+\t\tcommit->object.flags |= BISECTED_BW;\n+\t\twork_insert_bisects(info->bisect_backward, item->bisect+1, item);\n+\t\titem = NULL;\n+\t\tif (!(flags & (POPPED|NOTCOMMON)))\n+\t\t\treturn commit;\n+\t}\n+\n+\tif (item)\n+\t\tfree(item);\n+\treturn NULL;\n+}\n+\n+\n+static struct commit* get_rev_new(void)\n+{\n+\tstruct commit *commit = NULL;\n+\tstruct work_item *item;\n+\n+\twhile (commit == NULL) {\n+\t\titem = work_heap_pop();\n+\t\tif (!item)\n+\t\t\treturn NULL;\n+\t\tcheck_parsed_and_mark(item->commit);\n+\t\tif (item->bisect) {\n+\t\t\tcommit = get_rev_new_bisect(item);\n+\t\t} else {\n+\t\t\tcommit = get_rev_new_stride(item);\n+\t\t\tif (commit) {\n+\t\t\t\t/* there's no point in bisecting the\n+\t\t\t\t * first level both ways */\n+\t\t\t\tcommit->object.flags |= BISECTED_FW;\n+\t\t\t\twork_insert_bisect(commit, 1);\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tcommit->object.flags |= POPPED;\n+\treturn commit;\n+}\n+\n+static void pop_outstanding(void)\n+{\n+\tstruct commit_list *item = outstanding;\n+\toutstanding = item->next;\n+\tfree(item);\n+}\n+\n /*\n  * Send 'have' for the next batch of revisions.  Returns 0 if we ran\n  * out of commits to send, 1 otherwise.\n@@ -167,7 +900,10 @@ static int send_have_lines(int fd[2], int *flushes, unsigned *in_vain)\n \tint i;\n \n \tfor (i = 0; i < 32; i++) {\n-\t\tcommit = get_rev();\n+\t\tif (exp_stride_algorithm)\n+\t\t\tcommit = get_rev_new();\n+\t\telse\n+\t\t\tcommit = get_rev();\n \t\tif (!commit)\n \t\t\treturn 0;\n \t\tpacket_write(fd[1], \"have %s\\n\",\n@@ -175,6 +911,14 @@ static int send_have_lines(int fd[2], int *flushes, unsigned *in_vain)\n \t\tif (args.verbose)\n \t\t\tfprintf(stderr, \"have %s\\n\",\n \t\t\t\tsha1_to_hex(commit->object.sha1));\n+\n+\t\tif (outstanding) {\n+\t\t\tcommit_list_insert(commit, &(outstanding_end->next));\n+\t\t\toutstanding_end = outstanding_end->next;\n+\t\t} else {\n+\t\t\tcommit_list_insert(commit, &outstanding);\n+\t\t\toutstanding_end = outstanding;\n+\t\t}\n \t}\n \tpacket_flush(fd[1]);\n \t*flushes += 1;\n@@ -195,7 +939,10 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \t\tfor_each_ref(clear_marks, NULL);\n \tmarked = 1;\n \n-\tfor_each_ref(rev_list_insert_ref, NULL);\n+\tif (exp_stride_algorithm)\n+\t\tfor_each_ref(work_heap_insert_ref, NULL);\n+\telse\n+\t\tfor_each_ref(rev_list_insert_ref, NULL);\n \n \tfetching = 0;\n \tfor ( ; refs ; refs = refs->next) {\n@@ -218,7 +965,7 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t}\n \n \t\tif (!fetching)\n-\t\t\tpacket_write(fd[1], \"want %s%s%s%s%s%s%s%s\\n\",\n+\t\t\tpacket_write(fd[1], \"want %s%s%s%s%s%s%s%s%s\\n\",\n \t\t\t\t     sha1_to_hex(remote),\n \t\t\t\t     (multi_ack ? \" multi_ack\" : \"\"),\n \t\t\t\t     (use_sideband == 2 ? \" side-band-64k\" : \"\"),\n@@ -226,6 +973,7 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t\t\t     (args.use_thin_pack ? \" thin-pack\" : \"\"),\n \t\t\t\t     (args.no_progress ? \" no-progress\" : \"\"),\n \t\t\t\t     (args.include_tag ? \" include-tag\" : \"\"),\n+\t\t\t\t     (exp_stride_algorithm ? \" no-giveup\" : \"\"),\n \t\t\t\t     \" ofs-delta\");\n \t\telse\n \t\t\tpacket_write(fd[1], \"want %s\\n\", sha1_to_hex(remote));\n@@ -294,12 +1042,31 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t\t} else if (ack == 2) {\n \t\t\t\tstruct commit *commit =\n \t\t\t\t\tlookup_commit(result_sha1);\n-\t\t\t\tmark_common(commit, 0, 1);\n+\t\t\t\tif (exp_stride_algorithm) {\n+\t\t\t\t\twhile (commit != outstanding->item) {\n+\t\t\t\t\t\tif (args.verbose)\n+\t\t\t\t\t\t\tfprintf(stderr, \"unwinding: %s\\n\", sha1_to_hex(outstanding->item->object.sha1));\n+\t\t\t\t\t\tmark_not_common(outstanding->item);\n+\t\t\t\t\t\tpop_outstanding();\n+\t\t\t\t\t\tunwound++;\n+\t\t\t\t\t}\n+\t\t\t\t\tpop_outstanding();\n+\t\t\t\t\tunwound++;\n+\t\t\t\t\tmark_common_new(commit, 0, 1);\n+\t\t\t\t} else {\n+\t\t\t\t\tmark_common(commit, 0, 1);\n+\t\t\t\t}\n \t\t\t\tretval = 0;\n \t\t\t\tin_vain = 0;\n \t\t\t\tgot_continue = 1;\n \t\t\t}\n \t\t} while (ack);\n+\t\twhile (exp_stride_algorithm && unwound++ < 32) {\n+\t\t\tif (args.verbose)\n+\t\t\t\tfprintf(stderr, \"unwinding: %s\\n\", sha1_to_hex(outstanding->item->object.sha1));\n+\t\t\tmark_not_common(outstanding->item);\n+\t\t\tpop_outstanding();\n+\t\t}\n \t\tflushes--;\n \t\tif (got_continue && MAX_IN_VAIN < in_vain) {\n \t\t\tif (args.verbose)\n@@ -467,7 +1234,10 @@ static int everything_local(struct ref **refs, int nr_match, char **match)\n \t\tif (!(o->flags & SEEN)) {\n \t\t\trev_list_push((struct commit *)o, COMMON_REF | SEEN);\n \n-\t\t\tmark_common((struct commit *)o, 1, 1);\n+\t\t\tif (exp_stride_algorithm)\n+\t\t\t\tmark_common_new((struct commit *)o, 1, 1);\n+\t\t\telse\n+\t\t\t\tmark_common((struct commit *)o, 1, 1);\n \t\t}\n \t}\n \n@@ -617,6 +1387,11 @@ static struct ref *do_fetch_pack(int fd[2],\n \t\t\tfprintf(stderr, \"Server supports side-band\\n\");\n \t\tuse_sideband = 1;\n \t}\n+\tif (server_supports(\"no-giveup\")) {\n+\t\tif (args.verbose)\n+\t\t\tfprintf(stderr, \"Server supports no-giveup\\n\");\n+\t\texp_stride_algorithm = 1;\n+\t}\n \tif (everything_local(&ref, nr_match, match)) {\n \t\tpacket_flush(fd[1]);\n \t\tgoto all_done;\ndiff --git a/upload-pack.c b/upload-pack.c\nindex e5adbc0..8f05dbf 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -37,6 +37,7 @@ static unsigned int timeout;\n  */\n static int use_sideband;\n static int debug_fd;\n+static int disable_give_up;\n \n static void reset_timeout(void)\n {\n@@ -414,7 +415,7 @@ static int get_common_commits(void)\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\tif (multi_ack && ok_to_give_up())\n+\t\t\t\tif (multi_ack && !disable_give_up && ok_to_give_up())\n \t\t\t\t\tpacket_write(1, \"ACK %s continue\\n\",\n \t\t\t\t\t\t     sha1_to_hex(sha1));\n \t\t\t\tbreak;\n@@ -501,6 +502,8 @@ static void receive_needs(void)\n \t\t\tno_progress = 1;\n \t\tif (strstr(line+45, \"include-tag\"))\n \t\t\tuse_include_tag = 1;\n+\t\tif (strstr(line+45, \"no-giveup\"))\n+\t\t\tdisable_give_up = 1;\n \n \t\t/* We have sent all our refs already, and the other end\n \t\t * should have chosen out of them; otherwise they are\n@@ -573,7 +576,7 @@ static int send_ref(const char *refname, const unsigned char *sha1, int flag, vo\n {\n \tstatic const char *capabilities = \"multi_ack thin-pack side-band\"\n \t\t\" side-band-64k ofs-delta shallow no-progress\"\n-\t\t\" include-tag\";\n+\t\t\" include-tag no-giveup\";\n \tstruct object *o = parse_object(sha1);\n \n \tif (!o)\n-- \ntg: (73ef856..) t/fp-speedup (depends on: origin/master t/fp-refactor)\n"}]}