{"thread":{"id":"34961","subject":"Git pack v4: next step, help required","startedAt":"2013-09-18T17:40:23Z","lastAt":"2013-09-19T01:28:28Z","messageCount":2,"participants":["Nicolas Pitre","Duy Nguyen"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"227846","messageId":"alpine.LFD.2.03.1309181120390.20709@syhkavp.arg","threadId":"34961","inReplyTo":null,"subject":"Git pack v4: next step, help required","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-18T17:40:23Z","receivedAt":"2013-09-18T17:40:23Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nI think the pack v4 format and compatibility code is pretty stable now, \nand probably as optimal as it can reasonably be.\n\n@Junio: might be a good idea to refresh your pu branch again.\n\nNow the biggest problem to solve is the actual tree \n\"deltification\".  I don't have the time to spend on this otherwise very \ninteresting problem (IMHO at least) so I'm sending this request for help \nin the hope that more people would be keen to contribute their computing \nskills to solve this challenge.\n\nI'll make a quick description of the pv4 tree encoding first and explain \nthe problem to solve afterwards.\n\nA pv4 tree is comprised of two types of records: immediate tree entry \nand tree sequence copy.\n\n1) Immediate Tree Entry\n\nThis is made of the following tuple:\n\n\t<path component index>,{SHA1 reference index>\n\nThe path component index refers to the path dictionary table where path \nstrings and file modes are uniquely stored.  The SHA1 index refers to \nthe sorted SHA1 table as previously found in the pack index but which is \nnow part of the pack file itself.  So on average a single tree entry may \ntake between 1 to 2 bytes for the path component index and 1 to 3 bytes \nfor the SHA1 index.\n\n2) Tree Sequence Copy\n\nThis is used to literally copy a contiguous list of tree entries from \nanother tree object.  This goes as follows:\n\n\t<tree entry where to start>,<number of entries to copy>\n\t[,<SHA1 index of the object to copy from>]\n\nSo instead of having arbitrary copying of data like in delta objects, we \nrefer directly to tree entries in another object.  The big advantage \nhere is that the tree walker may directly jump to the copied object \nwithout having to do any delta patching and caching. The SHA1 index is \noptional if it refers to the same copied object as the previous tree \nsequence copy record in this tree object.  And another possible \noptimization for the tree walker when enumerating objects is to skip the \ncopy entry entirely if the object being copied from has already been \nenumerated.\n\nThe size of this entry is more variable and is typically between 1 to 2 \nbytes for the start index, 1 to 2 bytes for the copy size, and 0 to 3 \nbytes for the SHA1 index.\n\nSo... what to do with this?\n\nCurrently the \"deltification\" is achieved using a pretty dumb heuristic \nwhich is to simply take each tree object in a pack v2 with their \ncorresponding base delta object and perform a straight conversion into \npack v4 tree format i.e. use copy records whenever possible as long as \nthey represent a space saving over the corresponding immediate tree \nentries (which is normally the case).\n\nHowever this is rather sub-optimal for two reasons:\n\n1) This doesn't benefit from the ability to use multiple base objects to \n   copy from and is potentially missing on additional opportunities for \n   copy sequences which are not possible in the selected base object \n   from the pack v2 delta base selection. Pack v4 is already quite \n   smaller than pack v2 yet it might possibly be smaller still.\n\n2) This makes deep delta chains very inefficient at runtime when the \n   pack is subsequently accessed.\n\nLet's consider this example to fully illustrate #2.\n\n\tTree A:\n\tentry 0:\t\"foo.txt\"\n\tentry 1-3:\tcopy from tree B: start=2 count=3\n\n\tTree B:\n\tentry 0-5:\tcopy from tree C: start=2 count=5\n\tentry 6:\t\"bar.txt\"\n\n\tTree C:\n\tentry 0:\t\"file_a\"\n\tentry 1:\t\"file_b\"\n\tentry 2:\t\"file_c\"\n\tentry 3:\t\"file_D\"\n\tentry 4:\t\"file_E\"\n\tentry 5:\t\"file_F\"\n\tentry 6:\t\"file_G\"\n\nThis is a good example of what typically happens when the above heuristic \nis applied.  And it is not uncommon to see a long indirection chain of \n\"copy those 2 entries from that other object\" sometimes reaching 50 \nlevels deep where the same 2 (or more) entries require up to 50 object \nhops before they can be obtained.\n\nObviously here the encoding should be optimized to reduce the chaining \neffect simply by referring to the final object directly.  Hence tree A \ncould be encoded as follows:\n\n\tTree A:\n\tentry 0:\t\"foo.txt\"\n\tentry 1-3:\tcopy from tree C: start=4 count=3\n\nThe on-disk encoding is likely to be the same size but the runtime \naccess is greatly optimized.\n\nNow... instead of trying to do reference simplification by factoring out \nthe chain effect, I think a whole new approach to tree delta compression \nfor pack v4 should be developed which would also address issue #1 above.\n\nFor example, we may try to make each canonical tree objects into \nsequences of hashed tree entries in memory where each tree entry would \nbe reduced down to a single CRC32 value (or even Adler32 for speed).  \nEach tree object would then be represented by some kind of 32-bit \ncharacter \"string\".  Then it is just a matter of applying substring \nmatching algorithms to find the best copy sequences without creating \nreference cycles, weighted by the number of indirections involved when \na referred object already has a copy sequence covering part or all of \nthe matched string. Etc.\n\nOr that can be something else entirely.  Certainly there are similar \nproblems already solved in the literature somewhere.\n\nAnd it has to be _fast_.\n\nSo if someone is on the lookout for a nice algorithmic and coding \nchallenge then here's your opportunity!\n\n\nNicolas\n"},{"id":"227869","messageId":"CACsJy8Cyg3Qdnx_eh4gVpeLLgHrTWRZbOnd3z57oqMVtJy9h8A@mail.gmail.com","threadId":"34961","inReplyTo":"alpine.LFD.2.03.1309181120390.20709@syhkavp.arg","subject":"Re: Git pack v4: next step, help required","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-19T01:28:28Z","receivedAt":"2013-09-19T01:28:28Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Sep 19, 2013 at 12:40 AM, Nicolas Pitre <nico@fluxnic.net> wrote:\n>\n> I think the pack v4 format and compatibility code is pretty stable now,\n> and probably as optimal as it can reasonably be.\n>\n> @Junio: might be a good idea to refresh your pu branch again.\n>\n> Now the biggest problem to solve is the actual tree\n> \"deltification\".  I don't have the time to spend on this otherwise very\n> interesting problem (IMHO at least) so I'm sending this request for help\n> in the hope that more people would be keen to contribute their computing\n> skills to solve this challenge.\n\nJust so we're clear as I'm involved a bit in packv4 series. I plan to\nmake the test suite fully pass, then add v4 support to git protocol.\nAfter that I may look into adding multi-base tree support to\nindex-pack/unpack-objects, and only then either look into this\nchallenge or continue to add v4-aware tree walker to git. In short,\nyou you are intereted in Nico's challenge, go ahead, it will not\noverlap with my work, at least in the next one or two months.\n-- \nDuy\n"}]}