{"thread":{"id":"31661","subject":"Re: Commit cache to speed up rev-list and merge","startedAt":"2012-09-27T15:51:51Z","lastAt":"2012-10-01T05:16:34Z","messageCount":10,"participants":["Shawn Pearce","Jeff King","Nguyen Thai Ngoc Duy"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"200014","messageId":"CAJo=hJtoqYEL5YiKawCt_SsSUqfCeYEQzY8Ntyb91cNfNS1w_Q@mail.gmail.com","threadId":"31661","inReplyTo":null,"subject":"Re: Commit cache to speed up rev-list and merge","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-09-27T15:51:51Z","receivedAt":"2012-09-27T15:51:51Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Sep 27, 2012 at 5:17 AM, Nguyen Thai Ngoc Duy wrote:\n> I'd like to see some sort of extension mechanism like in\n> $GIT_DIR/index, so that we don't have to increase pack index version\n> often. What I have in mind is optional commit cache to speed up\n> rev-list and merge, which could be stored in pack index too.\n\nCan you share some of your ideas?\n\nIn Linus' Linux kernel tree there are currently about 323,178 commits.\nIf we store just the pre-parsed commit time as an int32 field this is\nan additional 1.2 MiB of data in the pack-*.idx file, assuming we can\nuse additional data like pack offset position to correlate commit to\nthe parsed int. If we stored parent pointers in a similar way you\nprobably need at least 3.6 MiB of additional disk space on the index.\nFor example, use 12 bytes for each commit to store enough of the\nparsed commit time to sort commits, and up to 2 parent pointers per\ncommit.... with a reserved magic value for octopus merges to mean the\ncommit itself has to be parsed to get the graph structure correct.\n"},{"id":"200025","messageId":"20120927173932.GE1547@sigill.intra.peff.net","threadId":"31661","inReplyTo":"CAJo=hJtoqYEL5YiKawCt_SsSUqfCeYEQzY8Ntyb91cNfNS1w_Q@mail.gmail.com","subject":"Re: Commit cache to speed up rev-list and merge","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-09-27T17:39:32Z","receivedAt":"2012-09-27T17:39:32Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Sep 27, 2012 at 08:51:51AM -0700, Shawn O. Pearce wrote:\n\n> On Thu, Sep 27, 2012 at 5:17 AM, Nguyen Thai Ngoc Duy wrote:\n> > I'd like to see some sort of extension mechanism like in\n> > $GIT_DIR/index, so that we don't have to increase pack index version\n> > often. What I have in mind is optional commit cache to speed up\n> > rev-list and merge, which could be stored in pack index too.\n> \n> Can you share some of your ideas?\n\nSome of it is here:\n\n http://article.gmane.org/gmane.comp.version-control.git/203308\n\n-Peff\n"},{"id":"200027","messageId":"CAJo=hJtus46UGyTcnfTDArp=RkK-P24wO8pjhEY7qAmssyxgVA@mail.gmail.com","threadId":"31661","inReplyTo":"20120927173932.GE1547@sigill.intra.peff.net","subject":"Re: Commit cache to speed up rev-list and merge","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-09-27T17:45:32Z","receivedAt":"2012-09-27T17:45:32Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Sep 27, 2012 at 10:39 AM, Jeff King wrote:\n> On Thu, Sep 27, 2012 at 08:51:51AM -0700, Shawn O. Pearce wrote:\n>> On Thu, Sep 27, 2012 at 5:17 AM, Nguyen Thai Ngoc Duy wrote:\n>> > I'd like to see some sort of extension mechanism like in\n>> > $GIT_DIR/index, so that we don't have to increase pack index version\n>> > often. What I have in mind is optional commit cache to speed up\n>> > rev-list and merge, which could be stored in pack index too.\n>>\n>> Can you share some of your ideas?\n>\n> Some of it is here:\n>\n> http://article.gmane.org/gmane.comp.version-control.git/203308\n\nQuoting from that patch:\n\nOn 2012-08-12 Nguyen Thai Ngoc Duy wrote:\n> Long term we might gain slight lookup speedup if we know object type\n> as search region is made smaller. But for that to happen, we need to\n> propagate object type hint down to find_pack_entry_one() and friends.\n> Possible thing to do, I think.\n\nI'm not sure reclustering the index by object type is going to make a\nworthwhile difference. Of 2.2m objects in the Linux tree, 320k are\ncommits. The difference between doing the binary search through all\nobjects vs. just commits is only 2 iterations more of binary search if\nwe assume the per-type ranges have their own fan-out tables.\n\n> The main reason to group objects by type is to make it possible to\n> create another sha1->something mapping for a particular object type,\n> without wasting space for storing sha-1 keys again. For example, we\n> can store commit caches, tree caches... at the end of the index as\n> extensions.\n\nUsing ordinal position in the pack also works, and doesn't require\nclustering objects by type.\n"},{"id":"200034","messageId":"20120927183244.GB2519@sigill.intra.peff.net","threadId":"31661","inReplyTo":"CAJo=hJtus46UGyTcnfTDArp=RkK-P24wO8pjhEY7qAmssyxgVA@mail.gmail.com","subject":"Re: Commit cache to speed up rev-list and merge","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-09-27T18:32:44Z","receivedAt":"2012-09-27T18:32:44Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Sep 27, 2012 at 10:45:32AM -0700, Shawn O. Pearce wrote:\n\n> On 2012-08-12 Nguyen Thai Ngoc Duy wrote:\n> > Long term we might gain slight lookup speedup if we know object type\n> > as search region is made smaller. But for that to happen, we need to\n> > propagate object type hint down to find_pack_entry_one() and friends.\n> > Possible thing to do, I think.\n> \n> I'm not sure reclustering the index by object type is going to make a\n> worthwhile difference. Of 2.2m objects in the Linux tree, 320k are\n> commits. The difference between doing the binary search through all\n> objects vs. just commits is only 2 iterations more of binary search if\n> we assume the per-type ranges have their own fan-out tables.\n\nTo me the big win would be implicit indexing for items that are present\nfor every instance of a particular object type. So if we wanted to keep\nthe timestamp for every commit, you could have a \"pack-*.timestamps\"\nthat is literally just a packed list of uint32's, one per commit, where\nthe position of a commit's timestamp in the list is the same as its\nposition in the index of sha1s in the pack index.\n\nThat's simple to do if your index is just commits. But if it includes\nall objects, then your list is sparse. So either you waste space by\nmaking an empty slot for the non-commit objects, or you have an extra\nlevel of indirection mapping the commit into the packed list, which is\ngoing to double the storage in this case (though you could reuse that\nextra mapping for the parent, generation number, etc, so it at least\ngets amortized as you store more data). Or is there some clever solution\nI'm missing?\n\nFor your extension, I don't think it matters. You're sparse even in the\ncommit-object space, so you have to store the mapping anyway. And your\ndata is big enough that the overhead isn't too painful.\n\n-Peff\n"},{"id":"200063","messageId":"CACsJy8AodZgikh0Fq3=asUx94bx1_mdNNHzuuprNm8czXkbKxA@mail.gmail.com","threadId":"31661","inReplyTo":"20120927173932.GE1547@sigill.intra.peff.net","subject":"Re: Commit cache to speed up rev-list and merge","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-09-28T01:43:26Z","receivedAt":"2012-09-28T01:43:26Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Sep 28, 2012 at 12:39 AM, Jeff King wrote:\n> On Thu, Sep 27, 2012 at 08:51:51AM -0700, Shawn O. Pearce wrote:\n>\n>> On Thu, Sep 27, 2012 at 5:17 AM, Nguyen Thai Ngoc Duy wrote:\n>> > I'd like to see some sort of extension mechanism like in\n>> > $GIT_DIR/index, so that we don't have to increase pack index version\n>> > often. What I have in mind is optional commit cache to speed up\n>> > rev-list and merge, which could be stored in pack index too.\n>>\n>> Can you share some of your ideas?\n>\n> Some of it is here:\n>\n> http://article.gmane.org/gmane.comp.version-control.git/203308\n\nAnd an experiment was done earlier\n\nhttp://thread.gmane.org/gmane.comp.version-control.git/194306/focus=194596\n-- \nDuy\n"},{"id":"200064","messageId":"CACsJy8APNsDrTH+hUxgcB=MY0eECCGktm6P1feEEpz2427OQqg@mail.gmail.com","threadId":"31661","inReplyTo":"CAJo=hJtoqYEL5YiKawCt_SsSUqfCeYEQzY8Ntyb91cNfNS1w_Q@mail.gmail.com","subject":"Re: Commit cache to speed up rev-list and merge","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-09-28T02:14:54Z","receivedAt":"2012-09-28T02:14:54Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Sep 27, 2012 at 10:51 PM, Shawn Pearce wrote:\n> In Linus' Linux kernel tree there are currently about 323,178 commits.\n> If we store just the pre-parsed commit time as an int32 field this is\n> an additional 1.2 MiB of data in the pack-*.idx file, assuming we can\n> use additional data like pack offset position to correlate commit to\n> the parsed int. If we stored parent pointers in a similar way you\n> probably need at least 3.6 MiB of additional disk space on the index.\n> For example, use 12 bytes for each commit to store enough of the\n> parsed commit time to sort commits, and up to 2 parent pointers per\n> commit.... with a reserved magic value for octopus merges to mean the\n> commit itself has to be parsed to get the graph structure correct.\n\nThis is much better than my naive approach (storing sha-1 and\ntimestamps). We could use less space by storing parent pointer of\nnon-merge commits only. Merge commits linux-2.6 is 6% the number of\ncommits. git.git has higher percentage, 21%. I bet many projects do\nnot merge as much and the number of merge commits is less than 5%.\n-- \nDuy\n"},{"id":"200230","messageId":"CAJo=hJtweVTOUT84U1=ONnjQXz5Rt_sDYD2BjUP9tOQ4HDj6Kg@mail.gmail.com","threadId":"31661","inReplyTo":"CACsJy8APNsDrTH+hUxgcB=MY0eECCGktm6P1feEEpz2427OQqg@mail.gmail.com","subject":"Re: Commit cache to speed up rev-list and merge","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-10-01T01:49:24Z","receivedAt":"2012-10-01T01:49:24Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Sep 27, 2012 at 7:14 PM, Nguyen Thai Ngoc Duy wrote:\n> On Thu, Sep 27, 2012 at 10:51 PM, Shawn Pearce wrote:\n>> In Linus' Linux kernel tree there are currently about 323,178 commits.\n>> If we store just the pre-parsed commit time as an int32 field this is\n>> an additional 1.2 MiB of data in the pack-*.idx file, assuming we can\n>> use additional data like pack offset position to correlate commit to\n>> the parsed int. If we stored parent pointers in a similar way you\n>> probably need at least 3.6 MiB of additional disk space on the index.\n>> For example, use 12 bytes for each commit to store enough of the\n>> parsed commit time to sort commits, and up to 2 parent pointers per\n>> commit.... with a reserved magic value for octopus merges to mean the\n>> commit itself has to be parsed to get the graph structure correct.\n>\n> This is much better than my naive approach (storing sha-1 and\n> timestamps). We could use less space by storing parent pointer of\n> non-merge commits only. Merge commits linux-2.6 is 6% the number of\n> commits. git.git has higher percentage, 21%. I bet many projects do\n> not merge as much and the number of merge commits is less than 5%.\n\nSome projects merge quite often. Android's frameworks/base repository\nhas a very large number of merges. Out of 79905 commits reachable from\nthe master branch, 65.3% are merges. So actually there are more merge\ncommits in the Android history than there are code commits. A cache of\nonly non-merges may be worthless on such a history.\n"},{"id":"200232","messageId":"CACsJy8BY2DFhgqdwQdm58+rCuwDj8-7xtqUV9S5cbErU36+zPQ@mail.gmail.com","threadId":"31661","inReplyTo":"CAJo=hJtweVTOUT84U1=ONnjQXz5Rt_sDYD2BjUP9tOQ4HDj6Kg@mail.gmail.com","subject":"Re: Commit cache to speed up rev-list and merge","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-10-01T02:05:48Z","receivedAt":"2012-10-01T02:05:48Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Oct 1, 2012 at 8:49 AM, Shawn Pearce wrote:\n> On Thu, Sep 27, 2012 at 7:14 PM, Nguyen Thai Ngoc Duy wrote:\n>> On Thu, Sep 27, 2012 at 10:51 PM, Shawn Pearce wrote:\n>>> In Linus' Linux kernel tree there are currently about 323,178 commits.\n>>> If we store just the pre-parsed commit time as an int32 field this is\n>>> an additional 1.2 MiB of data in the pack-*.idx file, assuming we can\n>>> use additional data like pack offset position to correlate commit to\n>>> the parsed int. If we stored parent pointers in a similar way you\n>>> probably need at least 3.6 MiB of additional disk space on the index.\n>>> For example, use 12 bytes for each commit to store enough of the\n>>> parsed commit time to sort commits, and up to 2 parent pointers per\n>>> commit.... with a reserved magic value for octopus merges to mean the\n>>> commit itself has to be parsed to get the graph structure correct.\n>>\n>> This is much better than my naive approach (storing sha-1 and\n>> timestamps). We could use less space by storing parent pointer of\n>> non-merge commits only. Merge commits linux-2.6 is 6% the number of\n>> commits. git.git has higher percentage, 21%. I bet many projects do\n>> not merge as much and the number of merge commits is less than 5%.\n>\n> Some projects merge quite often. Android's frameworks/base repository\n> has a very large number of merges. Out of 79905 commits reachable from\n> the master branch, 65.3% are merges. So actually there are more merge\n> commits in the Android history than there are code commits. A cache of\n> only non-merges may be worthless on such a history.\n\nThe good thing about these cache is it's configurable. Merge-preferred\nprojects can choose to cache the first two parents. Non-merge projects\ncan choose to cache just the first parent. We don't need a fixed\nformat for both.\n-- \nDuy\n"},{"id":"200234","messageId":"CAJo=hJsGptu8c04XQh0xLmMhz+mxYKAOQfhbjaNK887dY-jAMA@mail.gmail.com","threadId":"31661","inReplyTo":"CACsJy8BY2DFhgqdwQdm58+rCuwDj8-7xtqUV9S5cbErU36+zPQ@mail.gmail.com","subject":"Re: Commit cache to speed up rev-list and merge","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-10-01T02:27:56Z","receivedAt":"2012-10-01T02:27:56Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sun, Sep 30, 2012 at 7:05 PM, Nguyen Thai Ngoc Duy wrote:\n> On Mon, Oct 1, 2012 at 8:49 AM, Shawn Pearce wrote:\n>> On Thu, Sep 27, 2012 at 7:14 PM, Nguyen Thai Ngoc Duy wrote:\n>>> On Thu, Sep 27, 2012 at 10:51 PM, Shawn Pearce wrote:\n>>>> In Linus' Linux kernel tree there are currently about 323,178 commits.\n>>>> If we store just the pre-parsed commit time as an int32 field this is\n>>>> an additional 1.2 MiB of data in the pack-*.idx file, assuming we can\n>>>> use additional data like pack offset position to correlate commit to\n>>>> the parsed int. If we stored parent pointers in a similar way you\n>>>> probably need at least 3.6 MiB of additional disk space on the index.\n>>>> For example, use 12 bytes for each commit to store enough of the\n>>>> parsed commit time to sort commits, and up to 2 parent pointers per\n>>>> commit.... with a reserved magic value for octopus merges to mean the\n>>>> commit itself has to be parsed to get the graph structure correct.\n>>>\n>>> This is much better than my naive approach (storing sha-1 and\n>>> timestamps). We could use less space by storing parent pointer of\n>>> non-merge commits only. Merge commits linux-2.6 is 6% the number of\n>>> commits. git.git has higher percentage, 21%. I bet many projects do\n>>> not merge as much and the number of merge commits is less than 5%.\n>>\n>> Some projects merge quite often. Android's frameworks/base repository\n>> has a very large number of merges. Out of 79905 commits reachable from\n>> the master branch, 65.3% are merges. So actually there are more merge\n>> commits in the Android history than there are code commits. A cache of\n>> only non-merges may be worthless on such a history.\n>\n> The good thing about these cache is it's configurable. Merge-preferred\n> projects can choose to cache the first two parents. Non-merge projects\n> can choose to cache just the first parent. We don't need a fixed\n> format for both.\n\nGit has enough magic switches. It doesn't need yet another magic\nswitch that one group of users needs to set, and another can safely\nignore because their project's usage just happens to align with Linus\nTorvald's current world view.\n"},{"id":"200240","messageId":"CACsJy8CQaOw9aUJDAoG+gg_n0=A-62KdwYukf-MbgXwCigr8xA@mail.gmail.com","threadId":"31661","inReplyTo":"CAJo=hJsGptu8c04XQh0xLmMhz+mxYKAOQfhbjaNK887dY-jAMA@mail.gmail.com","subject":"Re: Commit cache to speed up rev-list and merge","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-10-01T05:16:34Z","receivedAt":"2012-10-01T05:16:34Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Oct 1, 2012 at 9:27 AM, Shawn Pearce wrote:\n> Git has enough magic switches. It doesn't need yet another magic\n> switch that one group of users needs to set, and another can safely\n> ignore because their project's usage just happens to align with Linus\n> Torvald's current world view.\n\nI see it as tuning, not switching. It's like setting the number of\ncommits where bitmaps are taken. We can see the commit cache as a\ntable, where columns are commit properties. We have a column for date,\none for the first parent. Users can choose to have a third column for\nthe second parent, or another one for root tree sha-1. The\nimplementation could be made generic to support caching any \nsha1-columns.\n-- \nDuy\n"}]}