Weird growth in packfile during initial push

I was doing a more recent conversion of the Gentoo repo, and ran into
some odd behavior in the packfile size.

For anybody else following the repo, you can now get it on the new hardware at:
http://git-exp.overlays.gentoo.org/gitweb/?p=exp/gentoo-x86.git;a=summary

I did the conversion with cvs2svn, packed, added the remote and pushed, only to
find that the pack on the remote side suddenly seemed to be ~60MiB larger.

$ time git repack -adf --window=250 --depth=250
real    19m59.339s
user    96m48.011s
sys     0m36.914s

$ ls -la /tmp/convert/gentoo-x86-cvs2git/.git/objects/pack
total 903804
drwxr-xr-x 2 robbat2 users       119 Apr 14 08:05 .
drwxr-xr-x 4 robbat2 users        28 Apr 14 08:05 ..
-r--r--r-- 1 robbat2 users 139155472 Apr 14 08:05 pack-f805bb448f864becfeac9c7f8a8ac2ef90c26787.idx
-r--r--r-- 1 robbat2 users 786336481 Apr 14 08:05 pack-f805bb448f864becfeac9c7f8a8ac2ef90c26787.pack

$ git remote add origin git+ssh://git@git-exp.overlays.gentoo.org/exp/gentoo-x86.git
$ git push origin master:master
Initialized empty Git repository in /var/gitroot/exp/gentoo-x86.git/
Counting objects: 4969800, done.
Delta compression using up to 8 threads.
Compressing objects: 100% (1217809/1217809), done.
Writing objects: 100% (4969800/4969800), 810.56 MiB | 21608 KiB/s, done.
Total 4969800 (delta 3735812), reused 4969800 (delta 3735812)
To git+ssh://git@git-exp.overlays.gentoo.org/exp/gentoo-x86.git
 * [new branch]      master -> master

$ ls -la /var/gitroot/exp/gentoo-x86.git/objects/pack
total 966876
drwxr-xr-x 2 git git      4096 Apr 14 08:43 .
drwxr-xr-x 4 git git      4096 Apr 14 08:35 ..
-r--r--r-- 1 git git 139155472 Apr 14 08:43 pack-f805bb448f864becfeac9c7f8a8ac2ef90c26787.idx
-r--r--r-- 1 git git 849936308 Apr 14 08:43 pack-f805bb448f864becfeac9c7f8a8ac2ef90c26787.pack

On the client side after the initial clone, it DOES match (in size) what was
cloned.

(If you're looking for the 849MB one right now, I'll have to get it back for
you, I wanted to save that extra space so just did an rsync of the other pack
over the too-large one for now).

-- 
Robin Hugh Johnson
Gentoo Linux Developer & Infra Guy
E-Mail     : robbat2@gentoo.org
GnuPG FP   : 11AC BA4F 4778 E3F6 E4ED  F38E B27B 944E 3488 4E85

On Wed, 15 Apr 2009, Robin H. Johnson wrote:

I was doing a more recent conversion of the Gentoo repo, and ran into
some odd behavior in the packfile size.

For anybody else following the repo, you can now get it on the new hardware at:
http://git-exp.overlays.gentoo.org/gitweb/?p=exp/gentoo-x86.git;a=summary

I did the conversion with cvs2svn, packed, added the remote and pushed, only to
find that the pack on the remote side suddenly seemed to be ~60MiB larger.

Hmmm.

$ ls -la /tmp/convert/gentoo-x86-cvs2git/.git/objects/pack
total 903804
drwxr-xr-x 2 robbat2 users       119 Apr 14 08:05 .
drwxr-xr-x 4 robbat2 users        28 Apr 14 08:05 ..
-r--r--r-- 1 robbat2 users 139155472 Apr 14 08:05 pack-f805bb448f864becfeac9c7f8a8ac2ef90c26787.idx
-r--r--r-- 1 robbat2 users 786336481 Apr 14 08:05 pack-f805bb448f864becfeac9c7f8a8ac2ef90c26787.pack

$ git remote add origin git+ssh://git@git-exp.overlays.gentoo.org/exp/gentoo-x86.git
$ git push origin master:master
Initialized empty Git repository in /var/gitroot/exp/gentoo-x86.git/
Counting objects: 4969800, done.
Delta compression using up to 8 threads.
Compressing objects: 100% (1217809/1217809), done.
Writing objects: 100% (4969800/4969800), 810.56 MiB | 21608 KiB/s, done.
Total 4969800 (delta 3735812), reused 4969800 (delta 3735812)

