Martin Koegler [off-list ref] writes:
Keeping the last used delta base object, if it would be dropped,
supports creating smaller packs with shorter delta chains.
Instead of treating the "the last used one happened to be on the
horizon -- try not to drop it" special case, I wonder if it
makes sense to float the last used delta base object early in
the window _after_ it is used. Wouldn't we keep more than one
very recently used delta base objects in the window that way?
Junio C Hamano [off-list ref] writes:
Martin Koegler [off-list ref] writes:
quoted
Keeping the last used delta base object, if it would be dropped,
supports creating smaller packs with shorter delta chains.
Instead of treating the "the last used one happened to be on the
horizon -- try not to drop it" special case, I wonder if it
makes sense to float the last used delta base object early in
the window _after_ it is used. Wouldn't we keep more than one
very recently used delta base objects in the window that way?
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. 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.
Also the calculation of a delta can get aborted once it exceeds the
size of a previous delta. 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.
Its size needs to be large enough so that the bit maps will be
dominated by zeros: hash collisions not actually corresponding to
matching data lead to underestimates. If those become too many, the
pruning of comparisons will become ineffective:
A match implies that the next 2*RABIN_SIZE-1 (31) bytes at least could
possibly be expressed as a delta, and every match after another
RABIN_SIZE implies another RABIN_SIZE bytes might get folded into the
previous delta.
So false positives seriously distort the estimate. There is still a
good chance that a good candidate will land early in the sort order
due to such an estimate and thus other candidates will have their
deltaing cut off early, but of course it is quite more effective if
their deltaing does not even have to start.
--
David Kastrup
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