* [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list @ 2013-07-02 23:53 Brandon Casey 2013-07-03 6:23 ` Jeff King 0 siblings, 1 reply; 12+ messages in thread From: Brandon Casey @ 2013-07-02 23:53 UTC (permalink / raw) To: git; +Cc: peff, mfick, gitster, 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 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list 2013-07-02 23:53 [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list Brandon Casey @ 2013-07-03 6:23 ` Jeff King 2013-07-03 18:12 ` Brandon Casey 0 siblings, 1 reply; 12+ messages in thread From: Jeff King @ 2013-07-03 6:23 UTC (permalink / raw) To: Brandon Casey; +Cc: git, mfick, gitster, Brandon Casey 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 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list 2013-07-03 6:23 ` Jeff King @ 2013-07-03 18:12 ` Brandon Casey 2013-07-03 18:40 ` Junio C Hamano 0 siblings, 1 reply; 12+ messages in thread From: Brandon Casey @ 2013-07-03 18:12 UTC (permalink / raw) To: Jeff King; +Cc: Brandon Casey, git@vger.kernel.org, Martin Fick, Junio C Hamano 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list 2013-07-03 18:12 ` Brandon Casey @ 2013-07-03 18:40 ` Junio C Hamano 2013-07-03 19:00 ` Jeff King 2013-07-03 19:21 ` Brandon Casey 0 siblings, 2 replies; 12+ messages in thread From: Junio C Hamano @ 2013-07-03 18:40 UTC (permalink / raw) To: Brandon Casey; +Cc: Jeff King, Brandon Casey, git@vger.kernel.org, Martin Fick 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? ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list 2013-07-03 18:40 ` Junio C Hamano @ 2013-07-03 19:00 ` Jeff King 2013-07-03 20:05 ` Brandon Casey 2013-07-03 19:21 ` Brandon Casey 1 sibling, 1 reply; 12+ messages in thread From: Jeff King @ 2013-07-03 19:00 UTC (permalink / raw) To: Junio C Hamano Cc: Brandon Casey, Brandon Casey, git@vger.kernel.org, Martin Fick 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list 2013-07-03 19:00 ` Jeff King @ 2013-07-03 20:05 ` Brandon Casey 0 siblings, 0 replies; 12+ messages in thread From: Brandon Casey @ 2013-07-03 20:05 UTC (permalink / raw) To: Jeff King; +Cc: Junio C Hamano, Brandon Casey, git@vger.kernel.org, Martin Fick 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list 2013-07-03 18:40 ` Junio C Hamano 2013-07-03 19:00 ` Jeff King @ 2013-07-03 19:21 ` Brandon Casey 2013-07-03 20:22 ` Junio C Hamano 1 sibling, 1 reply; 12+ messages in thread From: Brandon Casey @ 2013-07-03 19:21 UTC (permalink / raw) To: Junio C Hamano; +Cc: Brandon Casey, Jeff King, git@vger.kernel.org, Martin Fick 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list 2013-07-03 19:21 ` Brandon Casey @ 2013-07-03 20:22 ` Junio C Hamano 2013-07-08 7:02 ` [PATCH v2] remote.c: avoid O(m*n) behavior in match_push_refs Brandon Casey 0 siblings, 1 reply; 12+ messages in thread From: Junio C Hamano @ 2013-07-03 20:22 UTC (permalink / raw) To: Brandon Casey; +Cc: Brandon Casey, Jeff King, git@vger.kernel.org, Martin Fick 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. ^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH v2] remote.c: avoid O(m*n) behavior in match_push_refs 2013-07-03 20:22 ` Junio C Hamano @ 2013-07-08 7:02 ` Brandon Casey 2013-07-08 7:50 ` Jeff King 0 siblings, 1 reply; 12+ messages in thread From: Brandon Casey @ 2013-07-08 7:02 UTC (permalink / raw) To: gitster; +Cc: peff, git, mfick, bcasey, 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 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [PATCH v2] remote.c: avoid O(m*n) behavior in match_push_refs 2013-07-08 7:02 ` [PATCH v2] remote.c: avoid O(m*n) behavior in match_push_refs Brandon Casey @ 2013-07-08 7:50 ` Jeff King 2013-07-08 8:58 ` [PATCH v2 w/prune index] " Brandon Casey 0 siblings, 1 reply; 12+ messages in thread From: Jeff King @ 2013-07-08 7:50 UTC (permalink / raw) To: Brandon Casey; +Cc: gitster, git, mfick, bcasey 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH v2 w/prune index] remote.c: avoid O(m*n) behavior in match_push_refs 2013-07-08 7:50 ` Jeff King @ 2013-07-08 8:58 ` Brandon Casey 2013-07-08 16:12 ` Junio C Hamano 0 siblings, 1 reply; 12+ messages in thread From: Brandon Casey @ 2013-07-08 8:58 UTC (permalink / raw) To: peff; +Cc: gitster, git, mfick, bcasey, 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 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [PATCH v2 w/prune index] remote.c: avoid O(m*n) behavior in match_push_refs 2013-07-08 8:58 ` [PATCH v2 w/prune index] " Brandon Casey @ 2013-07-08 16:12 ` Junio C Hamano 0 siblings, 0 replies; 12+ messages in thread From: Junio C Hamano @ 2013-07-08 16:12 UTC (permalink / raw) To: Brandon Casey; +Cc: peff, git, mfick, bcasey 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. ^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2013-07-08 16:12 UTC | newest] Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2013-07-02 23:53 [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list Brandon Casey 2013-07-03 6:23 ` Jeff King 2013-07-03 18:12 ` Brandon Casey 2013-07-03 18:40 ` Junio C Hamano 2013-07-03 19:00 ` Jeff King 2013-07-03 20:05 ` Brandon Casey 2013-07-03 19:21 ` Brandon Casey 2013-07-03 20:22 ` Junio C Hamano 2013-07-08 7:02 ` [PATCH v2] remote.c: avoid O(m*n) behavior in match_push_refs Brandon Casey 2013-07-08 7:50 ` Jeff King 2013-07-08 8:58 ` [PATCH v2 w/prune index] " Brandon Casey 2013-07-08 16:12 ` Junio C Hamano
Code repositories for project(s) associated with this public inbox https://80x24.org/mirrors/git.git This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).