{"thread":{"id":"5513","subject":"Change set based shallow clone","startedAt":"2006-09-07T19:52:59Z","lastAt":"2006-09-12T00:25:08Z","messageCount":99,"participants":["Jon Smirl","Jakub Narebski","Jeff King","Junio C Hamano","linux@horizon.com","Martin Langhoff","Aneesh Kumar K.V","Andreas Ericsson","A Large Angry SCM","Linus Torvalds","Paul Mackerras","Petr Baudis","Marco Costalba","Josef Weidendorfer","Anand Kumria","Shawn Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"26537","messageId":"9e4733910609071252ree73effwb06358e9a22ba965@mail.gmail.com","threadId":"5513","inReplyTo":null,"subject":"Change set based shallow clone","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-07T19:52:59Z","receivedAt":"2006-09-07T19:52:59Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"Here's a change set based shallow clone scheme I've been thinking\nabout, does it have potential?\n\nWhen the client wants a shallow clone it starts by telling the server\nall of the HEADs and how many change sets down each of those HEADs it\nhas locally. That's a small amout of data to transmit and it can be\neasily tracked. Let's ignore merged branches for the moment.\n\nThe client then says I want at least 10 (or N) change sets for all of\nthe HEADs present at the server. The server starts from each HEAD and\nworks backwards until it encounters a change set present on the\nclient. At that point it will be able to compute efficient deltas to\nsend.\n\nIf you haven't updated for six months when the server walks backwards\nfor 10 change sets it's not going to find anything you have locally.\nWhen this situation is encountered the server needs to generate a\ndelta just for you between one of the change sets it knows you have\nand one of the 10 change sets you want. By generating this one-off\ndelta it lets you avoid the need to fetch all of the objects back to a\ncommon branch ancestor. The delta functions as a jump over the\nintervening space.\n\nIn the case of an initial shallow clone the client won't have anything\nto delta against. The server will be forced to send a full version\nfor one of the 10 change sets requested and deltas for the rest.\nGetting an initial shallow clone should take about as long as a CVS\ncheck out.\n\nThis scheme does require the server to sometimes generate custom diffs\nfor the client, but in all the cases I have been working with\neverything is always IO bound so it is better to spend some CPU to\nreduce the IO needed.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26539","messageId":"edpuut$dns$1@sea.gmane.org","threadId":"5513","inReplyTo":"9e4733910609071252ree73effwb06358e9a22ba965@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-09-07T20:21:12Z","receivedAt":"2006-09-07T20:21:12Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Jon Smirl wrote:\n\n> If you haven't updated for six months when the server walks backwards\n> for 10 change sets it's not going to find anything you have locally.\n> When this situation is encountered the server needs to generate a\n> delta just for you between one of the change sets it knows you have\n> and one of the 10 change sets you want. By generating this one-off\n> delta it lets you avoid the need to fetch all of the objects back to a\n> common branch ancestor. The delta functions as a jump over the\n> intervening space.\n\nI don't understand. Git is _not_ patchset based (like GNU Arch, or\nMercurial, or CVS). It is snapshot based. So if you want to download\n\"skip\", you need only for the local part of doenloader to make appropriate\ngrafts, like below\n\n\n *--*--*--*--*--*--*--*--*--*--*--HEAD (server)\n\n *--*--*...........*--*--*--*--*--HEAD (shallow/sparse clone)\n\nBut the part you were talking about is _easy_ part; the hard part is\nmerges including merging branch which was split off the trunk before\ncutoff-point, history rewriting (c.f. 'pu' branch, and rebases), etc.\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"26540","messageId":"9e4733910609071341u7e430214j71ddcbefa26810ca@mail.gmail.com","threadId":"5513","inReplyTo":"edpuut$dns$1@sea.gmane.org","subject":"Re: Change set based shallow clone","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-07T20:41:20Z","receivedAt":"2006-09-07T20:41:20Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/7/06, Jakub Narebski wrote:\n> I don't understand. Git is _not_ patchset based (like GNU Arch, or\n\nI meant change set to refer to a commit plus trees plus blobs that\nmake it up. These may be present in full or delta form.\n\n> Mercurial, or CVS). It is snapshot based. So if you want to download\n> \"skip\", you need only for the local part of doenloader to make appropriate\n> grafts, like below\n>\n>\n> *--*--*--*--*--*--*--*--*--*--*--HEAD (server)\n>\n> *--*--*...........*--*--*--*--*--HEAD (shallow/sparse clone)\n>\n> But the part you were talking about is _easy_ part; the hard part is\n> merges including merging branch which was split off the trunk before\n> cutoff-point, history rewriting (c.f. 'pu' branch, and rebases), etc.\n\nDoes an average user do these things? The shallow clone is there to\naddress the casual user who gags at a five hour download to get an\ninitial check out Mozilla when they want to make a five line change or\njust browse the source for a few minutes.\n\nI would expect advanced users to have a full tree present.\n\nI was going to have the dangling references from the shallow clone\npoint to 'not-present' objects. When you try to do any of the more\ncomplex operations you would hit these objects and fault down more of\nthe tree.\n\nThere would also be a command to bring down all of the objects to\nfully populate a sparse tree. You could do the shallow clone to begin\nwith and then do the full tree populate overnight or in the\nbackground.\n\nMaybe the answer is to build a shallow clone tool for casual use, and\nthen if you try to run anything too complex on it git just tells you\nthat you have to download the entire tree.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26541","messageId":"20060907213306.GA10781@sigio.intra.peff.net","threadId":"5513","inReplyTo":"9e4733910609071341u7e430214j71ddcbefa26810ca@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-09-07T21:33:07Z","receivedAt":"2006-09-07T21:33:07Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Sep 07, 2006 at 04:41:20PM -0400, Jon Smirl wrote:\n\n> Maybe the answer is to build a shallow clone tool for casual use, and\n> then if you try to run anything too complex on it git just tells you\n> that you have to download the entire tree.\n\nCan you list which operations you'd like to do on the shallow clone?\n\nMany operations that look at history are going to fail with a very short\nhistory (e.g., finding a merge base). Some operations can work with a\nshort history, but the results are probably not useful (seeing the last\n10 commits from git-log is probably not interesting). If you just want\nthe latest snapshot, the remote git-archive work going on right now will\nprobably take care of that.\n\n-Peff\n"},{"id":"26542","messageId":"edq3eb$1tm$1@sea.gmane.org","threadId":"5513","inReplyTo":"9e4733910609071341u7e430214j71ddcbefa26810ca@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-09-07T21:37:42Z","receivedAt":"2006-09-07T21:37:42Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Jon Smirl wrote:\n\n> On 9/7/06, Jakub Narebski wrote:\n>> I don't understand. Git is _not_ patchset based (like GNU Arch, or\n> \n> I meant change set to refer to a commit plus trees plus blobs that\n> make it up. These may be present in full or delta form.\n> \n>> Mercurial, or CVS). It is snapshot based. So if you want to download\n>> \"skip\", you need only for the local part of downloader to make \n>> appropriate grafts, like below\n>>\n>>\n>> *--*--*--*--*--*--*--*--*--*--*--HEAD (server)\n>>\n>> *--*--*...........*--*--*--*--*--HEAD (shallow/sparse clone)\n>>\n>> But the part you were talking about is _easy_ part; the hard part is\n>> merges including merging branch which was split off the trunk before\n>> cutoff-point, history rewriting (c.f. 'pu' branch, and rebases), etc.\n> \n> Does an average user do these things? The shallow clone is there to\n> address the casual user who gags at a five hour download to get an\n> initial check out Mozilla when they want to make a five line change or\n> just browse the source for a few minutes.\n\nThe question is not if average user do these things, but do average user\nencounter these things. I think that merging branches into 'master' branch\n(trunk) is quite common, and merging trunk into branches for checking is\nalso common.\n\nAs to checking out latest revision... with git-archive --remote (or\ngit-tar-tree --remote as of now) you can download newest version as\narchive; although without commit object I think.\n\n> I would expect advanced users to have a full tree present.\n> \n> I was going to have the dangling references from the shallow clone\n> point to 'not-present' objects. When you try to do any of the more\n> complex operations you would hit these objects and fault down more of\n> the tree.\n\nOnly if you consider git-log to be complex operation. It would be better I\nthink to cover laps using grafts.\n\nIn first post you are talking about downloading diff covering the lap/skip;\nit would be important only if git was patchset based. You need to download\ncommits and referenced objects, _except_ cutting off some parents.\n\n> There would also be a command to bring down all of the objects to\n> fully populate a sparse tree. You could do the shallow clone to begin\n> with and then do the full tree populate overnight or in the\n> background.\n\nAnd that should be done by marking \"shallow\"/\"sparse\" grafts and just delete\nthem (or update if needed).\n\n> Maybe the answer is to build a shallow clone tool for casual use, and\n> then if you try to run anything too complex on it git just tells you\n> that you have to download the entire tree.\n\nThe shallow/sparse/lazy[*1*] clone proposal is one of recurring proposals\n(besides subproject support) on git mailing list.\n\nFootnotes:\n[*1*] Lazy clone, also known as remote alternatives.\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"26544","messageId":"edq48l$1tm$3@sea.gmane.org","threadId":"5513","inReplyTo":"20060907213306.GA10781@sigio.intra.peff.net","subject":"Re: Change set based shallow clone","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-09-07T21:51:45Z","receivedAt":"2006-09-07T21:51:45Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Jeff King wrote:\n\n> Many operations that look at history are going to fail with a very short\n> history (e.g., finding a merge base). Some operations can work with a\n> short history, but the results are probably not useful (seeing the last\n> 10 commits from git-log is probably not interesting). If you just want\n> the latest snapshot, the remote git-archive work going on right now will\n> probably take care of that.\n\nThat is the source of the idea of _sparse_ clone, which would include e.g.\ntop 10 commits from each of selected branches, all commits pointed by\nbranches and tags, and all merge bases, and roots, joined using grafts.\n\nE.g. if the full history looks like this.\n\n -*.|.......... head \n / |\n -*--*--*- -*--*--x--*-|-*--*--*-- head\n / \\ / |\n *--*--*--*--*--*--*--*--*--*--*--*--*-|-*--*--*-- head\n \\...............|.......... tag\n |\n \\- [cut-off]\n\nthen the sparse clone history would look like that:\n(---) denotes parentage, (...) denotes grafts below\n\n\n |\n ,......x....|.*--*--*-- head\n : |\n *....................*--*.............|.*--*--*-- head\n \\...............|.......... tag\n |\n \\- [cut-off]\n\nof course assuming that we have no earlier commits (i.e. sparse clone, not\nsparse fetch).\n\nOf course, that solves only some of troubles...\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"26545","messageId":"7vpse7tjp0.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"9e4733910609071252ree73effwb06358e9a22ba965@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-07T22:07:07Z","receivedAt":"2006-09-07T22:07:07Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I've been postponing thinking about shallow clones with a plan\nto do so when I have absolutely nothing else to do for a solid\nfew days. Since my time is booked pretty much full with day job\nand the ongoing pack-file topics these days, I will most likely\nstick to that plan after I finish this message.\n\nNot because I think it is an insignificant problem at the fringe\n(I did not say \"when I have nothing better to do\"), but because\nI feel this is something important (and hard) that requires\n\"think about it and only about it straight through for a few\ndays, dropping everything else\" kind of thinking.\n\nWhen you have a ref under .git/refs/ pointing at an object, you\nare making this assertion:\n\n The object store associated with this repository\n (usually, .git/objects and alternates pointed at by\n .git/objects/info/alternates) holds _all_ objects that\n are recursively reachable from this object by following\n tag reference, commit ancestry chain, commit to its\n tree, and tree to its subtrees and blobs.\n\nSo by definition, a shallow clone is a broken/incomplete\nrepository. Unless we fix the breakage in some way.\n\nOne way to do so which has often been talked about is to use the\ngrafts facility. You cut off the history at some commit, and\ncauterize the commit ancestry chain at that point by telling git\nto pretend that the commit does not have any parent. While this\nwould work after setting it up, in the sense that \"git log\"\nwould stop at the commit and \"git fsck-objects\" would say\nnothing is missing, it is cumbersome to set up, we do not have\nan easy way to fetch (or clone -- but clone is a special case of\nfetch where the downstream starts out from emptiness) from such\na repository, unplugging to get histories further back with\na later fetch is quite involved, and it is not clear what it\nmeans to further fetch from such a shallow clone.\n\nWhere does the difficulty in fetching come from? Mostly because\nthe upload side and download side needs to agree on the altered\nhistory.\n\nLet's say the download side is empty and somehow tells the\nupload side that it wants the latest 5-commit worth of stuff\nstarting from the tip:\n\n - The upload side runs\n\n rev-list --objects HEAD~5..HEAD | pack-objects --stdout\n\n to give you the needed data. This is almost [*1*] doable by\n telling it that you have HEAD~5.\n\n - Also the upload side can say \"pretend that this commit HEAD~4\n has no parent, although cat-file on it would say otherwise\".\n\n - The downloader creates a suitable grafts file to cauterize\n commit HEAD~4.\n\nIs this enough? Hardly.\n\nConsider:\n\n o---o---o---o---o---*---*---*---*---*\n \\ ^ / ^ \n \\ HEAD~5 / HEAD\n \\ /\n o---o---*---*---*\n ^ ^\n HEAD^^2~3 HEAD^^2\n\n5-commit request should apply to send '*' commits, so the\noriginal \"HEAD~5..HEAD\" was bogus to begin with. You have to\nsay \"HEAD --not HEAD~5 HEAD^^2~3\" to get the above.\n\nComing up with this restriction needs to be done on the upload\nside. Doing so on the download side means it needs to retrieve\nthe recent \"real\" history to do that computation to come up with\nwhere to cut things off, which is crazy.\n\nHowever, it may be that the above graph is not what the usual\ndownloader wants. If the upload side is _the_ official\nrepository of some sort that merges in subsystem branches, and\nif you are mostly interested in the official repository's\nhistory, you might have meant to ask this with your 5-commit\nrequest instead:\n\n o---o---o---o---o---*---*---*---*---*\n \\ ^ / ^ \n \\ HEAD~5 / HEAD\n \\ /\n o---o---o---o---o\n ^\n HEAD^^2\n\nThat is, you would want to cauterize the side branch. The pack\nneeds to be built with \"HEAD --not HEAD~5 HEAD^^2\", and the\ncauterize instructions would say \"HEAD~4 has no parent, HEAD^\nhas only one parent that is HEAD~2\", instead of saying just\n\"HEAD~4 has no parent.\"\n\nSo whoever is computing this cauterization point has a policy\ndecision to make, because the meaning of \"5-commits away\" or\n\"recent 10 days\" are very fuzzy when merges are involved.\n\nIt obviously is easy to declare that the policy decision is\nsolely made on the uploader side, from the implementation point\nof view, but I do not offhand know what the ramification of that\ndecision is.\n\nOh, about \"recent 10 days\".\n\nThe side branch might be an very old development that were\nmerged recently into the mainline. From mainline's point of\nview, everything that happened on the side branch is something\nnew to him (think of Linus pulled from Jeff who has been cooking\nhis stuff for quite some time). Looking at each individual\ncommit on the side branch, however, they have older commit and\nauthor timestamps. If you pick \"I want mainline's point of\nview\", that means you need to compute (in the above picture):\n\n - notice commit timestamp of HEAD^ (the merge) is within the\n recent 10-day window.\n\n - using HEAD^^1 (supposedly the state of the mainline before\n the merge happened [*2*]) and HEAD^^2 (side branch),\n compute:\n\n rev-list HEAD^^1..HEAD^^2\n\n the results are the \"new\" ones that appeared when the merge\n was made, so they are within the recent 10-day window from\n the mainline's point of view. Include them.\n\nWhat that means is, assuming that HEAD~5 is also the 10-day\ncut-off point on the mainline, and HEAD^ is recent, we would\nsend this:\n\n\n o---o---o---o---o---*---*---*---*---*\n \\ ^ / ^ \n \\ HEAD~5 / HEAD\n \\ /\n *---*---*---*---*\n ^\n HEAD^^2\n\nI'll leave it as an exercise to the readers to Come up with the\npack generation specification and cauterizing instructions to\ngive to the downloader, but you see how quickly this becomes\nvery complex, and we still haven't talked about the above when\nmultiple merge bases are involved.\n\nThinking about it a bit more, maybe \"from mainline's point of\nview\" policy would include the same entire side branch when\nlimiting by depth of commits. After all the whole side branch\nwas something new when HEAD^ merge was created. But that is\nanother policy decision. And the downloader side cannot make\nthat decision before seeing what the true ancestry graph looks\nlike.\n\nLet's say we somehow managed to make a shallow clone. The\ndownloader has '*' commits:\n\n o---o---o---o---o---*---*---*---*---*\n \\ ^ / ^ \n \\ HEAD~5 / HEAD\n \\ /\n o---o---*---*---*\n ^ ^\n HEAD^^2~3 HEAD^^2\n\nIn the meantime, the uploader side made some more commits:\n\n x---x---x---x---x---x\n / \\\n / \\\n / \\\n o---o---o---F---o---*---*---*---*---H---x---X\n \\ /\n \\ /\n \\ /\n o---o---*---*---*\n\nNow the downloader wants to update. How does that go?\n\n - The uploader says the tip is at X\n\n - The downloader says it has old HEAD (H), H^, ...\n\n - Suppose the development on the new side branch recently\n merged did not touch most of the files since it forked from\n the mainline at F, but the mainline made lot of changes that\n were not touched by commits 'x', which is now part of the\n downloader's history. The uploader, if it did not know the\n downloader has altered history, would take \"have H\" from the\n downloader to mean \"the other side has everything reachable\n from H\", so it would compute X..H (commits that are not in H\n but in X and trees and blobs needed to complete them). But\n that can leave out the trees and blobs that existed in F (and\n was part of commits on the new side branch).\n\n - So the uploader side needs to know how the history on the\n downloader's side is altered from reality when interpreting\n \"have H\". It does not mean \"H and all the history behind it\"\n to the uploader anymore.\n\nOne way to do so is to send grafts information from downloader\nto uploader. If the uploader _knows_ that the altered history\nends at the leftmost '*' commit on the mainline, then it can \ntake it into account the fact that the downloader does not have\ncommit 'F'. That, however, introduces another problem. Where\nshould it stop? Obviously X needs to be sent, so is X^, but\nhow do we know which 'x' commit to stop at? Do we record the\ninitial cut-off criteria (remember, we started the clone with\n5-commit cutoff) somewhere in the downloader's repository and\nsend that to the uploader so that the uploader can apply the\nsame rule to include only 5 commits from the new side branch?\nWhat happens if there are less than 5 commits on that new side\nbranch? Would we end up including 'F', which the downloader\nspecifically did not want when making this shallow clone\ninitially?\n\nI won't go into the details, but when you think about what needs\nto happen when fetching _from_ a shallow clone (i.e. the\nuploader side is incomplete), your head will explode ;-). It is\nsolvable in the same sense that you can solve the previous\n\"fetching to update\" problem by trying to define a reasonable\nsemantics to the operation by answering the questions I posed in\nthe above paragraph (which obviously is no way an exhaustive\nset), but the result will be quite complex. It would involve\nsending graft information both from uploader and downloader\n(after all the downloader side can also be shallow but with\ndifferent cut-off points from the uploader) and somehow coming\nup with the intersection of both to arrive at a shared view of\naltered history before starting the traversal to find what to\nsend.\n\nAlso often people would want to deepen history (i.e. fetching\nolder history than initially fetched) after \"checking out only\nthe tip\". It is a reasonable request, and is somewhat easier\nproblem to solve than the initial shallow clone problem. If you\nhave a working initial shallow clone, essentially you can:\n\n - Find the earlier cut off points by looking at your own grafts\n file;\n\n - Ask the uploader to clone shallowly from the parents missing\n from your repository.\n\nand update the resulting grafts information.\n\nAnyway, it is a useful feature, an important operation, and\nit involves a lot of thinking (and hard work, obviously).\n\nI will not think about this anymore, until I have absolutely\nnothing else to do for a solid few days, but you probably\nhaven't read this far ;-).\n\n -jc\n\n*1* Currently there is no way to find out what HEAD~10 is during\nthe initial protocol handshake, but this message is mostly about\npotential protocol update needs.\n\n*2* First parent of a merge is _usually_ what the repository\nowner saw, i.e. the mainline merging side branch into it, but\nthat is not universally true when fast forwards are involved.\n"},{"id":"26546","messageId":"7vlkovtjd1.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"9e4733910609071341u7e430214j71ddcbefa26810ca@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-07T22:14:18Z","receivedAt":"2006-09-07T22:14:18Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Jon Smirl\" writes:\n\n> Does an average user do these things? The shallow clone is there to\n> address the casual user who gags at a five hour download to get an\n> initial check out Mozilla when they want to make a five line change or\n> just browse the source for a few minutes.\n>...\n> Maybe the answer is to build a shallow clone tool for casual use, and\n> then if you try to run anything too complex on it git just tells you\n> that you have to download the entire tree.\n\nFor that kind of thing, \"git-tar-tree --remote\" would suffice I\nwould imagine. The five line change can be tracked locally by\ncreating an initial commit from the tar-tree extract; such a\ncasual user will not be pushing or asking to pull but sending in\npatches to upstream, no?\n"},{"id":"26547","messageId":"edq74k$cuu$1@sea.gmane.org","threadId":"5513","inReplyTo":"7vpse7tjp0.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-09-07T22:40:47Z","receivedAt":"2006-09-07T22:40:47Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Junio C Hamano wrote:\n\n> One way to do so is to send grafts information from downloader\n> to uploader.  If the uploader _knows_ that the altered history\n> ends at the leftmost '*' commit on the mainline, then it can \n> take it into account the fact that the downloader does not have\n> commit 'F'.  That, however, introduces another problem.  Where\n> should it stop?  Obviously X needs to be sent, so is X^, but\n> how do we know which 'x' commit to stop at?  Do we record the\n> initial cut-off criteria (remember, we started the clone with\n> 5-commit cutoff) somewhere in the downloader's repository and\n> send that to the uploader so that the uploader can apply the\n> same rule to include only 5 commits from the new side branch?\n> What happens if there are less than 5 commits on that new side\n> branch?  Would we end up including 'F', which the downloader\n> specifically did not want when making this shallow clone\n> initially?\n> \n> I won't go into the details, but when you think about what needs\n> to happen when fetching _from_ a shallow clone (i.e. the\n> uploader side is incomplete), your head will explode ;-).  It is\n> solvable in the same sense that you can solve the previous\n> \"fetching to update\" problem by trying to define a reasonable\n> semantics to the operation by answering the questions I posed in\n> the above paragraph (which obviously is no way an exhaustive\n> set), but the result will be quite complex.  It would involve\n> sending graft information both from uploader and downloader\n> (after all the downloader side can also be shallow but with\n> different cut-off points from the uploader) and somehow coming\n> up with the intersection of both to arrive at a shared view of\n> altered history before starting the traversal to find what to\n> send.\n\nThe proposed solution was to send graft information and cutoff from\ndownloader to uploader, coming up with the effective graft points which\nwould be intersection of downloader and uploader grafts[*1*], and then use\nthis intersection as graft information when calculating what to send.\n\nWith sparse clone we would have:\n\n #---o---#---o---o---*---*---*---*---*\n \\ ^ / ^ \n \\ HEAD~5 / HEAD\n \\ /\n o---o---*---*---*\n ^ ^\n HEAD^^2~3 HEAD^^2\n\nwhere # and * are the commit which the downloader has (# are additional\ncommits for sparse rather thatn shallow clone).\n\n x---x---x---x---x---x\n / \\\n / \\\n / \\\n #---o---#---F---o---*---*---*---*---H---x---X\n \\ /\n \\ /\n \\ /\n o---o---*---*---*\n\nNow, when we are shallow fetching, we should have remembered somewhere the\ncutoff used (or use the same cutoff). So we sould get then\n\n\n x---*---*---*---*---*\n / \\\n / \\\n / \\\n #---o---#---#---o---*---*---*---*---*---*---*\n \\ /\n \\ /\n \\ /\n o---o---*---*---*\n\n\nFootnotes:\n[*1*] It would be some kind of graph intersection. Note that the repository\nwe clone from might be shallow clone, shallower in parts than our\nrepository, or might be repository with historic repository grafted on\n(grafts adding history, not simplyfying it).\n\n[*2*] I agree that shallow/sparse clone is hard. Lazy clone (or remote\nalternatives) is also hard: when we do download objects, do we\ndownload-ahead, do we cache downloaded object or move them to local\nrepository, how often we clean cache etc.\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"26548","messageId":"9e4733910609071609o50e5dacm53323e023e90358f@mail.gmail.com","threadId":"5513","inReplyTo":"7vlkovtjd1.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-07T23:09:21Z","receivedAt":"2006-09-07T23:09:21Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/7/06, Junio C Hamano wrote:\n> \"Jon Smirl\" writes:\n>\n> > Does an average user do these things? The shallow clone is there to\n> > address the casual user who gags at a five hour download to get an\n> > initial check out Mozilla when they want to make a five line change or\n> > just browse the source for a few minutes.\n> >...\n> > Maybe the answer is to build a shallow clone tool for casual use, and\n> > then if you try to run anything too complex on it git just tells you\n> > that you have to download the entire tree.\n>\n> For that kind of thing, \"git-tar-tree --remote\" would suffice I\n> would imagine. The five line change can be tracked locally by\n> creating an initial commit from the tar-tree extract; such a\n> casual user will not be pushing or asking to pull but sending in\n> patches to upstream, no?\n\n>From my observation the casual user does something like this:\n\nget a shallow clone\nlook at it for a while\npull once a day to keep it up to date\n\ndecide to make some changes\nstart a local branch\ncommit changes on local branch\n\npush these changes to someone else for review\nmaybe pull changes on the branch back from the other person\n\nkeep pulling updates from the main repository\nmerge these updates to the local branch\nbrowse around on the recent logs to see who changed what\n\nfinally push the branch to a maintainer\npull it back down from the main repository after the maintainer puts it in\nabandon work on local branch\n\nSome people can't figure out the branch step and just copy the repository.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26554","messageId":"20060908010112.6962.qmail@science.horizon.com","threadId":"5513","inReplyTo":"9e4733910609071252ree73effwb06358e9a22ba965@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-09-08T01:01:12Z","receivedAt":"2006-09-08T01:01:12Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> Here's a change set based shallow clone scheme I've been thinking\n> about, does it have potential?\n\nWell, let's look at the problems...\n\nYou might want to look at the explanation of the current git network\nprotocol at\nhttp://www.spinics.net/lists/git/msg08899.html\n\nI'm just understanding it myself, but as best I understant it,\nit has four phases:\n\n- First, the server lists all of the heads it has, by SHA1 and name.\n- Second, the client tells it which ones it wants, by name.\n- Third, an interactive protocol is entered in which the client\n tells the server which commits it has in terms the server can\n understand. This proceeds as follows:\n\n - For each head the client has, it lists commit objects going\n backwards in history.\n - As soon as the server sees one that it has heard of, it sends\n back \"ACK continue\". The client stops tracing that\n branch and starts in on the next one.\n - (Periodically, the client sends a ping to the server, which\n responds \"NAK\" if it's still alive.)\n - This continues until the client says \"done\".\n\nAt this point, the server knows a set of commits which the client has,\nand a set of commits which the client wants. Then it invokes\n\n\tgit-rev-list --objects-edge ^ ^\n\n(In practice, there will be a lot more than two of each, but forgive\nme if I simplify.)\n\nThis builds a list of commits that are ancestors of and \nbut not or . (A commit is considered an ancestor of\nitself, so and are in the set, while and \nare not.)\n\nThen it enumerates the complete trees of each of those commits. Then it\nsubtracts from that object set all of the trees and blobs in the \nand commits.\n\nThis is a good approximation to the set of objects that the client needs\nto be sent. It does not search the ancestors of and ,\nso it is possible that a copy of some object exists in an older commit,\nand the state in is a reversion to a pre- state, but it's\nunlikely and not worth looking for. Sending it redundantly is harmless.\n\n\nThen, this set of objects is piped to git-pack-objects, which finds them\nand builds a pack file. If the objects are stored locally as deltas\nrelative to other objects which are either to be sent, or are in the\n or commits (which information is included in the data\noutput by git-rev-list), the delta is copied to the pack file verbatim.\nOtherwise, more CPU is spent to pack it.\n\nAgain, the server is allowed to check for deltas against ancestors\nof or , but doesn't bother for efficiency.\n\n\nFourth, the pack file is sent to the client, which unpacks it (and\ndiscards any duplicates).\n\n> When the client wants a shallow clone it starts by telling the server\n> all of the HEADs and how many change sets down each of those HEADs it\n> has locally. That's a small amout of data to transmit and it can be\n> easily tracked. Let's ignore merged branches for the moment.\n\nWhen you say \"change set\", I'm going to assume you mean \"commit object\".\n\nOkay. Now, the server hasn't heard of one or more of those commit\nobjects, because they're local changes. What then?\n\n\nAnother issue is that a client with a nearly-full copy has to do a full\nwalk of its history to determine the depth count that it has. That can\nbe more than 2500 commits down in the git repository, and worse in the\nmozilla one. It's actually pretty quick (git-show-branch --more=99999\nwill do it), but git normally tries to avoid full traversals like the\nplague \n\nOh, and was \"for the moment\" supposed to last past the end of your e-mail?\nI don't see what to do if there's a merge in the history and the depth\non different sides is not equal. E.g. the history looks like:\n\n...a---b---c---d---e---f\n / \\\n ...w---x---y HEAD\n /\n ...p---q---r---s\n\nWhere \"...\" means that there are ancestors, but they're missing.\n\n> If you haven't updated for six months when the server walks backwards\n> for 10 change sets it's not going to find anything you have locally.\n> When this situation is encountered the server needs to generate a\n> delta just for you between one of the change sets it knows you have\n> and one of the 10 change sets you want. By generating this one-off\n> delta it lets you avoid the need to fetch all of the objects back to a\n> common branch ancestor. The delta functions as a jump over the\n> intervening space.\n\nYour choice of words keeps giving me the impression that you believe\nthat a \"change set\" is a monolithic object that includes all the changes\nmade to all the files. It's neither monolithic nor composed of changes.\nA commit objects consists soley of metadata, and contains a pointer to\na tree object, which points recursively to the entire project state at\nthe time of the commit.\n\nThere is massive sharing of component objects between successive\ncommits, but they are NOT stored as deltas relative to one another.\n\nThe pack-forming heuristics tend to achieve that effect, but it is not\nguaranteed or required by design.\n\nPlease understand that, deep in your bones: git is based on snapshots,\nnot deltas.\n\n\nBut okay, so we've sent the client the latest 10 commits, with a dangling\ntail at the bottom. (The files may have been sent as deltas against the\nold state, or just fresh compressed copies, but that doesn't matter.)\nThen the heads like \"origin\" have been advanced.\n\nSo the old commit history is now unreferenced garbage; nothing points\nto it, and it will be deleted next time git-prune is run. Is that\nthe intended behavior? Or should updates to an existing clone always\ncomplete the connections?\n"},{"id":"26556","messageId":"9e4733910609071923tf1c49f6o70419e961e9eb66f@mail.gmail.com","threadId":"5513","inReplyTo":"20060908010112.6962.qmail@science.horizon.com","subject":"Re: Change set based shallow clone","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-08T02:23:18Z","receivedAt":"2006-09-08T02:23:18Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 7 Sep 2006 21:01:12 -0400, linux@horizon.com wrote:\n> > When the client wants a shallow clone it starts by telling the server\n> > all of the HEADs and how many change sets down each of those HEADs it\n> > has locally. That's a small amout of data to transmit and it can be\n> > easily tracked. Let's ignore merged branches for the moment.\n>\n> When you say \"change set\", I'm going to assume you mean \"commit object\".\n>\n> Okay. Now, the server hasn't heard of one or more of those commit\n> objects, because they're local changes. What then?\n\nToss them, if they don't exist on the server the server is going to be\nable to send any objects for them.\n\n> Another issue is that a client with a nearly-full copy has to do a full\n> walk of its history to determine the depth count that it has. That can\n> be more than 2500 commits down in the git repository, and worse in the\n> mozilla one. It's actually pretty quick (git-show-branch --more=99999\n> will do it), but git normally tries to avoid full traversals like the\n> plague\n\nClient would track this incrementally and not recompute it each time.\n\n> Oh, and was \"for the moment\" supposed to last past the end of your e-mail?\n> I don't see what to do if there's a merge in the history and the depth\n> on different sides is not equal. E.g. the history looks like:\n>\n> ...a---b---c---d---e---f\n> / \\\n> ...w---x---y HEAD\n> /\n> ...p---q---r---s\n>\n> Where \"...\" means that there are ancestors, but they're missing.\n>\n> > If you haven't updated for six months when the server walks backwards\n> > for 10 change sets it's not going to find anything you have locally.\n> > When this situation is encountered the server needs to generate a\n> > delta just for you between one of the change sets it knows you have\n> > and one of the 10 change sets you want. By generating this one-off\n> > delta it lets you avoid the need to fetch all of the objects back to a\n> > common branch ancestor. The delta functions as a jump over the\n> > intervening space.\n>\n> Your choice of words keeps giving me the impression that you believe\n> that a \"change set\" is a monolithic object that includes all the changes\n> made to all the files. It's neither monolithic nor composed of changes.\n> A commit objects consists soley of metadata, and contains a pointer to\n> a tree object, which points recursively to the entire project state at\n> the time of the commit.\n\nI was using change set to refer to snapshot.\n\n> There is massive sharing of component objects between successive\n> commits, but they are NOT stored as deltas relative to one another.\n\nYes, most of the sharing occurs via the tree structures.\n\n> The pack-forming heuristics tend to achieve that effect, but it is not\n> guaranteed or required by design.\n>\n> Please understand that, deep in your bones: git is based on snapshots,\n> not deltas.\n>\n>\n> But okay, so we've sent the client the latest 10 commits, with a dangling\n> tail at the bottom. (The files may have been sent as deltas against the\n> old state, or just fresh compressed copies, but that doesn't matter.)\n> Then the heads like \"origin\" have been advanced.\n>\n> So the old commit history is now unreferenced garbage; nothing points\n> to it, and it will be deleted next time git-prune is run. Is that\n> the intended behavior? Or should updates to an existing clone always\n> complete the connections?\n\nIf you follow the links in what looks to be a dangling object sooner\nor latter you will run into the root object or a 'not present' object.\nIf you hit one of those the objects are not dangling and should be\npreserved.\n\n\n\nHere is another way to look at the shallow clone problem. The only\npublic ids in a git tree are the head and tag pointers. Send these to\nthe client. Now let's modify the git tools to fault the full objects\nin one by one from the server whenever a git operation needs the\nobject. Dangling references would point to 'not-present' objects.\n\nFor a typical user using a model like this, how much of the Mozilla\nrepository would end up being faulted into their machine? Mozilla has\n2M objects and 250K commits in a 450MB pack. My estimate is that a\ntypical user is going to touch less than 200K of the objects and maybe\nless than 100K.\n\nOf course always faulting in full objects is wasteful. A smart scheme\nwould be to try and anticipate with some read ahead and figure out\nways to send deltas. Tools like gitk would need to only touch the\nobjects needed to draw the screen and not run the full commit chain at\nstartup.\n\nThis experiment can be done fairly easily. Put all of the kernel\nsource into a single pack file. Modify the git tools to set a bit in\nthe index file if an object is accessed. Use the pack for a few days\nand then dump out the results.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26558","messageId":"46a038f90609072054u5ec8bc46x9878a601953b2c5d@mail.gmail.com","threadId":"5513","inReplyTo":"7vpse7tjp0.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2006-09-08T03:54:11Z","receivedAt":"2006-09-08T03:54:11Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On 9/8/06, Junio C Hamano wrote:\n...\n> Anyway, it is a useful feature, an important operation, and\n> it involves a lot of thinking (and hard work, obviously).\n>\n> I will not think about this anymore, until I have absolutely\n> nothing else to do for a solid few days, but you probably\n> haven't read this far ;-).\n\nFor when you come back, then. I agree this is rather complicated, so\nmuch so that I suspect that we may be barking up the wrong tree.\n\nPeople who want shallow clones are actually asking for a \"light\"\nclone, in terms of \"how much do I need to download\". If everyone has\nthe whole commit chain (but may be missing olden blobs, and even\ntrees), the problem becomes a lot easier.\n\nOn the wire, all the client needs to say from root commit X to later\ncommits A, B, C, D, can I have all the relevant blobs? (Some may end\nup being resent, but that's a tradeoff).\n\nOn the server side, keeping commits (and/or trees) in a segregated\npack makes sense as an optimization. On the client side, a similar\nsegregated pack for the 'known blobless' commits/trees may make sense\nto be able to be able treat ops on the blobless part of history\ndifferently.\n\n{From a user interaction point of view, it is also easier to error out\nsaying \"don't have it, but you'll get it if you ask for history from\n[SHA1] onwards\".}\n\njust my .2\n\n\nm\n"},{"id":"26559","messageId":"edqtna$3v6$1@sea.gmane.org","threadId":"5513","inReplyTo":"7vpse7tjp0.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Aneesh Kumar K.V","fromEmail":"aneesh.kumar@gmail.com","sentAt":"2006-09-08T05:05:40Z","receivedAt":"2006-09-08T05:05:40Z","isPatch":false,"sender":{"key":"aneesh.kumar@gmail.com","avatar":"https://gravatar.com/avatar/0621fc0b2f14ead1e9024382f16053a808c148596da30c1b92572fa075621f68?d=mp&s=160"},"body":"Junio C Hamano wrote:\n> I've been postponing thinking about shallow clones with a plan\n> to do so when I have absolutely nothing else to do for a solid\n> few days. Since my time is booked pretty much full with day job\n> and the ongoing pack-file topics these days, I will most likely\n> stick to that plan after I finish this message.\n> \n> Not because I think it is an insignificant problem at the fringe\n> (I did not say \"when I have nothing better to do\"), but because\n> I feel this is something important (and hard) that requires\n> \"think about it and only about it straight through for a few\n> days, dropping everything else\" kind of thinking.\n> \n> When you have a ref under .git/refs/ pointing at an object, you\n> are making this assertion:\n> \n> The object store associated with this repository\n> (usually, .git/objects and alternates pointed at by\n> .git/objects/info/alternates) holds _all_ objects that\n> are recursively reachable from this object by following\n> tag reference, commit ancestry chain, commit to its\n> tree, and tree to its subtrees and blobs.\n> \n> So by definition, a shallow clone is a broken/incomplete\n> repository. Unless we fix the breakage in some way.\n> \n> One way to do so which has often been talked about is to use the\n> grafts facility. You cut off the history at some commit, and\n> cauterize the commit ancestry chain at that point by telling git\n> to pretend that the commit does not have any parent. While this\n> would work after setting it up, in the sense that \"git log\"\n> would stop at the commit and \"git fsck-objects\" would say\n> nothing is missing, it is cumbersome to set up, we do not have\n> an easy way to fetch (or clone -- but clone is a special case of\n> fetch where the downstream starts out from emptiness) from such\n> a repository, unplugging to get histories further back with\n> a later fetch is quite involved, and it is not clear what it\n> means to further fetch from such a shallow clone.\n\n\nPardon my ignorance, but won't having a http:// or ssh based url support in objects/info/alternates\nwill support such shallow clones. What i am wondering is can't we make the objects/info/alternates following code\ntraverse the network transport and make git log work like cvs log in case things are not in local repository. This\nshould make all the git operation slow, but if you are interested in speed one can clone the repository fully.\n\n-aneesh \n"},{"id":"26560","messageId":"7vac5ancvo.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"46a038f90609072054u5ec8bc46x9878a601953b2c5d@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-08T05:30:51Z","receivedAt":"2006-09-08T05:30:51Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Martin Langhoff\" writes:\n\n> On 9/8/06, Junio C Hamano wrote:\n> ...\n>> Anyway, it is a useful feature, an important operation, and\n>> it involves a lot of thinking (and hard work, obviously).\n>>\n>> I will not think about this anymore, until I have absolutely\n>> nothing else to do for a solid few days, but you probably\n>> haven't read this far ;-).\n>\n> For when you come back, then. I agree this is rather complicated, so\n> much so that I suspect that we may be barking up the wrong tree.\n>\n> People who want shallow clones are actually asking for a \"light\"\n> clone, in terms of \"how much do I need to download\". If everyone has\n> the whole commit chain (but may be missing olden blobs, and even\n> trees), the problem becomes a lot easier.\n\nNo, I do not think so. You are just pushing the same problem to\nanother layer.\n\nReachability through commit ancestry chain is no more special\nthan reachability through commit-tree or tree-containment\nrelationships. The grafts mechanism happen to treat commit\nancestry more specially than others, but that is not inherent\nproperty of git [*1*]. It is only an implementation detail (and\nlimitation -- grafts cannot express anything but commit\nancestry) of the current system.\n\nBut let's touch a slightly different but related topic first.\nPeople do not ask for shallow clones. They just want faster\ntransfer of \"everything they care about\". Shallow and lazy\nclones are implementation techniques to achieve the goal of\nmaking everything they care about appear available, typically\ntaking advantage of the fact that people care about recent past\na lot more than they do about ancient history.\n\nShallow clones do so by explicitly saying \"sorry you told me\nearlier you do not care about things older than X so if you now\ncare about things older than X please do such and such to deepen\nyour history\". What you are saying is a variant of shallow that\nsays \"NAK; commits I have but trees and blobs associated with\nsuch an old commit you have to ask me to retrieve from\nelsewhere\". Lazy clones do so by \"faulting missing objects on\ndemand\" [*2*]. That is essentially automating the \"please do\nsuch and such\" part. So they are all not that different.\n\nNow, first and foremost, while I would love to have a system\nthat gracefully operates with a \"sparse\" repository that lacks\nobjects that should exist from tag/commit/tree/blob reachability\npoint of view, it is an absolute requirement that I can tell why\nobjects are missing from a repository when I find some are\nmissing by running fsck-objects [*3*]. If repository is a\nshallow clone, not having some object may be expected, but I\nwant to be able to tell repository corruption locally even in\nthat case, so \"assume lack of object is perhaps it was not\ndownloaded by shallow cloning\" is an unacceptable attitude, and\n\"when you find an object missing from your repository, you can\nask the server [*4*], and if the server does not have it then\nyou know your repository is corrupt otherwise it is Ok\" is a\nwrong answer.\n\nI talked about the need of upload-pack protocol extension to\nexchange grafts information between uploader and downloader to\ncome up with the resulting graft and update the grafts in\ndownloaded repository after objects tranfer is done. It is\nneeded because by having such cauterizing graft entries I can be\nsure that the repository is not corrupt when fsck-objects that\ndoes look at grafts says \"nothing is missing\". Jon talked about\n\"fault-in on demand and leave stub objects until downloading the\nreal thing\"; those stub objects are natural extension of grafts\nfacility but extends to trees and blobs. Either of these would\nallow me to validate the sparse repository locally.\n\nNow I'll really shut up ;-).\n\n\n[*1*] For example, rev-list --object knows that it needs to show\nthe tree-containment when given only a tree object without any commit.\n\n[*2*] You probably could write a FUSE module that mount on\nyour .git/objects, respond to accesses to .git/objects/??\ndirectory and files with 38-byte hexadecimal names under them by\ntalking to other repositories over the wire. No, I am not going\nto do it, and I will probably not touch it even with ten-foot\npole for reasons I state elsewhere in this message.\n\n[*3*] The real fsck-objects always looks at grafts. The\nfictitious version of fsck-objects I am talking about here is\nthe one that uses parents recorded on the \"parent \" line of\ncommit objects, that is, the true object level reachability.\n\n[*4*] In git, there is no inherent server vs client or upstream\nvs downstream relationship between repositories. You may be\neven fetching from many people and do not have a set upstream at\nall. Or you are _the_ upstream, and your notebook has the\nlatest devevelopment history, and after pushing that latest\nhistory to your mothership repository, you may decide you do not\nwant ancient development history on a puny notebook, and locally\ncauterize the history on your notebook repository and prune\nancient stuff. The objects missing from the notebook repository\nare retrievable from your mothership repository again if/when\nneeded and you as the user would know that (and if you are lucky\nyou may even remember that a few months later), but git doesn't,\nand there is no reason for git to want to know it. If we want\nto do \"fault-in on demand\", we need to add a way to say \"it is\nOk for this repository to be incomplete -- objects that are\nmissing must be completed from that repository (or those\nrepositories)\". But that's quite a special case of having a\nfixed upstream.\n"},{"id":"26563","messageId":"46a038f90609080015u56daae78u9d78584edae7fb72@mail.gmail.com","threadId":"5513","inReplyTo":"7vac5ancvo.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2006-09-08T07:15:53Z","receivedAt":"2006-09-08T07:15:53Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On 9/8/06, Junio C Hamano wrote:\n> \"Martin Langhoff\" writes:\n> > People who want shallow clones are actually asking for a \"light\"\n> > clone, in terms of \"how much do I need to download\". If everyone has\n> > the whole commit chain (but may be missing olden blobs, and even\n> > trees), the problem becomes a lot easier.\n>\n> No, I do not think so. You are just pushing the same problem to\n> another layer.\n>\n> Reachability through commit ancestry chain is no more special\n> than reachability through commit-tree or tree-containment\n> relationships. The grafts mechanism happen to treat commit\n\nAgreed that it is no more special. OTOH, if we focus on the fact that\npeople want to avoid high-cost data transfers, transferring commit\nchains is cheap and allows the client to ask good questions when\ntalking to the server.\n\nSo as far as tradeoffs go, it allows you to keep the protocol simple,\nand minimise complex guessing at either end of the wire.\n\n> But let's touch a slightly different but related topic first.\n> People do not ask for shallow clones. They just want faster\n> transfer of \"everything they care about\". Shallow and lazy\n\nI'd disagree a bit here. They care about the whole project, and in\ntime they'll find that out and end up pulling it all if they use git\nmuch at all ;-)\n\nThey want fast, cheap initial checkouts.\n\n...\n> So they are all not that different.\n\nEarlier you were pointing out how hard it was for the client to even\nknow what to ask for because it can't see the whole picture. Having\nthe ancestry complete means you always know what to ask for.\n\n> Now, first and foremost, while I would love to have a system\n> that gracefully operates with a \"sparse\" repository that lacks\n> objects that should exist from tag/commit/tree/blob reachability\n> point of view, it is an absolute requirement that I can tell why\n> objects are missing from a repository when I find some are\n> missing by running fsck-objects [*3*].\n\nI agree -- and you can keep those objects you know are expected to be\nmissing listed in an \"packless\" idx file somewhere.\n\n> If repository is a\n> shallow clone, not having some object may be expected, but I\n> want to be able to tell repository corruption locally even in\n> that case,\n\n+1\n\n> I talked about the need of upload-pack protocol extension\n\nAs far as I can see, this would not need any change to the upload-pack\nprotocol.\n\nThere are some hard problems in dealing with a sparse repo that need\nthinking through. My thinking is that by having the whole commit chain\naround the protocol can be kept sane, by virtue of the local repo\nalways having a clear \"overall\" picture, including knowing what it's\nmissing.\n\n> [*4*] In git, there is no inherent server vs client or upstream\n> vs downstream relationship between repositories.\n\nHere an importaant distiction must be made. A \"publishing\" repo cannot\nbe sparse. A sparse repo probably cannot be cloned from.\n\n> You may be\n> even fetching from many people and do not have a set upstream at\n> all. Or you are _the_ upstream, and your notebook has the\n> latest devevelopment history, and after pushing that latest\n> history to your mothership repository, you may decide you do not\n> want ancient development history on a puny notebook, and locally\n> cauterize the history on your notebook repository and prune\n> ancient stuff.\n\nWell, that's easy again: \"prune old blobs and list them in an idx\"\nshould work well.\n\ncheers,\n\n\n\nmartin\n"},{"id":"26568","messageId":"7v4pvikbaf.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"46a038f90609080015u56daae78u9d78584edae7fb72@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-08T08:33:28Z","receivedAt":"2006-09-08T08:33:28Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Martin Langhoff\" writes:\n\n> As far as I can see, this would not need any change to the upload-pack\n> protocol.\n\nThat I have to disagree. Take your earlier example of \"I have X\nand I learned you have A B C D\". Now the fetch that got X was a\ncommit-only one (but you have full tree for X), but you got X\nfrom somebody else, not the uploader you are talking with right\nnow. There is a common ancestor Y somewhere behind X, but\nbetween Y and X you lack trees and blobs.\n\nHow would the current protocol work (I am explaining that it\nwon't be \"not need any change\")? After you express interest for\nA, B, C, D with \"want\" messages, you start telling \"have X\",\n\"have X~1\", have \"X~2\",... to the uploader (X, X~1 etc. are\nobject names not symbolic). Eventually the uploader would\nrecognize Y that is an ancestor of X that it has and will Ack\nit, you stop traversing the ancestor of an acked one and say\n\"done\". So now we have a common ancestor and the upload side\nknows it can omit commits behind that common commit Y, trees\nand blobs contained in Y.\n\nSee an Oops here? You do NOT have trees and blobs associated\nwith commit Y.\n\nI am not saying we should not change the protocol. I am just\ntrying to explain that the problem is not something you can\nfudge without changing the protocol.\n\nAs a first level approximation, we could in addition to the\ncommit object name have a bit that says \"do I have trees and\nblobs associated with the commit\" bit on each \"have\" message (by\nthe way, this is _expensive_. You have to traverse down the\ntree contained in each commit using has_sha1_file() recursively\nto see if you have anything missing from _each_ commit you send\nto the other). Alternatively, you can say \"I have this commit,\nbut I do not have this tree and I do not even know if I have\nblobs needed to complete that tree because I do not know what\nthat tree I am missing contains -- I may have them, I may not. I\ntruly do not know\" to convey the same information.\n\nThink about it a bit -- saying \"I know I am missing this tree\"\nis one thing, but if we end up saying \"I do not even know what I\nam missing\", it is like saying \"don't care what I say, just send\neverything to me\". Are we gaining much by having only commit\nobjects on our end?\n\nOnce you end up sending a full tree, it is like doing an initial\ncheckout over CVS when you think you are incrementally fetching,\nand you are already lost. For example, a recent kernel tarball\ncompressed with gzip is around 50MB; the history for 34k commits\nsince 2.6.12-rc2 fully packed is slightly less than 150MB.\n"},{"id":"26569","messageId":"edra0v$42a$1@sea.gmane.org","threadId":"5513","inReplyTo":"9e4733910609071923tf1c49f6o70419e961e9eb66f@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-09-08T08:36:13Z","receivedAt":"2006-09-08T08:36:13Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Jon Smirl wrote:\n\n> Here is another way to look at the shallow clone problem. The only\n> public ids in a git tree are the head and tag pointers. Send these to\n> the client. Now let's modify the git tools to fault the full objects\n> in one by one from the server whenever a git operation needs the\n> object.  Dangling references would point to 'not-present' objects.\n> \n> For a typical user using a model like this, how much of the Mozilla\n> repository would end up being faulted into their machine? Mozilla has\n> 2M objects and 250K commits in a 450MB pack. My estimate is that a\n> typical user is going to touch less than 200K of the objects and maybe\n> less than 100K.\n> \n> Of course always faulting in full objects is wasteful. A smart scheme\n> would be to try and anticipate with some read ahead and figure out\n> ways to send deltas. Tools like gitk would need to only touch the\n> objects needed to draw the screen and not run the full commit chain at\n> startup.\n\nYes, that is also recurring _lazy_ clone idea (or remote alternatives[*1*]\nidea). With it's own set of difficulties, like cache management, readahead\nand such, and of course differentiating between not present, and present on\nthe remote server. And what to do when network fails... wouldn't it be just\neasier to use networking system like Coda or InterMezzo?\n\n\n[*1*] From Documentation/repository-layout.txt or\nhttp://www.kernel.org/pub/software/scm/git/docs/repository-layout.html\n\nYou can be using `objects/info/alternates` mechanism, or\n`$GIT_ALTERNATE_OBJECT_DIRECTORIES` mechanism to 'borrow'\nobjects from other object stores. A repository with this kind\nof incomplete object store is not suitable to be published for\nuse with dumb transports but otherwise is OK as long as\n`objects/info/alternates` points at the right object stores\nit borrows from.\n\n[...]\n\nobjects/info/alternates::\n This file records absolute filesystem paths of alternate\n object stores that this object store borrows objects\n from, one pathname per line.\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"26570","messageId":"7vzmdaiwg5.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"edra0v$42a$1@sea.gmane.org","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-08T08:39:22Z","receivedAt":"2006-09-08T08:39:22Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jakub Narebski writes:\n\n> [*1*] From Documentation/repository-layout.txt or\n> http://www.kernel.org/pub/software/scm/git/docs/repository-layout.html\n>\n> You can be using `objects/info/alternates` mechanism, or\n> `$GIT_ALTERNATE_OBJECT_DIRECTORIES` mechanism to 'borrow'\n> objects from other object stores. A repository with this kind\n> of incomplete object store is not suitable to be published for\n> use with dumb transports but otherwise is OK as long as\n> `objects/info/alternates` points at the right object stores\n> it borrows from.\n\nAh, you spotted an obsolete documentation again ;-).\n"},{"id":"26572","messageId":"45012E67.6050406@op5.se","threadId":"5513","inReplyTo":"9e4733910609071341u7e430214j71ddcbefa26810ca@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2006-09-08T08:48:39Z","receivedAt":"2006-09-08T08:48:39Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Jon Smirl wrote:\n> On 9/7/06, Jakub Narebski wrote:\n>> I don't understand. Git is _not_ patchset based (like GNU Arch, or\n> \n> I meant change set to refer to a commit plus trees plus blobs that\n> make it up. These may be present in full or delta form.\n> \n>> Mercurial, or CVS). It is snapshot based. So if you want to download\n>> \"skip\", you need only for the local part of doenloader to make \n>> appropriate\n>> grafts, like below\n>>\n>>\n>> *--*--*--*--*--*--*--*--*--*--*--HEAD (server)\n>>\n>> *--*--*...........*--*--*--*--*--HEAD (shallow/sparse clone)\n>>\n>> But the part you were talking about is _easy_ part; the hard part is\n>> merges including merging branch which was split off the trunk before\n>> cutoff-point, history rewriting (c.f. 'pu' branch, and rebases), etc.\n> \n> Does an average user do these things? The shallow clone is there to\n> address the casual user who gags at a five hour download to get an\n> initial check out Mozilla when they want to make a five line change or\n> just browse the source for a few minutes.\n> \n\nA better idea would be to allow those users to download a gzipped \ntarball of a pre-grafted repository. It shouldn't be terribly difficult \nto set up an update-hook that creates the pre-grafted repository for you \nwhenever a tag (or some such) is created in the repo you host wherever \neverybody does their initial clone from.\n\nAs I understand it (although I've admittedly followed the git \nmailing-list sporadically the past three or so months), grafts already \nwork as intended, and the users can then fetch into their grafted repo \nto get a bare minimum of objects.\n\n> \n> There would also be a command to bring down all of the objects to\n> fully populate a sparse tree. You could do the shallow clone to begin\n> with and then do the full tree populate overnight or in the\n> background.\n> \n\nWith the pre-grafted history this would work as follow\n\n$ mkdir pregraft\n$ wget http://pre-grafts.mozilla.org/pregrafted.git.tgz\n$ cd pregraft\n$ tar xvzf ../pregrafted.git.tgz\n$ cd ..\n$ git clone mozilla-repo-url >& /dev/null &\n$ cd pregraft\n# work, work, work; full clone completes\n$ cd ../mozilla-repo\n$ git pull ../pregraft master\n\nor something similar.\n\niow, you get the small repo quickly and can start hacking while the \nfull-history clone is downloading. If I understand grafts correctly, you \ncould then merge in your changes made in the grafted repo to the one \nwith full history.\n\n> Maybe the answer is to build a shallow clone tool for casual use, and\n> then if you try to run anything too complex on it git just tells you\n> that you have to download the entire tree.\n> \n\nI believe all tools that work with history understand grafts already, \nand if so they should provide sane messages when the user attempts to \naccess history beyond the grafts. I might have missed or misunderstood \nsomething, but this seems to me like a simple solution to a complex problem.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"26583","messageId":"9e4733910609080720s7a143d9bp5a1dd36869967c22@mail.gmail.com","threadId":"5513","inReplyTo":"7vac5ancvo.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-08T14:20:06Z","receivedAt":"2006-09-08T14:20:06Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/8/06, Junio C Hamano wrote:\n> [*4*] In git, there is no inherent server vs client or upstream\n> vs downstream relationship between repositories. You may be\n> even fetching from many people and do not have a set upstream at\n> all. Or you are _the_ upstream, and your notebook has the\n> latest devevelopment history, and after pushing that latest\n> history to your mothership repository, you may decide you do not\n> want ancient development history on a puny notebook, and locally\n> cauterize the history on your notebook repository and prune\n> ancient stuff. The objects missing from the notebook repository\n> are retrievable from your mothership repository again if/when\n> needed and you as the user would know that (and if you are lucky\n> you may even remember that a few months later), but git doesn't,\n> and there is no reason for git to want to know it. If we want\n> to do \"fault-in on demand\", we need to add a way to say \"it is\n> Ok for this repository to be incomplete -- objects that are\n> missing must be completed from that repository (or those\n> repositories)\". But that's quite a special case of having a\n> fixed upstream.\n\nA 'not-present' object would be a normal git object, it would contain\na list of sha1s that it is stubbing for. These alias sha1s need to end\nup somewhere where the git tools can find them. Maybe put all of the\n'not-present' objects into their own pack and add the aliases to the\nindex. If the aliases point back the 'not-present' object everything\ncan be validated even if the alias sha1s don't match the one of the\nobject. This pack would be private and not sent to other repositories.\n\nIt would be useful to maintain a list of possible remote repositories\nto search for the missing objects if needed. This list could be shared\nwith people that clone from you.\n\nIf you clone from a remote repository that is a partial copy you may\nnot be able to get all of the objects you want. The only choice here\nis to point them to 'not-present' stub and try searching the\nalternative repository list.\n\nIf you really want to build something for the future, have all of the\ngit repositories on the net talk to each other and use a distributed\nhash scheme to spread redundant copies of the objects out over the\ncloud of servers. This will have the effect of creating a global\nnamespace for all git projects.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26584","messageId":"eds3fg$u30$1@sea.gmane.org","threadId":"5513","inReplyTo":"9e4733910609080720s7a143d9bp5a1dd36869967c22@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-09-08T15:50:40Z","receivedAt":"2006-09-08T15:50:40Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"My idea for lazy clone/fetch (lazy = on-demand) is via remote alternatives\nmechanism. We put URI for repository (repositories) that hosts the project,\nand we would need at start to download at least heads and tags, and only\nheads and tags.\n\nWhen there is request for an object (commit, tree, blob or tag) which we\ndon't have locally, we ask remote repository if it have it, and download it\n(and perhaps some related objects); this needs extension I guess for the\ngit downloader ('wantonly'), it should be fairly easy for dumb downloaders\nif you don't mind getting whole pack i.e. perhaps more than intended.\nPerhaps 'wantonly' for git protocol should work the same: one would get\nready pack (perhaps with limit on pack size: otherwise one would get only\nthe requested objects).\n\nOne thing that needs extending for lazy clone is git-fsck... otherwise you\nwould get whole repository when calling git-fsck. Simplest would be\nfsck-ing only the local part, perhaps checking if the \"missing\" objects are\npresent in remote repository, but not downloading them and not checking\nconnectivity further... and of course notifying user that this is lazy\nclone. Unless we run git-fsck-objects on the remote side, then pass results\nto the local side.\n\nThere is probably bunch of problems with this idea...\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"26586","messageId":"4501A5DC.609@gmail.com","threadId":"5513","inReplyTo":"46a038f90609080015u56daae78u9d78584edae7fb72@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2006-09-08T17:18:20Z","receivedAt":"2006-09-08T17:18:20Z","isPatch":false,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Martin Langhoff wrote:\n> On 9/8/06, Junio C Hamano wrote:\n...\n>> [*4*] In git, there is no inherent server vs client or upstream\n>> vs downstream relationship between repositories.\n> \n> Here an importaant distiction must be made. A \"publishing\" repo cannot\n> be sparse. A sparse repo probably cannot be cloned from.\n\nWith the use of \"placeholder\" objects; neither one of these assertions\nis true.\n"},{"id":"26587","messageId":"20060908184215.31789.qmail@science.horizon.com","threadId":"5513","inReplyTo":"9e4733910609071923tf1c49f6o70419e961e9eb66f@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-09-08T18:42:15Z","receivedAt":"2006-09-08T18:42:15Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"Thanks for making suggestions. It's easier to knock straw men down\nthan make them. But forgive me if I have fun pointing out the holes...\n\n>> Okay. Now, the server hasn't heard of one or more of those commit\n>> objects, because they're local changes. What then?\n>\n> Toss them, if they don't exist on the server the server is going to be\n> able to send any objects for them.\n\nEr... that makes \"git pull git://git.other-hacker.personal/dir\"\nimpossible. There's a reason that git can handle this as it presently\nexists: \n a-b-c-d-e-f <-- HEAD\n /\nHacker 1: o-o-o-o <-- origin\n\nHacker 2: o-o-o-o-o-o <-- origin\n \\\n v-w-x-y <-- HEAD\n\nSuppose hacker 2, who happened to sync with upstream more recently,\nwants to pull from hacker 1, in the hopes of building\n\n a-b-c-d-e-f\n / \\\nHacker 2: o-o-o-o-o-o z <-- HEAD\n \\ /\n v-w-x-y\n\nThis works now, and should continue to work.\n\n> Client would track this incrementally and not recompute it each time.\n\nYes, this is probably possible. I haven't worked it out, but given a\ncache of precomputed (commit,depth) numbers, you can trace back from the\nnew heads until you hit a cache entry.\n\n> If you follow the links in what looks to be a dangling object sooner\n> or latter you will run into the root object or a 'not present' object.\n> If you hit one of those the objects are not dangling and should be\n> preserved.\n\nI don't understand. It seems like you're saying that any commit without an\nancestor, and all objects recursively pointing to it, are not garbage.\nHow would anything ever get declared garbage in this case?\n\n> Here is another way to look at the shallow clone problem. The only\n> public ids in a git tree are the head and tag pointers. Send these to\n> the client. Now let's modify the git tools to fault the full objects\n> in one by one from the server whenever a git operation needs the\n> object. Dangling references would point to 'not-present' objects.\n\nEr... that would fault in a gigabyte the first time someone ran gitk,\nor several other history-browsing commands. Don't you need a way to say\n\"tell the user this isn't present and will take an hour to download\"?\n\n\nWell, thinking, there are actually two shallow clone possibilities:\n1) Don't load the unwanted commit objects\n2) Clone the commit objects, but not their trees.\n\nThe latter would let you browse the commit history, at least.\n"},{"id":"26593","messageId":"9e4733910609081413p32456768g280bdc9b232d7902@mail.gmail.com","threadId":"5513","inReplyTo":"20060908184215.31789.qmail@science.horizon.com","subject":"Re: Change set based shallow clone","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-08T21:13:42Z","receivedAt":"2006-09-08T21:13:42Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"> > Here is another way to look at the shallow clone problem. The only\n> > public ids in a git tree are the head and tag pointers. Send these to\n> > the client. Now let's modify the git tools to fault the full objects\n> > in one by one from the server whenever a git operation needs the\n> > object. Dangling references would point to 'not-present' objects.\n>\n> Er... that would fault in a gigabyte the first time someone ran gitk,\n> or several other history-browsing commands. Don't you need a way to say\n> \"tell the user this isn't present and will take an hour to download\"?\n\ngitk would need to be modified to only run enough of the commit tree\nto draw what is displayed in the window. As you page down it would\nretrive more commits if needed. There is no need for gitk to run 250K\ncommits when I'm usually never going to look at them all. Of course\nthis may mean some rework for gitk.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26605","messageId":"edsqmj$gh3$2@sea.gmane.org","threadId":"5513","inReplyTo":"9e4733910609081413p32456768g280bdc9b232d7902@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-09-08T22:27:01Z","receivedAt":"2006-09-08T22:27:01Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Jon Smirl wrote:\n\n>> > Here is another way to look at the shallow clone problem. The only\n>> > public ids in a git tree are the head and tag pointers. Send these to\n>> > the client. Now let's modify the git tools to fault the full objects\n>> > in one by one from the server whenever a git operation needs the\n>> > object. Dangling references would point to 'not-present' objects.\n>>\n>> Er... that would fault in a gigabyte the first time someone ran gitk,\n>> or several other history-browsing commands. Don't you need a way to say\n>> \"tell the user this isn't present and will take an hour to download\"?\n> \n> gitk would need to be modified to only run enough of the commit tree\n> to draw what is displayed in the window. As you page down it would\n> retrive more commits if needed. There is no need for gitk to run 250K\n> commits when I'm usually never going to look at them all. Of course\n> this may mean some rework for gitk.\n\nOr remembering to set --max-count or --max-age parameters to gitk (which are\nthen passed to git-rev-list).\n\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"26608","messageId":"Pine.LNX.4.64.0609081600530.27779@g5.osdl.org","threadId":"5513","inReplyTo":"9e4733910609081413p32456768g280bdc9b232d7902@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-08T23:09:15Z","receivedAt":"2006-09-08T23:09:15Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 8 Sep 2006, Jon Smirl wrote:\n> \n> gitk would need to be modified to only run enough of the commit tree\n> to draw what is displayed in the window. As you page down it would\n> retrive more commits if needed. There is no need for gitk to run 250K\n> commits when I'm usually never going to look at them all. Of course\n> this may mean some rework for gitk.\n\nActually, it's more than a little rework.\n\nThe _real_ problem is that gitk uses \"--topo-order\" to git-rev-list, which \nbasically means that git-rev-list needs to parse EVERY SINGLE COMMIT.\n\nSo far, nobody has written a topological sort that can reasonably \nefficiently handle partial trees and automatically notice when there is no \nway that a DAG cannot have any more references to a commit any more (if \nyou can show that the result would cause a cycle, you could output a \npartial topological tree early).\n\nIt's possible that no such topological sorting (ie the efficient kind, \nthat can work with partial DAG's) even exists.\n\nSo if you want to be able to visualize a partial repository, you need to \nteach git to not need \"--topo-order\" first. That's likely the _big_ \nchange. After that, the rest should be easy.\n\n[ One way to do it might be: the normal ordering of revisions without \n \"--topo-order) is \"_close_ to topological\", and gitk could just decide \n to re-compute the whole graph whenever it gets a commit that has a \n parent that it has already graphed. Done right, it would probably almost \n never actually generate re-computed graphs (if you only actually \n generate the graph when the user scrolls down to it).\n\n Getting rid of the --topo-order requirement would speed up gitk \n absolutely immensely, especially for unpacked cold-cache archives. So it \n would probably be a good thing to do, regardless of any shallow clone \n issues ]\n\nHmm?\n\n\t\tLinus\n"},{"id":"26610","messageId":"9e4733910609081628w2a59551foc28c689d0538a984@mail.gmail.com","threadId":"5513","inReplyTo":"Pine.LNX.4.64.0609081600530.27779@g5.osdl.org","subject":"Re: Change set based shallow clone","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-08T23:28:46Z","receivedAt":"2006-09-08T23:28:46Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/8/06, Linus Torvalds wrote:\n> Getting rid of the --topo-order requirement would speed up gitk\n> absolutely immensely, especially for unpacked cold-cache archives. So it\n> would probably be a good thing to do, regardless of any shallow clone\n> issues ]\n>\n> Hmm?\n\ngitk takes about a minute to come up on the Mozilla repo when\neverything is in cache. It takes about twice as long when things are\ncold. It's enough of delay that I don't use the tool.\n\n>\n> Linus\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26611","messageId":"17666.142.886652.667529@cargo.ozlabs.ibm.com","threadId":"5513","inReplyTo":"9e4733910609081628w2a59551foc28c689d0538a984@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2006-09-08T23:45:18Z","receivedAt":"2006-09-08T23:45:18Z","isPatch":false,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Jon Smirl writes:\n\n> gitk takes about a minute to come up on the Mozilla repo when\n> everything is in cache. It takes about twice as long when things are\n> cold. It's enough of delay that I don't use the tool.\n\nHow long does it take for git rev-list --topo-order to produce its\nfirst line of output, in the cache-hot case? That is, is it just\ngitk's graph layout that is taking the time, or is it git rev-list\n(meaning that gitk needs to stop using --topo-order)?\n\nPaul.\n"},{"id":"26612","messageId":"17666.4936.894588.825011@cargo.ozlabs.ibm.com","threadId":"5513","inReplyTo":"Pine.LNX.4.64.0609081600530.27779@g5.osdl.org","subject":"Re: Change set based shallow clone","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2006-09-09T01:05:12Z","receivedAt":"2006-09-09T01:05:12Z","isPatch":false,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Linus Torvalds writes:\n\n> [ One way to do it might be: the normal ordering of revisions without \n> \"--topo-order) is \"_close_ to topological\", and gitk could just decide \n> to re-compute the whole graph whenever it gets a commit that has a \n> parent that it has already graphed. Done right, it would probably almost \n> never actually generate re-computed graphs (if you only actually \n> generate the graph when the user scrolls down to it).\n> \n> Getting rid of the --topo-order requirement would speed up gitk \n> absolutely immensely, especially for unpacked cold-cache archives. So it \n> would probably be a good thing to do, regardless of any shallow clone \n> issues ]\n> \n> Hmm?\n\nI recently added code to gitk to add extra commits after the graph has\nbeen laid out, provided that the extra commits have one parent and no\nchildren. If I generalized that to handle arbitrary numbers of\nparents and children, it might go close to what you're suggesting.\n\nIt might get nasty if we have laid out A and then later B, and then C\ncomes along and turns out to be a child of A but a parent of B,\nmeaning that both B and C have to be put above A.\n\nAnother thing I have been thinking of is that gitk probably should\nimpose a time limit of say 3 months by default, unless the user\nspecifies some other ending condition (such as commitid.., ^commitid\nor --since=something-else). Together with a menu to select the time\nlimit, I think that would be quite usable and would make gitk start up\n*much* faster.\n\nPaul.\n"},{"id":"26613","messageId":"9e4733910609081845u36699865g2cc78e5a08267a86@mail.gmail.com","threadId":"5513","inReplyTo":"17666.142.886652.667529@cargo.ozlabs.ibm.com","subject":"Re: Change set based shallow clone","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-09T01:45:27Z","receivedAt":"2006-09-09T01:45:27Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/8/06, Paul Mackerras wrote:\n> Jon Smirl writes:\n>\n> > gitk takes about a minute to come up on the Mozilla repo when\n> > everything is in cache. It takes about twice as long when things are\n> > cold. It's enough of delay that I don't use the tool.\n>\n> How long does it take for git rev-list --topo-order to produce its\n> first line of output, in the cache-hot case? That is, is it just\n> gitk's graph layout that is taking the time, or is it git rev-list\n> (meaning that gitk needs to stop using --topo-order)?\n\nCold cache:\njonsmirl@jonsmirl:/opt/t1$ time git rev-list --all --topo-order\n--parents >/dev/null\n\nreal 0m27.687s\nuser 0m5.672s\nsys 0m0.560s\n\nHot cache:\njonsmirl@jonsmirl:/opt/t1$ time git rev-list --all --topo-order\n--parents >/dev/null\n\nreal 0m6.041s\nuser 0m5.768s\nsys 0m0.276s\njonsmirl@jonsmirl:/opt/t1$\n\nI have enough RAM (3GB) that everything fits.\n\nHot cache, 27 seconds to get first line of display in gitk\nIt takes about two minutes get everything loaded into the window and\nscroll to the head\n\nThis a 450MB pack, 250K commits, 2M objects.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26615","messageId":"Pine.LNX.4.64.0609081944060.27779@g5.osdl.org","threadId":"5513","inReplyTo":"17666.4936.894588.825011@cargo.ozlabs.ibm.com","subject":"Re: Change set based shallow clone","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-09T02:56:00Z","receivedAt":"2006-09-09T02:56:00Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 9 Sep 2006, Paul Mackerras wrote:\n> \n> It might get nasty if we have laid out A and then later B, and then C\n> comes along and turns out to be a child of A but a parent of B,\n> meaning that both B and C have to be put above A.\n\nRight. This is why I would suggest just recomputing the thing entirely, \ninstead of trying to make it incremental. It would definitely cause \nre-organization of the tree when you find a new relationship between two \nold commits that basically creates a new orderign between them.\n\nTrying to do that incrementally sounds really really hard. But just \n_detecting_ the situation that you are getting a new commit that has a \nparent that you have already shown (and that thus must go _before_ one of \nthe things you've shown already, and implies a new line reacing it) is \nvery easy. And then re-generating the graph might not be too bad.\n\nRunning \"gitk\" on the kernel with a hot cache and fully packed (and enough \nmemory) isn't too bad, because git rev-list literally takes under a second \nfor that case, so the advantage of avoiding --topo-order isn't _that_ \nnoticeable. \n\nAnd the \"fully packed\" part is probably the most important part. A packed \nLinux historic tree takes just under six seconds cold-cache and under two \nseconds hot-cache, but that's because pack-files are _really_ good at \nmapping all the commits in just one go, and at the beginning of the \npack-file.\n\nBut try the same thing with a fully unpacked kernel, and you'll see the \nreal pain of having to traverse all of history. We're talking minutes, \neven when hot in the cache.\n\n> Another thing I have been thinking of is that gitk probably should\n> impose a time limit of say 3 months by default\n\nI don't think time is good, because for an old project (like the Linux \nhistoric repo), three months is literally nothing. So it would be much \nbetter to go simply by numbers, but sadly, that won't help - simply \nbecause if we want to know the 100 first commits in --topo-order, we'll do \nthe whole history and sort it _first_, and then do the \"pick top 100 \ncommits\" only after that.\n\n(Which may not be sensible, of course, but it's what we do.. It's almost \nimpossible to do it the other way, because you won't know until the point \nwhere you do \"get_revision()\" if you are _actually_ going to use a commit \nor not, so counting them before the end is fundamentally very hard).\n\n> Together with a menu to select the time limit, I think that would be \n> quite usable and would make gitk start up *much* faster.\n\nThe menu would help, of course. But it would be even nicer if you'd be \nable to make do without the --topo-order.\n\n\t\tLinus\n"},{"id":"26616","messageId":"20060909031307.GE23891@pasky.or.cz","threadId":"5513","inReplyTo":"eds3fg$u30$1@sea.gmane.org","subject":"Re: Change set based shallow clone","fromName":"Petr Baudis","fromEmail":"pasky@suse.cz","sentAt":"2006-09-09T03:13:07Z","receivedAt":"2006-09-09T03:13:07Z","isPatch":false,"sender":{"key":"pasky@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/18439?v=4"},"body":"Dear diary, on Fri, Sep 08, 2006 at 05:50:40PM CEST, I got a letter\nwhere Jakub Narebski said that...\n> My idea for lazy clone/fetch (lazy = on-demand) is via remote alternatives\n> mechanism. We put URI for repository (repositories) that hosts the project,\n> and we would need at start to download at least heads and tags, and only\n> heads and tags.\n\n One thing to note is that you won't last very long without getting\nat least basically all the commits from the history. git log, git\nmerge-base and such would either just suck them all, get partially moved\nto the server side, or would undergo quite a painful and slooooooooow\nprocess \"get me commit X... thank you, sir. hmm, it appears that its\nparent is commit Y. could you get me commit Y, please...? thank you,\nsir. hmm, it appears...\".\n\n-- \n\t\t\t\tPetr \"Pasky\" Baudis\nStuff: http://pasky.or.cz/\nSnow falling on Perl. White noise covering line noise.\nHides all the bugs too. -- J. Putnam\n"},{"id":"26617","messageId":"7vfyf1ena5.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"Pine.LNX.4.64.0609081944060.27779@g5.osdl.org","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-09T03:23:14Z","receivedAt":"2006-09-09T03:23:14Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> And the \"fully packed\" part is probably the most important part. A packed \n> Linux historic tree takes just under six seconds cold-cache and under two \n> seconds hot-cache, but that's because pack-files are _really_ good at \n> mapping all the commits in just one go, and at the beginning of the \n> pack-file.\n>\n> But try the same thing with a fully unpacked kernel, and you'll see the \n> real pain of having to traverse all of history. We're talking minutes, \n> even when hot in the cache.\n\nJust a random thought... Does that suggest the general purpose\nfilesystem you would use for \"a fully unpacked\" case have room\nfor improvements? Would a special purpose filesystem that is\ndesigned to host .git/objects/??/ directory help?\n"},{"id":"26618","messageId":"17666.13716.401727.601933@cargo.ozlabs.ibm.com","threadId":"5513","inReplyTo":"Pine.LNX.4.64.0609081944060.27779@g5.osdl.org","subject":"Re: Change set based shallow clone","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2006-09-09T03:31:32Z","receivedAt":"2006-09-09T03:31:32Z","isPatch":false,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Linus Torvalds writes:\n\n> Right. This is why I would suggest just recomputing the thing entirely, \n> instead of trying to make it incremental. It would definitely cause \n> re-organization of the tree when you find a new relationship between two \n> old commits that basically creates a new orderign between them.\n\nI think it may be possible to back up the layout algorithm to the row\nwhere the parent is and redo it from there down.\n\nInterestingly, I only see two commits out of order on the linux-2.6\nrepository, but on the full history (up to linux-2.6.12-rc2) I see\n520.\n\n> The menu would help, of course. But it would be even nicer if you'd be \n> able to make do without the --topo-order.\n\nThe graph does seem to look a little nicer with --topo-order, in that\nit tends to do a whole string of commits on a single branch in a\nbunch, whereas without --topo-order it seems to hop from branch to\nbranch more.\n\nPaul.\n"},{"id":"26619","messageId":"Pine.LNX.4.64.0609082054560.27779@g5.osdl.org","threadId":"5513","inReplyTo":"17666.13716.401727.601933@cargo.ozlabs.ibm.com","subject":"Re: Change set based shallow clone","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-09T04:04:04Z","receivedAt":"2006-09-09T04:04:04Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 9 Sep 2006, Paul Mackerras wrote:\n> \n> > The menu would help, of course. But it would be even nicer if you'd be \n> > able to make do without the --topo-order.\n> \n> The graph does seem to look a little nicer with --topo-order, in that\n> it tends to do a whole string of commits on a single branch in a\n> bunch, whereas without --topo-order it seems to hop from branch to\n> branch more.\n\nYeah, see \"--date-order\". It's topologically sorted, but within that \ntopological sort it is in the \"date order\", which approximates the normal \nnon-sorted output.\n\nWithout sorting, you also won't see any sorting by branch, although it \ncould be done by the consumer of the rev-list data (ie you could do it in \ngitk, similarly to how you'd effectively do a topological sort of your \nown).\n\nSo it actually boils down to the exact same thing:\n\n - git-rev-list doing whatever sorting is \"convenient\", in that it's the \n one common interface to git revisions, so once you do it there, you do \n it for everybody.\n\n - however, for much the same reason, git-rev-list by definition doesn't \n know _who_ it is sorting things for, or how it's going to be visualized \n (exactly because it's the \"one convenient central place\", of course), \n and as a result it needs to not only get the right answer, it needs to \n get it on the first try and can't go back incrementally to fix up the \n list of commits.\n\nSo the convenience of doing any kind of sorting in git-rev-list is by \ndefinition also the thing that causes it to have bad latency, in that it \nneeds to parse the _whole_ history.\n\nIn contrast, doing some of the same sorting that git-rev-list already does \nin the consumer instead, is obviously duplicating the same basic notions, \nbut once you do it in the consumer, you can suddenly do things that simply \nweren't possible in git-rev-list - do things incrementally, and then if \nyou notice half-way that you did something wrong, you can go back and fix \nit up (which can be quite acceptable). That just isn't an option in a \nlinear environment like the git-rev-list output.\n\n\t\t\tLinus\n"},{"id":"26621","messageId":"edtuj5$p76$1@sea.gmane.org","threadId":"5513","inReplyTo":"20060909031307.GE23891@pasky.or.cz","subject":"Re: Change set based shallow clone","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-09-09T08:39:37Z","receivedAt":"2006-09-09T08:39:37Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Petr Baudis wrote:\n\n> Dear diary, on Fri, Sep 08, 2006 at 05:50:40PM CEST, I got a letter\n> where Jakub Narebski said that...\n>> My idea for lazy clone/fetch (lazy = on-demand) is via remote alternatives\n>> mechanism. We put URI for repository (repositories) that hosts the project,\n>> and we would need at start to download at least heads and tags, and only\n>> heads and tags.\n> \n> One thing to note is that you won't last very long without getting\n> at least basically all the commits from the history. git log, git\n> merge-base and such would either just suck them all, get partially moved\n> to the server side, or would undergo quite a painful and slooooooooow\n> process \"get me commit X... thank you, sir. hmm, it appears that its\n> parent is commit Y. could you get me commit Y, please...? thank you,\n> sir. hmm, it appears...\".\n\nAs I said there is load of troubles with lazy clone/fetch = remote \nalternatives I didn't thought about.\n\ngit log/git rev-list and git fsck-objects among them.\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"26623","messageId":"e5bfff550609090147q37d61f37j9c3e8ae6d3a0cf35@mail.gmail.com","threadId":"5513","inReplyTo":"Pine.LNX.4.64.0609082054560.27779@g5.osdl.org","subject":"Re: Change set based shallow clone","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2006-09-09T08:47:49Z","receivedAt":"2006-09-09T08:47:49Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 9/9/06, Linus Torvalds wrote:\n>\n>\n>\n> In contrast, doing some of the same sorting that git-rev-list already does\n> in the consumer instead, is obviously duplicating the same basic notions,\n> but once you do it in the consumer, you can suddenly do things that simply\n> weren't possible in git-rev-list - do things incrementally, and then if\n> you notice half-way that you did something wrong, you can go back and fix\n> it up (which can be quite acceptable). That just isn't an option in a\n> linear environment like the git-rev-list output.\n>\n\nPerhaps is total idiocy but why do not implement the fix-up logic\ndirectly in git-rev-list?\n\nIf the out of order revisions are a small amount of the total then\ncould be possible to have something like\n\ngit rev-list --topo-order --with-appended-fixups HEAD\n\nWhere, while git-rev-list is working _whithout sorting the whole tree\nfirst_, when finds an out of order revision stores it in a fixup-list\nbuffer and *at the end* of normal git-rev-lsit the buffer is flushed\nto receiver, so that the drawing logic does not change and the out of\norder revisions arrive at the end, already packed, sorted and prepared\nby git-rev-list.\n\nInstead of changing drwing logic is then enough to add a fixup\nroutine that cycles through out of order commits and updates the\ngraph.\n\nThis also avoids recursive reordering where perhaps the same part of\na graph should be redrawn more then one time due to differtent new\nparents to the same child arrives at different times.\n\nMarco\n"},{"id":"26642","messageId":"Pine.LNX.4.64.0609091022360.27779@g5.osdl.org","threadId":"5513","inReplyTo":"e5bfff550609090147q37d61f37j9c3e8ae6d3a0cf35@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-09T17:33:03Z","receivedAt":"2006-09-09T17:33:03Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 9 Sep 2006, Marco Costalba wrote:\n> \n> Perhaps is total idiocy but why do not implement the fix-up logic\n> directly in git-rev-list?\n\nIt's possible in theory, but in practice it's not worth it.\n\nWhy?\n\nBecause you really want the _asynchronous_ nature of having a separate \nuser, that only shows _partial_ results.\n\nIn other words, we could reasonably easily make git-rev-list do something \nlike\n\n - output all revisions in the normal non-topological ordering\n\n - when git-rev-list notices a topological sort error, it outputs a \n \"FIXME\" line, and restarts the whole thing - printing out the commits \n in the newly fixed ordering - and does it right the next time around\n\n - it then continues doing this until it's totally exhausted the whole \n commit list and has done one final output in the proper topological \n ordering.\n\nPossible? Yes.\n\nBUT:\n\n - as long as git-rev-list is entirely single-threaded (and trust me, it's \n going to be that, because otherwise we'd be better off doing it in a \n separate process - like gitk), this means that it will be _entirely_ \n unaware of what has actually been _shown_, so it will restart a LOT \n more than the external interactive process would do. So it would be \n much worse than doing it externally and knowing what you've actually \n shown to the user (if you haven't shown the bad thing yet, there's no \n reason to restart).\n\n - Again, as long as it's single-threaded, git-rev-list will block once it\n has filled up the pipeline between the processes, so instead of parsing \n everything in parallel with the \"show it all\", if will synchronize with \n the showing process all the time, and especially so when it needs to \n re-show the stuff that it already sent once. So it's also fairly \n inefficient.\n\nHowever, what you seem to imply is something different:\n\n> Where, while git-rev-list is working _whithout sorting the whole tree\n> first_, when finds an out of order revision stores it in a fixup-list\n> buffer and *at the end* of normal git-rev-lsit the buffer is flushed\n> to receiver, so that the drawing logic does not change and the out of\n> order revisions arrive at the end, already packed, sorted and prepared\n> by git-rev-list.\n\nBut this is exactly what we already do. We flush things *at the end* \nbecause that's when we actually know the ordering. And that's exactly why \n\"git-rev-list --topo-ordering\" has a latency ranging from a few seconds to \na few minutes for large projects (depending on whether they are packed or \nnot).\n\nThe \"wait for the end\" is _not_ good, exactly because the end will take \nsome time to arrive. The whole point is to start outputting the data \nearly, and thet BY DEFINITION means that the order of revisions isn't \nguaranteed to be in topological order.\n\n\t\tLinus\n"},{"id":"26643","messageId":"e5bfff550609091104s3709b82fld3057a07a84ae857@mail.gmail.com","threadId":"5513","inReplyTo":"Pine.LNX.4.64.0609091022360.27779@g5.osdl.org","subject":"Re: Change set based shallow clone","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2006-09-09T18:04:29Z","receivedAt":"2006-09-09T18:04:29Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 9/9/06, Linus Torvalds wrote:\n>\n>\n> - output all revisions in the normal non-topological ordering\n>\n> - when git-rev-list notices a topological sort error, it outputs a\n> \"FIXME\" line, and restarts the whole thing - printing out the commits\n> in the newly fixed ordering - and does it right the next time around\n>\n\nSorry, but I don't understand why you should restart the whole thing\ninstead of store away the FIXME commit and continue.\n\nIf you read my previous e-mail in this thread perhaps it is better\nexplained the whole idea.\n\nAnyhow the basic is:\n\n-git-rev-list starts outputting the data early (order is not guaranteed)\n\n-before to mark for output a revision check if it breaks --topo-order\n\n-if the above is true store the revision away and *do not send*\n\n- at the end you get an early started steram of topological corrects\nrevisions without\npreordering, just because you filter away the (few?) revisions that\nare not in order.\nThe list you get is guaranteed to be in topo order although my not be complete.\n\n- _then_ you send the missing revisions that where previously\nfiltered out. At this stage the receiver has already drwan the graph,\nindeed it has start drwaing as soon as the first revisons arrived and\n*very important* receiver used old and fast topo-order parsing code.\n\n- finally the fixup routine at receiver's end updates the graph with\nthe info from the small set of out of order revisions filtered out\nbefore and sent at the end (only this small set is sent at the end).\n\nSorry if it is not still clear, in the previous my e-mail in this\nthread there is also a small example that could be useful.\n\n Marco\n"},{"id":"26644","messageId":"20060909184441.23764.qmail@science.horizon.com","threadId":"5513","inReplyTo":"e5bfff550609091104s3709b82fld3057a07a84ae857@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-09-09T18:44:41Z","receivedAt":"2006-09-09T18:44:41Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> Anyhow the basic is:\n> \n> -git-rev-list starts outputting the data early (order is not guaranteed)\n> \n> -before to mark for output a revision check if it breaks --topo-order\n> \n> -if the above is true store the revision away and *do not send*\n> \n> - at the end you get an early started steram of topological corrects\n> revisions without\n> preordering, just because you filter away the (few?) revisions that\n> are not in order.\n> The list you get is guaranteed to be in topo order although my not be complete.\n> \n> - _then_ you send the missing revisions that where previously\n> filtered out. At this stage the receiver has already drwan the graph,\n> indeed it has start drwaing as soon as the first revisons arrived and\n> *very important* receiver used old and fast topo-order parsing code.\n> \n> - finally the fixup routine at receiver's end updates the graph with\n> the info from the small set of out of order revisions filtered out\n> before and sent at the end (only this small set is sent at the end).\n\nThe problem is that the gitk display code doesn't *like* input like this;\nit's only designed to append to a list. Handling insertions would be\nhard work for a rare corner case, and a perpetual source of bugs.\n\nUnless gitk does a complete second pass, or course, which would\nguarantee an annoying flicker a few seconds after startup.\nAnd Twice the work.\n\nThe original alternative was to note that out-of-order commits\nusually aren't *very* out of order. So if gitk could checkpoint\nthe state of its display algorithm periodically, it could just, when\nseeing an out-of-order commit, rewind to the last checkpoint\nbefore the problem and replay while merging in the corrections.\n\nWhile that is potentially O(n^2) (if you feed it all the commits\nin reverse order), in practice it\n- Is less than 2*n work, and\n- Always maintains the longest possible correct prefix of\n recent commits. It's the old stuff that takes a while to\n fill in.\n\nEither way, gitk has to have topo-sorting code added to it. I think\nLinus' idea was to avoid that.\n"},{"id":"26645","messageId":"e5bfff550609091217r7fc17438pc969b2b2ae080584@mail.gmail.com","threadId":"5513","inReplyTo":"20060909184441.23764.qmail@science.horizon.com","subject":"Re: Change set based shallow clone","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2006-09-09T19:17:10Z","receivedAt":"2006-09-09T19:17:10Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 9 Sep 2006 14:44:41 -0400, linux@horizon.com wrote:\n> > Anyhow the basic is:\n> >\n> > -git-rev-list starts outputting the data early (order is not guaranteed)\n> >\n> > -before to mark for output a revision check if it breaks --topo-order\n> >\n> > -if the above is true store the revision away and *do not send*\n> >\n> > - at the end you get an early started steram of topological corrects\n> > revisions without\n> > preordering, just because you filter away the (few?) revisions that\n> > are not in order.\n> > The list you get is guaranteed to be in topo order although my not be complete.\n> >\n> > - _then_ you send the missing revisions that where previously\n> > filtered out. At this stage the receiver has already drwan the graph,\n> > indeed it has start drwaing as soon as the first revisons arrived and\n> > *very important* receiver used old and fast topo-order parsing code.\n> >\n> > - finally the fixup routine at receiver's end updates the graph with\n> > the info from the small set of out of order revisions filtered out\n> > before and sent at the end (only this small set is sent at the end).\n>\n> The problem is that the gitk display code doesn't *like* input like this;\n> it's only designed to append to a list. Handling insertions would be\n> hard work for a rare corner case, and a perpetual source of bugs.\n>\n> Unless gitk does a complete second pass, or course, which would\n> guarantee an annoying flicker a few seconds after startup.\n> And Twice the work.\n>\n\nI think I need to add another argument here, I didn't mention before\nfor clarity (indeed I'm not very good at this it seems ;-) )\n\nI don't know for gitk, perhaps Paul can better explain, but the usual\noptimization of a git visualizer is simply to not draw any graph\nuntil that part does became visibile on the screen.\n\nSo your arguments are true but the fact is that there is no graph\ninsertion handling at all in almost all cases, but only insertion in\nloaded revs list ; when the user scrolls to the inserted commit only\n_then_ the graph will be calculated and dispalyed (I'm not sure in\ngitk, but in qgit it works that way). So there's no flickering too,\nand not double work.\n\nIndeed lazy/on demand graph drawing policy is very well supported by\nthe above schema, and the above schema is good also because of the\nlazy graph drawing.\n\n Marco\n"},{"id":"26647","messageId":"Pine.LNX.4.64.0609091256110.27779@g5.osdl.org","threadId":"5513","inReplyTo":"e5bfff550609091104s3709b82fld3057a07a84ae857@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-09T20:05:42Z","receivedAt":"2006-09-09T20:05:42Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 9 Sep 2006, Marco Costalba wrote:\n> \n> Sorry, but I don't understand why you should restart the whole thing\n> instead of store away the FIXME commit and continue.\n> \n> If you read my previous e-mail in this thread perhaps it is better\n> explained the whole idea.\n> \n> Anyhow the basic is:\n> \n> -git-rev-list starts outputting the data early (order is not guaranteed)\n> \n> -before to mark for output a revision check if it breaks --topo-order\n> \n> -if the above is true store the revision away and *do not send*\n\nYou don't seem to understand.\n\nIt's not that individual new commits might be \"out of order\", and you can \nsuppress them.\n\nIt's that individual commits end up showing that OTHER COMMITS, THAT YOU \nHAVE ALREADY SEEN AND SHOWN, can now be shown to be \"out of order\".\n\nSo you're _not_ just suppressing and delaying the few commits that didn't \nconform to the topological sorting. What you're asking for is impossible. \nYou can't just delay those to the end, because they implicitly are telling \nyou that the earlier commits were already shown in the wrong order.\n\nThe example is\n\n\t\t A\t\t<--- tip of branch\n\t\t / \\\n\t\t B E\n | |\n\t\t | F\n\t\t | /\n\t\t C \n\t\t |\n\t\t D\n\t\t...\n\nwhere the lettering is in \"date order\" (ie \"A\" is more recent than \"B\" \netc). In this situation, we'd start following the branch A->B->C->D->.. \nbefore we even start looking at E and F, because they all _look_ more \nrecent.\n\nBut then, at some point, we see E and F, and suddenly when looking at F we \nrealize that C was printed out much much earlier, and was already shown as \nhaving only one child. We can't just say \"delay F to the end\", because \nwe'd then have to draw the line _backwards_ to C, which we haven't even \nleft room for in the graph, not to mention that the end result would look \nabsolutely disgusting even if we had.\n\nSo we started out painting this as\n\n\t\t A\n\t\t / \\\n\t\tB |\n\t\t| |\n\t\tC |\n\t\t| |\n\t\tD |\n\t\t| |\n\t\t| E\n\t\t| |\n\t\t| F\n\t\t| |\n\nbefore we notice how wrong it was, and now we have to go _back_, and \nrepaint both E and F as being above C, because only once we hit F do we \nsuddenly realize that yeah, it really _was_ younger than C, despite the \ntimestamp (which was off, because somebody had set his clock to be a week \nin the past by mistake).\n\nSo we can't just delay F and \"fix it up\" at the end.\n\n\t\tLinus\n"},{"id":"26648","messageId":"20060909204307.GB16906@coredump.intra.peff.net","threadId":"5513","inReplyTo":"Pine.LNX.4.64.0609091256110.27779@g5.osdl.org","subject":"Re: Change set based shallow clone","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-09-09T20:43:07Z","receivedAt":"2006-09-09T20:43:07Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Sep 09, 2006 at 01:05:42PM -0700, Linus Torvalds wrote:\n\n> The example is\n> \n> \t\t A\t\t<--- tip of branch\n> \t\t / \\\n> \t\t B E\n> | |\n> \t\t | F\n> \t\t | /\n> \t\t C \n> \t\t |\n> \t\t D\n> \t\t...\n> \n> where the lettering is in \"date order\" (ie \"A\" is more recent than \"B\" \n> etc). In this situation, we'd start following the branch A->B->C->D->.. \n> before we even start looking at E and F, because they all _look_ more \n> recent.\n\nI'm just coming into this discussion in the middle and know very little\nabout the rev-list code, so please humor me and tell me why my\nsuggestion is completely irrelevant.\n\nThe problem you describe seems to come from doing a depth-first display\nof each branch. Why not look at the tip of each \"active\" branch\nsimultaneously and pick the one with the most recent date? Something\nlike:\n void show_all(commit_array start)\n {\n commit_array active;\n\n copy_array(active, start);\n sort_array(active);\n while (active.size > 0) {\n show_commit(active.data[0]);\n push_back(active.data[0].parents);\n pop_front(active);\n sort_array(active);\n }\n }\nObviously you could use a specialized data structure to add nodes into\nthe right place instead of resorting constantly.\n\n-Peff\n"},{"id":"26650","messageId":"7v4pvgwxrc.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"20060909204307.GB16906@coredump.intra.peff.net","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-09T21:11:51Z","receivedAt":"2006-09-09T21:11:51Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I'm just coming into this discussion in the middle and know very little\n> about the rev-list code, so please humor me and tell me why my\n> suggestion is completely irrelevant.\n\nNot irrelevant.\n\n> The problem you describe seems to come from doing a depth-first display\n> of each branch. Why not look at the tip of each \"active\" branch\n> simultaneously and pick the one with the most recent date? Something\n> like:\n\nThat's what we have been doing from day one.\n\nThe trouble Linus illustrated is that in a global project you\ncannot rely on timestamps always being correct. You can use\nthem as HINT, but you need to be prepared to do sensible things\nwhen some people screw up the time.\n\n> On Sat, Sep 09, 2006 at 01:05:42PM -0700, Linus Torvalds wrote:\n>\n>> The example is\n>> \n>> \t\t A\t\t<--- tip of branch\n>> \t\t / \\\n>> \t\t B E\n>> | |\n>> \t\t | F\n>> \t\t | /\n>> \t\t C \n>> \t\t |\n>> \t\t D\n>> \t\t...\n>> \n>> where the lettering is in \"date order\" (ie \"A\" is more recent than \"B\" \n>> etc). In this situation, we'd start following the branch A->B->C->D->.. \n>> before we even start looking at E and F, because they all _look_ more \n>> recent.\n\nThe ancestry graph, topologically, flows from bottom to top but\nthe timestamps are in F E D C B A order (A is closer to current,\nF is in the most distant past). Somebody forked from C on a\nmachine with slow clock, made two commits with wrong (from the\npoint of view of the person who made commit C anyway) timestamps,\nand that side branch ended up merged with B into A.\n\nYou start following A, read A and find B and E (now B and E are\n\"active\" in your lingo), pop B because it is the most recent.\nWe look at B, find C is the parent, push C into the active list\n(which is always sorted by timestamp order). Now \"active\" are C\nand E, and C is most recent so we pop C.\n\nIn the past people suggested workarounds such as making commit-tree \nto ensure that a child commit has timestamp no older than any of\nits parents by either refusing to make such or automatically\nadjusting. That would surely work around the problem, but if\nsomebody made a commit with a wrong timestamp far into the\nfuture, every commit that is made after that will have\n\"adjusted\" timestamp that pretty much is meaningless, so that\nwould not work well in practice.\n\nIf we had a commit generation number field in the commit object,\nwe could have used something like that. Each commit gets\ngeneration number that is maximum of its parents' generation\nnumber plus one, and we prime the recursive definition by giving\nroot commits generation number of 0, and rev-list would have\nused the generation number not timestamp to do the above\n\"date-order\" sort and we will always get topology right. Of\ncourse fsck-objects needs to be taught to check and complain if\nthe generation numbers between parent and child are inverted.\n\nBut it's too late in the game now -- maybe in git version 47.\n"},{"id":"26651","messageId":"20060909211420.GA17339@coredump.intra.peff.net","threadId":"5513","inReplyTo":"7v4pvgwxrc.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-09-09T21:14:20Z","receivedAt":"2006-09-09T21:14:20Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Sep 09, 2006 at 02:11:51PM -0700, Junio C Hamano wrote:\n\n> The trouble Linus illustrated is that in a global project you\n> cannot rely on timestamps always being correct. You can use\n> them as HINT, but you need to be prepared to do sensible things\n> when some people screw up the time.\n\nRight, I forgot about the unreliability of the timestamps. Thanks for\nthe explanation!\n\n-Peff\n"},{"id":"26652","messageId":"Pine.LNX.4.64.0609091433460.27779@g5.osdl.org","threadId":"5513","inReplyTo":"20060909204307.GB16906@coredump.intra.peff.net","subject":"Re: Change set based shallow clone","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-09T21:40:30Z","receivedAt":"2006-09-09T21:40:30Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 9 Sep 2006, Jeff King wrote:\n> \n> The problem you describe seems to come from doing a depth-first display\n> of each branch\n\nNo, not at all.\n\nWe _don't_ do depth-first, or breadth-first. The thing is, neither would \nreally work, since the \"distance\" between commits is very variable.\n\nInstead, the rule is always to try to traverse the tree in date order. \nThat's most likely the closest order to what you want - it ends up being \nbreadth-first if there is a lot of concurrent work, and if there is one \nold branch and one new branch, we'll look at the new one first, and \napproximate depth-first there.\n\n> Why not look at the tip of each \"active\" branch\n> simultaneously and pick the one with the most recent date?\n\nWhich is _exactly_ what we do.\n\nHowever, it's just a heuristic. \"Most recent date\" is not well-defined in \na distributed environment that doesn't have a global clock. If somebody \ndoes commits on a machine that has the clock just set wrong, \"most recent\" \nmay well not be _really_ recent.\n\nSo all the algorithms are actually very careful to just use the date as a \nheuristic. They have real guarantees, but they aren't about the ordering. \nThe ordering is just used as a way to have _some_ non-random and likely \ngood order to traverse the DAG in. Doing it depth-first would suck (you'd \nalways reach the root before you reach a lot of much more interesting \ncommits), and breadth-first is not well-defined either, since one \"level\" \ncan be a year old for one parent, and a day old for another.\n\nSo you could kind of think of the ordering as \"breadth-first, modified by \ndate\" kind of thing.\n\n\t\tLinus\n"},{"id":"26658","messageId":"9e4733910609091554m2a8a001axd575defff9a0e7a9@mail.gmail.com","threadId":"5513","inReplyTo":"Pine.LNX.4.64.0609091433460.27779@g5.osdl.org","subject":"Re: Change set based shallow clone","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-09T22:54:34Z","receivedAt":"2006-09-09T22:54:34Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/9/06, Linus Torvalds wrote:\n> However, it's just a heuristic. \"Most recent date\" is not well-defined in\n> a distributed environment that doesn't have a global clock. If somebody\n> does commits on a machine that has the clock just set wrong, \"most recent\"\n> may well not be _really_ recent.\n\nWhen a merge happens could git fix things up in the database by adding\na corrected, hidden time stamp that would keep things from having an\nout of order time sequence? That way you wouldn't need to rediscover\nthe out of order commit each time the tree is generated.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26660","messageId":"Pine.LNX.4.64.0609091708340.27779@g5.osdl.org","threadId":"5513","inReplyTo":"9e4733910609091554m2a8a001axd575defff9a0e7a9@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-10T00:18:10Z","receivedAt":"2006-09-10T00:18:10Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 9 Sep 2006, Jon Smirl wrote:\n> \n> When a merge happens could git fix things up in the database by adding\n> a corrected, hidden time stamp that would keep things from having an\n> out of order time sequence? That way you wouldn't need to rediscover\n> the out of order commit each time the tree is generated.\n\nI don't think any such algorithm exists, and it's too late now ;)\n\nI was thinking of some \"sequence number\" algorithm, but the thing is, it's \nnot _merges_ that are the problem per se, it's the \"branch points\". And \nyou don't actually know that a commit is a branch point in advance: it's \na branch point not because you branched, but because somebody else \nhappened to use the same parent as the basis of their independent work.\n\nSo we could make the rule be something like \"when we commit, the new \ncommit must have a datestamp that is equal to or in the future from the \nparent commits\". However, that results in some really strange problems in \na distributed environment, where _if_ somebody has their clock set wrong, \nyou'll end up either unable to merge with them, or you have to generate a \ntotally bogus time yourself (which then moves up the chain).\n\nIt might be simpler to then not think of the thing as a \"date\" at all, but \nas a pure sequence number. Then the rule would be: a new commit has to \nhave a sequence number that is \"max(of-the-parent-sequence-numbers) + 1\".\nThat _may_ or may not actually help.\n\nIt was discussed (a bit) early on - summer-05 - but I wasn't convinced \nenough that it would help that I was willing to change the format and add \nthat sequence number. I still am not. I'm not even sure it would really \nwork.\n\nIn other words, it's probably just not worth it. It's better to just say \n\"dates don't really _matter_, and all that matters is the parenthood \ninformation\". Which is really what git does - the dates aren't _important_ \nfor any real operation, they are literally just a heuristic.\n\nBut hey, maybe somebody can come up with some operation that becomes \n_much_ cheaper with the above kind of sequence number. It shouldn't be \nhard to test..\n\n\t\tLinus\n"},{"id":"26662","messageId":"7vvenwv7lr.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"Pine.LNX.4.64.0609091708340.27779@g5.osdl.org","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-10T01:22:08Z","receivedAt":"2006-09-10T01:22:08Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> But hey, maybe somebody can come up with some operation that becomes \n> _much_ cheaper with the above kind of sequence number. It shouldn't be \n> hard to test..\n\nSometimes I get a feeling that we are saying the same thing in\nthe same thread but in parallel without reading what the other\nis saying. This is such a thread ;-).\n"},{"id":"26663","messageId":"e5bfff550609092049t5e016cacr2502ce81bbb6489e@mail.gmail.com","threadId":"5513","inReplyTo":"Pine.LNX.4.64.0609091256110.27779@g5.osdl.org","subject":"Re: Change set based shallow clone","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2006-09-10T03:49:47Z","receivedAt":"2006-09-10T03:49:47Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 9/9/06, Linus Torvalds wrote:\n>\n>\n>\n> The example is\n>\n> A <--- tip of branch\n> / \\\n> B E\n> | |\n> | F\n> | /\n> C\n> |\n> D\n> ...\n>\n\nOk now it' clear, thanks. But anyhow I think that it should be\npossible to avoid the check and reordering on the receiver side.\n\nSuppose for a moment to split the graph drawing from the sequence\nreordering problem, suppose for a moment that receiver does do not\ndraw the graph immediately.\n\nAs you described, in our case git-rev-list sends the following sequence:\nA, B, C, D, E, F\n\ninstead git-rev-list --topo-order would have sent something like\nA, E, F, B, C, D\n\nNow I ask, is it possible to have a sequence (without latency) like\nA, B, C, D, (-3)E, (-3)F\n\nwhere, in case of not topological correct revisions, git-rev-list\ngives the hint on the correct position in sequence (3 revs before in\nour case) where the revision would have been if the sequence would\nhave been --topo-order ?\n\nThis saves all the checking and reordering on the receiver side and\nguarantees consistent results on different implementations of git\nvisualizers because the --topo-order algorithm logic is computed in\ngit rev-list only.\n\nThe visualizers could be sequence order agnostic, i.e. receivers can\nhandle --topo-order or --date-order sequences or any other kind of\nsequence with the same code, simply they recreate the sequence in the\nway git-rev-list tells them.\n\nMarco\n"},{"id":"26664","messageId":"7vpse4uzos.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"e5bfff550609092049t5e016cacr2502ce81bbb6489e@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-10T04:13:07Z","receivedAt":"2006-09-10T04:13:07Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Marco Costalba\" writes:\n\n> On 9/9/06, Linus Torvalds wrote:\n>>\n>> The example is\n>>\n>> A <--- tip of branch\n>> / \\\n>> B E\n>> | |\n>> | F\n>> | /\n>> C\n>> |\n>> D\n>> ...\n>>\n>\n> Ok now it' clear, thanks. But anyhow I think that it should be\n> possible to avoid the check and reordering on the receiver side.\n>\n> Suppose for a moment to split the graph drawing from the sequence\n> reordering problem, suppose for a moment that receiver does do not\n> draw the graph immediately.\n>\n> As you described, in our case git-rev-list sends the following sequence:\n> A, B, C, D, E, F\n>\n> instead git-rev-list --topo-order would have sent something like\n> A, E, F, B, C, D\n>\n> Now I ask, is it possible to have a sequence (without latency) like\n> A, B, C, D, (-3)E, (-3)F\n>\n> where, in case of not topological correct revisions, git-rev-list\n> gives the hint on the correct position in sequence (3 revs before in\n> our case) where the revision would have been if the sequence would\n> have been --topo-order ?\n\nWhen rev-list is writing E out, it does not know it is a\ndescendant of something it already emitted (i.e. C) because it\nhasn't looked at F nor checked its parent yet. So asking for\n(-3)F may be fine but I think (-3)E is just a fantasy.\n"},{"id":"26665","messageId":"e5bfff550609092123t1d8b6c70s5750fbb787534812@mail.gmail.com","threadId":"5513","inReplyTo":"7vpse4uzos.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2006-09-10T04:23:11Z","receivedAt":"2006-09-10T04:23:11Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 9/10/06, Junio C Hamano wrote:\n> \"Marco Costalba\" writes:\n>\n> > On 9/9/06, Linus Torvalds wrote:\n> >>\n> >> The example is\n> >>\n> >> A <--- tip of branch\n> >> / \\\n> >> B E\n> >> | |\n> >> | F\n> >> | /\n> >> C\n> >> |\n> >> D\n> >> ...\n> >>\n> >\n> > Ok now it' clear, thanks. But anyhow I think that it should be\n> > possible to avoid the check and reordering on the receiver side.\n> >\n> > Suppose for a moment to split the graph drawing from the sequence\n> > reordering problem, suppose for a moment that receiver does do not\n> > draw the graph immediately.\n> >\n> > As you described, in our case git-rev-list sends the following sequence:\n> > A, B, C, D, E, F\n> >\n> > instead git-rev-list --topo-order would have sent something like\n> > A, E, F, B, C, D\n> >\n> > Now I ask, is it possible to have a sequence (without latency) like\n> > A, B, C, D, (-3)E, (-3)F\n> >\n> > where, in case of not topological correct revisions, git-rev-list\n> > gives the hint on the correct position in sequence (3 revs before in\n> > our case) where the revision would have been if the sequence would\n> > have been --topo-order ?\n>\n> When rev-list is writing E out, it does not know it is a\n> descendant of something it already emitted (i.e. C) because it\n> hasn't looked at F nor checked its parent yet. So asking for\n> (-3)F may be fine but I think (-3)E is just a fantasy.\n>\nOk. What about something like this?\nA, B, C, D, E, (-3, 1)F\n\nwhere -3 is the correct position in sequence and 1 is the number of\nrevisions before F to whom apply the -3 rule.\n\n\n>\n"},{"id":"26666","messageId":"e5bfff550609092146x624353daqc6e649c0d32d315f@mail.gmail.com","threadId":"5513","inReplyTo":"e5bfff550609092123t1d8b6c70s5750fbb787534812@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2006-09-10T04:46:44Z","receivedAt":"2006-09-10T04:46:44Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 9/10/06, Marco Costalba wrote:\n> On 9/10/06, Junio C Hamano wrote:\n> > \"Marco Costalba\" writes:\n> >\n> > > On 9/9/06, Linus Torvalds wrote:\n> > >>\n> > >> The example is\n> > >>\n> > >> A <--- tip of branch\n> > >> / \\\n> > >> B E\n> > >> | |\n> > >> | F\n> > >> | /\n> > >> C\n> > >> |\n> > >> D\n> > >> ...\n> > >>\n> > >\n> > > Ok now it' clear, thanks. But anyhow I think that it should be\n> > > possible to avoid the check and reordering on the receiver side.\n> > >\n> > > Suppose for a moment to split the graph drawing from the sequence\n> > > reordering problem, suppose for a moment that receiver does do not\n> > > draw the graph immediately.\n> > >\n> > > As you described, in our case git-rev-list sends the following sequence:\n> > > A, B, C, D, E, F\n> > >\n> > > instead git-rev-list --topo-order would have sent something like\n> > > A, E, F, B, C, D\n> > >\n> > > Now I ask, is it possible to have a sequence (without latency) like\n> > > A, B, C, D, (-3)E, (-3)F\n> > >\n> > > where, in case of not topological correct revisions, git-rev-list\n> > > gives the hint on the correct position in sequence (3 revs before in\n> > > our case) where the revision would have been if the sequence would\n> > > have been --topo-order ?\n> >\n> > When rev-list is writing E out, it does not know it is a\n> > descendant of something it already emitted (i.e. C) because it\n> > hasn't looked at F nor checked its parent yet. So asking for\n> > (-3)F may be fine but I think (-3)E is just a fantasy.\n> >\n> Ok. What about something like this?\n> A, B, C, D, E, (-3, 1)F\n>\n> where -3 is the correct position in sequence and 1 is the number of\n> revisions before F to whom apply the -3 rule.\n>\n\nSuppose git-rev-list gives:\n\nA, B, H, C, D, E, F, G, I, L, M, N\n\nSuppose git-rev-list --topo-order would have sent\n\nA, B, C, D, E, F, G, H, I, L, M, N\n\nPerhaps a more general fixup syntax could be:\n\nA,B, H, C, D, E, F, G, I(6, C, D, E, F, G, H), L, M, N\n\nWhere 6 is the number of previous revisions to rearrange with the\ncorresponding correct sequence(C, D, E, F, G, H).\n\nNote that the same subset could be rearranged multiple times if it\nhelps git-rev-list parsing, as example it should be possible to have\nsomething like:\n\nA,B, H, C, D, E, F, G, I(6, C, D, E, F, G, H), L, M(3, L, G, H), N\n\n\nMarco\n"},{"id":"26667","messageId":"7virjwuxrz.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"e5bfff550609092123t1d8b6c70s5750fbb787534812@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-10T04:54:24Z","receivedAt":"2006-09-10T04:54:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Marco Costalba\" writes:\n\n> >>\n> >> A <--- tip of branch\n> >> / \\\n> >> B E\n> >> | |\n> >> | F\n> >> | /\n> >> C\n> >> |\n> >> D\n> >> ...\n> >>\n>\n> Ok. What about something like this?\n> A, B, C, D, E, (-3, 1)F\n>\n> where -3 is the correct position in sequence and 1 is the number of\n> revisions before F to whom apply the -3 rule.\n\nThat means F knows who its descendants are, and commit objects\ndo not have that information, so while traversing you need to\nkeep track of all the descendants yourself, doesn't it?\n\nAnd how does that fix-up information help the user of the stream\nanyway? If I understand your model correctly, the model does\nnot synchronously draw nodes as they are received, so it keeps\ntrack of what it has seen so far. When it sees F it can notice\nthat its parent, C, is something it has seen, so it can tell F\nis wrong. It also knows that it has seen E and E's parent is F\n(which turned out to be at a wrong spot), so it can suspect E is\nalso in the wrong spot (now, it is fuzzy to me how that chain\nof suspicion ends at E and does not propagate up to A, but let's\nthink about that later).\n\nThere is one thing that the user knows a lot better than the\ngeneric rev-list output part. It is the size of the output\nwindow (how tall the window is). I wonder if there is a way to\nexploit it, either in the user, or telling the size of the\nwindow (and perhaps where the display region at the top begins\nat) to rev-list...\n\nIf we are dealing in a 3-item-tall window, we will traverse A B\nC D, notice they form a single strand of pearls, and can make a\nmental note that we do not have to worry about ancestors of D\nfor now, because D's ancestors will be drawn below C, which is\nalready the putative bottom edge of the window (when oddballs\nlike E and F comes later, they can only push things down at the\nbottom edge of the window). Then rev-list can postpone\ntraversing D and go on to traverse other nodes that are in the\n\"active\" list (in this case, E).\n\nI am starting to suspect that introducing \"generation\" header to\nthe commit objects might actually be a very good thing. For\none thing, rev-list will automatically get the topology always\nright if we did so.\n\nWe obviously need to update 'convert-objects' and tell everybody\nthat they need to rewrite their history if we take this route.\nThat kind of flag-day conversion used to be an Ok thing to do,\nbut it is getting harder and harder these days for obvious\nreasons, though.\n"},{"id":"26668","messageId":"e5bfff550609092214t4f8e195eib28e302f4d284aa@mail.gmail.com","threadId":"5513","inReplyTo":"7virjwuxrz.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2006-09-10T05:14:09Z","receivedAt":"2006-09-10T05:14:09Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 9/10/06, Junio C Hamano wrote:\n> \"Marco Costalba\" writes:\n>\n> > >>\n> > >> A <--- tip of branch\n> > >> / \\\n> > >> B E\n> > >> | |\n> > >> | F\n> > >> | /\n> > >> C\n> > >> |\n> > >> D\n> > >> ...\n> > >>\n> >\n> > Ok. What about something like this?\n> > A, B, C, D, E, (-3, 1)F\n> >\n> > where -3 is the correct position in sequence and 1 is the number of\n> > revisions before F to whom apply the -3 rule.\n>\n> That means F knows who its descendants are, and commit objects\n> do not have that information, so while traversing you need to\n> keep track of all the descendants yourself, doesn't it?\n>\n\nYes! it is, but you do it in git instead of in the visualizer ;-)\nbecause I think in any case someone defenitly needs to keep track of\nit.\n\n> And how does that fix-up information help the user of the stream\n> anyway? If I understand your model correctly, the model does\n> not synchronously draw nodes as they are received,\n\nVisualizers draw only what is on screen so when you start them they\ndraw the first 20/30 lines only. And noramally git output it's faster\nthen user scrolling so when user scrolls down revisions are already\narrived.\n\n> track of what it has seen so far. When it sees F it can notice\n> that its parent, C, is something it has seen, so it can tell F\n> is wrong. It also knows that it has seen E and E's parent is F\n> (which turned out to be at a wrong spot), so it can suspect E is\n> also in the wrong spot (now, it is fuzzy to me how that chain\n> of suspicion ends at E and does not propagate up to A, but let's\n> think about that later).\n>\nIs it possible, in that case flicker will be involved, but it is very\nuncommon, so in the big amount of all other cases we have no\nflickering and early graph drawing.\n\nBecasue the worst that can happen on visualizer side is flickering we\ncan accept a worst rare case to have a big adavantage (no latency and\nno flickering) on the (very) common case: \"user scrolls to a given\npage when the corresponding revisions are already arrived and, in\ncase, fixed up\".\n\n\n Marco\n"},{"id":"26669","messageId":"7vejukuvcy.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"e5bfff550609092214t4f8e195eib28e302f4d284aa@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-10T05:46:37Z","receivedAt":"2006-09-10T05:46:37Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Marco Costalba\" writes:\n\n> On 9/10/06, Junio C Hamano wrote:\n>> \"Marco Costalba\" writes:\n>>\n>> > >>\n>> > >> A <--- tip of branch\n>> > >> / \\\n>> > >> B E\n>> > >> | |\n>> > >> | F\n>> > >> | /\n>> > >> C\n>> > >> |\n>> > >> D\n>> > >> ...\n>> > >>\n>> >\n>> > Ok. What about something like this?\n>> > A, B, C, D, E, (-3, 1)F\n>> >\n>> > where -3 is the correct position in sequence and 1 is the number of\n>> > revisions before F to whom apply the -3 rule.\n>>\n>> That means F knows who its descendants are, and commit objects\n>> do not have that information, so while traversing you need to\n>> keep track of all the descendants yourself, doesn't it?\n>>\n>\n> Yes! it is, but you do it in git instead of in the visualizer ;-)\n> because I think in any case someone defenitly needs to keep track of\n> it.\n\nNot really.\n\nTo git-rev-list, which does not know how the visualizer uses the\ndata, what you are saying essentially means that it needs to\nhold onto the data it parsed forever. That's where my earlier\nsuggestion for visualizers to take advantage of the \"windowing\"\ninformation comes from. Since the chain depicted in the above\nbetween E..F can be arbitrary long (and you would need to keep\ntrack of information for B and C too, well, essentially\neverything), that is unacceptable for rev-list if you do not\ngive it additional clue when it can discard that information.\n"},{"id":"26673","messageId":"ee0n1g$7jj$1@sea.gmane.org","threadId":"5513","inReplyTo":"7virjwuxrz.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-09-10T09:49:13Z","receivedAt":"2006-09-10T09:49:13Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Junio C Hamano wrote:\n\n> I am starting to suspect that introducing \"generation\" header to\n> the commit objects might actually be a very good thing.  For\n> one thing, rev-list will automatically get the topology always\n> right if we did so.\n> \n> We obviously need to update 'convert-objects' and tell everybody\n> that they need to rewrite their history if we take this route.\n> That kind of flag-day conversion used to be an Ok thing to do,\n> but it is getting harder and harder these days for obvious\n> reasons, though.\n\nWouldn't it be possible to have not that more complex code if some\nof the commit objects (newer) would have \"generation\" header, and some\nof them (older) wouldn't have it? Git would use generation header if it is\npresent, and current heuristic timestamp based code if it is not present.\n\nIt would be better of course if the new commits have correct \"generation\"\nheader, so insertion of \"new\" commit after \"old\" commit would have some\nextra overhead...\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"26674","messageId":"200609101228.12956.Josef.Weidendorfer@gmx.de","threadId":"5513","inReplyTo":"7virjwuxrz.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Josef Weidendorfer","fromEmail":"josef.weidendorfer@gmx.de","sentAt":"2006-09-10T10:28:12Z","receivedAt":"2006-09-10T10:28:12Z","isPatch":false,"sender":{"key":"josef.weidendorfer@gmx.de","avatar":null},"body":"On Sunday 10 September 2006 06:54, Junio C Hamano wrote:\n> I am starting to suspect that introducing \"generation\" header to\n> the commit objects might actually be a very good thing. For\n> one thing, rev-list will automatically get the topology always\n> right if we did so.\n\nI do not think that any commits need to be changed, but only\n\"rev-list --topo-order\" to build its own private cache of\nsequence numbers for commits.\n\nAFAICS, a generation number is pure redundant information, as a single\nrun of \"rev-list --topo-order\" can recalculate it. If it can not find\nthe number in its private per-repository cache of sequence numbers,\nit calculates it the hard way (same as currently) and puts the found\nnumbers into the cache afterwards.\n\nThe cache should be similar in size to a pack index of a fully packed repository,\nbut probably could be way smaller, by storing only one sequence number for\na linear sequence of commits with only one parent each.\n\nJosef\n"},{"id":"26679","messageId":"17668.2019.732961.855446@cargo.ozlabs.ibm.com","threadId":"5513","inReplyTo":"9e4733910609081628w2a59551foc28c689d0538a984@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2006-09-10T12:41:07Z","receivedAt":"2006-09-10T12:41:07Z","isPatch":false,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Jon Smirl writes:\n\n> gitk takes about a minute to come up on the Mozilla repo when\n> everything is in cache. It takes about twice as long when things are\n> cold. It's enough of delay that I don't use the tool.\n\nI've been doing some timing measurements with Jon's repo. The results\nare interesting.\n\nIt turns out that a lot of the initial delay is in reading all the\nreferences. With ~1600 heads and almost as many tags, readrefs was\ntaking about 30 seconds (on my 2.5GHz quad G5), largely because it was\ndoing two execs for each tag, a git rev-parse and a git cat-file,\nwhich was a bit stupid. With that fixed, it's about 5 or 6 seconds\nfrom starting gitk to seeing a window with commits listed in it in the\nhot cache case, even still using --topo-order. Without --topo-order\nit's about 2-3 seconds to seeing the window with commits listed, but\nthe overall process takes longer (I still need to figure out why).\n\nIn the cold cache case, it takes about 32 seconds to read all the\nreferences, even with the fixed version of readrefs, since that's\nabout how long git ls-remote .git takes. Also, if you do gitk --all\n(as I often do), then gitk does a git rev-parse, which takes about 20\nseconds (but then readrefs only takes 10 seconds since the heads are\nin cache).\n\nThe bottom line is that I can speed up the startup for the hot-cache\ncase quite a lot. The cold-cache case is going to take about 20-30\nseconds whatever I do unless Linus or Junio can come up with a way to\npack the heads and tags. I could read the refs asynchronously but\nthere will still be a long delay in git rev-parse if you give\narguments such as --all.\n\nPaul.\n"},{"id":"26680","messageId":"9e4733910609100756r1ece1e22m38054536a2909dd4@mail.gmail.com","threadId":"5513","inReplyTo":"17668.2019.732961.855446@cargo.ozlabs.ibm.com","subject":"Re: Change set based shallow clone","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-10T14:56:25Z","receivedAt":"2006-09-10T14:56:25Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/10/06, Paul Mackerras wrote:\n> Jon Smirl writes:\n>\n> > gitk takes about a minute to come up on the Mozilla repo when\n> > everything is in cache. It takes about twice as long when things are\n> > cold. It's enough of delay that I don't use the tool.\n>\n> I've been doing some timing measurements with Jon's repo. The results\n> are interesting.\n\nUsing the Mozilla repo you downloaded is not a normal situation since\nit is 100% packed. Most people are going to have a few thousand loose\nobjects floating around too. Loose objects really slow things down.\n\nYou noticed too that forks of small apps are relatively slow. The\nfirst pass of the import tools used fork for everything and took a\nweek to run with 60% of the time spent in the kernel. There may be\nsome work to do on fork in the kernel. Does mapping the kernel into\nthe top 1G slow down fork of these small apps? Or are they dynamically\nlinked to something that is bringing in millions of pages? When I was\ndoing oprofile all of the time was in the actual fork call and page\ntable copying.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26681","messageId":"20060910152122.31694.qmail@science.horizon.com","threadId":"5513","inReplyTo":"e5bfff550609092214t4f8e195eib28e302f4d284aa@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-09-10T15:21:22Z","receivedAt":"2006-09-10T15:21:22Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"This conversation is going in so many directions at once that it's\ngetting annoying.\n\nThe first level decision requires input from the point of view of gitk\nand qgit internals as to what's easy to implement.\n\nI'm trying to figure out the gitk code, but I'm not fluent in tcl, and\nit has 39 non-boilerplate comment lines in 229 functions and 6308 lines\nof source, so it requires fairly intensive grokking.\n\nStill, while it obviously doesn't render bitmaps until the data\nappears in the window, it appears as though at least part of the\nlayout (the \"layoutmore\" function) code is performed eagerly as\nsoon as new data arrives via the getcommitlines callback.\n\n(Indeed, it appears that Tk does not inform it of window scroll\nevents, so it can't wait any longer to decide on the layout.)\n\n\nCase 1: The visualizer is NOT CAPABLE of accepting out-of-order\n\tinput. Without very sophisticated cacheing in git-rev-list,\n\tit must process all of the data before outputting any in\n\torder to make an absolute guarantee of no out-of-order data\n\tdespite possibly messed-up timestamps.\n\n\tIt is possible to notice that the date-first traversal only\n\thas one active chain and flush the queued data at that point,\n\tbut that situation is unlikely to arise in repositories of\n\tnon-trivial size, which are exactly the ones for which\n\tthe batch-sorting delay is annoying.\n\nCase 2: The visualizer IS CAPABLE of accepting out-of-order input.\n\tRegardless of whether the layout is done eagerly or lazily,\n\tthis requires the visualizer to potentially undo part of\n\tits layout and re-do it, so has a UI implementation cost.\n\n\tThe re-doing does not need to be highly efficient; any number\n\tof heuristics and exception caches can reduce the occurrence of\n\tthis in git-rev-list output to very low levels. It's just\n\tabsolutely excluding it, without losing incremental output,\n\tthat is difficult.\n\n\tHeuristic: I suspect the most common wrong-timestamp case is\n\ta time zone misconfiguration, so holding back output until the\n\ttree traversal has advanced 24 hours will eliminate most of the\n\tproblems. Atypically large time jumps (like more than a year)\n\tcould also trigger special \"gross clock error\" handling.\n\n\tCache: whenever a child timestamped older than an ancestor is\n\tencountered, this can be entered in a persistent cache that can\n\tbe used to give the child a different sorting priority next time.\n\tThe simplest implementation would propagate this information up a\n\tchain of bad timestamps by one commit per git-rev-list invocation,\n\tbut even that's probably okay.\n\n\t(A study of timestamp ordering problems in existing repositories\n\twould be helpful for tuning these.)\n\nIn case 2, I utterly fail to see how delaying emitting the out-of-order\ncommit is of the slightest help to the UI. The simplest way to merge\nout-of-order data is with an insertion sort (a.k.a. roll back and\nreprocess forward), and the cost of that is minimized if the distance\nto back up is minimized.\n\nSome \"oops!\" annotation on the git-rev-list output may be helpful to\ntell the UI that it needs to search back, but it already has an internal\nindex of commits, so perhaps even that isn't worth bothering with.\nFancier output formats are also more work to process.\n\nWith sufficient cacheing of exceptions in git-rev-list, it may be\npractical to just have a single \"oops, I screwed up; let's start again\"\noutput line, which very rarely triggers.\n\n\nBut can we stop designing git-rev-list output formats until we've figured\nout if and how to implement it in the visualizer? Or, more to the point,\nvisualizers plural. That's the hard part. Then we can see what sort\nof git-rev-list output would be most convenient.\n\nFor example, is fixing a small number of out-of-place commits practical,\nor is it better to purge and restart? The former avoids deleting\nalready-existing objects, while the latter avoids moving them.\n\nThe original problem is that the long delay between starting a git history\nbrowser and being able to browse them is annoying. The visualizer UIs\nalready support browsing while history is flowing in from git-rev-list,\nbut git-rev-list is reading and sorting the entire history before\noutputting the first line.\n"},{"id":"26683","messageId":"20060910161007.8846.qmail@science.horizon.com","threadId":"5513","inReplyTo":"9e4733910609100756r1ece1e22m38054536a2909dd4@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-09-10T16:10:07Z","receivedAt":"2006-09-10T16:10:07Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> You noticed too that forks of small apps are relatively slow. The\n> first pass of the import tools used fork for everything and took a\n> week to run with 60% of the time spent in the kernel. There may be\n> some work to do on fork in the kernel. Does mapping the kernel into\n> the top 1G slow down fork of these small apps? Or are they dynamically\n> linked to something that is bringing in millions of pages? When I was\n> doing oprofile all of the time was in the actual fork call and page\n> table copying.\n\nActually, Linux has one of the fastest forks around, 100-200 us on\nmodern x86. For large executables, the shared page tables patch (is it\nmerged yet?) might help.\n\nNo, mapping the kernel does NOT slow anything down. Those page tables are\nshared between all processes, and use the x86's global bit to avoid being\nforced out of the TLB during context switch. Attempting to make the\nkernel mapping vary between processes would slow things down enormously!\n\nI'm not finding reasonably recent Linux/FreeBSD comparisons. There are\nplenty of Max OS X comparisons, but it appears to particularly suck,\nso that's a bit of a straw man. See, e.g.\nhttp://www.anandtech.com/mac/showdoc.aspx?i=2520&p=7\nor some figures from 2002:\nhttp://lists.apple.com/archives/darwin-kernel/2002/Oct/msg00009.html\n----------------------------------------------------------------\nHost OS Mhz null null open selct sig sig fork exec sh\n call I/O stat clos TCP inst hndl proc proc proc\n--------- ------------- ---- ---- ---- ---- ---- ----- ---- ---- ---- ---- ----\ng4 Darwin 1.4 799 2.21 3.19 12.6 16.4 30.4 3.78 9.88 1576 4095 13.K\ng4 Darwin 5.5 797 2.26 3.15 14.5 17.8 30.4 3.82 10.2 5685 12.K 40.K\ng4.local. Darwin 6.0 797 1.47 2.73 17.2 20.7 27.2 3.00 10.5 7517 17.K 41.K\ng4.local. Darwin 6.0 (after misconfiguration fixed) 1575\ng4 Linux 2.4.18- 799 0.42 0.69 2.52 3.79 33.6 1.23 3.08 659. 2642 12.K\n--------- ------------- ---- ---- ---- ---- ---- ----- ---- ---- ---- ---- ----\njim Darwin 1.4 448 2.85 4.23 9.53 17 4.83 14 2402 6817 19K\njim.local Darwin 6.1 448 1.89 3.71 21 29 43 3.85 15 2832 8955 19K\n\nFor small processes such as lmbench uses, you can see from the above that\nexec is much more expensive than fork. Also\nhttp://www.opersys.com/lrtbf/index.html\nhttp://marc.theaimsgroup.com/?l=linux-kernel&m=112086443319815\nhttp://www.opensourcetutorials.com/tutorials/Server-Side-Coding/Administration/hyper-threading-linux/page4.html\n\nAs for small apps and dynamic linking, glibc isn't tiny (prelink can\nhelp), but that's post-exec. If it's in the fork() call, then it's just\na case that your app's memory space is big and even copying all of its\npage tables is expensive.\n\nIf you're invoking one of the git programs that's a shell script, that\nadds its own startup overhead, of course.\n"},{"id":"26687","messageId":"9e4733910609101100u515ae6e3seababd5780db715d@mail.gmail.com","threadId":"5513","inReplyTo":"20060910161007.8846.qmail@science.horizon.com","subject":"Re: Change set based shallow clone","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-10T18:00:13Z","receivedAt":"2006-09-10T18:00:13Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 10 Sep 2006 12:10:07 -0400, linux@horizon.com wrote:\n> Actually, Linux has one of the fastest forks around, 100-200 us on\n> modern x86. For large executables, the shared page tables patch (is it\n> merged yet?) might help.\n\nHere is the opfile of the kernel\n\n3467889 18.9893 copy_page_range\n2190416 11.9941 unmap_vmas\n1156011 6.3300 page_fault\n887794 4.8613 release_pages\n860853 4.7138 page_remove_rmap\n633243 3.4675 get_page_from_freelist\n398773 2.1836 do_wp_page\n344422 1.8860 __mutex_lock_slowpath\n280070 1.5336 __handle_mm_fault\n241713 1.3236 do_page_fault\n238398 1.3054 __d_lookup\n236654 1.2959 vm_normal_page\n\nAt the time this was measured parsecvs was executing millions of git\ncommand using system(command). 40% of the CPU was in the kernel, it\nstayed that way for hours.\n\n18262372 41.0441 /home/good/vmlinux\n 5465741 12.2841 /usr/bin/cvs\n 4374336 9.8312 /lib/libc-2.4.so\n 3627709 8.1532 /lib/libcrypto.so.0.9.8a\n 2494610 5.6066 /usr/bin/oprofiled\n 2471238 5.5540 /usr/lib/libz.so.1.2.3\n 945349 2.1246 /usr/lib/perl5/5.8.8/i386-linux-thread-multi/CORE/libperl.so\n 933646 2.0983 /usr/local/bin/git-read-tree\n 758776 1.7053 /usr/local/bin/git-write-tree\n 642502 1.4440 /lib/ld-2.4.so\n 472903 1.0628 /nvidia\n 379254 0.8524 /usr/local/bin/git-pack-objects\n\nMaybe we are looking at the wrong thing, it may be fast to fork a\nprocess, is it fast for the process to exit?\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26689","messageId":"e5bfff550609101132x7e7ed336xa394b6220ab3643@mail.gmail.com","threadId":"5513","inReplyTo":"20060910152122.31694.qmail@science.horizon.com","subject":"Re: Change set based shallow clone","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2006-09-10T18:32:13Z","receivedAt":"2006-09-10T18:32:13Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":">\n> But can we stop designing git-rev-list output formats until we've figured\n> out if and how to implement it in the visualizer? Or, more to the point,\n> visualizers plural. That's the hard part. Then we can see what sort\n> of git-rev-list output would be most convenient.\n>\n\nRegarding qgit we have two cases:\n\n-arrive of fixup set for out of order commits _not_ currently\ndisplayed on the screen\nThis is by far the most common case expecially for big archives. In\nthis case the fix speed depends on how far are the fixed commits from\nthe last loaded commit (it's an insertion in a vector). In any case\nfar more quick then redrawing the graph. No flickering side effect\nhere. Implementation is easy.\n\n-arrive of fixup set for out of order commits currently displayed on the screen\nHere implementation _could_ be more difficult, but given the very low\nstatistic of this case (a rare case among rare cases) we could accept\nthe brutal approach of reset the complete graph, *but not the loaded\nrevisions data*, and redraw the graph. With this approach\nimplementation is almost as easy as before but flickering is involved.\n\nI agree with you that we should have fixup information as soon as\ngit-rev-list discovers out of order commits.\n\n Marco\n"},{"id":"26690","messageId":"7v1wqjsgfx.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"9e4733910609100756r1ece1e22m38054536a2909dd4@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-10T18:51:46Z","receivedAt":"2006-09-10T18:51:46Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Jon Smirl\" writes:\n\n> Using the Mozilla repo you downloaded is not a normal situation since\n> it is 100% packed. Most people are going to have a few thousand loose\n> objects floating around too. Loose objects really slow things down.\n\nWhen you have a few thousand loose objects you definitely should\nconsider repacking (not \"repack -a\" for Mozilla case, perhaps).\n\nWe could benefit from the suggested organization of one base\narchive pack plus a current active pack. The core side code to\nhelp doing so was posted here which followed a discussion on how\nto have repack make use of it last week.\n\n http://thread.gmane.org/gmane.comp.version-control.git/26218/focus=26326\n\nAny takers?\n"},{"id":"26697","messageId":"20060910190332.17667.qmail@science.horizon.com","threadId":"5513","inReplyTo":"9e4733910609101100u515ae6e3seababd5780db715d@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-09-10T19:03:32Z","receivedAt":"2006-09-10T19:03:32Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> Maybe we are looking at the wrong thing, it may be fast to fork a\n> process, is it fast for the process to exit?\n\nThe lmbench benchmark figures I cited are for fork+exit. The other is\nfork+exec+exit.\n\n> At the time this was measured parsecvs was executing millions of git\n> command using system(command). 40% of the CPU was in the kernel, it\n> stayed that way for hours.\n\nAh! You are aware, aren't you, that system(string) invokes\n/bin/sh to parse the string, right? So you're starting bash\nseveral million times. (\"man system\" explains.)\n\nA direct fork() (or even faster, vfork) and exec() is going to have a\nlot less overhead, although it's more work to code. See Stevens for\nexcellent examples.\n"},{"id":"26698","messageId":"Pine.LNX.4.64.0609101254590.27779@g5.osdl.org","threadId":"5513","inReplyTo":"20060910190332.17667.qmail@science.horizon.com","subject":"Re: Change set based shallow clone","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-10T20:00:21Z","receivedAt":"2006-09-10T20:00:21Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 10 Sep 2006, linux@horizon.com wrote:\n> \n> A direct fork() (or even faster, vfork) and exec() is going to have a\n> lot less overhead, although it's more work to code. See Stevens for\n> excellent examples.\n\nWell, that said, the Linux fork/exec/exit is certainly fairly efficient, \nbut nothing can hide the fact that it _is_ a very expensive operation.\n\nSo we may do a fork/exit in a millisecond, but on the other hand, we can \ngenerally open a file in a microsecond. So we're definitely talking about \nseveral orders of magnitude difference..\n\nAnd a lot of the trivial git helpers are literally not doing a lot more \nthan opening a file, reading it, and parsing it. That's for things like \nlooking up the SHA1 of a branch head, for example. Doing it in-line might \nbe a microsecond or two, while spawning a shell to execute git-rev-parse \nwill take you several microseconds.\n\nDo it a million times, and the difference is now a second vs an hour. Or a \nfew minutes vs a week.\n\nSo in that sense, it is absolutely undeniable that fork/exit is slow. \nEverything is relative. The Linux fork/exit is fast when compared to most \nother systems fork/exit, but it's slow as hell when compared to just doing \nsome small op directly in-line.\n\n\t\t\tLinus\n"},{"id":"26700","messageId":"9e4733910609101400j2604ace1vdb2e363c1296418f@mail.gmail.com","threadId":"5513","inReplyTo":"Pine.LNX.4.64.0609101254590.27779@g5.osdl.org","subject":"Re: Change set based shallow clone","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-10T21:00:53Z","receivedAt":"2006-09-10T21:00:53Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/10/06, Linus Torvalds wrote:\n> On Sun, 10 Sep 2006, linux@horizon.com wrote:\n> >\n> > A direct fork() (or even faster, vfork) and exec() is going to have a\n> > lot less overhead, although it's more work to code. See Stevens for\n> > excellent examples.\n>\n> Well, that said, the Linux fork/exec/exit is certainly fairly efficient,\n> but nothing can hide the fact that it _is_ a very expensive operation.\n\ncvs2svn + fastimport can import the same Mozilla repo in about 2hrs\nthat was taking parsecvs about five days to do. The algorithms are not\nthat different, cvs2svn is probably slower than parsecvs for detecting\nchangesets. The difference is mostly due to the removal of forks.\n\nIs the kernel mapped into user processes using huge pages? That would\nreduce some of the pressure on TLBs. Another thing that should be\nmapped with huge pages is the video RAM.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26704","messageId":"17668.38032.20688.991295@cargo.ozlabs.ibm.com","threadId":"5513","inReplyTo":"Pine.LNX.4.64.0609101254590.27779@g5.osdl.org","subject":"Re: Change set based shallow clone","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2006-09-10T22:41:20Z","receivedAt":"2006-09-10T22:41:20Z","isPatch":false,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Linus Torvalds writes:\n\n> So we may do a fork/exit in a millisecond, but on the other hand, we can \n> generally open a file in a microsecond. So we're definitely talking about \n> several orders of magnitude difference..\n\nUnless the file isn't in memory, in which case it's probably around a\nmillisecond or more...\n\nDo you think there is any way to speed up the cold-cache case for\ngit-ls-remote and git-rev-parse with thousands of heads and tags?\n\nPaul.\n"},{"id":"26705","messageId":"ee26jo$jqp$1@sea.gmane.org","threadId":"5513","inReplyTo":"9e4733910609071609o50e5dacm53323e023e90358f@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Anand Kumria","fromEmail":"wildfire@progsoc.org","sentAt":"2006-09-10T23:20:24Z","receivedAt":"2006-09-10T23:20:24Z","isPatch":false,"sender":{"key":"wildfire@progsoc.org","avatar":null},"body":"On Thu, 07 Sep 2006 19:09:21 -0400, Jon Smirl wrote:\n\n> On 9/7/06, Junio C Hamano wrote:\n>> \"Jon Smirl\" writes:\n>>\n>> > Does an average user do these things? The shallow clone is there to\n>> > address the casual user who gags at a five hour download to get an\n>> > initial check out Mozilla when they want to make a five line change or\n>> > just browse the source for a few minutes.\n>> >...\n>> > Maybe the answer is to build a shallow clone tool for casual use, and\n>> > then if you try to run anything too complex on it git just tells you\n>> > that you have to download the entire tree.\n>>\n>> For that kind of thing, \"git-tar-tree --remote\" would suffice I\n>> would imagine. The five line change can be tracked locally by\n>> creating an initial commit from the tar-tree extract; such a\n>> casual user will not be pushing or asking to pull but sending in\n>> patches to upstream, no?\n> \n> From my observation the casual user does something like this:\n> \n> get a shallow clone\n\nThis could basically be something which look at the remote HEAD and pulls\ndown a copy of that commit/tree (and associated objects), right?\n\n> look at it for a while\n> pull once a day to keep it up to date\n\nSame again.\n\n> decide to make some changes\n> start a local branch\n> commit changes on local branch\n> \n> push these changes to someone else for review\n> maybe pull changes on the branch back from the other person\n\n[...]\n\nAt what point, if any, do you envisage a casual user pulling down a full\ncopy of the repository?\n\nCheers,\nAnand\n"},{"id":"26706","messageId":"20060911000306.GA28927@spearce.org","threadId":"5513","inReplyTo":"17668.2019.732961.855446@cargo.ozlabs.ibm.com","subject":"Re: Change set based shallow clone","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-11T00:03:06Z","receivedAt":"2006-09-11T00:03:06Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Paul Mackerras wrote:\n[snip]\n> The bottom line is that I can speed up the startup for the hot-cache\n> case quite a lot. The cold-cache case is going to take about 20-30\n> seconds whatever I do unless Linus or Junio can come up with a way to\n> pack the heads and tags. I could read the refs asynchronously but\n> there will still be a long delay in git rev-parse if you give\n> arguments such as --all.\n\nI've been thinking about implementing ref storage within a Git tree\nobject. Just store the commit/tag/object IDs in a tree (or graph\nof trees) with a mode of '0'. Anchor that under '.git/refs-tree'.\nAny edit of a ref would \"lock\" .git/refs-tree, create a new tree\ncontaining the update, then replace .git/refs-tree.\n\nBut it would put additional stress on the objects directory by\ncreating a lot of trees which would never get pulled into pack\nfiles and thus would need to be pruned away on a regular basis.\n\nIt also would make parallel updates more difficult on the server\nside as everyone would need to wait for the lock to .git/refs-tree\nbefore they can change any ref; today users only need to wait for\nthe ref they are trying to change.\n\nIt also doesn't help looking up a ref quickly; although trees are\nsorted they are variable length entries which forces the application\nto read the entire tree to find its entry.\n\n\nGiven those three downsides I haven't put anything to code yet.\n\n-- \nShawn.\n"},{"id":"26707","messageId":"20060911000403.GB28927@spearce.org","threadId":"5513","inReplyTo":"7v1wqjsgfx.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-11T00:04:03Z","receivedAt":"2006-09-11T00:04:03Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> We could benefit from the suggested organization of one base\n> archive pack plus a current active pack. The core side code to\n> help doing so was posted here which followed a discussion on how\n> to have repack make use of it last week.\n> \n> http://thread.gmane.org/gmane.comp.version-control.git/26218/focus=26326\n> \n> Any takers?\n\nI thought this was settled and you had it implemented? Is this\nstill an open topic?\n\n-- \nShawn.\n"},{"id":"26708","messageId":"7vfyezqlny.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"20060911000306.GA28927@spearce.org","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-11T00:41:53Z","receivedAt":"2006-09-11T00:41:53Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> I've been thinking about implementing ref storage within a Git tree\n> object. Just store the commit/tag/object IDs in a tree (or graph\n> of trees) with a mode of '0'. Anchor that under '.git/refs-tree'.\n> Any edit of a ref would \"lock\" .git/refs-tree, create a new tree\n> containing the update, then replace .git/refs-tree.\n>\n> But it would put additional stress on the objects directory by\n> creating a lot of trees which would never get pulled into pack\n> files and thus would need to be pruned away on a regular basis.\n\nI do not see any advantage of making such a phoney object at\nall, but I do agree that the current one file per ref can be\nless than optimal when your repository has tons of tags or\nrefs.\n\nWe've designed the ref interface well enough so that only very\nnarrow core functions know the implementation (and properly\nwritten Porcelain would access refs via update-ref and\nsymbolic-ref interfaces), so the impact of changing the\none-file-per-ref implementation to something based on a single\nsimple databasy file (e.g. gdbm, bdb, sqlite, ...) would be\nreasonably limited.\n"},{"id":"26709","messageId":"7v8xkrqlma.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"20060911000403.GB28927@spearce.org","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-11T00:42:53Z","receivedAt":"2006-09-11T00:42:53Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> Junio C Hamano wrote:\n>> We could benefit from the suggested organization of one base\n>> archive pack plus a current active pack. The core side code to\n>> help doing so was posted here which followed a discussion on how\n>> to have repack make use of it last week.\n>> \n>> http://thread.gmane.org/gmane.comp.version-control.git/26218/focus=26326\n>> \n>> Any takers?\n>\n> I thought this was settled and you had it implemented? Is this\n> still an open topic?\n\nI've implemented the core side and I think it is ready. People\nwho actually have need for such a repack are welcome to take a\ncrack at it at the Porcelain-ish level.\n"},{"id":"26710","messageId":"ee2cms$o18$1@sea.gmane.org","threadId":"5513","inReplyTo":"7vfyezqlny.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-09-11T01:04:31Z","receivedAt":"2006-09-11T01:04:31Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Junio C Hamano wrote:\n\n> the impact of changing the\n> one-file-per-ref implementation to something based on a single\n> simple databasy file (e.g. gdbm, bdb, sqlite, ...)\n\nOne of the complaints against Subversion was that it use BerkeleyDB\n(bdb) backend... but it was before it acquired fsfs interface. Perhaps\nwe could use it too.\n\nOr perhaps it is for something like Electra, or ReiserFS file properites\naccess...\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"26711","messageId":"9e4733910609101911y25005ca6v7dfdbf20f95577f2@mail.gmail.com","threadId":"5513","inReplyTo":"7vfyezqlny.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-11T02:11:03Z","receivedAt":"2006-09-11T02:11:03Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/10/06, Junio C Hamano wrote:\n> I do not see any advantage of making such a phoney object at\n> all, but I do agree that the current one file per ref can be\n> less than optimal when your repository has tons of tags or\n> refs.\n\nHere's a hack, instead of of putting the sha inside the file, put the\nsha into the filename.\n\nmaster_86a8534ba23a5532f6d0ddd01ecd8f02f662cf78\n\nNow you can just do a directory listing and get all of the data\nquickly. To keep the existing porcelain working add a symlink.\n\nln -s master_86a8534ba23a5532f6d0ddd01ecd8f02f662cf78 master\n\nYou might want the sha1 encoded names in a new directory\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26713","messageId":"20060911024434.GA29368@spearce.org","threadId":"5513","inReplyTo":"ee2cms$o18$1@sea.gmane.org","subject":"Re: Change set based shallow clone","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-11T02:44:34Z","receivedAt":"2006-09-11T02:44:34Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jakub Narebski wrote:\n> Junio C Hamano wrote:\n> \n> > the impact of changing the\n> > one-file-per-ref implementation to something based on a single\n> > simple databasy file (e.g. gdbm, bdb, sqlite, ...)\n> \n> One of the complaints against Subversion was that it use BerkeleyDB\n> (bdb) backend... but it was before it acquired fsfs interface. Perhaps\n> we could use it too.\n\nI'm against the latest Berkely DB (Sleepy Cat) implementations.\nEvery time I've stored data in them or in applications which use\nthem I've lost everything. GNU dbm might not be too bad. SQL Lite\nis overkill.\n\nI was thinking of using a tree object only because its a well\ndefined Git file format that's already in use. Plus its \"easy\"\nto repair by loading it into an index, twiddline it and invoking\ngit-write-tree to convert it back. But there's a lot of downsides.\n\nThis is probably something that is easily solved by a simple fixed\nrecord format holding a 20 byte SHA1 (binary) and a fixed width null\nterminated string holding the ref name, with the records sorted\nby ref name. Its yet another file format with yet another set of\nutilities needed but we pretty much have those (update-ref).\n \n> Or perhaps it is for something like Electra, or ReiserFS file properites\n> access...\n\nExcept not everyone has those filesystems. :-)\n\n-- \nShawn.\n"},{"id":"26714","messageId":"Pine.LNX.4.64.0609101946330.27779@g5.osdl.org","threadId":"5513","inReplyTo":"9e4733910609101400j2604ace1vdb2e363c1296418f@mail.gmail.com","subject":"Re: Change set based shallow clone","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-11T02:49:38Z","receivedAt":"2006-09-11T02:49:38Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 10 Sep 2006, Jon Smirl wrote:\n> \n> Is the kernel mapped into user processes using huge pages?\n\nYup. Huge pages and global. So the kernel should have fairly low TLB \nimpact (depending on CPU - the kernel also has less locality than user \nspace, since the data structures are all over the place, and some CPU's \nhave very few hugepage entries. System code generally tends to have much \nworse I$ and TLB behaviour than most user apps, but at least the hugepage \nmappings tend to mitigate the TLB side somewhat).\n\n> Another thing that should be mapped with huge pages is the video RAM.\n\nI doubt it ends up being a huge deal in most cases. If you don't use the \ngraphics chip to access video RAM with accelerated methods, the TLB is the \n_least_ of your worries. Going over the PCI bus (even with PCI-X etc) is \nthe real problem.\n\nThere's a reason you want to do acceleration even in 2D..\n\n\t\tLinus\n"},{"id":"26715","messageId":"Pine.LNX.4.64.0609101949580.27779@g5.osdl.org","threadId":"5513","inReplyTo":"17668.38032.20688.991295@cargo.ozlabs.ibm.com","subject":"Re: Change set based shallow clone","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-11T02:55:23Z","receivedAt":"2006-09-11T02:55:23Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 11 Sep 2006, Paul Mackerras wrote:\n> \n> Do you think there is any way to speed up the cold-cache case for\n> git-ls-remote and git-rev-parse with thousands of heads and tags?\n\nNothing obvious comes to mind.\n\nIf we did the same pack-file approach that we do for objects, the problem \nends up being that _updating_ things is really hard. What we could do (and \nmight work) is that a \"git repack\" would create a \"packed representation \nof the heads too\".\n\nThe issue is that once you create a pack, you _really_ don't want to use \nread-modify-write to modify it ever afterwards. That's how you get nasty \ncorruption. The \"append-only\" side of the git object database is really \nwhat makes things so stable, and packing multiple heads in the same file \nautomatically means that if something goes wrong, it's _disastrously_ \nwrong, in a way it isn't when you have separate files.\n\nSo we could generate a \"pack of references\", but then any modifications \nwould be done with the current loose \"file objects\" approach, and just \nhave the filesystem override the pack-files. The problem then actually \nbecomes one of _deleting_ branches, because then we'd have to add a \n\"negative branch\" loose object. Ugly.\n\nAn alternate approach might be to keep the current filesystem layour, but \nsimply do the readdir over the whole reference situation in one pass, then \nsort them by inode number, and look them up in order. That would help on \nsome filesystems, at least.\n\n\t\tLinus\n"},{"id":"26716","messageId":"Pine.LNX.4.64.0609102002300.27779@g5.osdl.org","threadId":"5513","inReplyTo":"Pine.LNX.4.64.0609101949580.27779@g5.osdl.org","subject":"Re: Change set based shallow clone","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-11T03:18:49Z","receivedAt":"2006-09-11T03:18:49Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 10 Sep 2006, Linus Torvalds wrote:\n> \n> If we did the same pack-file approach that we do for objects, the problem \n> ends up being that _updating_ things is really hard. What we could do (and \n> might work) is that a \"git repack\" would create a \"packed representation \n> of the heads too\".\n\nTo clarify: I'm _not_ suggesting actually using the \"pack-file\" \nrepresentation itself for the references.\n\nI'm saying that we could have something like a\n\n\t.git/refs-packed\n\nfile, which could be (for example) just a plain linear text-file, of the \nform\n\n\t19ed368b17abfb9ad5c7467ea74fd8a045d96b43\trefs/heads/html\n\t60a6bf5f53635005f4f68d8b8a33172309193623\trefs/heads/maint\n\t2d32e76f893b2ac432201ce7596c8bab691691e6\trefs/heads/man\n\ta41fae9c46a4cb5e59cc1a17d19f6a3a6cbfbb2f\trefs/heads/master\n\t61af0aaf26e003a61848e551bbd57e78e94eacdc\trefs/heads/next\n\t585729203fef6ade64923277e7151b2e3a4ca330\trefs/heads/pu\n\t997283a8e87179b5b87a909686869d7843c8e19a\trefs/heads/todo\n\ta0e7d36193b96f552073558acf5fcc1f10528917\trefs/tags/junio-gpg-pub\n\td6602ec5194c87b0fc87103ca4d67251c76f233a\trefs/tags/v0.99\n\tf25a265a342aed6041ab0cc484224d9ca54b6f41\trefs/tags/v0.99.1\n\tc5db5456ae3b0873fc659c19fafdde22313cc441\trefs/tags/v0.99.2\n\t7ceca275d047c90c0c7d5afb13ab97efdf51bd6e\trefs/tags/v0.99.3\n\tb3e9704ecdf48869f635f0aa99ddfb513f885aff\trefs/tags/v0.99.4\n\t07e38db6a5a03690034d27104401f6c8ea40f1fc\trefs/tags/v0.99.5\n\tf12e22d4c12c3d0263fa681f25c06569f643da0f\trefs/tags/v0.99.6\n\tf8696fcd2abc446a5ccda3e414b731eff2a7e981\trefs/tags/v0.99.7\n\t1094cf40f7029f803421c1dcc971238507c830c5\trefs/tags/v0.99.7a\n\tda30c6c39cd3b048952a15929c5440acfd71b912\trefs/tags/v0.99.7b\n\t9165ec17fde255a1770886189359897dbb541012\trefs/tags/v0.99.7c\n\t02b2acff8bafb6d73c6513469cdda0c6c18c4138\trefs/tags/v0.99.7d\n\t...\n\nie it would contain just a linear file with the \"\"\nformat. Then, the way to look up a reference would be:\n\n - look it up in the traditional loose file\n - if it exists, and contains zeros (or not a hex value), it's considered \n a \"negative entry\", and the branch doesn't exist\n - otherwise, if it's a good SHA1, that's the result\n - if it's not there, look it up in the \".git/refs-packed\" file by just \n doing a simple linear scan (trivial, and actually efficient - we're \n talking about just a few kB of memory after all, and the _cost_ is \n actually the IO, where \"simple linear scan\" is actually very good for \n performance).\n\nThe end result would be that we'd probably have very few loose references \n(we'd get them whenever we change a ref, or delete one), making the lookup \nscale better. The big _bulk_ of the references tend to be very stable, \nnotably they are tags that seldom - if ever - change, and would thus stay \njust in the packed refs file.\n\nSo the normal situation would be that you'd have a few hundred (maybe, for \na bigger project) refs in the single .git/refs-packed file, totalling a \nfew kB of disk-space, and then you might have a handful of \"active\" heads \nthat are in the traditional single-file format .git/refs/ \nbecause they are beign actively modified and have changed since the last \nrepack.\n\nI bet it would work fairly well. But somebody would need to implement it.\n\nThe good news is that the refs-handling code tends to be _fairly_ well \nabstracted out, because we already wanted that for the logging thing. So \nwe hopefully already don't actually access the loose file objects by hand \nfrom shell scripts any more - we use git-rev-parse and git-update-ref etc \nto look up refnames, and that all goes back to git/refs.c.\n\nSo _most_ of the bulk of it would probably be in refs.c, but there's \nobviously also things like git-branch.sh that needs to be taught the new \nrules about deleting branches etc.\n\nAnybody want to try the above rules out? I bet the _only_ real issue would \nbe \"for_each_ref()\", where it's important to _first_ do the loose objects, \nand remember them all, so that you do _not_ show the refs that are in the \n.git/refs-packed file and already got shown because they were loose.\n\nNOTE! It's important that whatever sceme used gets locking right. The \nabove suggestion gets it right simply because it doesn't really _change_ \nanything. Any new or modified ref ends up using the old code, and using a \n\".lock\" file and renaming it automatically does the same thing it ever \ndid.\n\n\t\tLinus\n"},{"id":"26721","messageId":"7vac57nfb5.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"20060911024434.GA29368@spearce.org","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-11T05:27:26Z","receivedAt":"2006-09-11T05:27:26Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> Jakub Narebski wrote:\n>> Junio C Hamano wrote:\n>> \n>> > the impact of changing the\n>> > one-file-per-ref implementation to something based on a single\n>> > simple databasy file (e.g. gdbm, bdb, sqlite, ...)\n>> \n>> One of the complaints against Subversion was that it use BerkeleyDB\n>> (bdb) backend... but it was before it acquired fsfs interface. Perhaps\n>> we could use it too.\n>\n> I'm against the latest Berkely DB (Sleepy Cat) implementations.\n> Every time I've stored data in them or in applications which use\n> them I've lost everything. GNU dbm might not be too bad. SQL Lite\n> is overkill.\n>...\n> This is probably something that is easily solved by a simple fixed\n> record format holding a 20 byte SHA1 (binary) and a fixed width null\n> terminated string holding the ref name, with the records sorted\n> by ref name. Its yet another file format with yet another set of\n> utilities needed but we pretty much have those (update-ref).\n\nYup. That is one reasonable implementation of \"single simple\ndatabasy file\" I suggested. Or we could just borrow .git/info/refs\nformat.\n"},{"id":"26723","messageId":"20060911060820.GB29368@spearce.org","threadId":"5513","inReplyTo":"7vac57nfb5.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-11T06:08:20Z","receivedAt":"2006-09-11T06:08:20Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> Shawn Pearce writes:\n> > This is probably something that is easily solved by a simple fixed\n> > record format holding a 20 byte SHA1 (binary) and a fixed width null\n> > terminated string holding the ref name, with the records sorted\n> > by ref name. Its yet another file format with yet another set of\n> > utilities needed but we pretty much have those (update-ref).\n> \n> Yup. That is one reasonable implementation of \"single simple\n> databasy file\" I suggested. Or we could just borrow .git/info/refs\n> format.\n\nI think Linus was suggesting the same thing, just not nearly as\nobvious. He also was looking for ways to not update it frequently.\nBut I can't say I'm a fan of negative entries. :-)\n\nI'd probably rather code this as a fixed width binary heap file.\nIt should scale reasonable well to larger sets of refs. I know\nsomeone on the list wanted to store Perforce change identifiers\nas tags in Git but it was taking up more disk in ref files than\nin pack-*.pack. That could be a very larger number of refs and\nhaving O(log N) access there might be good.\n\n\nBut at this point I have more on my plate than I have time for. :-)\n\nI've got to get that map window code merged against master or next\n(preference Junio? next touches code I'm touching too but those\naren't in master yet) for 32 bit offset. Should be slightly easier\nto do but the pack verification change really threw a wrench into\nmy merge. Other things have also kept me from really working on it.\nI probably won't be able to look at it again until Wednesday.\n\nI also want to spend more time on the dictionary packing prototype to\nsee if its worth spending even more time on. My amd64 box is happily\ninstalling itself as write this (finally!) so I now have some more\nreasonable hardware to deal with transforming the Mozilla pack. :)\n\n-- \nShawn.\n"},{"id":"26724","messageId":"7vk64anc5x.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"Pine.LNX.4.64.0609102002300.27779@g5.osdl.org","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-11T06:35:22Z","receivedAt":"2006-09-11T06:35:22Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Sun, 10 Sep 2006, Linus Torvalds wrote:\n>> \n>> If we did the same pack-file approach that we do for objects, the problem \n>> ends up being that _updating_ things is really hard. What we could do (and \n>> might work) is that a \"git repack\" would create a \"packed representation \n>> of the heads too\".\n>\n> To clarify: I'm _not_ suggesting actually using the \"pack-file\" \n> representation itself for the references.\n>\n> I'm saying that we could have something like a\n>\n> \t.git/refs-packed\n>\n> file, which could be (for example) just a plain linear text-file, of the \n> form\n>\n> \t19ed368b17abfb9ad5c7467ea74fd8a045d96b43\trefs/heads/html\n> \t60a6bf5f53635005f4f68d8b8a33172309193623\trefs/heads/maint\n> \t...\n>\n> ie it would contain just a linear file with the \"\"\n> format. Then, the way to look up a reference would be:\n>...\n> NOTE! It's important that whatever sceme used gets locking right. The \n> above suggestion gets it right simply because it doesn't really _change_ \n> anything. Any new or modified ref ends up using the old code, and using a \n> \".lock\" file and renaming it automatically does the same thing it ever \n> did.\n\nThis is all interesting and can be done by somebody interested\nin the really core part of the system.\n\nI was just looking at Paul's \"new\" branch, and realized that\nthere is something else that somebody _else_ can do in parallel\nto make life easier for gitk and gitweb, and it is not on so\nbare-metal-core side. The latest commit in Paul's \"new\" branch\nsays:\n\n We were doing two execs for each tag - one to map the tag ID to a commit\n ID (which git ls-remote was already giving us as refs/tags/foo^{}) and\n one to read the contents of the tag for later display....\n\nI think this is a typical problem any Porcelain layer faces. To\ngrab summary information for all refs in a concise form in one\ngo.\n\nWe discussed such a potential command about a month ago with\nJakub, but the suggestion did not go anywhere.\n\nhttp://thread.gmane.org/gmane.comp.version-control.git/25013/focus=25055\n\nIn addition to what I described there, such a command should at\nleast allow specifying some special formatting for tag objects,\nsuch as dereferencing it once (i.e. what the object name and\ntype of the referenced object is) and dereferencing it\nrepeatedly until a non-tag appears (i.e. \"$that_tag^{}\" along\nwith its type).\n\nThe show-ref command will alleviate the fork+exec problem; the\ncore side update you suggested for ref handling will improve the\nperformance of the implementation of such a command and can be\ndone in parallel.\n"},{"id":"26725","messageId":"7vr6yikhdj.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"20060911060820.GB29368@spearce.org","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-11T07:11:04Z","receivedAt":"2006-09-11T07:11:04Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> I think Linus was suggesting the same thing, just not nearly as\n> obvious. He also was looking for ways to not update it frequently.\n> But I can't say I'm a fan of negative entries. :-)\n\nI like Linus's suggestion quite a lot actually. It would be a\nnice little project that needs to touch reasonably well-isolated\narea of the code, but I suspect it would need a bit more\nexposure and familiarity to the existing code than somebody who\nlooks at the core code for the first time.\n\n> But at this point I have more on my plate than I have time for. :-)\n\nYou've done quite a lot of work on refs area yourself, so you\nmight want to give somebody else the chance to try first ;-).\n\n> I've got to get that map window code merged against master or next\n> (preference Junio? next touches code I'm touching too but those\n> aren't in master yet) for 32 bit offset.\n\nAs you know I've shelved the 64-bit offset stuff. My preference\nis to base it on 106d710b but basing it on 'next' would be fine.\nBetween 106d710b and next there is only one unrelated change to\nsha1_file.c, which is the hexval[] change that is in 'master'.\n\nI've sent out \"What's in\" tonight but forgot to talk about plans\nfor topics in \"next\", so here is an update.\n\n - These things are probably Ok, and after a bit more testing\n I'd like to push them out to 'master' by my Wednesday:\n\n - Andy Whitcroft's \"send-pack to use git-rev-list --stdin\"\n - \"git apply\" to apply binary without explicit --binary flag;\n - \"git diff --binary\" to do full-index only for binary patch;\n - \"git unpack-objects -r\", except it needs a better name\n (perhaps --recover).\n\n - And these by the end of week:\n\n - Jeff King's git-runstatus;\n - Frank and Rene's git-archive along with git-daemon change;\n\n - I am not _so_ comfortable with these quite yet, but plan to\n test it a bit more to gain confidence and decide when to push\n out to 'master' perhaps by the middle of the week:\n\n - pack-objects --unpacked=this-pack --unpacked=that-pack\n - pack-objects --stdin\n\n> I also want to spend more time on the dictionary packing prototype to\n> see if its worth spending even more time on.\n\nSo far I liked the per-object-type dictionary conjecture the\nmost, primarily because my gut feeling tells me that it would\ninvolve the least amount of hassle in the interoperability area.\n\nBut honestly speaking I am not looking forward to a packfile\nformat update at this moment. I'd like things to settle down a\nbit now, after merging good bits from 'next' to 'master' and\ndeclare 1.4.3 first, perhaps by the end of the month.\n"},{"id":"26726","messageId":"17669.8191.778645.311304@cargo.ozlabs.ibm.com","threadId":"5513","inReplyTo":"Pine.LNX.4.64.0609101949580.27779@g5.osdl.org","subject":"Re: Change set based shallow clone","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2006-09-11T08:36:15Z","receivedAt":"2006-09-11T08:36:15Z","isPatch":false,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Linus Torvalds writes:\n\n> So we could generate a \"pack of references\", but then any modifications \n> would be done with the current loose \"file objects\" approach, and just \n> have the filesystem override the pack-files. The problem then actually \n> becomes one of _deleting_ branches, because then we'd have to add a \n> \"negative branch\" loose object. Ugly.\n\nCould we do a cache of the refs that stores the stat information for\neach of the files under .git/refs plus the sha1 that the ref points\nto? In other words this cache would do for the refs what the index\ndoes for the working directory. Reading all the refs would mean we\nstill had to stat each of the files, but that's much quicker than\nreading them in the cold-cache case. In the common case when most of\nthe stat information matches, we don't have to read the file because\nwe have the sha1 that the file contains right there in the cache.\n\nIdeally we would have two sha1 values in the cache - the sha1 in the\nfile, and if that is the ID of a tag object, we would also put the\nsha1 of the commit that the tag points to in the cache.\n\nPaul.\n"},{"id":"26729","messageId":"ee38ri$pp8$2@sea.gmane.org","threadId":"5513","inReplyTo":"Pine.LNX.4.64.0609101949580.27779@g5.osdl.org","subject":"Re: Change set based shallow clone","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-09-11T09:04:54Z","receivedAt":"2006-09-11T09:04:54Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Linus Torvalds wrote:\n\n> On Mon, 11 Sep 2006, Paul Mackerras wrote:\n>> \n>> Do you think there is any way to speed up the cold-cache case for\n>> git-ls-remote and git-rev-parse with thousands of heads and tags?\n> \n> Nothing obvious comes to mind.\n> \n> If we did the same pack-file approach that we do for objects, the problem \n> ends up being that _updating_ things is really hard. What we could do (and \n> might work) is that a \"git repack\" would create a \"packed representation \n> of the heads too\".\n\nBecause usually there is reasonable number of heads, and that is the tags\nthat might be problem, because the number of tags likes to grow with the\nhistory, perhaps we could pack only tags heads into the pack? This has\nadditional advantage that tags, especially annotated tags (i.e. true tags\nobjects) changes rarely.\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"26731","messageId":"17669.13028.198886.947400@cargo.ozlabs.ibm.com","threadId":"5513","inReplyTo":"20060910152122.31694.qmail@science.horizon.com","subject":"Re: Change set based shallow clone","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2006-09-11T09:56:52Z","receivedAt":"2006-09-11T09:56:52Z","isPatch":false,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"linux@horizon.com writes:\n\n> I'm trying to figure out the gitk code, but I'm not fluent in tcl, and\n> it has 39 non-boilerplate comment lines in 229 functions and 6308 lines\n> of source, so it requires fairly intensive grokking.\n\nSorry :)\n\n> Still, while it obviously doesn't render bitmaps until the data\n> appears in the window, it appears as though at least part of the\n> layout (the \"layoutmore\" function) code is performed eagerly as\n> soon as new data arrives via the getcommitlines callback.\n\nIt doesn't render bitmaps as such at the Tcl level, what it does is\ncreate items on canvases, add text to text widgets, etc. Tk takes\ncare of turning it into bitmaps.\n\nThe work of drawing the graph is done in three stages - layout,\noptimization and drawing. The layout and optimization stages are done\nwhen we have enough data because, at least for the layout stage,\nearlier rows can affect later rows arbitrarily far away. For the\noptimization stage, I don't think the changes it makes can propagate\narbitrarily far, so it would be possible to defer that stage, and I am\nlooking into implementing that. The drawing stage is done on demand,\njust for the part that's actually visible.\n\n> (Indeed, it appears that Tk does not inform it of window scroll\n> events, so it can't wait any longer to decide on the layout.)\n\nThe Tcl code does get to know when the canvas has been scrolled - see\nthe scrollcanv procedure.\n\n> In case 2, I utterly fail to see how delaying emitting the out-of-order\n> commit is of the slightest help to the UI. The simplest way to merge\n\nIndeed. I would want to see it as early as possible.\n\n> out-of-order data is with an insertion sort (a.k.a. roll back and\n> reprocess forward), and the cost of that is minimized if the distance\n> to back up is minimized.\n\nThat part isn't too hard; I already have modifications to gitk to\nhandle that much of it. The harder part is backing up the graph\ndrawing algorithm.\n\n> For example, is fixing a small number of out-of-place commits practical,\n> or is it better to purge and restart? The former avoids deleting\n> already-existing objects, while the latter avoids moving them.\n\nFor gitk, I'm thinking of a reorder buffer of say 10 entries at the\nfront end to cope with minor misorderings; then if misordering occurs\nthat is outside the scope of the reorder buffer to fix, freeze the\nlayout algorithms at that point, read in the rest of the commits and\nreorder as necessary, then at the end restart the layout algorithm\nfrom scratch, probably with a popup to inform the user what happened.\nIf the user could set the size of the reorder buffer then they could\navoid having that happen in future, at the cost of it taking longer to\nshow the first screenful of commits.\n\nPaul.\n"},{"id":"26734","messageId":"20060911123937.6521.qmail@science.horizon.com","threadId":"5513","inReplyTo":"17669.13028.198886.947400@cargo.ozlabs.ibm.com","subject":"Re: Change set based shallow clone","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-09-11T12:39:37Z","receivedAt":"2006-09-11T12:39:37Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":">> I'm trying to figure out the gitk code, but I'm not fluent in tcl, and\n>> it has 39 non-boilerplate comment lines in 229 functions and 6308 lines\n>> of source, so it requires fairly intensive grokking.\n>\n> Sorry :)\n\nI was more making excuses for my failure to understand its properties.\nStill, if you get the chance, a couple of paragraphs of comments on the\nprimary data structures would be an immense help.\n\nAnyway, thanks for the summary.\n\n>> For example, is fixing a small number of out-of-place commits practical,\n>> or is it better to purge and restart? The former avoids deleting\n>> already-existing objects, while the latter avoids moving them.\n\n> For gitk, I'm thinking of a reorder buffer of say 10 entries at the\n> front end to cope with minor misorderings; then if misordering occurs\n> that is outside the scope of the reorder buffer to fix, freeze the\n> layout algorithms at that point, read in the rest of the commits and\n> reorder as necessary, then at the end restart the layout algorithm\n> from scratch, probably with a popup to inform the user what happened.\n> If the user could set the size of the reorder buffer then they could\n> avoid having that happen in future, at the cost of it taking longer to\n> show the first screenful of commits.\n\nMy thoughts were that anything you could do, git-rev-list could do better,\nincluding the re-order buffer, so don't even bother. (For example, I\nwas thinking of a time- or depth-based one rather than a count-based one.)\n\nSo I read your suggestion as a \"purge and restart\" preference, with\ngit-rev-list keeping a cache of problems encountered so that on most\nruns, it doesn't have to do it. Putting that logic in git-rev-list\nmeans that you don't have to detect ordering problems or do any sorting,\njust handle an \"oops!\" line in the output.\n\nBasically, given the example graph (with letters indicating timestamps)\n\n...G--D--C--B---A\n \\ /\n F--E\n\nYou'd get something like\nA B E\nB C\nC D\nD G\nE F\n*** ERROR - restarting - please wait\nA B E\nB C\nE F\nF C\nC D\nD G\nG ...\n"},{"id":"26735","messageId":"20060911142644.32313.qmail@science.horizon.com","threadId":"5513","inReplyTo":"17669.8191.778645.311304@cargo.ozlabs.ibm.com","subject":"Re: Change set based shallow clone","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-09-11T14:26:44Z","receivedAt":"2006-09-11T14:26:44Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> Could we do a cache of the refs that stores the stat information for\n> each of the files under .git/refs plus the sha1 that the ref points\n> to? In other words this cache would do for the refs what the index\n> does for the working directory. Reading all the refs would mean we\n> still had to stat each of the files, but that's much quicker than\n> reading them in the cold-cache case. In the common case when most of\n> the stat information matches, we don't have to read the file because\n> we have the sha1 that the file contains right there in the cache.\n\nWell, that could save one of two seeks, but that's not *much* quicker.\n(Indeed, a git ref would fit into the 60 bytes of block pointer space\nin an ext2/3 inode if regular files were stuffed there as well as symlinks.)\n\n> Ideally we would have two sha1 values in the cache - the sha1 in the\n> file, and if that is the ID of a tag object, we would also put the\n> sha1 of the commit that the tag points to in the cache.\n\nNow that's not a bad idea. Hacking it in to Linus's scheme, that's\n\n\\t\\tfoo\n\n\nA couple of thoughts:\n1) I bet Hans Reiser is enjoying this; he's been agitating for better\n lots-of-small-files support for years.\n\n2) Since I've written about two caches in a few minutes (here\n and in git-rev-list), a standardized cache validation hook for\n git-fsck-objects and git-prune's use might be useful.\n\n3) If we use Linus's idea of a flat \"static refs\" file overridden by loose\n refs (presumably, refs would be stuffed in if their mod times got old\n enough, and on initial import you'd use the timestamp of the commit\n they point to), we'll have to do a bit of a dance to move refs to and\n from it.\n\n Basically, to move refs into the refs file, it's\n - Read all the old refs and loose refs and write the new refs file.\n - Rename the new refs file into place.\n - For each loose ref moved in, lock it, verify it hasn'd changed,\n and delete it.\n with some more locking to prevent two people from doing this at once.\n\n Folks looking up tags will do an FS search, then validate their refs\n file cache, then if necessary, suck in the refs file.\n\n Now, exploding a refs file into loose refs is tricky. There's\n the possible race condition with a reader:\n\n A: Looks for loose ref \"foo\", doesn't find it.\n\t\tB: Write out loose ref \"foo\"\n\t\tB: Deletes now-unpacked refs file\n A: Looks for refs file, doesn't find it.\n A: Concludes that ref \"foo\" doesn't exist.\n\n The only solution I can think of is to stat the refs file at the\n start of the operation and restart from the beginning if it changes\n by the time it actually opens and read it.\n"},{"id":"26736","messageId":"9e4733910609110801p19ab39q5ef62bb60b89abb5@mail.gmail.com","threadId":"5513","inReplyTo":"20060911142644.32313.qmail@science.horizon.com","subject":"Re: Change set based shallow clone","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-11T15:01:49Z","receivedAt":"2006-09-11T15:01:49Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 11 Sep 2006 10:26:44 -0400, linux@horizon.com wrote:\n> > Could we do a cache of the refs that stores the stat information for\n> > each of the files under .git/refs plus the sha1 that the ref points\n> > to? In other words this cache would do for the refs what the index\n> > does for the working directory. Reading all the refs would mean we\n> > still had to stat each of the files, but that's much quicker than\n> > reading them in the cold-cache case. In the common case when most of\n> > the stat information matches, we don't have to read the file because\n> > we have the sha1 that the file contains right there in the cache.\n>\n> Well, that could save one of two seeks, but that's not *much* quicker.\n> (Indeed, a git ref would fit into the 60 bytes of block pointer space\n> in an ext2/3 inode if regular files were stuffed there as well as symlinks.)\n\nDoes everyone hate my idea of putting the sha in the file name and\nusing the directory structure as a simple database with locking? No\none made any comments.\n\n------------------------------------------------\nHere's a hack, instead of of putting the sha inside the file, put the\nsha into the filename.\n\nmaster_86a8534ba23a5532f6d0ddd01ecd8f02f662cf78\n\nNow you can just do a directory listing and get all of the data\nquickly. To keep the existing porcelain working add a symlink.\n\nln -s master_86a8534ba23a5532f6d0ddd01ecd8f02f662cf78 master\n\nYou might want the sha1 encoded names in a new director\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26738","messageId":"7vy7sqic4e.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"20060911142644.32313.qmail@science.horizon.com","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-11T16:47:29Z","receivedAt":"2006-09-11T16:47:29Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"linux@horizon.com writes:\n\n>> Ideally we would have two sha1 values in the cache - the sha1 in the\n>> file, and if that is the ID of a tag object, we would also put the\n>> sha1 of the commit that the tag points to in the cache.\n>\n> Now that's not a bad idea. Hacking it in to Linus's scheme, that's\n>\n> \\t\\tfoo\n\nThat's a dubious idea.\n\n - Why assume a tag points directly at a commit, or if it is\n not, why assume \"foo^{}\" (dereferencing repeatedly until we\n get a non-tag) is special?\n\n - Why assume the user wants access to only the object name of\n what the tag points at? Perhaps most users would want to\n have its type, dates (committer and author), and probably the\n first line of the commit message if it is (and most likely it\n is) a commit? -- at least gitweb and gitk would want these.\n\nYou should separate the issue of the internal data structure\nimplementation and programming interface for Porcelains. From\nthe internal data structure point-of-view, the second one is a\nredundant piece of information. Caching it _would_ speed up the\naccess to it, but then the issue becomes where we draw the line\nto stop.\n\nIt is probably more useful to think about what kind of\ninformation formatted in what way is often wanted by Porcelains\nwho want to grab many refs in one-go. If you can come up with a\nset that can satisfy everybody using that as the cache file\nformat would be fine, but I strongly doubt you can satisfy\neverybody. In which case, thinking about the ways for the\nPorcelain to express flexibly what information is wanted and\nformatted in what way, and have a command to access that\n(git-show-refs, anybody?) would be more fruitful, and at that\npoint, the internal representation of the cached data becomes\nthe implementation detail.\n"},{"id":"26739","messageId":"20060911175230.GA7213@spearce.org","threadId":"5513","inReplyTo":"7vr6yikhdj.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-11T17:52:30Z","receivedAt":"2006-09-11T17:52:30Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> As you know I've shelved the 64-bit offset stuff. My preference\n> is to base it on 106d710b but basing it on 'next' would be fine.\n> Between 106d710b and next there is only one unrelated change to\n> sha1_file.c, which is the hexval[] change that is in 'master'.\n\nOK. I'll rebase on 106d710b and try to get the series out in a day\nor two.\n \n> So far I liked the per-object-type dictionary conjecture the\n> most, primarily because my gut feeling tells me that it would\n> involve the least amount of hassle in the interoperability area.\n\nAgreed, except I don't think its going to save us very much (~4%)\nand its enough of a change still to make things a little ugly.\nIf the \"true\" dictionary compression idea has any value it may\nsave us even more and make it easier to implement fast full text\nsearching across files. But its definately more complex. So I'm\ngoing to shut up now.\n \n> But honestly speaking I am not looking forward to a packfile\n> format update at this moment. I'd like things to settle down a\n> bit now, after merging good bits from 'next' to 'master' and\n> declare 1.4.3 first, perhaps by the end of the month.\n\nNo worry there. I won't have enough time between now and the end\nof this month to create a dictionary pack that's even ready for pu,\nlet alone next. I hope we see 1.4.3 before then. :-)\n\n-- \nShawn.\n"},{"id":"26740","messageId":"7v8xkqgrnz.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"Pine.LNX.4.64.0609102002300.27779@g5.osdl.org","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-11T18:54:40Z","receivedAt":"2006-09-11T18:54:40Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Sun, 10 Sep 2006, Linus Torvalds wrote:\n>> \n>> If we did the same pack-file approach that we do for objects, the problem \n>> ends up being that _updating_ things is really hard. What we could do (and \n>> might work) is that a \"git repack\" would create a \"packed representation \n>> of the heads too\".\n>\n> To clarify: I'm _not_ suggesting actually using the \"pack-file\" \n> representation itself for the references.\n>\n> I'm saying that we could have something like a\n>\n> \t.git/refs-packed\n>\n> file, which could be (for example) just a plain linear text-file, of the \n> form\n>\n> \t19ed368b17abfb9ad5c7467ea74fd8a045d96b43\trefs/heads/html\n> \t60a6bf5f53635005f4f68d8b8a33172309193623\trefs/heads/maint\n> \t2d32e76f893b2ac432201ce7596c8bab691691e6\trefs/heads/man\n>...\n> \t9165ec17fde255a1770886189359897dbb541012\trefs/tags/v0.99.7c\n> \t02b2acff8bafb6d73c6513469cdda0c6c18c4138\trefs/tags/v0.99.7d\n> \t...\n>\n> ie it would contain just a linear file with the \"\"\n> format.\n\nThis depends on how expensive it is to read a file backwards,\nbut it might make sense to have a single append-only file.\n\n${GIT_DIR}/refs-packed file would be a sequence of records, each\nrecord is of form:\n\n\ttype SP timestamp LF payload LF length LF\n\nwhere length and timestamp are ASCII integers, the former is the\nlength of this record and you would use to compute the file\noffset you give lseek() to seek back to the beginning of this\nrecord. The latter is the creation time of this record. The\ntype of the record is either full or incremental (perhaps 'F'\nand 'I').\n\nA full record describes in the above \"object-name refname\" tuple\nformat. An incremental record has entries only for the subset\nof refs, with 0{40} object name denoting deletion of a ref as in\nyour suggestion.\n\nA few nice things about this representation:\n\n - It gives reflog for free (we need to add 'author' and\n 'reason' encoded after timestamp, though); it also gives\n reflog to tags which I sometimes miss.\n\n - Garbage collection is straightforward, although it requires\n locking the whole refs.\n\n - You can now have 'foo' and 'foo/a', 'foo/b', branches at the\n same time. It is natural to organize a topic branch 'foo'\n which consists of a merge of subtopics 'foo/a', 'foo/b', ...,\n but this cannot be expressed with the current directory-file\n based scheme.\n\nSome minor details:\n\n - After every N (I do not think we would need to make this\n configurable, but we need to decide on a sane value) updates,\n we would want to write a full record so that we do not have\n to traverse too long a chain.\n\n - An incremental record could be delta since the last full,\n instead of delta since the last record, as the above\n introduction hints. If we start from A, B, and C, and then A\n and B are modified in turn, we might have:\n\n\tFull: A B C\n Incr: A'\n Incr: B'\n\n but we could have instead:\n\n\tFull: A B C\n Incr: A'\n Incr: A' B'\n\n For this to make sense, the record header needs to record a\n back-pointer to the last full record before the current\n incremental record. With that, we would need to read at most\n two records to find out the current status.\n\nLocking between writers and readers can become problematic. The\nreader would read the last line to find the record length, seek\nthat much back to find the beginning of the \"then-latest\"\nrecord, but when there is a simultanous writer, there is no\nguarantee that what at the last line of the file _is_ the length\nof the last record. The writer may be in the middle of\nappending something. We may be able to work it around by:\n\n - Add hash of the record at the end;\n\n - The reader assumes that there is usually no collision, reads\n the hash and the length, seeks back and reads the record and\n validate the hash -- if the hash does not match, it is likely\n that it detected the writer-reader collision so it should\n wait until the file grows and stops growing and then retry.\n\nBut writer-writer contention obviously needs a file lock. Maybe\nwe can use flock/lockf/fcntl(F_SETLKW)? If we are going to do\nthat then protecting the reader-writer side with the same\nmechanism may be simpler and cleaner.\n\n> NOTE! It's important that whatever sceme used gets locking right. The \n> above suggestion gets it right simply because it doesn't really _change_ \n> anything. Any new or modified ref ends up using the old code, and using a \n> \".lock\" file and renaming it automatically does the same thing it ever \n> did.\n\nThe above changes things quite a bit, so locking aspect of it\nneeds to be thought through thouroughly.\n"},{"id":"26746","messageId":"17669.55963.930152.564529@cargo.ozlabs.ibm.com","threadId":"5513","inReplyTo":"7vy7sqic4e.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2006-09-11T21:52:27Z","receivedAt":"2006-09-11T21:52:27Z","isPatch":false,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Junio C Hamano writes:\n\n> That's a dubious idea.\n> \n> - Why assume a tag points directly at a commit, or if it is\n> not, why assume \"foo^{}\" (dereferencing repeatedly until we\n> get a non-tag) is special?\n\nUmm, I'm not sure what you're getting at here - if one shouldn't make\nthose assumptions, why does git ls-remote output both the tag and\ntag^{} lines?\n\n> - Why assume the user wants access to only the object name of\n> what the tag points at? Perhaps most users would want to\n> have its type, dates (committer and author), and probably the\n> first line of the commit message if it is (and most likely it\n> is) a commit? -- at least gitweb and gitk would want these.\n\nThere are two things here. Gitk needs to know which IDs have tags\nwhen displaying the graph, and their names. It doesn't need to know\nthe other details until someone clicks on the commit or the tag. Thus\nthe information that needs to be collected for every tag at startup is\njust the name and the sha1 id of the commit it eventually points to\n(if it doesn't eventually point to a commit it's basically not\ninteresting).\n\nPaul.\n"},{"id":"26751","messageId":"7v1wqige41.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"17669.55963.930152.564529@cargo.ozlabs.ibm.com","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-11T23:47:26Z","receivedAt":"2006-09-11T23:47:26Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Paul Mackerras writes:\n\n> Junio C Hamano writes:\n>\n>> That's a dubious idea.\n>> \n>> - Why assume a tag points directly at a commit, or if it is\n>> not, why assume \"foo^{}\" (dereferencing repeatedly until we\n>> get a non-tag) is special?\n>\n> Umm, I'm not sure what you're getting at here - if one shouldn't make\n> those assumptions, why does git ls-remote output both the tag and\n> tag^{} lines?\n\nThis was originally done to support Cogito's tag following which\nwas in its infancy. So in that sense it is already special (iow\nwe know one user that can take advantage of it), but my point\nwas that its usefulness for a commit chain fetching application\n(i.e. Cogito) does not automatically mean it is also useful for\nvisualizers like gitk and gitweb.\n"},{"id":"26755","messageId":"ee4tmo$mhm$1@sea.gmane.org","threadId":"5513","inReplyTo":"7v1wqige41.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-09-12T00:06:56Z","receivedAt":"2006-09-12T00:06:56Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Junio C Hamano wrote:\n\n> Paul Mackerras writes:\n> \n>> Junio C Hamano writes:\n>>\n>>> That's a dubious idea.\n>>> \n>>> - Why assume a tag points directly at a commit, or if it is\n>>> not, why assume \"foo^{}\" (dereferencing repeatedly until we\n>>> get a non-tag) is special?\n>>\n>> Umm, I'm not sure what you're getting at here - if one shouldn't make\n>> those assumptions, why does git ls-remote output both the tag and\n>> tag^{} lines?\n> \n> This was originally done to support Cogito's tag following which\n> was in its infancy. So in that sense it is already special (iow\n> we know one user that can take advantage of it), but my point\n> was that its usefulness for a commit chain fetching application\n> (i.e. Cogito) does not automatically mean it is also useful for\n> visualizers like gitk and gitweb.\n\nActually 'git ls-remote .' _is_ useful for gitweb, see the new \ngit_get_references code. \n\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"26756","messageId":"7vodtmey30.fsf@assigned-by-dhcp.cox.net","threadId":"5513","inReplyTo":"ee4tmo$mhm$1@sea.gmane.org","subject":"Re: Change set based shallow clone","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-12T00:18:59Z","receivedAt":"2006-09-12T00:18:59Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jakub Narebski writes:\n\n> Actually 'git ls-remote .' _is_ useful for gitweb, see the new \n> git_get_references code. \n\nYou are missing the point.\n\nWe are not discussing if having foo^{} is useful. There is no\nargument about it. Without it the user is forced to ask\nrev-parse.\n\nThe point is if it is Ok to assume foo and foo^{} (and nothing\nelse) are enough to make Porcelains and visualizers happy, and I\nsuspected the answer was no (remember show-ref discussion?).\n"},{"id":"26757","messageId":"ee4uos$oq7$1@sea.gmane.org","threadId":"5513","inReplyTo":"7vodtmey30.fsf@assigned-by-dhcp.cox.net","subject":"Re: Change set based shallow clone","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-09-12T00:25:08Z","receivedAt":"2006-09-12T00:25:08Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Junio C Hamano wrote:\n\n> Jakub Narebski writes:\n> \n>> Actually 'git ls-remote .' _is_ useful for gitweb, see the new \n>> git_get_references code. \n> \n> You are missing the point.\n> \n> We are not discussing if having foo^{} is useful. There is no\n> argument about it. Without it the user is forced to ask\n> rev-parse.\n> \n> The point is if it is Ok to assume foo and foo^{} (and nothing\n> else) are enough to make Porcelains and visualizers happy, and I\n> suspected the answer was no (remember show-ref discussion?).\n\nWell, it is enough for ref markers (this commit is this head or tag), for\ndumb http transport (indo/refs output is the same as ls-remote), and not\nmuch else... \n\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"}]}