Re: small question about the repack algorithm

> Pierre Habouzit <madcoder@debian.org> writes:
> 
> >   I've trying to see if that optimization was used but I was somehow
> > unable to find if it was the case, as the code is a bit tough :)
> >
> >   I was wondering if the repacking window was using triangle inequality
> > to discard trying some costly deltas (I assume that what costs the most
> > in the repacking is computing the delta). I mean, if you consider the
> > "size" of a delta, I'm almost sure that it's very near a distance.
> >
> >   So assuming that we know the delta sizes between any pair of reference
> > objects in the window, well, if an object we want to delta against the
> > window Od are near one reference O1 enough, for each Oi in the window
> > that holds: len(δ(O1, Oi)) > 2 * len(δ(Od, O1)), then it's not worth
> > investigating.
> 
> We do not keep track of the delta size matrix between delta-base
> candidates in the window, but I presume we could.  The storage
> cost for doing so is very cheap (window^2 * size_t).  But we do
> not even compute the distance matrix fully (I'll mention the
> reason why the above is not (window^2 * size_t / 2) later).
> 
>     1-----------------------------i   <= delta-base candidates
>      \
>       \ 
>        D <-- the target we are considering
> 
> Your idea is that if we want to find the cheapest delta-base,
> and after we find out that candidate #1 is close to our target D
> and candidate #i is very far from candidate #1, then delta to
> create D using candidate #i as the base would be much bigger.
> If the distance space is Euclidean, that would be a nice
> optimization.