Nicolas Pitre [off-list ref] writes:
The diff-delta code can exhibit O(m*n) behavior with some patological
data set where most hash entries end up in the same hash bucket.
Other data points from the Linux kernel repository:
blob 9af06ba723df75fed49f7ccae5b6c9c34bc5115f ->
blob dfc9cd58dc065d17030d875d3fea6e7862ede143
size (491102 -> 496045)
delta size (16 byte blocks): 248899 in less than 0.1 sec
delta size (3 byte blocks): 136000 in 11.8 secs
delta size (3 byte blocks + this patch): 171688 in 0.79 sec
These numbers are misleading.
The 36K objects pack I used in my previous tests gives 9971223
(from "next" branch) vs 9664546 (this patch) final pack size.
The wallclock time on my machine is 1m35 vs 3m30. I doubt many
people are willing to pay 100% more waiting time for 3% tighter
pack.
Although I do not mean to rain on your effort and substantial
improvement you made with this patch, we need to admit that
improving pathological corner case has quite a diminishing
effect in the overall picture.
But this definitely is an improvement nevertheless. I should
try this on my wife's AMD64 (Cygwin). The same datasets I used
in my previous complaint still seem to take a couple of seconds
(or more) each on my Duron 750 X-<.
A handful additional ideas.
* Lower the hash limit a bit more (obvious). That might have
detrimental effect in the general case.
* Study the hash bucket distribution for the pathological case
and see if we can cheaply detect a pattern. I suspect these
cases have relatively few but heavily collided buckets with
mostly sparse other entries. If there is such an easily
detectable pattern, maybe we can look for such a pattern at
runtime, and cull hash entries more aggressively in such a
case?
* Try checking the target buffer to see if it would have many
hits on the heavily collided hash entries from the source
(maybe hash_count the target buffer as well).
* Have pack-object detect a pathological blob (the test patch I
sent you previously uses the eye-candy timer for this
purpose, but we could getrusage() if we want to be more
precise) by observing how much time is spent for a single
round, and mark the blob as such, so we do not delta against
it with other blobs in find_deltas, when we are packing many
objects. It does not really matter in the big picture if we
choose not to delta the pathological ones tightly, as long as
they are relatively few.
* Also in pack-object, have an optional backing-store to write
out deltified representations for results that took more than
certain amount of time to produce in find_deltas(), and reuse
them in write_object().
If anybody is interested, here are some other interesting pairs
from the Linux 2.6 repositories.
2645d6239b74 cb968e7a0fcd
357980942d73 5bb837052ef1
5412dcb4b6d0 ac07e18abb1d
5bb837052ef1 1f8744ad9cde
63d827d7da07 5bb837052ef1
9af06ba723df 1896a0eea7e5
cb968e7a0fcd 97b5578ae9b1
d8c5a8dbd086 97b5578ae9b1
d8c5a8dbd086 cb968e7a0fcd
dfc9cd58dc06 1896a0eea7e5
fa0f82ec9fa0 b611e27470e1
Junio C Hamano [off-list ref] writes:
Nicolas Pitre [off-list ref] writes:
quoted
blob 9af06ba723df75fed49f7ccae5b6c9c34bc5115f ->
blob dfc9cd58dc065d17030d875d3fea6e7862ede143
size (491102 -> 496045)
delta size (16 byte blocks): 248899 in less than 0.1 sec
delta size (3 byte blocks): 136000 in 11.8 secs
delta size (3 byte blocks + this patch): 171688 in 0.79 sec
These numbers are misleading.
The 36K objects pack I used in my previous tests gives 9971223
(from "next" branch) vs 9664546 (this patch) final pack size.
The wallclock time on my machine is 1m35 vs 3m30. I doubt many
people are willing to pay 100% more waiting time for 3% tighter
pack.
I tried an experimental patch to cull collided hash buckets
very aggressively. I haven't applied your last "reuse index"
patch, though -- I think that is orthogonal and I'd like to
leave that to the next round.
With the same dataset: resulting pack is 9651096 vs 9664546
(your patch) final pack size, with wallclock 2m45s (user 2m31).
Still not good enough, and at the same time I wonder why it gets
_smaller_ results than yours. But the generated pack unpacked
cleanly in a cloned linux-2.6 repository (having objects and
refs up to v2.6.14) and the result was fsck-objects clean.
I'd appreciate it if you can test it on the 20MB blobs and see
what happens if you have time.
BTW, the benchmark I've been doing is with this dataset:
git rev-list --objects-edge v2.6.14..v2.6.15-rc1 >RL-N
time git pack-objects <RL-N --stdout | wc -c
---diff --git a/diff-delta.c b/diff-delta.c
index 0730b24..52df372 100644
--- a/diff-delta.c
+++ b/diff-delta.c
@@ -88,22 +88,35 @@ static struct index ** delta_index(const
/*
* Now make sure none of the hash buckets has more entries than
- * we're willing to test. Otherwise we short-circuit the entry
- * list uniformly to still preserve a good repartition across
- * the reference buffer.
+ * we're willing to test. Otherwise we cull the entry list to
+ * limit identical three byte prefixes to still preserve a good
+ * repartition across the reference buffer.
*/
for (i = 0; i < hsize; i++) {
+ struct index **list, *bucket, *remaining;
+ int cnt;
if (hash_count[i] < hlimit)
continue;
- entry = hash[i];
- do {
- struct index *keep = entry;
- int skip = hash_count[i] / hlimit / 2;
- do {
- entry = entry->next;
- } while(--skip && entry);
- keep->next = entry;
- } while(entry);
+
+ bucket = NULL;
+ list = &bucket;
+ remaining = hash[i];
+ cnt = 0;
+ while (cnt < hlimit && remaining) {
+ struct index *this = remaining, *that;
+ remaining = remaining->next;
+ for (that = bucket; that; that = that->next) {
+ if (!memcmp(that->ptr, this->ptr, 3))
+ break;
+ }
+ if (that)
+ continue; /* discard */
+ cnt++;
+ *list = this;
+ list = &(this->next);
+ this->next = NULL;
+ }
+ hash[i] = bucket;
}
free(hash_count);
On Mon, 27 Feb 2006, Junio C Hamano wrote:
Although I do not mean to rain on your effort and substantial
improvement you made with this patch, we need to admit that
improving pathological corner case has quite a diminishing
effect in the overall picture.
It does, unfortunately.
The problem is that the code in diff_delta() is highly solicited during
a pack generation. Just the simple hashing change from this patch that
involves two shifts instead of only one increased the CPU time to
generate a pack quite appreciably. This is just to say that this code
is pretty sensitive to even small details.
But this definitely is an improvement nevertheless. I should
try this on my wife's AMD64 (Cygwin). The same datasets I used
in my previous complaint still seem to take a couple of seconds
(or more) each on my Duron 750 X-<.
There is no miracle. To prevent the extreme cases additional tests have
to be performed in all cases, and therefore performance for all cases is
affected.
A handful additional ideas.
* Lower the hash limit a bit more (obvious). That might have
detrimental effect in the general case.
It does. The current parameters are what I think is the best compromize
between cost and compression. And still 99% of the cases don't need
a lower hash limit since their hash lists are already way below the
limit. For the cases where it makes a difference, well lowering the
hash limit also increase the cost associated with the reworking of the
hash list so there comes a point where you actually increase the
resulting delta size while the CPU time stays constant.
* Study the hash bucket distribution for the pathological case
and see if we can cheaply detect a pattern. I suspect these
cases have relatively few but heavily collided buckets with
mostly sparse other entries. If there is such an easily
detectable pattern, maybe we can look for such a pattern at
runtime, and cull hash entries more aggressively in such a
case?
Same issue as above. And "looking for such a pattern" really does
increase the CPU time in _all_ cases. So that looking for patological
cases has to be as cheap as possible which I think is the case right
now (and it is still too costly for my taste already). And yet I don't
think there is really a need for further reduction of the hash list at
this point since the patological cases are really handled gracefully
with this patch even with a nice and pretty packed delta.
* Try checking the target buffer to see if it would have many
hits on the heavily collided hash entries from the source
(maybe hash_count the target buffer as well).
Again that'd add another significant CPU cost to all cases, even those
that don't need it at all. The problem is not about those patological
cases anymore since I think they are well under control now. It is the
overhead those few patological cases impose on the other 180000 good
behaving objects that is a problem.
* Have pack-object detect a pathological blob (the test patch I
sent you previously uses the eye-candy timer for this
purpose, but we could getrusage() if we want to be more
precise) by observing how much time is spent for a single
round, and mark the blob as such, so we do not delta against
it with other blobs in find_deltas, when we are packing many
objects. It does not really matter in the big picture if we
choose not to delta the pathological ones tightly, as long as
they are relatively few.
That is one solution, but that doesn't handle the root of the problem
which is the cost of detecting those cases in the first place.
* Also in pack-object, have an optional backing-store to write
out deltified representations for results that took more than
certain amount of time to produce in find_deltas(), and reuse
them in write_object().
The pack reusing code is pretty effective in doing so already, isn't it?
Since using git-repack -f should not be the common case then those
patological cases (now taking one second instead of 60 or more) should
be reused most of the time.
I tried an experimental patch to cull collided hash buckets
very aggressively. I haven't applied your last "reuse index"
patch, though -- I think that is orthogonal and I'd like to
leave that to the next round.
It is indeed orthogonal and I think you could apply it to the next
branch without the other patches (it should apply with little problems).
This is an obvious and undisputable gain, even more if pack-objects is
reworked to reduce memory usage by keeping only one live index for
multiple consecutive deltaattempts.
With the same dataset: resulting pack is 9651096 vs 9664546
(your patch) final pack size, with wallclock 2m45s (user 2m31).
Still not good enough, and at the same time I wonder why it gets
_smaller_ results than yours.
It really becomes hard to find the best balance especially when the
resulting delta is then fed through zlib. Sometimes a larger delta will
compress better, sometimes not. My test bench was the whole git
repository and the kernel repository, and with such large number of
objects it seems that smaller deltas always translate into smaller
packs. But it might not necessarily always be the case.
I'd appreciate it if you can test it on the 20MB blobs and see
what happens if you have time.
Before your patch:
user 0m9.713s, delta size = 4910988 bytes, or 1744110 compressed.
With your patch:
user 0m3.948s, delta size = 6753517 bytes, or 1978803 once compressed.
BTW there is another potential for improvement in the delta code (but I
have real work to do now so)...
Let's suppose the reference buffer has:
***********************************************************************/
This is common with some comment block styles. Now that line will end
up with multiple blocks that will hash to the same thing and linked
successively in the same hash bucket except for the last ones where the
'/' is involved in the hashing.
Now if the target buffer also contains a line similar to the above but
one '*' character longer. The first "***" will be hashed to x, then x
will be looked up in the reference index, and the first entry
corresponding to the first character of the line above will be returned.
At that point a search forward is started to find out how much matches.
In this case it will match up to the '/' in the reference buffer while
the target will have another '*'. The length will be recorded as the
best match, so far so good.
Now the next entry from the same hash bucket will be tested in case it
might provide a starting point for a longer match. But we know in this
case that the location of the second '*' in the reference buffer will be
returned. And we obviously know that this cannot match more data than
the previous attempt, in fact it'll match one byte less. And the hash
entry to follow will return the location of the third '*' for another
byte less to match. Then the fourth '*' for yet another shorter match.
And so on repeating those useless string comparisons multiple times.
One improvement might consist of counting the number of consecutive
identical bytes when starting a compare, and manage to skip as many hash
entries (minus the block size) before looping again with more entries in
the same hash bucket.
The other case to distinguish is when the target buffer has instead a
_shorter_ line, say 5 fewer '*''s before the final '/'. Here we would
loop 4 times matching only a bunch of '*' before we finally match the
'/' as well on the fifth attempt becoming the best match. In this case
we could test if the repeated byte we noticed from the start is present
further away in the reference buffer, and if so simply skip hash entries
while searching forward in the reference buffer. When the reference
buffer doesn't match the repeated character then the comparison is
resumed with the target buffer, and in this case the '/' would match
right away, avoiding those four extra loops recomparing all those '*'
needlessly.
Such improvements added to the search algorithm might make it
significantly faster, even in the presence of multiple hash entries all
located in the same bucket. Or maybe not if the data set has few
repeated characters. And this is probably worthwhile only on top of my
small block patch. Only experimentation could tell. Someone willing to
try?
Nicolas
Junio C Hamano [off-list ref] writes:
quoted
These numbers are misleading.
The 36K objects pack I used in my previous tests gives 9971223
(from "next" branch) vs 9664546 (this patch) final pack size.
The wallclock time on my machine is 1m35 vs 3m30. I doubt many
people are willing to pay 100% more waiting time for 3% tighter
pack.
I started to suspect that the above benchmark was
unreliable, because I do not know how the original linux-2.6
repository I used for my testing were packed, and I was letting
the delta reusing to do its thing, so the times were probably
off (the 3-byte finer grained deltifier would have spent a lot
more time during the initial packing) and the result size were
too (the finer grained one would have packed things a lot more
tightly if the delta it was allowed to reuse was made by itself,
not by the old one).
So I tried a fresh packing without reusing delta at all,
with three variants: the original 16-byte one (master), 3-byte
finer grained one with your hash limit (nico), and 3-byte finer
grained one with my more aggressive hash limit (jc). The
benchmark is not meant to be scientific, but to see how well it
serves the kernel community ;-).
The first round. The set of objects packed were from
today's Linus tip (everything down to epoch v2.6.12-rc2), 193309
objects in total, on my Duron 750 with slow disks.
real user sys bytes savings
master 11m17.121s 10m23.280s 0m47.290s 109045599 N/A
nico 25m37.058s 23m0.770s 2m20.460s 104401392 4.25%
jc 24m12.072s 21m45.120s 2m16.400s 104409761 4.25%
My hack does not change things much in the overall picture
compared to yours, although it does cut down runtime by about
5%. We can immediately see that finer grained ones are
significantly more expensive than the original loose one either
way.
The next round of test is to place the "full pack"
generated in the previous experiment in .git/objects/pack and
generate packs by reusing delta. When testing the "master"
version, I move the pack produced above with "master" under
.git/objects/pack, and run this to emulate pack generation for
downloader who has v2.6.14 and wants v2.6.15-rc1 (the same 36K
objects test I did previously):
git rev-list --objects-edge v2.6.14..v2.6.15-rc1 |
time git-pack-objects --stdout | wc -c
When switching to test "nico" deltifier implementation, I start
with the full pack generated by "nico" in .git/object/pack to
make comparison fair. Here is the result:
real user sys bytes savings
master 1m37.703s 1m28.970s 0m5.860s 9968386 N/A
nico 3m39.982s 3m24.420s 0m14.380s 9182761 7.88%
jc 3m0.434s 2m35.940s 0m13.730s 9139460 8.31%
In thin transfer, base object is omitted, so the generated pack
has higher delta to non-delta ratio than usual -- and that is
the reason we see much more savings. Still, we are paying quite
a lot of overhead by finer grained delta code.
The last test is not to do a thin pack but still reusing
delta. This is to emulate "git repack" performance. Again, I
had the matching pack in .git/objects/pack to make the
compararison fair:
git rev-list --objects v2.6.14..v2.6.15-rc1 |
time git-pack-objects --stdout | wc -c
And here is the result:
real user sys bytes savings
master 1m0.866s 0m57.590s 0m2.810s 34601417 N/A
nico 2m8.059s 2m0.360s 0m6.350s 33888419 2.06%
jc 1m49.894s 1m42.250s 0m6.780s 33838262 2.20%
This one is not getting much savings compared to the full pack
case, but still spending about twice the time.
In short, I'd love to get a tighter packing, but as it
currently stands, I do not think 5% resulting packsize reduction
warrants making 100% slower operation the default. And the
experiment I did does not account for the memory pressure the
new delitifier imposes us (two pointers per every byte of source
material -- it could be reduced to one pointer though), so when
we start talking about huge files I am not sure we can manage to
keep the runtime reasonably low.
It maybe is an option to have a flag to tell "I want a
lot tighter pack made; you can spend all the time while I am
sleeping" and switch between two deltifiers, but otherwise...
One thing I do not understand is why my patch improves
the compressed result size. The patch was primarily to brutally
pessimize the selection of "copied from source" to avoid the
corner case performance problems, so I would understand why it
is faster than yours, but I expected it to *always* create a
looser pack. I am puzzled.
Swapping window scan order is orthogonal to this, so
maybe we could do it first and make it work, then start reusing
the refindex to see how well things improve. But we should be
reminded of the recent report that pack-object ran out of space
even with the current code that does not reuse the refindex when
packing 8 huge objects X-<.