[PATCH v3 0/4] Improve push performance with lots of refs

[PATCH v3 0/4] Improve push performance with lots of refs

[brian m. carlson]

This series contains patches to address a significant push performance
regression in repositories with large amounts of refs.  It avoids
performing expensive edge marking unless the repository is shallow.

The first patch in the series is a fix for a minor typo I discovered
when editing the documentation.  The second patch implements git
rev-list --objects-edge-aggressive, and the third patch ensures it's
used for shallow repos only.  The final patch ensures that sending packs
to shallow clients use --object-edge-aggressive as well.

The only change from v2 is the addition of a fourth patch, which fixes
t5500.  It's necessary because the test wants packs for fetches to
shallow clones to be minimal.

I'm not especially thrilled with having to provide a --shallow command
line argument, but the alternative is to buffer a potentially large
amount of data in order to determine whether the remote side is shallow.

The original fix was suggested by Duy Nguyen.

brian m. carlson (4):
  Documentation: add missing article in rev-list-options.txt
  rev-list: add an option to mark fewer edges as uninteresting
  pack-objects: use --objects-edge-aggressive only for shallow repos
  upload-pack: use --objects-edge-aggressive for shallow fetches

 Documentation/git-pack-objects.txt | 7 ++++++-
 Documentation/git-rev-list.txt     | 3 ++-
 Documentation/rev-list-options.txt | 7 ++++++-
 builtin/pack-objects.c             | 7 ++++++-
 list-objects.c                     | 4 ++--
 revision.c                         | 6 ++++++
 revision.h                         | 1 +
 upload-pack.c                      | 4 +++-
 8 files changed, 32 insertions(+), 7 deletions(-)

-- 
2.2.1.209.g41e5f3a

[PATCH v3 1/4] Documentation: add missing article in rev-list-options.txt

[brian m. carlson]

Add the missing article "a".

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 Documentation/rev-list-options.txt | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index afccfdc..2277fcb 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -653,7 +653,7 @@ These options are mostly targeted for packing of Git repositories.
 --objects-edge::
 	Similar to `--objects`, but also print the IDs of excluded
 	commits prefixed with a ``-'' character.  This is used by
-	linkgit:git-pack-objects[1] to build ``thin'' pack, which records
+	linkgit:git-pack-objects[1] to build a ``thin'' pack, which records
 	objects in deltified form based on objects contained in these
 	excluded commits to reduce network traffic.
 
-- 
2.2.1.209.g41e5f3a

[PATCH v3 2/4] rev-list: add an option to mark fewer edges as uninteresting

[brian m. carlson]

In commit fbd4a70 (list-objects: mark more commits as edges in
mark_edges_uninteresting - 2013-08-16), we marked an increasing number
of edges uninteresting.  This change, and the subsequent change to make
this conditional on --objects-edge, are used by --thin to make much
smaller packs for shallow clones.

Unfortunately, they cause a significant performance regression when
pushing non-shallow clones with lots of refs (23.322 seconds vs.
4.785 seconds with 22400 refs).  Add an option to git rev-list,
--objects-edge-aggressive, that preserves this more aggressive behavior,
while leaving --objects-edge to provide more performant behavior.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 Documentation/git-rev-list.txt     | 3 ++-
 Documentation/rev-list-options.txt | 4 ++++
 list-objects.c                     | 4 ++--
 revision.c                         | 6 ++++++
 revision.h                         | 1 +
 5 files changed, 15 insertions(+), 3 deletions(-)

diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt
index fd7f8b5..5b11922 100644
--- a/Documentation/git-rev-list.txt
+++ b/Documentation/git-rev-list.txt
@@ -46,7 +46,8 @@ SYNOPSIS
 	     [ \--extended-regexp | -E ]
 	     [ \--fixed-strings | -F ]
 	     [ \--date=(local|relative|default|iso|iso-strict|rfc|short) ]
-	     [ [\--objects | \--objects-edge] [ \--unpacked ] ]
+	     [ [ \--objects | \--objects-edge | \--objects-edge-aggressive ]
+	       [ \--unpacked ] ]
 	     [ \--pretty | \--header ]
 	     [ \--bisect ]
 	     [ \--bisect-vars ]
diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 2277fcb..8cb6f92 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -657,6 +657,10 @@ These options are mostly targeted for packing of Git repositories.
 	objects in deltified form based on objects contained in these
 	excluded commits to reduce network traffic.
 
