Re: [PATCH 3/4] pack-objects: don't traverse objects unnecessarily

From: Junio C Hamano <gitster@pobox.com>
Date: Nov 14, 2011, 05:40 UTC
Message-ID: <7vaa7zl0ru.fsf@alter.siamese.dyndns.org>
In-Reply-To: <CAEik5nPJ3r6gp9Lttzh5aQmiPRFxpZvhTBXZoreY98QV6Cocdg@mail.gmail.com>

Dan McGee <dpmcgee@gmail.com> writes:

Show 8 quoted lines

>>> unable to figure out how you generated those numbers so I wasn't able
>>> to do so (and had planned to get back to you to find out how you made
>>> those tables). Were you able to verify the ordering did not regress?
>>
>> No; I was hoping you would redo the benchmark using 5f44324 (core: log
>> offset pack data accesses happened, 2011-07-06).
>
> I'm still not sure what you used to parse these results,...

Ah, in the kernel repository, after running "repack -a -d -f" with versions of git and copying the resulting packfiles in PACK-OLD/ and PACK-NEW/, I used these scripts to examine the access pattern.

-- >8 -- DOIT.sh -- >8 -- #!/bin/sh

tmp=/var/tmp/ll$ trap 'rm -f "$tmp.*"' 0

ln -f PACK-OLD/* .git/objects/pack/. || exit log="$tmp.old" eval '/usr/bin/time rungit test -c core.logpackaccess="$log" '"$*"

ln -f PACK-NEW/* .git/objects/pack/. || exit log="$tmp.new" eval '/usr/bin/time rungit test -c core.logpackaccess="$log" '"$*"

perl OFS.perl "$tmp.old" "$tmp.new" -- 8< -- DOIT.sh -- 8< --

-- >8 -- OFS.perl -- >8 -- #!/usr/bin/perl

use strict; use warnings; use Getopt::Long;

my $verbose;

exit(1) if (!GetOptions("verbose" => \$verbose));

sub take_one {
	my ($filename) = @_;
	my (%lofs, $num);
	my @diff;
	open my $in, '<', $filename;

	$num = 0;
	while (<$in>) {
		my ($file, $ofs) = split(' ');
		if (!exists $lofs{$file}) {
			$lofs{$file} = [$num++, 0];
		}
		my $diff = $ofs - $lofs{$file}[1];
		$lofs{$file}[1] = $ofs;
		push @diff, abs($diff);
		print "$lofs{$file}[0] $diff $ofs\n" if $verbose;
	}
	return \@diff;
}

sub bsearch {
	my ($list, $target) = @_;
	my ($hi, $lo) = ((scalar @$list), 0);

	while ($lo < $hi) {
		my $mi = int(($lo + $hi) / 2);
		if ($list->[$mi] == $target) {
			return $mi;
		} elsif ($list->[$mi] < $target) {
			$lo = $mi + 1;
		} else {
			$hi = $mi;
		}
	}
	return $hi;
}

my @percentile = ();
for (my $i = 0; $i < 100; $i += 10) {
	push @percentile, $i;
}
push @percentile, 95, 99, 99.9, 99.99;

sub thcomma {
	my ($intval) = @_;
	my $result = "";
	while ($intval > 1000) {
		my $rem = $intval % 1000;
		if ($result ne "") {
			$result = sprintf "%03d,%s", $rem, $result;
		} else {
			$result = sprintf "%03d", $rem;
		}
		$intval -= $rem;
		$intval /= 1000;
	}
	if ($intval) {
		if ($result ne "") {
			$result = sprintf "%d,%s", $intval, $result;
		} else {
			$result = sprintf "%d", $intval;
		}
	}
	$result =~ s/^[0,]*//;
	$result = "0" if ($result eq "");
	return $result;
}

sub show_stat {
	my ($diff1, $diff2) = @_;
	my ($i, $ix);
	if ($diff2) {
		@$diff2 = sort { $a <=> $b } @$diff2;
	}
	@$diff1 = sort { $a <=> $b } @$diff1;
	printf "\nTotal number of access : %12s", thcomma(scalar(@$diff1));
	printf "%12s", thcomma(scalar(@$diff2)) if ($diff2);
	for $i (@percentile) {
		$ix = scalar(@$diff1) * $i / 100;
		printf "\n     %5.2f%% percentile : %12s", $i, thcomma($diff1->[$ix]);
		if ($diff2) {
			$ix = scalar(@$diff2) * $i / 100;
			printf "%12s", thcomma($diff2->[$ix]);
		}
	}

	$ix = bsearch($diff1, 2 * 1024 * 1024);
	printf "\n   Less than 2MiB seek :       %5.2f%%", ($ix * 100.0 / @$diff1);
	if ($diff2) {
		$ix = bsearch($diff2, 2 * 1024 * 1024);
		printf "      %5.2f%%", ($ix * 100.0 / @$diff2);
	}

	print "\n";
}

my ($diff1, $diff2); $diff1 = take_one($ARGV[0]); $diff2 = take_one($ARGV[1]) if ($ARGV[1]);

show_stat($diff1, $diff2); -- 8< -- OFS.perl -- 8< --