[PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list

[PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list

[Brandon Casey]

From: Brandon Casey <drafnel@gmail.com>

When pushing, each ref in the local repository must be paired with a
ref advertised by the remote server.  Currently, this is performed by
first applying the refspec to the local ref to transform the local ref
into the name of the remote ref, and then performing a linear search
through the list of remote refs to see if the remote ref was advertised
by the remote system.

This has O(n) complexity and makes match_push_refs() be an O(n^2)
operation.  If there are many refs 100,000+, then this ref matching
can take a significant amount of time.  Let's populate a string_list
with the remote ref names to allow searching in O(log n) time and
reduce the complexity of match_push_refs() to O(n log n).

Dry-run push of a repository with 121913 refs:

        before     after
real    1m40.582s  0m0.804s
user    1m39.914s  0m0.515s
sys     0m0.125s   0m0.106s

Signed-off-by: Brandon Casey <drafnel@gmail.com>
---
 remote.c | 26 ++++++++++++++++++++++++--
 1 file changed, 24 insertions(+), 2 deletions(-)

diff --git a/remote.c b/remote.c
index 6f57830..b416b8e 100644
--- a/remote.c
+++ b/remote.c
@@ -1302,6 +1302,15 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds
 	free(sent_tips.tip);
 }
 
+static void prepare_searchable_ref_list(struct ref *ref, struct string_list *ref_list)
+{
+	for ( ; ref; ref = ref->next)
+		string_list_append_nodup(ref_list, ref->name)->util = ref;
+
+	sort_string_list(ref_list);
+}
+
+
 /*
  * Given the set of refs the local repository has, the set of refs the
  * remote repository has, and the refspec used for push, determine
@@ -1320,6 +1329,7 @@ int match_push_refs(struct ref *src, struct ref **dst,
 	int errs;
 	static const char *default_refspec[] = { ":", NULL };
 	struct ref *ref, **dst_tail = tail_ref(dst);
+	struct string_list ref_list = STRING_LIST_INIT_NODUP;
 
 	if (!nr_refspec) {
 		nr_refspec = 1;
@@ -1328,8 +1338,11 @@ int match_push_refs(struct ref *src, struct ref **dst,
 	rs = parse_push_refspec(nr_refspec, (const char **) refspec);
 	errs = match_explicit_refs(src, *dst, &dst_tail, rs, nr_refspec);
 
+	prepare_searchable_ref_list(*dst, &ref_list);
+
 	/* pick the remainder */
 	for (ref = src; ref; ref = ref->next) {
+		struct string_list_item *dst_item;
 		struct ref *dst_peer;
 		const struct refspec *pat = NULL;
 		char *dst_name;
@@ -1338,7 +1351,8 @@ int match_push_refs(struct ref *src, struct ref **dst,
 		if (!dst_name)
 			continue;
 
-		dst_peer = find_ref_by_name(*dst, dst_name);
+		dst_item = string_list_lookup(&ref_list, dst_name);
+		dst_peer = dst_item ? dst_item->util : NULL;
 		if (dst_peer) {
 			if (dst_peer->peer_ref)
 				/* We're already sending something to this ref. */
@@ -1355,6 +1369,8 @@ int match_push_refs(struct ref *src, struct ref **dst,
 			/* Create a new one and link it */
 			dst_peer = make_linked_ref(dst_name, &dst_tail);
 			hashcpy(dst_peer->new_sha1, ref->new_sha1);
+			string_list_insert(&ref_list, dst_peer->name)->util =
+				dst_peer;
 		}
 		dst_peer->peer_ref = copy_ref(ref);
 		dst_peer->force = pat->force;
@@ -1362,6 +1378,8 @@ int match_push_refs(struct ref *src, struct ref **dst,
 		free(dst_name);
 	}
 
+	string_list_clear(&ref_list, 0);
+
 	if (flags & MATCH_REFS_FOLLOW_TAGS)
 		add_missing_tags(src, dst, &dst_tail);
 
@@ -1376,11 +1394,15 @@ int match_push_refs(struct ref *src, struct ref **dst,
 
 			src_name = get_ref_match(rs, nr_refspec, ref, send_mirror, FROM_DST, NULL);
 			if (src_name) {
-				if (!find_ref_by_name(src, src_name))
+				if (!ref_list.nr)
+					prepare_searchable_ref_list(src,
+						&ref_list);
+				if (!string_list_has_string(&ref_list, src_name))
 					ref->peer_ref = alloc_delete_ref();
 				free(src_name);
 			}
 		}
+		string_list_clear(&ref_list, 0);
 	}
 	if (errs)
 		return -1;
-- 
1.8.3.1.440.gc2bf105

Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list

[Jeff King]

On Tue, Jul 02, 2013 at 04:53:48PM -0700, Brandon Casey wrote:

> From: Brandon Casey <drafnel@gmail.com>
> 
> When pushing, each ref in the local repository must be paired with a
> ref advertised by the remote server.  Currently, this is performed by
> first applying the refspec to the local ref to transform the local ref
> into the name of the remote ref, and then performing a linear search
> through the list of remote refs to see if the remote ref was advertised
> by the remote system.
> 
> This has O(n) complexity and makes match_push_refs() be an O(n^2)
> operation.

Just to be sure I understand correctly, is this actually O(m*n) where
"m" is the number of local refs and "n" is the number of remote refs?

For a repository that repeatedly pushes everything it has to the remote,
we end up with m=n, but it would not necessarily be the case if you are
pushing a subset of your refs. But even pushing a small number of refs
into a repository with a very large number of refs would be
unnecessarily slow, as we would do several O(n) lookups which could be
O(log n). So it may speed things up even in the case of a normal-sized
repo pushing to a large one.

> Dry-run push of a repository with 121913 refs:
> 
>         before     after
> real    1m40.582s  0m0.804s
> user    1m39.914s  0m0.515s
> sys     0m0.125s   0m0.106s

Very nice. :)

> Signed-off-by: Brandon Casey <drafnel@gmail.com>
> ---
>  remote.c | 26 ++++++++++++++++++++++++--
>  1 file changed, 24 insertions(+), 2 deletions(-)

Patch itself looks good to me, although...

> @@ -1362,6 +1378,8 @@ int match_push_refs(struct ref *src, struct ref **dst,
>  		free(dst_name);
>  	}
>  
> +	string_list_clear(&ref_list, 0);
> +
>  	if (flags & MATCH_REFS_FOLLOW_TAGS)
>  		add_missing_tags(src, dst, &dst_tail);
>  
> @@ -1376,11 +1394,15 @@ int match_push_refs(struct ref *src, struct ref **dst,
>  
>  			src_name = get_ref_match(rs, nr_refspec, ref, send_mirror, FROM_DST, NULL);
>  			if (src_name) {
> -				if (!find_ref_by_name(src, src_name))
> +				if (!ref_list.nr)
> +					prepare_searchable_ref_list(src,
> +						&ref_list);
> +				if (!string_list_has_string(&ref_list, src_name))

This hunk threw me for a bit, as it looked like we were lazily
initializing ref_list in case we had not done so earlier. But we would
have cleared it mid-way through the function (in the hunk above), and it
is only that we are reusing the same ref_list for two different
purposes.

I do not feel strongly about it, but it might be a little more obvious
to just declare a new variable in the block, like:

diff --git a/remote.c b/remote.c
index 75255af..53bef82 100644
--- a/remote.c
+++ b/remote.c
@@ -1399,6 +1399,7 @@ int match_push_refs(struct ref *src, struct ref **dst,
 		add_missing_tags(src, dst, &dst_tail);
 
 	if (send_prune) {
+		struct string_list src_ref_index = STRING_LIST_INIT_NODUP;
 		/* check for missing refs on the remote */
 		for (ref = *dst; ref; ref = ref->next) {
 			char *src_name;
@@ -1409,15 +1410,15 @@ int match_push_refs(struct ref *src, struct ref **dst,
 
 			src_name = get_ref_match(rs, nr_refspec, ref, send_mirror, FROM_DST, NULL);
 			if (src_name) {
-				if (!ref_list.nr)
+				if (!src_ref_index.nr)
 					prepare_searchable_ref_list(src,
-						&ref_list);
-				if (!string_list_has_string(&ref_list, src_name))
+						&src_ref_index);
+				if (!string_list_has_string(&src_ref_index, src_name))
 					ref->peer_ref = alloc_delete_ref();
 				free(src_name);
 			}
 		}
-		string_list_clear(&ref_list, 0);
+		string_list_clear(&src_ref_index, 0);
 	}
 	if (errs)
 		return -1;

And similarly maybe call the outer ref_list dst_ref_index or something.
I also note that we don't do the lazy-prepare for the other loop. I
guess that is because we assume that "src" is always non-NULL?

-Peff

Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list

[Brandon Casey]

On Tue, Jul 2, 2013 at 11:23 PM, Jeff King <peff@peff.net> wrote:
> On Tue, Jul 02, 2013 at 04:53:48PM -0700, Brandon Casey wrote:
>
>> From: Brandon Casey <drafnel@gmail.com>
>>
>> When pushing, each ref in the local repository must be paired with a
>> ref advertised by the remote server.  Currently, this is performed by
>> first applying the refspec to the local ref to transform the local ref
>> into the name of the remote ref, and then performing a linear search
>> through the list of remote refs to see if the remote ref was advertised
>> by the remote system.
>>
>> This has O(n) complexity and makes match_push_refs() be an O(n^2)
>> operation.
>
> Just to be sure I understand correctly, is this actually O(m*n) where
> "m" is the number of local refs and "n" is the number of remote refs?

Yes, O(m*n) is more correct.  I think you understand completely.

> For a repository that repeatedly pushes everything it has to the remote,
> we end up with m=n, but it would not necessarily be the case if you are
> pushing a subset of your refs. But even pushing a small number of refs
> into a repository with a very large number of refs would be
> unnecessarily slow, as we would do several O(n) lookups which could be
> O(log n). So it may speed things up even in the case of a normal-sized
> repo pushing to a large one.

Right.  For repos with few refs on either side, I don't think there
will be any measurable difference.  When pushing a single ref to a
repo with a very large number of refs, we will see a very small net
loss for the time required to prepare the string list (which grows
linearly with the number of remote refs).  After 2 or 3 refs, we
should see a net gain.

So we're really just improving our worst case performance here.

>> Dry-run push of a repository with 121913 refs:
>>
>>         before     after
>> real    1m40.582s  0m0.804s
>> user    1m39.914s  0m0.515s
>> sys     0m0.125s   0m0.106s
>
> Very nice. :)
>
>> Signed-off-by: Brandon Casey <drafnel@gmail.com>
>> ---
>>  remote.c | 26 ++++++++++++++++++++++++--
>>  1 file changed, 24 insertions(+), 2 deletions(-)
>
> Patch itself looks good to me, although...
>
>> @@ -1362,6 +1378,8 @@ int match_push_refs(struct ref *src, struct ref **dst,
>>               free(dst_name);
>>       }
>>
>> +     string_list_clear(&ref_list, 0);
>> +
>>       if (flags & MATCH_REFS_FOLLOW_TAGS)
>>               add_missing_tags(src, dst, &dst_tail);
>>
>> @@ -1376,11 +1394,15 @@ int match_push_refs(struct ref *src, struct ref **dst,
>>
>>                       src_name = get_ref_match(rs, nr_refspec, ref, send_mirror, FROM_DST, NULL);
>>                       if (src_name) {
>> -                             if (!find_ref_by_name(src, src_name))
>> +                             if (!ref_list.nr)
>> +                                     prepare_searchable_ref_list(src,
>> +                                             &ref_list);
>> +                             if (!string_list_has_string(&ref_list, src_name))
>
> This hunk threw me for a bit, as it looked like we were lazily
> initializing ref_list in case we had not done so earlier. But we would
> have cleared it mid-way through the function (in the hunk above), and it
> is only that we are reusing the same ref_list for two different
> purposes.
>
> I do not feel strongly about it, but it might be a little more obvious
> to just declare a new variable in the block, like:
>
> diff --git a/remote.c b/remote.c
> index 75255af..53bef82 100644
> --- a/remote.c
> +++ b/remote.c
> @@ -1399,6 +1399,7 @@ int match_push_refs(struct ref *src, struct ref **dst,
>                 add_missing_tags(src, dst, &dst_tail);
>
>         if (send_prune) {
> +               struct string_list src_ref_index = STRING_LIST_INIT_NODUP;
>                 /* check for missing refs on the remote */
>                 for (ref = *dst; ref; ref = ref->next) {
>                         char *src_name;
> @@ -1409,15 +1410,15 @@ int match_push_refs(struct ref *src, struct ref **dst,
>
>                         src_name = get_ref_match(rs, nr_refspec, ref, send_mirror, FROM_DST, NULL);
>                         if (src_name) {
> -                               if (!ref_list.nr)
> +                               if (!src_ref_index.nr)
>                                         prepare_searchable_ref_list(src,
> -                                               &ref_list);
> -                               if (!string_list_has_string(&ref_list, src_name))
> +                                               &src_ref_index);
> +                               if (!string_list_has_string(&src_ref_index, src_name))
>                                         ref->peer_ref = alloc_delete_ref();
>                                 free(src_name);
>                         }
>                 }
> -               string_list_clear(&ref_list, 0);
> +               string_list_clear(&src_ref_index, 0);
>         }
>         if (errs)
>                 return -1;
>
> And similarly maybe call the outer ref_list dst_ref_index or something.

That looks/sounds reasonable.

> I also note that we don't do the lazy-prepare for the other loop. I
> guess that is because we assume that "src" is always non-NULL?

It really wasn't a conscious decision to not do the lazy prepare in
the other loop.  I gave extra attention to the pruning block since I
expect that deleting refs is less common than updating refs, so we
should be able to avoid the cost of building the string list most of
the time.  But, I don't see a down side to doing the lazy prepare in
the other loop too, and in fact, it looks like we may be able to avoid
building the string list when only explicit refspecs are used.  So,
yeah, we should lazy build in both loops.

-Brandon

Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list

[Junio C Hamano]

Brandon Casey <drafnel@gmail.com> writes:

> Right.  For repos with few refs on either side, I don't think there
> will be any measurable difference.  When pushing a single ref to a
> repo with a very large number of refs, we will see a very small net
> loss for the time required to prepare the string list (which grows
> linearly with the number of remote refs).  After 2 or 3 refs, we
> should see a net gain.
>
> So we're really just improving our worst case performance here.

... by penalizing the common case by how much?  If it is not too
much, then this obviously would be a good change.

> ...  But, I don't see a down side to doing the lazy prepare in
> the other loop too, and in fact, it looks like we may be able to avoid
> building the string list when only explicit refspecs are used.  So,
> yeah, we should lazy build in both loops.

OK, so will see a reroll sometime?

Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list

[Jeff King]

On Wed, Jul 03, 2013 at 11:40:12AM -0700, Junio C Hamano wrote:

> Brandon Casey <drafnel@gmail.com> writes:
> 
> > Right.  For repos with few refs on either side, I don't think there
> > will be any measurable difference.  When pushing a single ref to a
> > repo with a very large number of refs, we will see a very small net
> > loss for the time required to prepare the string list (which grows
> > linearly with the number of remote refs).  After 2 or 3 refs, we
> > should see a net gain.
> >
> > So we're really just improving our worst case performance here.
> 
> ... by penalizing the common case by how much?  If it is not too
> much, then this obviously would be a good change.

I don't think by much. If we have "m" local refs to push and "n" remote
refs, right now we do O(m*n) work ("m" linear searches of the remote
namespace). With Brandon's patch, we do O(n log n) to build the index,
plus O(m log n) for lookups.

So our break-even point is basically m = log n, and for m smaller than
that, we do more work building the index. Your absolute biggest
difference would be pushing a single ref to a repository with a very
large number of refs.

Here are the timings before and after Brandon's patch for pushing a
no-op single ref from a normal repo to one with 370K refs (the same
pathological repo from the upload-pack tests). Times are
best-of-five.

             before     after
     real    0m1.087s   0m1.156s
     user    0m1.344s   0m1.412s
     sys     0m0.288s   0m0.284s

So it's measurable, but even on a pathological worst-case, we're talking
about 6% slowdown.

You could try to guess about when to build the index based on the size
of "m" and "n", but I suspect you'd waste more time calculating whether
to build the index than you would simply building it in most cases.

-Peff

Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list

[Brandon Casey]

On 7/3/2013 12:00 PM, Jeff King wrote:
> On Wed, Jul 03, 2013 at 11:40:12AM -0700, Junio C Hamano wrote:
> 
>> Brandon Casey <drafnel@gmail.com> writes:
>>
>>> Right.  For repos with few refs on either side, I don't think there
>>> will be any measurable difference.  When pushing a single ref to a
>>> repo with a very large number of refs, we will see a very small net
>>> loss for the time required to prepare the string list (which grows
>>> linearly with the number of remote refs).  After 2 or 3 refs, we
>>> should see a net gain.
>>>
>>> So we're really just improving our worst case performance here.
>>
>> ... by penalizing the common case by how much?  If it is not too
>> much, then this obviously would be a good change.
> 
> I don't think by much. If we have "m" local refs to push and "n" remote
> refs, right now we do O(m*n) work ("m" linear searches of the remote
> namespace). With Brandon's patch, we do O(n log n) to build the index,

Whoops, yes, n log n, not linear as I misspoke.

> plus O(m log n) for lookups.
> 
> So our break-even point is basically m = log n, and for m smaller than
> that, we do more work building the index. Your absolute biggest
> difference would be pushing a single ref to a repository with a very
> large number of refs.
> 
> Here are the timings before and after Brandon's patch for pushing a
> no-op single ref from a normal repo to one with 370K refs (the same
> pathological repo from the upload-pack tests). Times are
> best-of-five.
> 
>              before     after
>      real    0m1.087s   0m1.156s
>      user    0m1.344s   0m1.412s
>      sys     0m0.288s   0m0.284s
> 
> So it's measurable, but even on a pathological worst-case, we're talking
> about 6% slowdown.

That agrees with what I've observed.

> You could try to guess about when to build the index based on the size
> of "m" and "n", but I suspect you'd waste more time calculating whether
> to build the index than you would simply building it in most cases.

I agree, I don't think it's worth trying to guess when to build an index
and when to just perform linear searches.  If building the payload for
each element in the index was more expensive than just assigning to a
pointer, than it could be worth it, but we're not, so I don't think it
is worth it.

-Brandon

Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list

[Brandon Casey]

On 7/3/2013 11:40 AM, Junio C Hamano wrote:
> Brandon Casey <drafnel@gmail.com> writes:
> 
>> Right.  For repos with few refs on either side, I don't think there
>> will be any measurable difference.  When pushing a single ref to a
>> repo with a very large number of refs, we will see a very small net
>> loss for the time required to prepare the string list (which grows
>> linearly with the number of remote refs).  After 2 or 3 refs, we
>> should see a net gain.
>>
>> So we're really just improving our worst case performance here.
> 
> ... by penalizing the common case by how much?  If it is not too
> much, then this obviously would be a good change.

For something the size of the git repo, 5 branches, and pushing with
matching refspecs, I can't measure any difference.  The fastest time I
record with or without this patch is the same:

   $ time git push -n
   real    0m0.178s
   user    0m0.020s
   sys     0m0.008s

Ditto, when only pushing a single branch.  Preparing the string list for
a repo with a "normal" number of refs has very little overhead.

When the remote side has very many refs, then there is a small penalty
when the local side is pushing very few refs.  But still, the penalty is
small.

My measurements for pushing from a repo with a single local branch into
my 100000+ ref repo showed <10% hit and the numbers were in the tens of
milliseconds.

        before    after
real    0m0.525s  0m0.566s
user    0m0.243s  0m0.279s
sys     0m0.075s  0m0.099s

>> ...  But, I don't see a down side to doing the lazy prepare in
>> the other loop too, and in fact, it looks like we may be able to avoid
>> building the string list when only explicit refspecs are used.  So,
>> yeah, we should lazy build in both loops.
> 
> OK, so will see a reroll sometime?

Yeah, I'll reroll.

-Brandon

Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list

[Junio C Hamano]

Brandon Casey <bcasey@nvidia.com> writes:

>> ... by penalizing the common case by how much?  If it is not too
>> much, then this obviously would be a good change.
>
> For something the size of the git repo, 5 branches, and pushing with
> matching refspecs, I can't measure any difference.  The fastest time I
> record with or without this patch is the same:
>
>    $ time git push -n
>    real    0m0.178s
>    user    0m0.020s
>    sys     0m0.008s
>
> Ditto, when only pushing a single branch.  Preparing the string list for
> a repo with a "normal" number of refs has very little overhead.

My repository git.git and Linus's kernel are not "normal".  It did
not matter so far to have O(n*m) when pushing to our histories.

The case that matters is for somebody to be pushing one (or a few)
refs against a repository with many many refs, like pushing a review
request to Gerrit instance, which I think Martin has in mind.

[PATCH v2] remote.c: avoid O(m*n) behavior in match_push_refs

[Brandon Casey]

When pushing using a matching refspec or a pattern refspec, each ref
in the local repository must be paired with a ref advertised by the
remote server.  This is accomplished by using the refspec to transform
the name of the local ref into the name it should have in the remote
repository, and then performing a linear search through the list of
remote refs to see if the remote ref was advertised by the remote
system.

Each of these lookups has O(n) complexity and makes match_push_refs()
be an O(m*n) operation, where m is the number of local refs and n is
the number of remote refs.  If there are many refs 100,000+, then this
ref matching can take a significant amount of time.  Let's prepare an
index of the remote refs to allow searching in O(log n) time and
reduce the complexity of match_push_refs() to O(m log n).

We prepare the index lazily so that it is only created when necessary.
So, there should be no impact when _not_ using a matching or pattern
refspec, i.e. when pushing using only explicit refspecs.

Dry-run push of a repository with 121,913 local and remote refs:

        before     after
real    1m40.582s  0m0.804s
user    1m39.914s  0m0.515s
sys     0m0.125s   0m0.106s

The creation of the index has overhead.  So, if there are very few
local refs, then it could take longer to create the index than it
would have taken to just perform n linear lookups into the remote
ref space.  Using the index should provide some improvement when
the number of local refs is roughly greater than the log of the
number of remote refs (i.e. m >= log n).  The pathological case is
when there is a single local ref and very many remote refs.

Dry-run push of a repository with 121,913 remote refs and a single
local ref:

        before    after
real    0m0.525s  0m0.566s
user    0m0.243s  0m0.279s
sys     0m0.075s  0m0.099s

Using an index takes 41 ms longer, or roughly 7.8% longer.

Jeff King measured a no-op push of a single ref into a remote repo
with 370,000 refs:

        before    after
real    0m1.087s  0m1.156s
user    0m1.344s  0m1.412s
sys     0m0.288s  0m0.284s

Using an index takes 69 ms longer, or roughly 6.3% longer.

None of the measurements above required transferring any objects to
the remote repository.  If the push required transferring objects and
updating the refs in the remote repository, the impact of preparing
the search index would be even smaller.

Note, we refrain from using an index in the send_prune block since it
is expected that the number of refs that are being pruned is more
commonly much smaller than the number of local refs (i.e. m << n,
and particularly m < log(n), where m is the number of refs that
should be pruned and n is the number of local refs), so the overhead
of creating the search index would likely exceed the benefit of using
it.

Signed-off-by: Brandon Casey <drafnel@gmail.com>
---

Here is the reroll with an updated commit message that hopefully
provides a little more detail to justify this change.  I removed
the use of the search index in the send_prune block since I think
that pruning many refs is an uncommon operation and the overhead
of creating the index will more commonly exceed the benefit of
using it.

This version now lazily builds the search index in the first loop,
so there should be no impact when pushing using explicit refspecs.

e.g. pushing a change for review to Gerrit

   $ git push origin HEAD:refs/for/master

I suspect that this is the most common form of pushing and furthermore
will become the default once push.default defaults to 'current'.

The remaining push cases can be distilled into the following:

  ref-count    impact
  m >= log n   improved with this patch
  m < log n    regressed with this patch roughly ~6-7%

So, I think what we have to consider is whether the improvement to
something like 'git push --mirror' is worth the impact to an asymmetric
push where the number of local refs is much smaller than the number of
remote refs.  I'm not sure how common the latter really is though.
Gerrit does produce repositories with many refs on the remote end in
the refs/changes/ namespace, but do people commonly push to Gerrit
using matching or pattern refspecs?  Not sure, but I'd tend to think
that they don't.

-Brandon

 remote.c | 20 +++++++++++++++++++-
 1 file changed, 19 insertions(+), 1 deletion(-)

diff --git a/remote.c b/remote.c
index 6f57830..8bca65a 100644
--- a/remote.c
+++ b/remote.c
@@ -1302,6 +1302,14 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds
 	free(sent_tips.tip);
 }
 
+static void prepare_ref_index(struct string_list *ref_index, struct ref *ref)
+{
+	for ( ; ref; ref = ref->next)
+		string_list_append_nodup(ref_index, ref->name)->util = ref;
+
+	sort_string_list(ref_index);
+}
+
 /*
  * Given the set of refs the local repository has, the set of refs the
  * remote repository has, and the refspec used for push, determine
@@ -1320,6 +1328,7 @@ int match_push_refs(struct ref *src, struct ref **dst,
 	int errs;
 	static const char *default_refspec[] = { ":", NULL };
 	struct ref *ref, **dst_tail = tail_ref(dst);
+	struct string_list dst_ref_index = STRING_LIST_INIT_NODUP;
 
 	if (!nr_refspec) {
 		nr_refspec = 1;
@@ -1330,6 +1339,7 @@ int match_push_refs(struct ref *src, struct ref **dst,
 
 	/* pick the remainder */
 	for (ref = src; ref; ref = ref->next) {
+		struct string_list_item *dst_item;
 		struct ref *dst_peer;
 		const struct refspec *pat = NULL;
 		char *dst_name;
@@ -1338,7 +1348,11 @@ int match_push_refs(struct ref *src, struct ref **dst,
 		if (!dst_name)
 			continue;
 
-		dst_peer = find_ref_by_name(*dst, dst_name);
+		if (!dst_ref_index.nr)
+			prepare_ref_index(&dst_ref_index, *dst);
+
+		dst_item = string_list_lookup(&dst_ref_index, dst_name);
+		dst_peer = dst_item ? dst_item->util : NULL;
 		if (dst_peer) {
 			if (dst_peer->peer_ref)
 				/* We're already sending something to this ref. */
@@ -1355,6 +1369,8 @@ int match_push_refs(struct ref *src, struct ref **dst,
 			/* Create a new one and link it */
 			dst_peer = make_linked_ref(dst_name, &dst_tail);
 			hashcpy(dst_peer->new_sha1, ref->new_sha1);
+			string_list_insert(&dst_ref_index,
+				dst_peer->name)->util = dst_peer;
 		}
 		dst_peer->peer_ref = copy_ref(ref);
 		dst_peer->force = pat->force;
@@ -1362,6 +1378,8 @@ int match_push_refs(struct ref *src, struct ref **dst,
 		free(dst_name);
 	}
 
+	string_list_clear(&dst_ref_index, 0);
+
 	if (flags & MATCH_REFS_FOLLOW_TAGS)
 		add_missing_tags(src, dst, &dst_tail);
 
-- 
1.8.1.1.252.gdb33759

Re: [PATCH v2] remote.c: avoid O(m*n) behavior in match_push_refs

[Jeff King]

On Mon, Jul 08, 2013 at 12:02:11AM -0700, Brandon Casey wrote:

> Here is the reroll with an updated commit message that hopefully
> provides a little more detail to justify this change.  I removed
> the use of the search index in the send_prune block since I think
> that pruning many refs is an uncommon operation and the overhead
> of creating the index will more commonly exceed the benefit of
> using it.

I don't know. I'd think that if you are using pruning, you might delete
a large chunk at one time (e.g., rearranging your ref hierarchy,
followed by "git push --mirror"). But that is just my gut feeling. I
haven't actually run into this slow-down in the real world (we typically
fetch from our giant repositories rather than push into them).

> This version now lazily builds the search index in the first loop,
> so there should be no impact when pushing using explicit refspecs.
> 
> e.g. pushing a change for review to Gerrit
> 
>    $ git push origin HEAD:refs/for/master
> 
> I suspect that this is the most common form of pushing and furthermore
> will become the default once push.default defaults to 'current'.

Nice.

> The remaining push cases can be distilled into the following:
> 
>   ref-count    impact
>   m >= log n   improved with this patch
>   m < log n    regressed with this patch roughly ~6-7%
> 
> So, I think what we have to consider is whether the improvement to
> something like 'git push --mirror' is worth the impact to an asymmetric
> push where the number of local refs is much smaller than the number of
> remote refs.  I'm not sure how common the latter really is though.
> Gerrit does produce repositories with many refs on the remote end in
> the refs/changes/ namespace, but do people commonly push to Gerrit
> using matching or pattern refspecs?  Not sure, but I'd tend to think
> that they don't.

To me it is not about what happens sometimes or not, but about having
runaway worst-case behavior that is unusable. The 6-7% increase (which
is the absolute worst-case measurement we could come up with; in the
real world you would usually transfer actual objects, and connect over
an actual network) is worth it, IMHO.

So I'd be in favor of applying this (possibly covering the send_prune
case, too). If somebody really wants to care about the 6-7%, they can
build on top of your patch with heuristics to avoid indexing in the
small cases.

-Peff

[PATCH v2 w/prune index] remote.c: avoid O(m*n) behavior in match_push_refs

[Brandon Casey]

When pushing using a matching refspec or a pattern refspec, each ref
in the local repository must be paired with a ref advertised by the
remote server.  This is accomplished by using the refspec to transform
the name of the local ref into the name it should have in the remote
repository, and then performing a linear search through the list of
remote refs to see if the remote ref was advertised by the remote
system.

Each of these lookups has O(n) complexity and makes match_push_refs()
be an O(m*n) operation, where m is the number of local refs and n is
the number of remote refs.  If there are many refs 100,000+, then this
ref matching can take a significant amount of time.  Let's prepare an
index of the remote refs to allow searching in O(log n) time and
reduce the complexity of match_push_refs() to O(m log n).

We prepare the index lazily so that it is only created when necessary.
So, there should be no impact when _not_ using a matching or pattern
refspec, i.e. when pushing using only explicit refspecs.

Dry-run push of a repository with 121,913 local and remote refs:

        before     after
real    1m40.582s  0m0.804s
user    1m39.914s  0m0.515s
sys     0m0.125s   0m0.106s

The creation of the index has overhead.  So, if there are very few
local refs, then it could take longer to create the index than it
would have taken to just perform n linear lookups into the remote
ref space.  Using the index should provide some improvement when
the number of local refs is roughly greater than the log of the
number of remote refs (i.e. m >= log n).  The pathological case is
when there is a single local ref and very many remote refs.

Dry-run push of a repository with 121,913 remote refs and a single
local ref:

        before    after
real    0m0.525s  0m0.566s
user    0m0.243s  0m0.279s
sys     0m0.075s  0m0.099s

Using an index takes 41 ms longer, or roughly 7.8% longer.

Jeff King measured a no-op push of a single ref into a remote repo
with 370,000 refs:

        before    after
real    0m1.087s  0m1.156s
user    0m1.344s  0m1.412s
sys     0m0.288s  0m0.284s

Using an index takes 69 ms longer, or roughly 6.3% longer.

None of the measurements above required transferring any objects to
the remote repository.  If the push required transferring objects and
updating the refs in the remote repository, the impact of preparing
the search index would be even smaller.

A similar operation is performed in the reverse direction when pruning
using a matching or pattern refspec.  Let's avoid O(m*n) behavior in
the same way by lazily preparing an index on the local refs.

Signed-off-by: Brandon Casey <drafnel@gmail.com>
---

On Mon, Jul 8, 2013 at 12:50 AM, Jeff King <peff@peff.net> wrote:
> On Mon, Jul 08, 2013 at 12:02:11AM -0700, Brandon Casey wrote:
> 
> > Here is the reroll with an updated commit message that hopefully
> > provides a little more detail to justify this change.  I removed
> > the use of the search index in the send_prune block since I think
> > that pruning many refs is an uncommon operation and the overhead
> > of creating the index will more commonly exceed the benefit of
> > using it.
> 
> I don't know. I'd think that if you are using pruning, you might delete
> a large chunk at one time (e.g., rearranging your ref hierarchy,
> followed by "git push --mirror"). But that is just my gut feeling. I
> haven't actually run into this slow-down in the real world (we typically
> fetch from our giant repositories rather than push into them).

Firstly, why are you still awake?!?! :)

Secondly, fair enough.  I don't think the change to the pruning block
will have much impact in real repos either way.  In this block, the
search is being performed on the local refs.  There would have to be
many refs on the local side for the generation of the index to be
significant enough to notice.

So, I'm fine with using the index when pruning too to avoid worst-case
behavior when there are many local refs and many deletions.

-Brandon

 remote.c | 27 +++++++++++++++++++++++++--
 1 file changed, 25 insertions(+), 2 deletions(-)

diff --git a/remote.c b/remote.c
index 6f57830..efcba93 100644
--- a/remote.c
+++ b/remote.c
@@ -1302,6 +1302,14 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds
 	free(sent_tips.tip);
 }
 
+static void prepare_ref_index(struct string_list *ref_index, struct ref *ref)
+{
+	for ( ; ref; ref = ref->next)
+		string_list_append_nodup(ref_index, ref->name)->util = ref;
+
+	sort_string_list(ref_index);
+}
+
 /*
  * Given the set of refs the local repository has, the set of refs the
  * remote repository has, and the refspec used for push, determine
@@ -1320,6 +1328,7 @@ int match_push_refs(struct ref *src, struct ref **dst,
 	int errs;
 	static const char *default_refspec[] = { ":", NULL };
 	struct ref *ref, **dst_tail = tail_ref(dst);
+	struct string_list dst_ref_index = STRING_LIST_INIT_NODUP;
 
 	if (!nr_refspec) {
 		nr_refspec = 1;
@@ -1330,6 +1339,7 @@ int match_push_refs(struct ref *src, struct ref **dst,
 
 	/* pick the remainder */
 	for (ref = src; ref; ref = ref->next) {
+		struct string_list_item *dst_item;
 		struct ref *dst_peer;
 		const struct refspec *pat = NULL;
 		char *dst_name;
@@ -1338,7 +1348,11 @@ int match_push_refs(struct ref *src, struct ref **dst,
 		if (!dst_name)
 			continue;
 
-		dst_peer = find_ref_by_name(*dst, dst_name);
+		if (!dst_ref_index.nr)
+			prepare_ref_index(&dst_ref_index, *dst);
+
+		dst_item = string_list_lookup(&dst_ref_index, dst_name);
+		dst_peer = dst_item ? dst_item->util : NULL;
 		if (dst_peer) {
 			if (dst_peer->peer_ref)
 				/* We're already sending something to this ref. */
@@ -1355,6 +1369,8 @@ int match_push_refs(struct ref *src, struct ref **dst,
 			/* Create a new one and link it */
 			dst_peer = make_linked_ref(dst_name, &dst_tail);
 			hashcpy(dst_peer->new_sha1, ref->new_sha1);
+			string_list_insert(&dst_ref_index,
+				dst_peer->name)->util = dst_peer;
 		}
 		dst_peer->peer_ref = copy_ref(ref);
 		dst_peer->force = pat->force;
@@ -1362,10 +1378,13 @@ int match_push_refs(struct ref *src, struct ref **dst,
 		free(dst_name);
 	}
 
+	string_list_clear(&dst_ref_index, 0);
+
 	if (flags & MATCH_REFS_FOLLOW_TAGS)
 		add_missing_tags(src, dst, &dst_tail);
 
 	if (send_prune) {
+		struct string_list src_ref_index = STRING_LIST_INIT_NODUP;
 		/* check for missing refs on the remote */
 		for (ref = *dst; ref; ref = ref->next) {
 			char *src_name;
@@ -1376,11 +1395,15 @@ int match_push_refs(struct ref *src, struct ref **dst,
 
 			src_name = get_ref_match(rs, nr_refspec, ref, send_mirror, FROM_DST, NULL);
 			if (src_name) {
-				if (!find_ref_by_name(src, src_name))
+				if (!src_ref_index.nr)
+					prepare_ref_index(&src_ref_index, src);
+				if (!string_list_has_string(&src_ref_index,
+					    src_name))
 					ref->peer_ref = alloc_delete_ref();
 				free(src_name);
 			}
 		}
+		string_list_clear(&src_ref_index, 0);
 	}
 	if (errs)
 		return -1;
-- 
1.8.1.1.252.gdb33759

Re: [PATCH v2 w/prune index] remote.c: avoid O(m*n) behavior in match_push_refs

[Junio C Hamano]

Brandon Casey <drafnel@gmail.com> writes:

> ...
> Using an index takes 41 ms longer, or roughly 7.8% longer.
>
> Jeff King measured a no-op push of a single ref into a remote repo
> with 370,000 refs:
>
>         before    after
> real    0m1.087s  0m1.156s
> user    0m1.344s  0m1.412s
> sys     0m0.288s  0m0.284s
>
> Using an index takes 69 ms longer, or roughly 6.3% longer.
>
> None of the measurements above required transferring any objects to
> the remote repository.  If the push required transferring objects and
> updating the refs in the remote repository, the impact of preparing
> the search index would be even smaller.
>
> A similar operation is performed in the reverse direction when pruning
> using a matching or pattern refspec.  Let's avoid O(m*n) behavior in
> the same way by lazily preparing an index on the local refs.

Thanks.  Both the explanation and the code change makes sense to me.

Will queue.