{"thread":{"id":"11935","subject":"small question about the repack algorithm","startedAt":"2008-02-07T09:03:31Z","lastAt":"2008-02-08T08:38:58Z","messageCount":3,"participants":["Pierre Habouzit","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"67767","messageId":"20080207090331.GA1958@artemis.madism.org","threadId":"11935","inReplyTo":null,"subject":"small question about the repack algorithm","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2008-02-07T09:03:31Z","receivedAt":"2008-02-07T09:03:31Z","isPatch":false,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"\n  I've trying to see if that optimization was used but I was somehow\nunable to find if it was the case, as the code is a bit tough :)\n\n  I was wondering if the repacking window was using triangle inequality\nto discard trying some costly deltas (I assume that what costs the most\nin the repacking is computing the delta). I mean, if you consider the\n\"size\" of a delta, I'm almost sure that it's very near a distance.\n\n  So assuming that we know the delta sizes between any pair of reference\nobjects in the window, well, if an object we want to delta against the\nwindow Od are near one reference O1 enough, for each Oi in the window\nthat holds: len(δ(O1, Oi)) > 2 * len(δ(Od, O1)), then it's not worth\ninvestigating.\n\n  I've seen quite many heuristics tried to avoid computing a delta at\nthe beginning of builtin-pack-objects.c:try_delta, but I don't seem to\nfind this one used, whereas it would even encompass most of the\nheuristics here. I mean the object-size based heuristics are (if I'm\ncorrect) a special case of the previous, e.g. I think one of the\nheuristics is to not trying a delta if:\n  | len(Oi) - len(Od) | > 2 * len(δ(Od, O1))\n\nBut it's just a subcase of the former because\n  len(δ(Od, Oi)) >= | len(Oi) - len(Od) |\n\n\n  Of course it needs us to know how objects in the same window diff\nagainst one each other, of have a good estimation of it (having not too\nbad lower estimates of the real deltas is an option here, as it just\nmakes the test a bit less discriminant, but can allow us to have a\ntrade-off between computing each crossed deltas in the window and\ndropping tried deltas early). Note that we don't need to store the\nactual deltas, just their length (or a more complicated score if we want\n-- probably -- take the chain depth into account, we just need that\nscore to look like a distance enough).\n\n\n  If it's already done, then don't mind me, though I'd like to be\npointed to where so that I can grok that code a bit more :)\n-- \n·O·  Pierre Habouzit\n··O                                                madcoder@debian.org\nOOO                                                http://www.madism.org\n"},{"id":"67902","messageId":"7vodarly4z.fsf@gitster.siamese.dyndns.org","threadId":"11935","inReplyTo":"20080207090331.GA1958@artemis.madism.org","subject":"Re: small question about the repack algorithm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-02-08T07:12:44Z","receivedAt":"2008-02-08T07:12:44Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Pierre Habouzit <madcoder@debian.org> writes:\n\n>   I've trying to see if that optimization was used but I was somehow\n> unable to find if it was the case, as the code is a bit tough :)\n>\n>   I was wondering if the repacking window was using triangle inequality\n> to discard trying some costly deltas (I assume that what costs the most\n> in the repacking is computing the delta). I mean, if you consider the\n> \"size\" of a delta, I'm almost sure that it's very near a distance.\n>\n>   So assuming that we know the delta sizes between any pair of reference\n> objects in the window, well, if an object we want to delta against the\n> window Od are near one reference O1 enough, for each Oi in the window\n> that holds: len(δ(O1, Oi)) > 2 * len(δ(Od, O1)), then it's not worth\n> investigating.\n\nWe do not keep track of the delta size matrix between delta-base\ncandidates in the window, but I presume we could.  The storage\ncost for doing so is very cheap (window^2 * size_t).  But we do\nnot even compute the distance matrix fully (I'll mention the\nreason why the above is not (window^2 * size_t / 2) later).\n\n    1-----------------------------i   <= delta-base candidates\n     \\\n      \\ \n       D <-- the target we are considering\n\nYour idea is that if we want to find the cheapest delta-base,\nand after we find out that candidate #1 is close to our target D\nand candidate #i is very far from candidate #1, then delta to\ncreate D using candidate #i as the base would be much bigger.\nIf the distance space is Euclidean, that would be a nice\noptimization.\n\nHowever I do not think deltification would work that way, for\ntwo reasons.\n\nThe deltified representation of an object is a sequence of two\nkinds of opcodes:\n\n (1) the N bytes in the target from the current point is a copy\n     of the source at offset M;\n\n (2) the N bytes in the target from the current point are the\n     following literal string.\n\nThe first form is two integers (and we represent short integers\nefficiently), and the second form is one integer plus N bytes\nliteral.\n\nAn efficient delta candidate is the one with most common\ncontents with the target image.  Saying \"copy that part\" is\ncheaper than \"Here is the contents.....\".\n\nNotice that it does not matter how much other cruft a target\ncontains.  In an extreme case, if the base candidate #1 is a\nprefix of the candidate #i, and the difference does not have any\ncommonality with target D, then the delta to represent D using\nthe base #1 and the delta using the base #i would be of the same\nsize and the same contents (as all offsets from the source image\nof copied parts would be the same).  The tail part of #i would\nnot participate reconstruction of D at all.\n\nIn such a case, you would have a long distance between #1 and\n#i, but that is because #i has very many unrelated contents that\nare not shared with #1 (so the difference has to be represented\nas \"Append these bytes to represent #i, as we cannot copy from #1\".\n\nBut that does not mean #i has less common contents than #1 has\nwith D.  In fact, we might even find common contents between the\ntail part of #i and D that the delta using base #1 needed to\nrepresent as literals.  In other words, #i could well be a\nbetter candidate than #1.\n\nThe second reason is that the deltification is not symmetric.\nIf you define the \"distance\" between #1 and #i as \"the size of\ndelta to reproduce #i using #1 as base\", the distance between #1\nand #i is very different from the distance between #i and #1.\n"},{"id":"67911","messageId":"20080208083858.GA24913@artemis.madism.org","threadId":"11935","inReplyTo":"7vodarly4z.fsf@gitster.siamese.dyndns.org","subject":"Re: small question about the repack algorithm","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2008-02-08T08:38:58Z","receivedAt":"2008-02-08T08:38:58Z","isPatch":false,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On Fri, Feb 08, 2008 at 07:12:44AM +0000, Junio C Hamano wrote:\n> Pierre Habouzit <madcoder@debian.org> writes:\n> \n> >   I've trying to see if that optimization was used but I was somehow\n> > unable to find if it was the case, as the code is a bit tough :)\n> >\n> >   I was wondering if the repacking window was using triangle inequality\n> > to discard trying some costly deltas (I assume that what costs the most\n> > in the repacking is computing the delta). I mean, if you consider the\n> > \"size\" of a delta, I'm almost sure that it's very near a distance.\n> >\n> >   So assuming that we know the delta sizes between any pair of reference\n> > objects in the window, well, if an object we want to delta against the\n> > window Od are near one reference O1 enough, for each Oi in the window\n> > that holds: len(δ(O1, Oi)) > 2 * len(δ(Od, O1)), then it's not worth\n> > investigating.\n> \n> We do not keep track of the delta size matrix between delta-base\n> candidates in the window, but I presume we could.  The storage\n> cost for doing so is very cheap (window^2 * size_t).  But we do\n> not even compute the distance matrix fully (I'll mention the\n> reason why the above is not (window^2 * size_t / 2) later).\n> \n>     1-----------------------------i   <= delta-base candidates\n>      \\\n>       \\ \n>        D <-- the target we are considering\n> \n> Your idea is that if we want to find the cheapest delta-base,\n> and after we find out that candidate #1 is close to our target D\n> and candidate #i is very far from candidate #1, then delta to\n> create D using candidate #i as the base would be much bigger.\n> If the distance space is Euclidean, that would be a nice\n> optimization.\n\n  Well, Euclidean is too much, a simple Metric Space is enough IIRC.\n\n> The second reason is that the deltification is not symmetric.\n> If you define the \"distance\" between #1 and #i as \"the size of\n> delta to reproduce #i using #1 as base\", the distance between #1\n> and #i is very different from the distance between #i and #1.\n\n  Well that's the most obvious reason indeed and I totally missed that,\ndang. The delta is not near a distance enough. Too bad :)\n\n-- \n·O·  Pierre Habouzit\n··O                                                madcoder@debian.org\nOOO                                                http://www.madism.org\n"}]}