Re: [PATCH] Keep last used delta base in the delta window

[mkoegler@auto.tuwien.ac.at (Martin Koegler)]

On Mon, Aug 27, 2007 at 12:07:58PM +0200, David Kastrup wrote:
> Well, given the little amount of spare time I have for personal
> projects, I should not go flaunting them too much, but anyway...
> 
> I am just drafting implementing a delta-diff size estimator: for every
> hash value it does not store hash chains or pointers to memory images,
> but just a bit map of at most 32 (possibly 64 where ulong delivers it,
> possibly even just 16 bits when one restricts oneself to 16 element
> windows in order to save memory) delta window files, telling which of
> the files show such a hash value anywhere. 

How do you want to select these few hash values? 

I eg. dump database tables as SQL statements in per table files and
commit all changes. All lines in each file share a common prefix
(INSERT INTO tablename (COL1, COL2, ...) VALUES). Statistics showed, that up
to 50% of the hash elements of the delta index were dropped, because
they had eqal has values.

With you apropach:

If rare used values are selected as the 32 hash values, you will
probably regard files, which contain different tables (and therefore a
different prefix), as "similar", although the files have not very much
similarity otherwise.

If you select the hash values of the prefixes, you will create for each
table one cluster (if the table count is < 32/64). This already happens
by using the hash value of the path name in the sorting.

I don't belive, that your idea will improve very much in this case.
I fear, that it will be even worser than the current algorithm.

> When a file is considered
> for deltaing, it is run once against this delta-diff estimator which
> does not even look at the files again.  This delivers a lower bound
> for the size a delta towards each of the delta candidates can take.
> The candidates are then sorted in increasing size of expected delta
> size and are considered in turn.  Once a delta has a lower size than
> the lowest bound for further delta candidates, no further candidates
> need to get considered.

So this means, that we have to hash the target entry too (which could
be merged with creating the delta index). We currently only hash an
entry, if it is really needed as source in a delta-diff.

On bigger blobs, this could slow the process down.

> Also the calculation of a delta can get aborted once it exceeds the
> size of a previous delta. 

This already happens.

> Somewhat more complex and error-prone would
> be to abort based on continually correcting the estimated lower bound
> from the estimator while one is creating a delta and dropping out as
> soon as it becomes impossible to beat a previous delta.
> 
> The nice thing about this is that one can start out with a simplistic
> estimator as long as it is guaranteed never to deliver an estimate
> that is too high.  As long as that is the case, the packs will never
> get worse than they are now: a bad estimator will just mean that more
> elements of the window need to be considered before the conclusion is
> reached.
> 
> Since the estimator data structure does not point into any
> memory-mapped files or hash chains scattered through memory, it should
> be comparatively light (in comparison to an actual delta) on page
> thrashing which appears to me one of the main performance problems,
> while delivering a reasonably useful lower bound for all deltas in the
> window at once.

Do you want to do your estimations only against a small window of objects
or all objects?

mfg Martin Kögler