I was somewhat surprised, because this repo behaves very differently from other ones as the window size increases. Our default window of 10 is somewhat arbitrary, but I think there was a sense from early tests that you got diminishing returns from increasing it (this is my vague recollection; I didn't actually search for old discussions). But here are some charts showing "repack -adf" with various window sizes on a few repositories. The first column is the window size; the second is the resulting pack size (and its percentage of the window=10 case); the third is the number of seconds of CPU time (and again, the percentage of the window=10 case).
Here's git.git:
10 | 31.3M (100%) | 54s (100%)
20 | 28.8M ( 92%) | 72s (133%)
40 | 27.4M ( 87%) | 101s (187%)
80 | 26.3M ( 84%) | 153s (282%)
160 | 25.7M ( 82%) | 247s (455%)
320 | 25.4M ( 81%) | 415s (763%)
You can see we get some benefit from increasing window size to 20 or even 40, but we hit an asymptote around 80%. Meanwhile, CPU time keeps jumping. Something like 20 or 40 seems like it might be a nice compromise.
Here's linux-2.6:
10 | 564M (100%) | 990s (100%)
20 | 521M ( 92%) | 1323s (134%)
40 | 495M ( 88%) | 1855s (187%)
80 | 479M ( 85%) | 2743s (277%)
160 | 470M ( 83%) | 4284s (432%)
320 | 463M ( 82%) | 7064s (713%)
It's quite similar, asymptotically heading towards ~80%. And the CPU numbers look quite similar, too.
And here's the phpmyadmin repository (the one I linked to earlier):
10 | 386M (100%) | 1592s (100%)
20 | 280M ( 72%) | 1947s (122%)
40 | 209M ( 54%) | 2514s (158%)
80 | 169M ( 44%) | 3386s (213%)
160 | 151M ( 39%) | 4822s (303%)
320 | 142M ( 37%) | 6948s (436%)
The packfile size improvements go on for much longer as we increase the window size. For this repo, a window size of 80-100 is probably a good spot.
That leads me to a few questions:
1. Should we bump our default window size? The numbers above show that
typical repos would benefit from jumping to 20 or even 40. 2. Is there a heuristic or other metric we can figure out to
differentiate the first two repositories from the third, and use a
larger window size on the latter? 3. Does the phpmyadmin case give us any insight into whether we can
improve our window sorting algorithm? Looking at the repo, ~55K of
the ~75K commits are small changes in the po/ directory (it looks
like they were using a web-based tool to let non-committers tweak
the translation files). In particular, I see a lot of commits in
which most of the changes are simply line number changes as the po
files are refreshed from the source. I wonder if that is making the
size-sorting heuristics perform poorly, as we end up with many
files of the same size, and the good deltas get pushed further
along the window. 4. What is typical? I suspect that git.git and linux-2.6 are typical,
and the weird po-files in the phpmyadmin repository are not. But
I'd be happy to test more repos if people have suggestions. And the
scripts that generated the charts are included below if anybody
wants to try it themselves.-Peff
-- >8 -- cat >collect <<\EOF #!/bin/sh # usage: collect /path/to/repo >foo.out
windows='10 20 40 80 160 320'
for i in $windows; do
echo >&2 "Repacking with window $i..."
rm -rf tmp && cp -a "$1" tmp && (
cd tmp &&
time=`time -f %U -o /dev/stdout git repack -adf --window=$i`
size=`du -bc objects/pack/pack-*.pack | tail -1 | awk '{print $1}'`
echo "$i $size $time"
)
done
EOFcat >chart <<\EOF #!/usr/bin/perl # usage: chart <foo.out
use strict;
my @base;
while (<>) {
chomp;
my ($window, $size, $time) = split; @base = ($size, $time) unless @base;
printf '%4s', $window;
print ' | ', humanize($size);
printf ' (%3d%%)', int($size / $base[0] * 100 + 0.5);
printf ' | %4ds', $time;
printf ' (%d%%)', int($time / $base[1] * 100 + 0.5);
print "\n";
}
sub human_digits {
my $n = shift;
my $digits = $n >= 100 ? 0 :
$n >= 10 ? 1 :
2;
return sprintf '%.*f', $digits, $n;
}sub humanize {
my $n = shift;
my $u;
foreach $u ('', qw(K M G)) {
return human_digits($n) . $u if $n < 900;
$n /= 1024;
}
return human_digits($n) . $u;
}
EOF
Jay Soffian
