{"thread":{"id":"38562","subject":"Pack v4 again..","startedAt":"2015-02-13T10:46:57Z","lastAt":"2015-02-17T04:12:33Z","messageCount":7,"participants":["Duy Nguyen","Nicolas Pitre","Jeff King","Junio C Hamano","Shawn Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"256058","messageId":"CACsJy8CMCTirggRhD28xvv4tM8b4+NL_ruF4LgW293dHAmLYdA@mail.gmail.com","threadId":"38562","inReplyTo":null,"subject":"Pack v4 again..","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2015-02-13T10:46:57Z","receivedAt":"2015-02-13T10:46:57Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"After taking 1.5 years \"vacation\" from pack v4, I plan to do something\nabout it again. Will post more when I have some patches to discuss.\nOnly one question for now (forgive me if I asked already, it's been\nquite some time)\n\nI think pack v4 does not deliver its best promise that walking a tree\nis simply following pointers and jumping from place to place. When we\nwant to copy from the middle of another tree, we need to scan from the\nbeginning of the tree. Tree offset cache helps, but the problem\nremains. What do you think about an alternative format that each\n\"copy\" instruction includes both index of the tree entry to copy from\n(i.e. what we store now)  _and_ the byte offset from the beginning of\nthe tree? With this byte offset, we know exactly where to start\ncopying without scanning from the beginning. It will be a bit(?)\nbigger, but it's also faster.\n\nI imagine this is an optimization that can be done locally. The pack\ntransferred over network does not have these byte offsets. After the\npack is stored and verified by index-pack, we can rewrite it and add\nthis info. The simplest way is use a fixed size for this offset (e.g.\nuint16_t or even uint8_t), add the place holder in copy instructions\nof all v4 trees. After that object offsets will not change again and\nwe can start filling real offsets to placeholders.\n\nPS. The rebased version on recent master is here if anyone is interested\n\nhttps://github.com/pclouds/git/commits/pack-v4\n-- \nDuy\n"},{"id":"256119","messageId":"alpine.LFD.2.11.1502152221480.22104@knanqh.ubzr","threadId":"38562","inReplyTo":"CACsJy8CMCTirggRhD28xvv4tM8b4+NL_ruF4LgW293dHAmLYdA@mail.gmail.com","subject":"Re: Pack v4 again..","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2015-02-16T04:59:02Z","receivedAt":"2015-02-16T04:59:02Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 13 Feb 2015, Duy Nguyen wrote:\n\n> After taking 1.5 years \"vacation\" from pack v4, I plan to do something\n> about it again. Will post more when I have some patches to discuss.\n> Only one question for now (forgive me if I asked already, it's been\n> quite some time)\n\nYeah.  I had to re-study my own code before replying.\n\n> I think pack v4 does not deliver its best promise that walking a tree\n> is simply following pointers and jumping from place to place. When we\n> want to copy from the middle of another tree, we need to scan from the\n> beginning of the tree. Tree offset cache helps, but the problem\n> remains. What do you think about an alternative format that each\n> \"copy\" instruction includes both index of the tree entry to copy from\n> (i.e. what we store now)  _and_ the byte offset from the beginning of\n> the tree? With this byte offset, we know exactly where to start\n> copying without scanning from the beginning. It will be a bit(?)\n> bigger, but it's also faster.\n\nThat would make the format inflexible.  If we want to do partial \nrepacking by, say, copying some objects and repacking others (some \nobjects might need repacking because the objects they refer to are \nomitted from the repack) then if those repacked objects are themselves \nreferred to by byte offset then we lose as the offset is no longer \nvalid.\n\n> I imagine this is an optimization that can be done locally. The pack\n> transferred over network does not have these byte offsets. After the\n> pack is stored and verified by index-pack, we can rewrite it and add\n> this info. The simplest way is use a fixed size for this offset (e.g.\n> uint16_t or even uint8_t), add the place holder in copy instructions\n> of all v4 trees. After that object offsets will not change again and\n> we can start filling real offsets to placeholders.\n\nHaving a local extra index is fine.  Just like the pack index which is \nalways created locally and can be recreated at any time.  Some tree \noffset cache might be beneficial, but I'd avoid making it into the pack \nfile itself.\n\nYet, I think the biggest problem with pack v4 at the moment is the \npacking algorithm for tree objects.  We are piggy-backing on the pack v2 \nobject delta compression sorting and that produces suboptimal results \ndue to deep recursions.  And it is the recursion that kills us. The pack \nv4 requires a new packing algorithm for its tree objects.\n\nWhat I imagined is something like this:\n\n- Each canonical tree entry is made of a SHA1, mode and path.  Let's \n  assume this is hashed into a 24-bit value.\n\n- Each tree object can therefore be represented as a string of 24-bit \n  \"characters\".\n\n- Delta-compressing a tree object becomes a substring search where we \n  try to replace a sequence of \"characters\" with the longest \"string\" \n  possible from another object.  Repeat with the remaining sequences.\n\nHaving a 24-bit hash value is totally arbitrary.  It could be 16 bits \nwith more collisions but much faster search and less memory usage.  The \noptimal value would need to be determined after some experimentation.\n\nAlgorithms for the longest common substring problem already exist.  So \none of the classical algorithms could probably be adapted here.\n\nThis would allow for exploiting the provision in pack v4 to copy from \nmore than one tree object.  And this would also favor shallower \nrecursions and even smaller packs.  Imposing a minimum substring length \n(rather than a maximum delta depth) would determine the runtime \nperformance when using the pack afterwards.\n\nIf you have enough free cycles to work on this, that's what I'd suggest \nyou explore at this point. I wish I could myself as I think this ought \nto be rather cool work.\n\n\nNicolas\n"},{"id":"256134","messageId":"20150216064537.GF32381@peff.net","threadId":"38562","inReplyTo":"alpine.LFD.2.11.1502152221480.22104@knanqh.ubzr","subject":"Re: Pack v4 again..","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-02-16T06:45:38Z","receivedAt":"2015-02-16T06:45:38Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Feb 15, 2015 at 11:59:02PM -0500, Nicolas Pitre wrote:\n\n> Yet, I think the biggest problem with pack v4 at the moment is the \n> packing algorithm for tree objects.  We are piggy-backing on the pack v2 \n> object delta compression sorting and that produces suboptimal results \n> due to deep recursions.  And it is the recursion that kills us. The pack \n> v4 requires a new packing algorithm for its tree objects.\n> \n> What I imagined is something like this:\n> \n> - Each canonical tree entry is made of a SHA1, mode and path.  Let's \n>   assume this is hashed into a 24-bit value.\n> \n> - Each tree object can therefore be represented as a string of 24-bit \n>   \"characters\".\n> \n> - Delta-compressing a tree object becomes a substring search where we \n>   try to replace a sequence of \"characters\" with the longest \"string\" \n>   possible from another object.  Repeat with the remaining sequences.\n\nSomewhat related to this, I was playing this weekend with the idea of\ngenerating fast tree diffs from our on-disk deltas. That is, given a\nbase tree and a binary delta against it, could I reliably reproduce a\ndiff (one way or the other) in O(size of diff), rather than O(size of\ntree)?\n\nI have two applications in mind:\n\n  1. Tree diffs for \"git log -- pathspec\" do the same diff (between a\n     tree and its corresponding version in the parent) over and over.\n     A significant percentage of the time (at least in linux.git and\n     git.git), we store deltas between these trees.  We could stop\n     wasting time walking the common parts of the trees, and jump right\n     to the differences.\n\n  2. Calculating reachability for packing[1] spends a lot of time in\n     lookup_object, as we have to go through each tree saying \"have we\n     seen object 1234abcd yet?\". If we could instead just view the\n     differences, we would not have to make those hash lookups for\n     entries whose objects we know we have seen.\n\nThe conclusion I came to was \"no, you cannot do it in the general case\nof byte-wise binary diffs\"[2].  Conceptually, it's not too difficult. For\nexample, if we know we have copied up to byte X from the source tree,\nthen we skip to byte Y, we know that bytes Y-X did not make it, and are\na deletion of entries. If those fall on whole-entry boundaries, it's\npretty simple. But of course we have no guarantee that they do in a\nbyte-wise diff. E.g., if entry \"foo\" changes its sha1, then we will\ngenerally copy up to and including the \"foo\\0\" from the source, and then\ninsert our own new sha1. Which means we need to walk backwards from\npoint \"Y\" to find the filename of the entry we are in. Or worse, the\nsha1s might share one or more leading bytes, and that would be part of\nthe copy, too.\n\nSo in short, we may end up anywhere within a tree object and need to\nwalk backwards to the start of the entry. But we cannot walk backwards\nlooking for a NUL, because it may also be part of a sha1. You can only\nreliably parse a git tree by starting at the beginning of the stream and\ngoing forwards[3].\n\nIf we knew that our deltas were always produced on entry-boundaries (a\n\"character\" in your description above), this would be much simpler.\n\nMaybe this is all stuff you already thought through, but if not, food\nfor thought. :)\n\n-Peff\n\n[1] Of course there are other reachability checks besides packing, like\n    git-prune. But all of those are even better sped up by using\n    reachability bitmaps. Packing, as the place where we generate the\n    bitmaps, and which is sensitive to things like traversal order,\n    remains the place where we will always need to actually walk.\n\n[2] One option, of course, is to generate byte-wise deltas, but with a\n    promise to always align them on entry boundaries. I'm tempted by\n    this, because the result would be readable by existing packv2\n    readers. We'd have to set a flag somewhere that indicates the pack\n    was written with this property, though.\n\n[3] I suspect you could come up with some heuristic that finds tree\n    entry boundaries with high probability, and in the low probability\n    case does not produce a wrong answer, but instead has to walk all\n    the way back to the beginning of the tree. That would be fine here.\n    But frankly, this \"walk backwards\" thing was just the straw that\n    broke the camel's back for me in working on this. Handling all the\n    possible cases was ending up quite complicated.\n"},{"id":"256136","messageId":"xmqqlhjy72jr.fsf@gitster.dls.corp.google.com","threadId":"38562","inReplyTo":"20150216064537.GF32381@peff.net","subject":"Re: Pack v4 again..","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-02-16T07:12:24Z","receivedAt":"2015-02-16T07:12:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n>   2. Calculating reachability for packing[1] spends a lot of time in\n>      lookup_object, as we have to go through each tree saying \"have we\n>      seen object 1234abcd yet?\". If we could instead just view the\n>      differences, we would not have to make those hash lookups for\n>      entries whose objects we know we have seen.\n\nHmm, that is an interesting idea.\n\n> So in short, we may end up anywhere within a tree object and need to\n> walk backwards to the start of the entry. But we cannot walk backwards\n> looking for a NUL, because it may also be part of a sha1. You can only\n> reliably parse a git tree by starting at the beginning of the stream and\n> going forwards[3].\n\nThat in general is true for non deltified tree object (you cannot\ntake advantage of the fact that entries are sorted by pathname to\nbisect to directly jump to an entry).\n\n> If we knew that our deltas were always produced on entry-boundaries (a\n> \"character\" in your description above), this would be much simpler.\n\n;-)\n\n> [2] One option, of course, is to generate byte-wise deltas, but with a\n>     promise to always align them on entry boundaries. I'm tempted by\n>     this, because the result would be readable by existing packv2\n>     readers. We'd have to set a flag somewhere that indicates the pack\n>     was written with this property, though.\n\nYes, that may work.\n"},{"id":"256142","messageId":"CACsJy8A46Xgnh8rsrvAXDGkNDA0fu-jCT3qtwpsHN2KTmsJGRw@mail.gmail.com","threadId":"38562","inReplyTo":"alpine.LFD.2.11.1502152221480.22104@knanqh.ubzr","subject":"Re: Pack v4 again..","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2015-02-16T10:11:18Z","receivedAt":"2015-02-16T10:11:18Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Feb 16, 2015 at 11:59 AM, Nicolas Pitre <nico@fluxnic.net> wrote:\n>> I think pack v4 does not deliver its best promise that walking a tree\n>> is simply following pointers and jumping from place to place. When we\n>> want to copy from the middle of another tree, we need to scan from the\n>> beginning of the tree. Tree offset cache helps, but the problem\n>> remains. What do you think about an alternative format that each\n>> \"copy\" instruction includes both index of the tree entry to copy from\n>> (i.e. what we store now)  _and_ the byte offset from the beginning of\n>> the tree? With this byte offset, we know exactly where to start\n>> copying without scanning from the beginning. It will be a bit(?)\n>> bigger, but it's also faster.\n>\n> That would make the format inflexible.  If we want to do partial\n> repacking by, say, copying some objects and repacking others (some\n> objects might need repacking because the objects they refer to are\n> omitted from the repack) then if those repacked objects are themselves\n> referred to by byte offset then we lose as the offset is no longer\n> valid.\n\nWhen generate new packs, we could rip out these offsets, but it\ndepends on whether we can reuse v4 trees unchanged like we do with v2\ndeltas. If we can, ripping is not an option because then we need to\nparse more.\n\n>> I imagine this is an optimization that can be done locally. The pack\n>> transferred over network does not have these byte offsets. After the\n>> pack is stored and verified by index-pack, we can rewrite it and add\n>> this info. The simplest way is use a fixed size for this offset (e.g.\n>> uint16_t or even uint8_t), add the place holder in copy instructions\n>> of all v4 trees. After that object offsets will not change again and\n>> we can start filling real offsets to placeholders.\n>\n> Having a local extra index is fine.  Just like the pack index which is\n> always created locally and can be recreated at any time.  Some tree\n> offset cache might be beneficial, but I'd avoid making it into the pack\n> file itself.\n\nHm.. right.\n\n> Yet, I think the biggest problem with pack v4 at the moment is the\n> packing algorithm for tree objects.  We are piggy-backing on the pack v2\n> object delta compression sorting and that produces suboptimal results\n> due to deep recursions.  And it is the recursion that kills us. The pack\n> v4 requires a new packing algorithm for its tree objects.\n\nYep. I made a conversion tool a few days ago to \"flatten\" v4 trees. So\nif tree A copies some entries from B, but then B copies from C, tree A\ncould copy directly from C. Performance improves significantly (close\nto v2 with rev-list, but still slower). But pack size doubles because\ncopy sequences are fragmented and we're duplicating same copy patterns\nover and over again. All because we follow the single delta chain\ndecided since v2 time so we only have one tree with no copy sequences\n(best to copy from).\n\n> What I imagined is something like this:\n>\n> - Each canonical tree entry is made of a SHA1, mode and path.  Let's\n>   assume this is hashed into a 24-bit value.\n>\n> - Each tree object can therefore be represented as a string of 24-bit\n>   \"characters\".\n>\n> - Delta-compressing a tree object becomes a substring search where we\n>   try to replace a sequence of \"characters\" with the longest \"string\"\n>   possible from another object.  Repeat with the remaining sequences.\n>\n> Having a 24-bit hash value is totally arbitrary.  It could be 16 bits\n> with more collisions but much faster search and less memory usage.  The\n> optimal value would need to be determined after some experimentation.\n>\n> Algorithms for the longest common substring problem already exist.  So\n> one of the classical algorithms could probably be adapted here.\n>\n> This would allow for exploiting the provision in pack v4 to copy from\n> more than one tree object.  And this would also favor shallower\n> recursions and even smaller packs.  Imposing a minimum substring length\n> (rather than a maximum delta depth) would determine the runtime\n> performance when using the pack afterwards.\n>\n> If you have enough free cycles to work on this, that's what I'd suggest\n> you explore at this point. I wish I could myself as I think this ought\n> to be rather cool work.\n\nI'm getting there. I'm writing an alternative implementation to your\npv4_encode_tree() that takes multiple base trees instead of just one,\nfinding all copy sequences from these bases, then somehow pick the\nbest ones. After trees are sorted by similarity in pack-objects, we\npreserve n trees as base trees (no copy sequences). There is a window\nto feed some of these base trees to this encode function, like how we\ndo it in try_delta().\n\nYour encoding tree entries as strings would be faster, but that's not\nthe immediate problem. Using the longest common substring is kinda\ngreedy (exactly what I'm thinking to do), but it probably produces a\nsuboptimal copy sequences. Maybe using two shorter copy sequences\nwould reduce fragmentation than one large copy sequence and a bunch of\nindividual tree entries, that sort of thing. Haven't worked it out\nyet..\n-- \nDuy\n"},{"id":"256145","messageId":"CACsJy8AP88yX39QSyF2nN-01TN=7-0rKc==ncSua14_GM4s+Fg@mail.gmail.com","threadId":"38562","inReplyTo":"20150216064537.GF32381@peff.net","subject":"Re: Pack v4 again..","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2015-02-16T10:48:28Z","receivedAt":"2015-02-16T10:48:28Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Feb 16, 2015 at 1:45 PM, Jeff King <peff@peff.net> wrote:\n> Somewhat related to this, I was playing this weekend with the idea of\n> generating fast tree diffs from our on-disk deltas. That is, given a\n> base tree and a binary delta against it, could I reliably reproduce a\n> diff (one way or the other) in O(size of diff), rather than O(size of\n> tree)?\n\nIf you add a \"delta\" base cache for v4 trees to avoid the recursion\nissue Nico mentioned, you effectively have a \"diff\" that aligns at\ntree entry boundaries. The v4 tree encoding will become just another\ndelta format from this perspective. I'm very tempted to just go with\nthis to take advantage of v4 SHA-1 encoding, ident and path encoding..\n-- \nDuy\n"},{"id":"256181","messageId":"CAJo=hJvR-3o3U3YWhvq4D-A6YomFbjwEyKxjT93EoNMRrW1PtQ@mail.gmail.com","threadId":"38562","inReplyTo":"20150216064537.GF32381@peff.net","subject":"Re: Pack v4 again..","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2015-02-17T04:12:33Z","receivedAt":"2015-02-17T04:12:33Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sun, Feb 15, 2015 at 10:45 PM, Jeff King <peff@peff.net> wrote:\n> On Sun, Feb 15, 2015 at 11:59:02PM -0500, Nicolas Pitre wrote:\n>\n>> Yet, I think the biggest problem with pack v4 at the moment is the\n>> packing algorithm for tree objects.  We are piggy-backing on the pack v2\n>> object delta compression sorting and that produces suboptimal results\n>> due to deep recursions.  And it is the recursion that kills us. The pack\n>> v4 requires a new packing algorithm for its tree objects.\n>>\n>> What I imagined is something like this:\n>>\n>> - Each canonical tree entry is made of a SHA1, mode and path.  Let's\n>>   assume this is hashed into a 24-bit value.\n>>\n>> - Each tree object can therefore be represented as a string of 24-bit\n>>   \"characters\".\n>>\n>> - Delta-compressing a tree object becomes a substring search where we\n>>   try to replace a sequence of \"characters\" with the longest \"string\"\n>>   possible from another object.  Repeat with the remaining sequences.\n>\n> Somewhat related to this, I was playing this weekend with the idea of\n> generating fast tree diffs from our on-disk deltas. That is, given a\n> base tree and a binary delta against it, could I reliably reproduce a\n> diff (one way or the other) in O(size of diff), rather than O(size of\n> tree)?\n\nYes, if you always make the tree diff *search* on entry boundaries.\n\n> The conclusion I came to was \"no, you cannot do it in the general case\n> of byte-wise binary diffs\"[2].\n\nThis is also why you cannot binary search inside of the canonical tree\nformat. :(\n\n> If we knew that our deltas were always produced on entry-boundaries (a\n> \"character\" in your description above), this would be much simpler.\n\nEons ago Nico and I were of the opinion that pack v4 trees could use\nthe existing byte based delta format on disk, but the delta\nsearch/encoder would always align to fixed width entry boundaries.\nThat gives you deltas that are understandable by the current decoder,\nbut are also trivially processed in delta format as insertions and\ncopy runs always cover complete entries and are never a partial entry.\n\nIt was all theory; we never actually wrote a prototype of that.\n\n> [1] Of course there are other reachability checks besides packing, like\n>     git-prune. But all of those are even better sped up by using\n>     reachability bitmaps. Packing, as the place where we generate the\n>     bitmaps, and which is sensitive to things like traversal order,\n>     remains the place where we will always need to actually walk.\n\n`git log -- $path` isn't trivially improved with reachability bitmaps.\nIts something we have been pondering a lot at $DAY_JOB and haven't\nfound a magic bullet solution for yet. Until someone comes up with\nanother chunk of magic, we need tree diffs for a lot of operations.\n\n> [2] One option, of course, is to generate byte-wise deltas, but with a\n>     promise to always align them on entry boundaries. I'm tempted by\n>     this, because the result would be readable by existing packv2\n>     readers. We'd have to set a flag somewhere that indicates the pack\n>     was written with this property, though.\n\nYes, that was always something we wanted to look at doing.\n\n> [3] I suspect you could come up with some heuristic that finds tree\n>     entry boundaries with high probability, and in the low probability\n>     case does not produce a wrong answer, but instead has to walk all\n>     the way back to the beginning of the tree. That would be fine here.\n>     But frankly, this \"walk backwards\" thing was just the straw that\n>     broke the camel's back for me in working on this. Handling all the\n>     possible cases was ending up quite complicated.\n\nNo, I tried this in JGit once. You can't do it reliably enough.\n"}]}