Here we know for sure that all objects were directly reused, so no 
attempt at recompressing them was done.  The only thing that 
pack-objects might do in this case in addition to directly streaming the 
existing pack is to convert delta object headers from OFS_DELTA to 
REF_DELTA.

$ ls -la /var/gitroot/exp/gentoo-x86.git/objects/pack
total 966876
drwxr-xr-x 2 git git      4096 Apr 14 08:43 .
drwxr-xr-x 4 git git      4096 Apr 14 08:35 ..
-r--r--r-- 1 git git 139155472 Apr 14 08:43 pack-f805bb448f864becfeac9c7f8a8ac2ef90c26787.idx
-r--r--r-- 1 git git 849936308 Apr 14 08:43 pack-f805bb448f864becfeac9c7f8a8ac2ef90c26787.pack

Let's see if my theory stands:

	849936308 - 786336481 = 63599827
	63599827 / 3735812 = 17.02

Hence an average difference of 17 bytes per delta.  Given that REF_DELTA 
objects have a 20-byte SHA1 base reference which is replaced with a 
variable length encoding of a pack offset in the OFS_DELTA case, we're 
talking about 2.98 bytes for that offset encoding which feels about 
right.

[...]

And the code matches this theory as well.  Can you try this patch if you 
have a chance?

diff --git a/builtin-send-pack.c b/builtin-send-pack.c
index 91c3651..e41adbf 100644
--- a/builtin-send-pack.c
+++ b/builtin-send-pack.c

@@ -44,12 +44,16 @@ static int pack_objects(int fd, struct ref *refs, struct extra_have_objects *ext
 		"--stdout",
 		NULL,
 		NULL,
+		NULL,
 	};
 	struct child_process po;
 	int i;
 
+	i = 4;
 	if (args->use_thin_pack)
-		argv[4] = "--thin";
+		argv[i++] = "--thin";
+	if (args->use_ofs_delta)
+		argv[i++] = "--delta-base-offset";
 	memset(&po, 0, sizeof(po));
 	po.argv = argv;
 	po.in = -1;

