Julian Phillips <julian@xxxxxxxxxxxxxxxxx> writes:
> I have a repository at $dayjob where fetch was taking ~30s to tell me
> that there were no updates.
>
> It turns out that I appear to have added a nasty linear search of all
> remote refs for every commit (i.e. tag^{}) tag ref way back in the
> original C implementation of fetch. This doesn't scale well to large
> numbers of refs, so this replaces it with a hash table based lookup
> instead, which brings the time down to a few seconds even for very large
> ref counts.
>
> I haven't tested it with non-native transports, but there is no reason
> to believe that the code should be transport specific.
Very interesting.
A few questions (not criticisms).
* 1m50s to 4.5s is quite impressive, even if it is only in a repository
with unusual refs-vs-commits ratio, but I personally think 10 refs per
every commit is already on the borderline of being insane, and the
normal ratio would be more like 1 refs per every 10-20 commits.
What are possible downsides with the new code in repositories with more
reasonable refs-vs-commits ratio? A hash table (with a sensible hash
function) would almost always outperform linear search in an randomly
ordered collection, so my gut tells me that there won't be performance
downsides, but are there other potential issues we should worry about?
* In an insanely large refs-vs-commits case, perhaps not 50000:1 but more
like 100:1, but with a history with far more than one commit, what is
the memory consumption? Judging from a cursory view, I think the way
ref-dict re-uses struct ref might be quite suboptimal, as you are using
only next (for hash-bucket link), old_sha1[] and its name field, and
also your ref_dict_add() calls alloc_ref() which calls one calloc() per
requested ref, instead of attempting any bulk allocation.
* The outer loop is walking the list of refs from a transport, and the
inner loop is walking a copy of the same list of refs from the same
transport, looking for each refs/tags/X^{} what record, if any, existed
for refs/tags/X.
Would it make sense to further specialize your optimization? For
example, something like...
/* Your hash records this structure */
struct tag_ref_record {
const char *name;
struct ref *self;
struct ref *peeled;
};
static void add_to_tail(struct ref ***tail,
struct string_list *existing_refs,
struct string_list *new_refs,
const struct ref *ref,
const unsigned char sha1[]) {
... the "appending to *tail" thing as a helper function ...
}
for (ref in all refs from transport) {
if (ref is of form "refs/tags/X^{}")
look up tag_ref_record for "refs/tags/X" and store
ref in its peeled member;
else if (ref is of form "refs/tags/X")
look up tag_ref_record for "refs/tags/X" and store
ref in its self member;
}
for (trr in all tag_ref_record database) {
add_to_tail(tail, &existing_refs, &new_refs,
trr->self, self->old_sha1);
add_to_tail(tail, &existing_refs, &new_refs,
trr->peeled, self->old_sha1);
}
* It is tempting to use a hash table when you have to deal with an
unordered collection, but in this case, wouldn't the refs obtained from
the transport (it's essentially a ls-remote output, isn't it?) be
sorted? Can't you take advantage of that fact to optimize the loop,
without adding a specialized hash table implementation?
We find refs/tags/v0.99 immediately followed by refs/tags/v0.99^{} in
the ls-remote output. And the inefficient loop is about finding
refs/tags/v0.99 when we see refs/tags/v0.99^{}, so if we remember the
tag ref we saw in the previous round, we can check with that first to
make sure our "sorted" assumption holds true, and optimize the loop out
that way, no?
diff --git a/builtin-fetch.c b/builtin-fetch.c
index cb48c57..3f12e28 100644
--- a/builtin-fetch.c
+++ b/builtin-fetch.c
@@ -516,6 +516,7 @@ static void find_non_local_tags(struct transport *transport,
const struct ref *tag_ref;
struct ref *rm = NULL;
const struct ref *ref;
+ const struct ref *last_tag_seen = NULL;
for_each_ref(add_existing, &existing_refs);
for (ref = transport_get_remote_refs(transport); ref; ref = ref->next) {
@@ -528,6 +529,11 @@ static void find_non_local_tags(struct transport *transport,
if (!strcmp(ref_name + ref_name_len - 3, "^{}")) {
ref_name[ref_name_len - 3] = 0;
+ if (last_tag_seen &&
+ !strcmp(last_tag_seen->name, ref_name)) {
+ ref_sha1 = last_tag_seen->old_sha1;
+ goto quick;
+ }
tag_ref = transport_get_remote_refs(transport);
while (tag_ref) {
if (!strcmp(tag_ref->name, ref_name)) {
@@ -536,8 +542,11 @@ static void find_non_local_tags(struct transport *transport,
}
tag_ref = tag_ref->next;
}
+ } else {
+ last_tag_seen = ref;
}
+ quick:
if (!string_list_has_string(&existing_refs, ref_name) &&
!string_list_has_string(&new_refs, ref_name) &&
(has_sha1_file(ref->old_sha1) ||
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html