{"thread":{"id":"5523","subject":"Re: Change set based shallow clone","startedAt":"2006-09-09T10:31:57Z","lastAt":"2006-09-09T13:00:08Z","messageCount":2,"participants":["linux@horizon.com","Marco Costalba"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"26627","messageId":"20060909103157.23388.qmail@science.horizon.com","threadId":"5523","inReplyTo":null,"subject":"Re: Change set based shallow clone","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-09-09T10:31:57Z","receivedAt":"2006-09-09T10:31:57Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> If the out of order revisions are a small amount of the total then\n> could be possible to have something like\n> \n> git rev-list --topo-order --with-appended-fixups HEAD\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\nI don't think I understand your proposal.  The problem arises when\ngit-rev-list finds a commit that it should have listed before something\nthat it has already output.\n\nJust for example:\n\nCommit D: Ancestor B\nCommit B: Ancestor A\nCommit C: Ancestor B\n\nCommit C is the problem, because if git-rev-list has already output B,\nthere's no way to back up and insert it in the right place.\n\nHow is waiting to output the already-behind-schedule commit C going\nto help anything?  The idea in gitk is to rewind the layout algorithm\nto before B was added, insert C, and replay from there.  This is\nmost efficient if C is encountered as soon after its correct place\nas possible.\n"},{"id":"26630","messageId":"e5bfff550609090600k4e4b1ae0s1cbee5e3fa01cba@mail.gmail.com","threadId":"5523","inReplyTo":"20060909103157.23388.qmail@science.horizon.com","subject":"Re: Change set based shallow clone","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2006-09-09T13:00:08Z","receivedAt":"2006-09-09T13:00:08Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 9 Sep 2006 06:31:57 -0400, linux@horizon.com <linux@horizon.com> wrote:\n> > If the out of order revisions are a small amount of the total then\n> > could be possible to have something like\n> >\n> > git rev-list --topo-order --with-appended-fixups HEAD\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>\n> I don't think I understand your proposal.  The problem arises when\n> git-rev-list finds a commit that it should have listed before something\n> that it has already output.\n>\n> Just for example:\n>\n> Commit D: Ancestor B\n> Commit B: Ancestor A\n> Commit C: Ancestor B\n>\n> Commit C is the problem, because if git-rev-list has already output B,\n> there's no way to back up and insert it in the right place.\n>\n> How is waiting to output the already-behind-schedule commit C going\n> to help anything?\n\nIt helps in a number of ways from receiver point of view.\n\n- Receiver doesn't need to keep a sorted list of loaded revisions.\n\n- Receiver doesn't need to stop parsing input and redraw the graph in\nthe middle of the loading.\n\n- Receiver doesn't need to  check for possible out of order commits\nwhen loading data, but can be assured data that arrives is\n--topo-order consistent (although my not be complete)\n\n- Split the in order parsing code (performance critical and common\ncase) from fixup-code (run at the end and on a small set of commits).\n\n- Much faster implementation because the sorting is done only in\ngit-rev-list and only once.\n\nFollowing your example my suggestion was something like this:\n\nInstead of:\n\ngit-rev-list HEAD\n\nCommit D: Ancestor B\nCommit B: Ancestor A\nCommit C: Ancestor B\nCommit A: Ancestor E\nCommit E: Ancestor F\nCommit F: Ancestor G\n....\nCommit V: Ancestor Z\n\ngit-rev-list --topo-order ----with-appended-fixups HEAD\n\nsends something like:\n\nCommit D: Ancestor B\nCommit B: Ancestor A\nCommit A: Ancestor E\nCommit E: Ancestor F\nCommit F: Ancestor G\n....\nCommit V: Ancestor Z\n(* end of correct sorted commits and start of out of order commits*)\nCommit C: Ancestor B\n......\nCommit  N: Ancestor M\n\nSo that receiver drawing code designed with working with --topo-order\nkind output could as usual draws the graph until Commit V: Ancestor Z\n(but without waiting for git-rev-list latency!!) and the new fixup\ncode could *at the end* loop across *already sorted* fixup set:\n\nCommit C: Ancestor B\n......\nCommit  N: Ancestor M\n\nand update the graph in one go. Of course some flag/syntax should be\nintroduced to trigger the end of sorted code and beginning of fixups\nin git-rev-list output stream.\n\n       Marco\n"}]}