+--objects-edge-aggressive::
+	Similar to `--objects-edge`, but it tries harder to find excluded
+	commits at the cost of increased time.
+
 --unpacked::
 	Only useful with `--objects`; print the object IDs that are not
 	in packs.
diff --git a/list-objects.c b/list-objects.c
index 2910bec..2a139b6 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -157,7 +157,7 @@ void mark_edges_uninteresting(struct rev_info *revs, show_edge_fn show_edge)
 
 		if (commit->object.flags & UNINTERESTING) {
 			mark_tree_uninteresting(commit->tree);
-			if (revs->edge_hint && !(commit->object.flags & SHOWN)) {
+			if (revs->edge_hint_aggressive && !(commit->object.flags & SHOWN)) {
 				commit->object.flags |= SHOWN;
 				show_edge(commit);
 			}
@@ -165,7 +165,7 @@ void mark_edges_uninteresting(struct rev_info *revs, show_edge_fn show_edge)
 		}
 		mark_edge_parents_uninteresting(commit, revs, show_edge);
 	}
-	if (revs->edge_hint) {
+	if (revs->edge_hint_aggressive) {
 		for (i = 0; i < revs->cmdline.nr; i++) {
 			struct object *obj = revs->cmdline.rev[i].item;
 			struct commit *commit = (struct commit *)obj;
diff --git a/revision.c b/revision.c
index 75dda92..753dd2f 100644
--- a/revision.c
+++ b/revision.c
@@ -1853,6 +1853,12 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
 		revs->tree_objects = 1;
 		revs->blob_objects = 1;
 		revs->edge_hint = 1;
+	} else if (!strcmp(arg, "--objects-edge-aggressive")) {
+		revs->tag_objects = 1;
+		revs->tree_objects = 1;
+		revs->blob_objects = 1;
+		revs->edge_hint = 1;
+		revs->edge_hint_aggressive = 1;
 	} else if (!strcmp(arg, "--verify-objects")) {
 		revs->tag_objects = 1;
 		revs->tree_objects = 1;
diff --git a/revision.h b/revision.h
index 9cb5adc..033a244 100644
--- a/revision.h
+++ b/revision.h
@@ -93,6 +93,7 @@ struct rev_info {
 			blob_objects:1,
 			verify_objects:1,
 			edge_hint:1,
+			edge_hint_aggressive:1,
 			limited:1,
 			unpacked:1,
 			boundary:2,
-- 
2.2.1.209.g41e5f3a

Re: [PATCH v3 2/4] rev-list: add an option to mark fewer edges as uninteresting

[Michael Blume]

This patch causes an error on my mac, test 5500 fetch-pack errors on
part 44 - fetch creating new shallow root. It looks for "remote: Total
1" in the fetch output and gets 3 instead.

On Tue, Dec 23, 2014 at 7:01 AM, brian m. carlson
<sandals@crustytoothpaste.net> wrote:
> In commit fbd4a70 (list-objects: mark more commits as edges in
> mark_edges_uninteresting - 2013-08-16), we marked an increasing number
> of edges uninteresting.  This change, and the subsequent change to make
> this conditional on --objects-edge, are used by --thin to make much
> smaller packs for shallow clones.
>
> Unfortunately, they cause a significant performance regression when
> pushing non-shallow clones with lots of refs (23.322 seconds vs.
> 4.785 seconds with 22400 refs).  Add an option to git rev-list,
> --objects-edge-aggressive, that preserves this more aggressive behavior,
> while leaving --objects-edge to provide more performant behavior.
>
> Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
> ---
>  Documentation/git-rev-list.txt     | 3 ++-
>  Documentation/rev-list-options.txt | 4 ++++
>  list-objects.c                     | 4 ++--
>  revision.c                         | 6 ++++++
>  revision.h                         | 1 +
>  5 files changed, 15 insertions(+), 3 deletions(-)
>
> diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt
> index fd7f8b5..5b11922 100644
> --- a/Documentation/git-rev-list.txt
> +++ b/Documentation/git-rev-list.txt
> @@ -46,7 +46,8 @@ SYNOPSIS
>              [ \--extended-regexp | -E ]
>              [ \--fixed-strings | -F ]
>              [ \--date=(local|relative|default|iso|iso-strict|rfc|short) ]
> -            [ [\--objects | \--objects-edge] [ \--unpacked ] ]
> +            [ [ \--objects | \--objects-edge | \--objects-edge-aggressive ]
> +              [ \--unpacked ] ]
>              [ \--pretty | \--header ]
>              [ \--bisect ]
>              [ \--bisect-vars ]
> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
> index 2277fcb..8cb6f92 100644
> --- a/Documentation/rev-list-options.txt
> +++ b/Documentation/rev-list-options.txt
> @@ -657,6 +657,10 @@ These options are mostly targeted for packing of Git repositories.
>         objects in deltified form based on objects contained in these
>         excluded commits to reduce network traffic.
>
> +--objects-edge-aggressive::
> +       Similar to `--objects-edge`, but it tries harder to find excluded
> +       commits at the cost of increased time.
> +
>  --unpacked::
>         Only useful with `--objects`; print the object IDs that are not
>         in packs.
> diff --git a/list-objects.c b/list-objects.c
> index 2910bec..2a139b6 100644
> --- a/list-objects.c
> +++ b/list-objects.c
> @@ -157,7 +157,7 @@ void mark_edges_uninteresting(struct rev_info *revs, show_edge_fn show_edge)
>
>                 if (commit->object.flags & UNINTERESTING) {
>                         mark_tree_uninteresting(commit->tree);
> -                       if (revs->edge_hint && !(commit->object.flags & SHOWN)) {
> +                       if (revs->edge_hint_aggressive && !(commit->object.flags & SHOWN)) {
>                                 commit->object.flags |= SHOWN;
>                                 show_edge(commit);
>                         }
> @@ -165,7 +165,7 @@ void mark_edges_uninteresting(struct rev_info *revs, show_edge_fn show_edge)
>                 }
>                 mark_edge_parents_uninteresting(commit, revs, show_edge);
>         }
> -       if (revs->edge_hint) {
> +       if (revs->edge_hint_aggressive) {
>                 for (i = 0; i < revs->cmdline.nr; i++) {
>                         struct object *obj = revs->cmdline.rev[i].item;
>                         struct commit *commit = (struct commit *)obj;
> diff --git a/revision.c b/revision.c
> index 75dda92..753dd2f 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -1853,6 +1853,12 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
>                 revs->tree_objects = 1;
>                 revs->blob_objects = 1;
>                 revs->edge_hint = 1;
> +       } else if (!strcmp(arg, "--objects-edge-aggressive")) {
> +               revs->tag_objects = 1;
> +               revs->tree_objects = 1;
> +               revs->blob_objects = 1;
> +               revs->edge_hint = 1;
> +               revs->edge_hint_aggressive = 1;
>         } else if (!strcmp(arg, "--verify-objects")) {
>                 revs->tag_objects = 1;
>                 revs->tree_objects = 1;
> diff --git a/revision.h b/revision.h
> index 9cb5adc..033a244 100644
> --- a/revision.h
> +++ b/revision.h
> @@ -93,6 +93,7 @@ struct rev_info {
>                         blob_objects:1,
>                         verify_objects:1,
>                         edge_hint:1,
> +                       edge_hint_aggressive:1,
>                         limited:1,
>                         unpacked:1,
>                         boundary:2,
> --
> 2.2.1.209.g41e5f3a
>
> --
> To unsubscribe from this list: send the line "unsubscribe git" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v3 2/4] rev-list: add an option to mark fewer edges as uninteresting

[Jeff King]

On Tue, Dec 23, 2014 at 12:55:48PM -0500, Michael Blume wrote:

> This patch causes an error on my mac, test 5500 fetch-pack errors on
> part 44 - fetch creating new shallow root. It looks for "remote: Total
> 1" in the fetch output and gets 3 instead.

It fails for me on Linux, too. Interestingly the tip of the series
passes. I didn't investigate further.

-Peff

Re: [PATCH v3 2/4] rev-list: add an option to mark fewer edges as uninteresting

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Tue, Dec 23, 2014 at 12:55:48PM -0500, Michael Blume wrote:
>
>> This patch causes an error on my mac, test 5500 fetch-pack errors on
>> part 44 - fetch creating new shallow root. It looks for "remote: Total
>> 1" in the fetch output and gets 3 instead.
>
> It fails for me on Linux, too. Interestingly the tip of the series
> passes. I didn't investigate further.

Not surprised, as the first three are the same from the yesterday's
one that failed for everybody.

Re: [PATCH v3 2/4] rev-list: add an option to mark fewer edges as uninteresting

[brian m. carlson]

[-- Attachment #1: Type: text/plain, Size: 929 bytes --]

On Tue, Dec 23, 2014 at 01:51:42PM -0500, Jeff King wrote:
> On Tue, Dec 23, 2014 at 12:55:48PM -0500, Michael Blume wrote:
> 
> > This patch causes an error on my mac, test 5500 fetch-pack errors on
> > part 44 - fetch creating new shallow root. It looks for "remote: Total
> > 1" in the fetch output and gets 3 instead.
> 
> It fails for me on Linux, too. Interestingly the tip of the series
> passes. I didn't investigate further.

Yes, the tip of the series fixes that issue.  I had trouble coming up
with a good technique to split the patches in a way such that they were
logically distinct yet addressed the failure.  I had an epiphany on how
to do that last night, so I'll reroll sometime today.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | http://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: RSA v4 4096b: 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[PATCH v3 3/4] pack-objects: use --objects-edge-aggressive only for shallow repos

[brian m. carlson]

Using --objects-edge-aggressive is important for shallow repos, as it
can result in a much smaller pack (in some cases, 10% of the size).
However, it performs poorly on large non-shallow repositories with many
refs.  Since shallow repositories are less likely to have many refs (due
to having less history), the smaller pack size is advantageous there.
Adjust pack-objects to use --objects-edge-aggressive only for shallow
repositories.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 Documentation/rev-list-options.txt | 3 ++-
 builtin/pack-objects.c             | 4 +++-
 2 files changed, 5 insertions(+), 2 deletions(-)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 8cb6f92..2984f40 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -659,7 +659,8 @@ These options are mostly targeted for packing of Git repositories.
 
 --objects-edge-aggressive::
 	Similar to `--objects-edge`, but it tries harder to find excluded
-	commits at the cost of increased time.
+	commits at the cost of increased time.  This is used instead of
+	`--objects-edge` to build ``thin'' packs for shallow repositories.
 
 --unpacked::
 	Only useful with `--objects`; print the object IDs that are not
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 3f9f5c7..f3ba861 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -2711,7 +2711,9 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 	argv_array_push(&rp, "pack-objects");
 	if (thin) {
 		use_internal_rev_list = 1;
-		argv_array_push(&rp, "--objects-edge");
+		argv_array_push(&rp, is_repository_shallow()
+				? "--objects-edge-aggressive"
+				: "--objects-edge");
 	} else
 		argv_array_push(&rp, "--objects");
 
-- 
2.2.1.209.g41e5f3a

[PATCH v3 4/4] upload-pack: use --objects-edge-aggressive for shallow fetches

[brian m. carlson]

When fetching into a shallow repository, we want to aggressively mark
edges as uninteresting, since this decreases the pack size.  However,
is_shallow_repository() returns false on the server side, since the
server is not shallow.

As the server, we get an indication of whether the client is shallow
based on stdin; however, by the time we get to parsing stdin, we already
will have called setup_revisions and won't be able to change our
decision anymore.  Teach pack-objects a --shallow option to indicate
that the remote side is shallow and use it in upload-pack.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 Documentation/git-pack-objects.txt | 7 ++++++-
 builtin/pack-objects.c             | 5 ++++-
 upload-pack.c                      | 4 +++-
 3 files changed, 13 insertions(+), 3 deletions(-)

diff --git a/Documentation/git-pack-objects.txt b/Documentation/git-pack-objects.txt
index d2d8f47..c2f76fb 100644
--- a/Documentation/git-pack-objects.txt
+++ b/Documentation/git-pack-objects.txt
@@ -13,7 +13,7 @@ SYNOPSIS
 	[--no-reuse-delta] [--delta-base-offset] [--non-empty]
 	[--local] [--incremental] [--window=<n>] [--depth=<n>]
 	[--revs [--unpacked | --all]] [--stdout | base-name]
-	[--keep-true-parents] < object-list
+	[--shallow] [--keep-true-parents] < object-list
 
 
 DESCRIPTION
@@ -190,6 +190,11 @@ required objects and is thus unusable by Git without making it
 self-contained. Use `git index-pack --fix-thin`
 (see linkgit:git-index-pack[1]) to restore the self-contained property.
 
+--shallow::
+	Optimize a pack that will be provided to a client with a shallow
+	repository.  This option, combined with \--thin, can result in a
+	smaller pack at the cost of speed.
+
 --delta-base-offset::
 	A packed archive can express the base object of a delta as
 	either a 20-byte object name or as an offset in the
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index f3ba861..6bfbd3d 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -2613,6 +2613,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 {
 	int use_internal_rev_list = 0;
 	int thin = 0;
+	int shallow = 0;
 	int all_progress_implied = 0;
 	struct argv_array rp = ARGV_ARRAY_INIT;
 	int rev_list_unpacked = 0, rev_list_all = 0, rev_list_reflog = 0;
@@ -2677,6 +2678,8 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 		  PARSE_OPT_OPTARG, option_parse_unpack_unreachable },
 		OPT_BOOL(0, "thin", &thin,
 			 N_("create thin packs")),
+		OPT_BOOL(0, "shallow", &shallow,
+			 N_("create packs suitable for shallow fetches")),
 		OPT_BOOL(0, "honor-pack-keep", &ignore_packed_keep,
 			 N_("ignore packs that have companion .keep file")),
 		OPT_INTEGER(0, "compression", &pack_compression_level,
@@ -2711,7 +2714,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 	argv_array_push(&rp, "pack-objects");
 	if (thin) {
 		use_internal_rev_list = 1;
-		argv_array_push(&rp, is_repository_shallow()
+		argv_array_push(&rp, is_repository_shallow() || shallow
 				? "--objects-edge-aggressive"
 				: "--objects-edge");
 	} else
diff --git a/upload-pack.c b/upload-pack.c
index ac9ac15..b531a32 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -86,7 +86,7 @@ static void create_pack_file(void)
 		"corruption on the remote side.";
 	int buffered = -1;
 	ssize_t sz;
-	const char *argv[12];
+	const char *argv[13];
 	int i, arg = 0;
 	FILE *pipe_fd;
 
@@ -100,6 +100,8 @@ static void create_pack_file(void)
 		argv[arg++] = "--thin";
 
 	argv[arg++] = "--stdout";
+	if (shallow_nr)
+		argv[arg++] = "--shallow";
 	if (!no_progress)
 		argv[arg++] = "--progress";
 	if (use_ofs_delta)
-- 
2.2.1.209.g41e5f3a

Re: [PATCH v3 0/4] Improve push performance with lots of refs

[Junio C Hamano]

"brian m. carlson" <sandals@crustytoothpaste.net> writes:

> The only change from v2 is the addition of a fourth patch, which fixes
> t5500.  It's necessary because the test wants packs for fetches to
> shallow clones to be minimal.
>
> I'm not especially thrilled with having to provide a --shallow command
> line argument, but the alternative is to buffer a potentially large
> amount of data in order to determine whether the remote side is shallow.

You spell "--thin-aggressive" as two words, "--thin" "--shallow", in
this series, essentially, no?

I think this is going in the right direction.  The "shallow"
propagated on the wire from the fetcher is the right thing to use
to make this decision.

I wonder if the call to is_repository_shallow() is still necessary
(read: I would prefer to see it go away) where we decide between
"--objects-edge" and "--objects-edge-aggressive".

Here is the relevant part from 4/4:

@@ -2711,7 +2714,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 	argv_array_push(&rp, "pack-objects");
 	if (thin) {
 		use_internal_rev_list = 1;
-		argv_array_push(&rp, is_repository_shallow()
+		argv_array_push(&rp, is_repository_shallow() || shallow
 				? "--objects-edge-aggressive"
 				: "--objects-edge");
 	} else

Re: [PATCH v3 0/4] Improve push performance with lots of refs

[brian m. carlson]

[-- Attachment #1: Type: text/plain, Size: 962 bytes --]

On Tue, Dec 23, 2014 at 10:40:54AM -0800, Junio C Hamano wrote:
> You spell "--thin-aggressive" as two words, "--thin" "--shallow", in
> this series, essentially, no?

Essentially, yes.  It became obligatory after I noticed the test
failure, since that test actually checks whether the remote side sends
a shallow-optimized pack.

> I think this is going in the right direction.  The "shallow"
> propagated on the wire from the fetcher is the right thing to use
> to make this decision.
> 
> I wonder if the call to is_repository_shallow() is still necessary
> (read: I would prefer to see it go away) where we decide between
> "--objects-edge" and "--objects-edge-aggressive".

Okay.  I'll try to push it up the stack a little bit.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | http://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: RSA v4 4096b: 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]