@@ -316,6 +320,8 @@ int send_pack(struct send_pack_args *args,
 		ask_for_status_report = 1;
 	if (server_supports("delete-refs"))
 		allow_deleting_refs = 1;
+	if (server_supports("ofs-delta"))
+		args->use_ofs_delta = 1;
 
 	if (!remote_refs) {
 		fprintf(stderr, "No refs in common and none specified; doing nothing.\n"

diff --git a/send-pack.h b/send-pack.h
index 83d76c7..1d7b1b3 100644
--- a/send-pack.h
+++ b/send-pack.h

@@ -6,6 +6,7 @@ struct send_pack_args {
 		send_mirror:1,
 		force_update:1,
 		use_thin_pack:1,
+		use_ofs_delta:1,
 		dry_run:1;
 };
 

Nicolas

Nicolas Pitre [off-list ref] writes:

quoted

$ git push origin master:master
Initialized empty Git repository in /var/gitroot/exp/gentoo-x86.git/
Counting objects: 4969800, done.
Delta compression using up to 8 threads.
Compressing objects: 100% (1217809/1217809), done.
Writing objects: 100% (4969800/4969800), 810.56 MiB | 21608 KiB/s, done.
Total 4969800 (delta 3735812), reused 4969800 (delta 3735812)

Here we know for sure that all objects were directly reused, so no 
attempt at recompressing them was done.  The only thing that 
pack-objects might do in this case in addition to directly streaming the 
existing pack is to convert delta object headers from OFS_DELTA to 
REF_DELTA.

quoted

$ ls -la /var/gitroot/exp/gentoo-x86.git/objects/pack
total 966876
drwxr-xr-x 2 git git      4096 Apr 14 08:43 .
drwxr-xr-x 4 git git      4096 Apr 14 08:35 ..
-r--r--r-- 1 git git 139155472 Apr 14 08:43 pack-f805bb448f864becfeac9c7f8a8ac2ef90c26787.idx
-r--r--r-- 1 git git 849936308 Apr 14 08:43 pack-f805bb448f864becfeac9c7f8a8ac2ef90c26787.pack

Let's see if my theory stands:

	849936308 - 786336481 = 63599827
	63599827 / 3735812 = 17.02

Hence an average difference of 17 bytes per delta.  Given that REF_DELTA 
objects have a 20-byte SHA1 base reference which is replaced with a 
variable length encoding of a pack offset in the OFS_DELTA case, we're 
talking about 2.98 bytes for that offset encoding which feels about 
right.

[...]

And the code matches this theory as well.  Can you try this patch if you 
have a chance?

Is there any progress on this?

I think you did a veryclear analysis.  8% size reduction is not only
unignorable but use of delta offset should also help runtime efficiency,
right?

On Wed, 29 Apr 2009, Junio C Hamano wrote:

Nicolas Pitre [off-list ref] writes:

quoted

And the code matches this theory as well.  Can you try this patch if you 
have a chance?

Is there any progress on this?

I'll try to find 5 min tomorrow to test the patch.


Nicolas

On Wed, Apr 29, 2009 at 04:57:37PM -0700, Junio C Hamano wrote:

quoted

And the code matches this theory as well.  Can you try this patch if you 
have a chance?

Is there any progress on this?

Sorry, I was just away for 2 weeks, only got back late yesterday. I'll
try to get to it in the next few days unless Nicolas beats me to it.

-- 
Robin Hugh Johnson
Gentoo Linux Developer & Infra Guy
E-Mail     : robbat2@gentoo.org
GnuPG FP   : 11AC BA4F 4778 E3F6 E4ED  F38E B27B 944E 3488 4E85

The fetching of OFS_DELTA objects has been negotiated between both peers 
since git version 1.4.4.  However, this was missing from the push side 
where every OFS_DELTA objects were always converted to REF_DELTA objects 
causing an increase in transferred data.

To fix this, both the client and the server processes have to be 
modified: the former to invoke pack-objects with --delta-base-offset 
when the server provides the ofs-delta capability, and the later to send 
that capability when OFS_DELTA objects are allowed as already indicated 
by the repack.usedeltabaseoffset config variable which is TRUE by 
default since git v1.6.0.

Signed-off-by: Nicolas Pitre <redacted>
---

On Wed, 29 Apr 2009, Junio C Hamano wrote:

Nicolas Pitre [off-list ref] writes:

quoted

Hence an average difference of 17 bytes per delta.  Given that REF_DELTA 
objects have a 20-byte SHA1 base reference which is replaced with a 
variable length encoding of a pack offset in the OFS_DELTA case, we're 
talking about 2.98 bytes for that offset encoding which feels about 
right.

[...]

And the code matches this theory as well.  Can you try this patch if you 
have a chance?

Is there any progress on this?

I think you did a veryclear analysis.  8% size reduction is not only
unignorable but use of delta offset should also help runtime efficiency,
right?

Indeed.

Here's the final patch.  My initial one didn't work because the server 
side didn't advertise the needed capability.  So both sides will have to 
be updated for pushes with OFS_DELTA to kick in.

 builtin-receive-pack.c |   22 +++++++++++++++-------
 builtin-send-pack.c    |    8 +++++++-
 send-pack.h            |    1 +
 3 files changed, 23 insertions(+), 8 deletions(-)

diff --git a/builtin-receive-pack.c b/builtin-receive-pack.c
index a970b39..4b9d921 100644
--- a/builtin-receive-pack.c
+++ b/builtin-receive-pack.c

@@ -27,10 +27,9 @@ static int receive_unpack_limit = -1;
 static int transfer_unpack_limit = -1;
 static int unpack_limit = 100;
 static int report_status;
+static int prefer_ofs_delta = 1;
 static const char *head_name;
-
-static char capabilities[] = " report-status delete-refs ";
-static int capabilities_sent;
+static char *capabilities_to_send;
 
 static enum deny_action parse_deny_action(const char *var, const char *value)
 {

@@ -84,24 +83,29 @@ static int receive_pack_config(const char *var, const char *value, void *cb)
 		return 0;
 	}
 
+	if (strcmp(var, "repack.usedeltabaseoffset") == 0) {
+		prefer_ofs_delta = git_config_bool(var, value);
+		return 0;
+	}
+
 	return git_default_config(var, value, cb);
 }
 
 static int show_ref(const char *path, const unsigned char *sha1, int flag, void *cb_data)
 {
-	if (capabilities_sent)
+	if (!capabilities_to_send)
 		packet_write(1, "%s %s\n", sha1_to_hex(sha1), path);
 	else
 		packet_write(1, "%s %s%c%s\n",
-			     sha1_to_hex(sha1), path, 0, capabilities);
-	capabilities_sent = 1;
+			     sha1_to_hex(sha1), path, 0, capabilities_to_send);
+	capabilities_to_send = NULL;
 	return 0;
 }
 
 static void write_head_info(void)
 {
 	for_each_ref(show_ref, NULL);
-	if (!capabilities_sent)
+	if (capabilities_to_send)
 		show_ref("capabilities^{}", null_sha1, 0, NULL);
 
 }

@@ -687,6 +691,10 @@ int cmd_receive_pack(int argc, const char **argv, const char *prefix)
 	else if (0 <= receive_unpack_limit)
 		unpack_limit = receive_unpack_limit;
 
+	capabilities_to_send = (prefer_ofs_delta) ?
+		" report-status delete-refs ofs-delta " :
+		" report-status delete-refs ";
+
 	add_alternate_refs();
 	write_head_info();
 	clear_extra_refs();

diff --git a/builtin-send-pack.c b/builtin-send-pack.c
index d5a1c48..473a3de 100644
--- a/builtin-send-pack.c
+++ b/builtin-send-pack.c

@@ -43,12 +43,16 @@ static int pack_objects(int fd, struct ref *refs, struct extra_have_objects *ext
 		"--stdout",
 		NULL,
 		NULL,
+		NULL,
 	};
 	struct child_process po;
 	int i;
 
+	i = 4;
 	if (args->use_thin_pack)
-		argv[4] = "--thin";
+		argv[i++] = "--thin";
+	if (args->use_ofs_delta)
+		argv[i++] = "--delta-base-offset";
 	memset(&po, 0, sizeof(po));
 	po.argv = argv;
 	po.in = -1;

@@ -315,6 +319,8 @@ int send_pack(struct send_pack_args *args,
 		ask_for_status_report = 1;
 	if (server_supports("delete-refs"))
 		allow_deleting_refs = 1;
+	if (server_supports("ofs-delta"))
+		args->use_ofs_delta = 1;
 
 	if (!remote_refs) {
 		fprintf(stderr, "No refs in common and none specified; doing nothing.\n"

diff --git a/send-pack.h b/send-pack.h
index 83d76c7..1d7b1b3 100644
--- a/send-pack.h
+++ b/send-pack.h

@@ -6,6 +6,7 @@ struct send_pack_args {
 		send_mirror:1,
 		force_update:1,
 		use_thin_pack:1,
+		use_ofs_delta:1,
 		dry_run:1;
 };
 

Nicolas Pitre [off-list ref] wrote:

The fetching of OFS_DELTA objects has been negotiated between both peers 
since git version 1.4.4.  However, this was missing from the push side 
where every OFS_DELTA objects were always converted to REF_DELTA objects 
causing an increase in transferred data.

Folks, this may have broken git push for me.

I'm trying to debug it right now, but something in next between
46488d2 and 03e1664 has caused "git push" to not create a pack
file, sending the remote peer 0 objects, when really we should have
transmitted objects, e.g. in the case I just looked at, we should
have sent 11.

FWIW, I'm currently blaming this change as its the only thing to
touch builtin-send-pack.c in that commit range.  :-)

/me goes off to debug this further...
 

 builtin-receive-pack.c |   22 +++++++++++++++-------
 builtin-send-pack.c    |    8 +++++++-
 send-pack.h            |    1 +
 3 files changed, 23 insertions(+), 8 deletions(-)

-- 
Shawn.

"Shawn O. Pearce" [off-list ref] wrote:

Nicolas Pitre [off-list ref] wrote:

quoted

The fetching of OFS_DELTA objects has been negotiated between both peers 
since git version 1.4.4.  However, this was missing from the push side 
where every OFS_DELTA objects were always converted to REF_DELTA objects 
causing an increase in transferred data.

Folks, this may have broken git push for me.

I'm trying to debug it right now, but something in next between
46488d2 and 03e1664 has caused "git push" to not create a pack
file, sending the remote peer 0 objects, when really we should have
transmitted objects, e.g. in the case I just looked at, we should
have sent 11.

Uhm, never mind.

Somehow my incremental build failed horribly; it compiled and created
a git-push which worked "some of the time".  Building again produced
a working git-push.

Scary stuff.  Now I have to worry about the toolchain on this system.
But I don't think there is a problem in git.git.
 
-- 
Shawn.