{"thread":{"id":"1968","subject":"Multi-head fetch proposal","startedAt":"2005-09-29T00:25:37Z","lastAt":"2005-09-29T04:45:22Z","messageCount":2,"participants":["Johannes Schindelin","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"9444","messageId":"Pine.LNX.4.63.0509290149540.19126@wgmdd8.biozentrum.uni-wuerzburg.de","threadId":"1968","inReplyTo":null,"subject":"Multi-head fetch proposal","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2005-09-29T00:25:37Z","receivedAt":"2005-09-29T00:25:37Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nI reported a while ago that a fetch downloaded objects which were already \nin the repository. While that was true, it was not the whole truth: This \nonly happened with multi-head fetch.\n\nAs far as I can tell, what happened was this:\n\n- fetch-pack connected to the server\n- it asked correctly for the remote refs\n- it then opened a (local) pipe to git-rev-list\n- it sent quite a few refs from that pipe over the wire\n- on the other side, upload-pack marked these refs as \"fetcher got those\"\n- since upload-pack has a limit on that list (only 16) it soon said STFU \n- it turned out that quite a few common refs were not yet marked\n- so upload-pack would upload these\n\nThe reason is that git-rev-list would happily output parents of refs \nwhich were already acknowledged by upload-pack to be common refs.\n\nI just sent out a patch which makes this irrelevant for the case that most \nor all of these heads are already fetched.\n\nNow, to really solve the multi-head problem, which really is the problem \n\"how to find the edges of the common commits\", I propose the following:\n\nFor each remote ref known to be not in the local repository, find the 1st, \n2nd, 4th, 8th, ... parents. Send these to upload-pack to be marked. For \neach ack'ed ref (i.e. remote side also has it), do a binary search to find \nthe edge (i.e. the youngest common ref) on that DAG branch.\n\n(To ease the burden on the server side, one coul mark only the edges \nas stop gaps for upload-pack. However, it might make things too \ncomplicated.)\n\nOf course, the trick is to do that asynchronously, so that the network \nbandwidth is used optimally. This means that not each ack'ed ref \nleads to a binary search, but only those refs where no descendant was \nack'ed.\n\nBTW this does not need any change of the protocol. In fact, it only needs \na change to fetch-pack.\n\nI'd also increase MAX_HAS in upload-pack.\n\nCiao,\nDscho\n"},{"id":"9451","messageId":"7voe6co525.fsf@assigned-by-dhcp.cox.net","threadId":"1968","inReplyTo":"Pine.LNX.4.63.0509290149540.19126@wgmdd8.biozentrum.uni-wuerzburg.de","subject":"Re: Multi-head fetch proposal","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-29T04:45:22Z","receivedAt":"2005-09-29T04:45:22Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I was wondering why I always end up fetching 35 or so objects\nwhen I ask master, maint and pu from my public repository, and\nwanted to spend today digging on this one.  Instead I ended up\nwasting the day on something else (I just sent it out), but I am\nglad you were looking into it.\n\nOf course, with your patch the problem does not happen anymore.\n"}]}