packed delta git
PATCH 1/1 packed delta git
Hello everyone,
Here's a new version of my packed git patch, diffed on top of Nicolas' delta code (link below to that). It doesn't change the core git commands to create packed/delta files, that is done via a new git-pack command. The git-pack usage is very simple:
git-pack [<reference_sha1>:]<target_sha1> [ <next_sha1> ... ]
If you use the ref:target notation, it will create a delta between those two objects and relink the target into the resulting packed file. If you don't provide a reference sha1, the sha1 file is relinked into the packed file.
A script is provided (git-pack-changes-script) that walks the rev-list output and puts your whole repository into packed/delta form. This is just a starting point, it needs more knobs for forward/reverse deltas, max depth etc. The script does delta tree files and packs both trees and commits in with the blobs.
git-diff-tree -t was added so that it will show the sha1 of subtrees that differ while it processes things.
There is no way to unpack a file yet, so please use these with caution.
I did tests against the current 2.6 git tree (ext3)
vanilla delta+pack
.git size 191M 62M
checkout-cache (cold) 2m13s 38.9s checkout-cache (hot) 8s (2s user) 14.9s (11.46s user)
2.6.11 without any changesets:
unpacked packed
.git size 91M 55M
Because the 2.6 kernel repo has 2.6.11 floating around in there as a tree with no commit, you have to do a few steps in order to pack things in.
# step one, pack all the files in 2.6.11 together
git-ls-tree -r v2.6.11 | awk '{print $3}' | xargs git-pack# step two, make packed deltas between trees for 2.6.11 and 2.6.12-rc2 # (git-pack-changes-script -t only works with trees, not commits/tags) git-pack-changes-script -t c39ae07f393806ccf406ef966e9a15afc43cc36a 1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 | xargs git-pack
# step three, use git-pack-changes to walk whole rev-list and pack/delta # everything else git-pack-changes-script | xargs git-pack
And finally, here's the patch. It is on top of Nicolas' code, which you can grab here:
http://marc.theaimsgroup.com/?l=git&m=111587004902021&w=2
--
cache.h +17 -1
@@ -77,6 +77,16 @@char name[0 ]; }; +struct packed_item { +/* length of compressed data */ +unsigned long len; +struct packed_item *next; +/* sha1 of uncompressed data */ +char sha1[20 ]; +/* compressed data */ +char *data; +}; +#define CE_NAMEMASK (0x0fff)#define CE_STAGEMASK (0x3000)#define CE_STAGESHIFT 12
@@ -135,8 +145,10 @@/* Read and unpack a sha1 file into memory, write memory to a sha1 file */ extern void *map_sha1_file (const unsigned char *sha1,unsigned long *size); -extern void *unpack_sha1_file (void *map,unsigned long mapsize,char *type,unsigned long *size); +extern void *unpack_sha1_file (const unsigned char *sha1,void *map,unsigned long mapsize,char *type,unsigned long *size,const unsigned char *recur_sha1,int *chain); +extern void *raw_unpack_sha1_file (void *map,unsigned long mapsize,char *type,unsigned long *size);extern void *read_sha1_file (const unsigned char *sha1,char *type,unsigned long *size); +extern void *read_sha1_delta_ref (const unsigned char *sha1,char *type,unsigned long *size,const unsigned char *,int *chain);extern int write_sha1_file (char *buf,unsigned long len,const char *type,unsigned char *return_sha1);extern int check_sha1_signature (unsigned char *sha1,void *buf,unsigned long size,const char *type);
@@ -152,6 +164,10 @@extern int get_sha1 (const char *str,unsigned char *sha1);extern int get_sha1_hex (const char *hex,unsigned char *sha1);extern char *sha1_to_hex (const unsigned char *sha1);/* static buffer result! */ +extern int pack_sha1_buffer (void *buf,unsigned long buf_len,char *type, +unsigned char *returnsha1,unsigned char *refsha1, +struct packed_item **,int max_depth); +int write_packed_list (struct packed_item *head);/* General helper functions */ extern void usage (const char *err);
Files linus.delta/.cache.h.swp and linus/.cache.h.swp differ
diff-tree.c +11 -5
@@ -5,6 +5,7 @@static int silent =0 ;static int verbose_header =0 ;static int ignore_merges =1 ; +static int show_tree_diffs =0 ;static int recursive =0 ;static int read_stdin =0 ;static int line_termination ='\n' ;
@@ -114,6 +115,7 @@const unsigned char *sha1, *sha2;int cmp, pathlen1, pathlen2;char old_sha1_hex[50 ]; +int retval =0 ; sha1 =extract (tree1, size1, &path1, &mode1); sha2 =extract (tree2, size2, &path2, &mode2);
@@ -143,11 +145,11 @@ }if (recursive &&S_ISDIR (mode1)) { -int retval;char *newbase =malloc_base (base, path1, pathlen1); retval =diff_tree_sha1 (sha1, sha2, newbase);free (newbase); -return retval; +if (!show_tree_diffs) +return retval; }if (header) {
@@ -155,7 +157,7 @@ header =NULL ; }if (silent) -return 0 ; +return retval;if (generate_patch) {if (!S_ISDIR (mode1))
@@ -168,7 +170,7 @@ old_sha1_hex,sha1_to_hex (sha2), base, path1, line_termination); } -return 0 ; +return retval; }static int interesting (void *tree,unsigned long size,const char *base)
@@ -387,7 +389,7 @@ }static char *diff_tree_usage = -"diff-tree [-p] [-r] [-z] [--stdin] [-m] [-s] [-v] <tree sha1> <tree sha1>" ; +"diff-tree [-p] [-r] [-z] [--stdin] [-m] [-s] [-v] [-t] <tree sha1> <tree sha1>" ;int main (int argc,char **argv) {
@@ -428,6 +430,10 @@ silent =1 ;continue ; } +if (!strcmp (arg,"-t" )) { + show_tree_diffs =1 ; +continue ; + }if (!strcmp (arg,"-v" )) { verbose_header =1 ; header_prefix ="diff-tree " ;
git-pack-changes-script +161 -0
161 lines not on this page · raw message
Makefile +1 -1
@@ -22,7 +22,7 @@ git-unpack-file git-export git-diff-cache git-convert-cache \ git-http-pull git-rpush git-rpull git-rev-list git-mktag \ git-diff-tree-helper git-tar-tree git-local-pull git-write-blob \ - git-mkdelta + git-mkdelta git-pack all: $(PROG)
mkdelta.c +1 -1
@@ -95,7 +95,7 @@unsigned long mapsize;void *map =map_sha1_file (sha1, &mapsize);if (map) { -void *buffer =unpack_sha1_file (map, mapsize, type, size); +void *buffer =raw_unpack_sha1_file (map, mapsize, type, size);munmap (map, mapsize);if (buffer)return buffer;
object.c +1 -1
@@ -107,7 +107,7 @@struct object *obj;char type[100 ];unsigned long size; -void *buffer =unpack_sha1_file (map, mapsize, type, &size); +void *buffer =unpack_sha1_file (sha1, map, mapsize, type, &size,NULL ,NULL );munmap (map, mapsize);if (!buffer)return NULL ;
pack.c +122 -0
122 lines not on this page · raw message
sha1_file.c +450 -33
513 lines not on this page · raw message
Quoted 8 lines · Chris Mason
Hello everyone,
Here's a new version of my packed git patch, diffed on top of Nicolas' delta code (link below to that). It doesn't change the core git commands to create packed/delta files, that is done via a new git-pack command. The git-pack usage is very simple:
git-pack [<reference_sha1>:]<target_sha1> [ <
next_sha1> ... ]
My original git-pack-changes script didn't properly limit the length of the delta chains, so you could use it to create a repo that you can't later read.
The new one below fixes that, and also changes the direction of the delta. Deltas are now done in reverse, leaving the most recent sha1 as a whole file and diffing old revisions against it.
The result is the same size (62M for current linux-2.6 git tree) and faster checkout times for head (9s vs 15s). I also tested against the bk-cvs patch set:
vanilla packed/delta
checkout-cache (hot) (only 1.5G ram) 15s
checkout-cache (cold) 4m30s 1m19s
size (du -sh .git) 2.5G 227M
The steps to pack/delta the 2.6 git tree have changed:
# step one, pack all of HEAD together
git-ls-tree -r HEAD | awk '{print $3}' | xargs git-pack# step two pack deltas for all revs back to the first commit git-pack-changes-script | xargs git-pack
# step three, pack a delta from 2.6.12-rc2 to 2.6.11 git-pack-changes-script -t 1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 c39ae07f393806ccf406ef966e9a15afc43cc36a | xargs git-pack
New git-pack-changes-script:
--
#!/usr/bin/perl
#
# script to search through the rev-list output and generate delta history # you can specify either a start and stop commit or two trees to search. # with no command line args it searches the entire revision history. # output is suitable for piping to xargs git-pack
use strict;
my $ret;
my $i;
my @wanted = ();
my $argc = scalar(@ARGV);
my $commit;
my $stop;
my %delta = ();
my %packed = ();
sub add_packed($) {
my ($sha1) = @_;
if (defined($packed{$sha1})) {
return 1;
}
if (defined($delta{$sha1})) {
return 1;
}
$packed{$sha1} = 1;
print "$sha1\n";
return 0;
}sub add_delta($$) {
my ($ref, $target) = @_;
my $chain = 0;
my $recur = $ref;
if (defined($delta{$target})) {
return 1;
}
if (defined($packed{$target})) {
return 1;
}
while(1) {
last if (!defined($delta{$recur}));
if ($target eq $delta{$recur}) {
add_packed($target);
return 1;
}
$chain++;
if ($chain > 32) {
add_packed($target);
return 1;
}
$recur = $delta{$recur};
}
$delta{$target} = $ref;
print "$ref:$target\n";
return 0;
}sub print_usage() {
print STDERR "usage: pack-changes [-c commit] [-s stop commit] [-t tree1 tree2]\n";
exit(1);
}sub find_tree($) {
my ($commit) = @_;
open(CM, "git-cat-file commit $commit|") || die "git-cat-file failed";
while(<CM>) {
chomp;
my @words = split;
if ($words[0] eq "tree") {
return $words[1];
} elsif ($words[0] ne "parent") {
last;
}
}
close(CM);
if ($? && ($ret = $? >> 8)) {
die "cat-file $commit failed with $ret";
}
return undef;
}sub test_diff($$) {
my ($a, $b) = @_;
open(DT, "git-diff-tree -r -t $a $b|") || die "diff-tree failed";
while(<DT>) {
chomp;
my @words = split;
my $sha1 = $words[2];
my $change = $words[0];
if ($change =~ m/^\*/) {
@words = split("->", $sha1);
add_delta($words[0], $words[1]);
} elsif ($change =~ m/^\-/) {
next;
} else {
add_packed($sha1);
}
}
close(DT);
if ($? && ($ret = $? >> 8)) {
die "git-diff-tree failed with $ret";
}
return 0;
}for ($i = 0 ; $i < $argc ; $i++) {
if ($ARGV[$i] eq "-c") {
if ($i == $argc - 1) {
print_usage();
}
$commit = $ARGV[++$i];
} elsif ($ARGV[$i] eq "-s") {
if ($i == $argc - 1) {
print_usage();
}
$stop = $ARGV[++$i];
} elsif ($ARGV[$i] eq "-t") {
if ($argc != 3 || $i != 0) {
print_usage();
}
if (test_diff($ARGV[1], $ARGV[2])) {
die "test_diff failed\n";
}
add_delta($ARGV[1], $ARGV[2]);
exit(0);
}
}if (!defined($commit)) {
$commit = `commit-id`;
if ($?) {
print STDERR "commit-id failed, try using -c to specify a commit\n";
exit(1);
}
chomp $commit;
}open(RL, "git-rev-list $commit|") || die "rev-list failed";
while(<RL>) {
chomp;
my $cur = $_;
my $cur_tree;
my $parent_tree;
my $parent_commit = undef;
open(PARENT, "git-cat-file commit $cur|") || die "cat-file failed";
while(<PARENT>) {
chomp;
my @words = split;
if ($words[0] eq "tree") {
$cur_tree = $words[1];
next;
} elsif ($words[0] ne "parent") {
last;
}
$parent_commit = $words[1];
my $next = <PARENT>;
# ignore merge sets for now
if ($next =~ m/^parent/) {
last;
}
# note that we run test_diff to generate a reverse
# diff
if (test_diff($cur, $words[1])) {
die "test_diff failed\n";
}
$parent_tree = find_tree($words[1]);
if (!defined($parent_tree)) {
die "failed to find tree for $words[1]\n";
}
add_delta($cur_tree, $parent_tree);
add_packed($cur);
last;
}
close(PARENT);
if (!defined($parent_commit)) {
print STDERR "parentless commit $cur\n";
}
if ($? && ($ret = $? >> 8)) {
die "cat-file failed with $ret";
}
if ($cur eq $stop) {
last;
}
}close(RL);
if ($? && ($ret = $? >> 8)) {
die "rev-list failed with $ret";
}Hello Chris,
Quoted 1 line
size (du -sh .git) 2.5G 227M
wow that beats bitkeeper in size. What is missing to actual use such a approach in a distributed environment?
Thomas
Quoted 6 lines · Thomas Glanzmann
Hello Chris,
Quoted 1 line
size (du -sh .git) 2.5G 227M
wow that beats bitkeeper in size. What is missing to actual use such a approach in a distributed environment?
It's not quite fair to compare with bitkeeper, since my changeset comments are only the name of the bk->cvs patch, and I've only got 28k changesets vs bk's 60k or so.
In terms of actually making use of this, we need to deal with the hard linked files during push/pull. This means using -H on rsync and teaching the push/pull code about packed files.
git-pack needs to be able to unpack/undelta files so that people can clean a tree.
git-fsck-cache needs to understand packed files and deltas.
-chris
Quoted 6 lines · Thomas Glanzmann
Hello Chris,
Quoted 1 line
size (du -sh .git) 2.5G 227M
wow that beats bitkeeper in size. What is missing to actual use such a approach in a distributed environment?
Me completing fsck-cache support for delta objects.
Nicolas