{"thread":{"id":"15510","subject":"O(#haves*...) behaviour in \"have <sha>\" processing in upload-pack","startedAt":"2008-09-13T00:11:07Z","lastAt":"2008-09-13T12:18:43Z","messageCount":2,"participants":["Thomas Rast"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"90618","messageId":"200809130211.14091.trast@student.ethz.ch","threadId":"15510","inReplyTo":null,"subject":"O(#haves*...) behaviour in \"have <sha>\" processing in upload-pack","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2008-09-13T00:11:07Z","receivedAt":"2008-09-13T00:11:07Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Hi *\n\nevilchelu (Cristi Balan) pointed out on IRC that 'git fetch' takes a\nlong time when fetching a history-disjoint repository.\n\nFor example,\n\n  mkdir test && cd test\n  git init\n  git remote add -f paperclip git://github.com/thoughtbot/paperclip.git\n  git remote add -f hoptoad git://github.com/thoughtbot/hoptoad_notifier.git\n  git remote add -f aasm git://github.com/rubyist/aasm.git\n  git remote add -f forgot git://github.com/greenisus/forgot_password.git\n  git remote add -f restful git://github.com/technoweenie/restful-authentication.git\n\n(taken straight from evilchelu's example, but it should be the same\nwith random repositories).\n\nPeeking at the transmission with Wireshark, there is a noticeable\npattern of 4-5s delays before _every_ \"0008NAK\\n\" line sent by the\nserver.\n\nLooking at upload-pack.c, it seems that the server does far too much\nwork when processing the \"have\" lines.  I've only just read into this\narea of code, but the rough idea seems to be:\n\n  [404: get_common_commits()]\n  for (H = every \"have\" line) {\n\n      [321: got_sha1()]\n      flag H and its parents (shallow!) as THEY_HAVE\n\n      [415: get_common_commits()]\n      if (we do not have H in our object store) {\n\n          [367: ok_to_give_up()]\n          for (W = every \"want\" object specified earlier) {\n\n              [338: reachable()]\n              walk the entire history to see if anything flagged\n              THEY_HAVE so far is reachable from W\n\n          }\n\n          [418: get_common_commits()]\n          if the innermost test succeeded for all W: ACK this H so the\n          client stops walking history from it\n      }\n  }\n\nThe entire loop seems to have O(h*w*n) (n=history) complexity, which\nprobably is to blame for the delays.\n\n* Isn't this ok_to_give_up() test moot?  If H is not in our object\n  store, it cannot be of any use in the transfer (of our history to\n  the client).  So if we are going to fake an ACK to stop the client\n  digging on this side of his history, we might as well send it right\n  away.  (And what does reaching a THEY_HAVE commit from all W's have\n  to do with it?)\n\n* Even assuming it is not, it would save some work if the server\n  avoided walking the entire history for every H.  For example, it\n  could buffer up all H's until a \"0000\\n\" arrives, which currently\n  seems to be 32 haves, then check all of them in a single pass over\n  history.  (Unfortunately the 'h' factor cannot be removed completely\n  unless we buffer all of them, which again defeats the point.)\n\nMuch of the code in question was added in 937a515 (upload-pack: stop\nthe other side when they have more roots than we do., 2006-07-05).\n\n[I hope I'm making some sense, it's far too late here, but it was\neither this or trying to understand it again in the morning.]\n\n- Thomas\n\n-- \nThomas Rast\ntrast@student.ethz.ch\n\n\n\n\n"},{"id":"90631","messageId":"200809131418.48637.trast@student.ethz.ch","threadId":"15510","inReplyTo":"200809130211.14091.trast@student.ethz.ch","subject":"Re: O(#haves*...) behaviour in \"have <sha>\" processing in upload-pack","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2008-09-13T12:18:43Z","receivedAt":"2008-09-13T12:18:43Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"I wrote:\n> * Isn't this ok_to_give_up() test moot?  If H is not in our object\n>   store, it cannot be of any use in the transfer (of our history to\n>   the client).  So if we are going to fake an ACK to stop the client\n>   digging on this side of his history, we might as well send it right\n>   away.\n\nNever mind this part, it's wrong:\n\nLet B=$(merge-base H W).  Suppose H is unknown to the server, but B is\nknown.  Then sending a fake ACK as a reply to H will cause\n\n* the client to believe we have everything reachable from H, including\n  B, and cease sending any history reachable from H; and thus\n\n* the server to believe that the client does not have B, since it did\n  not list this commit in a \"have\" line.\n\nSorry for the noise.\n\n- Thomas\n\n-- \nThomas Rast\ntrast@student.ethz.ch\n\n"}]}