Jeff King [off-list ref] writes:
quoted hunk
There's no reason to preserve the incoming order of the
heads we're requested to fetch. By having them sorted, we
can replace some of the quadratic algorithms with linear
ones.
Signed-off-by: Jeff King <redacted>
---
I actually wouldn't be surprised if these were typically sorted already,
as they frequently come from the ref-mapping functions, which in turn
process the lists we get from the remote. But we also might get random
junk on the command-line of fetch-pack, so we need to be careful.
builtin/fetch-pack.c | 7 +++++++
1 file changed, 7 insertions(+)
diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c
index 10db15b..380743e 100644
--- a/builtin/fetch-pack.c
+++ b/builtin/fetch-pack.c
@@ -1057,6 +1057,11 @@ int cmd_fetch_pack(int argc, const char **argv, const char *prefix)
return ret;
}
+static int compare_heads(const void *a, const void *b)
+{
+ return strcmp(*(const char **)a, *(const char **)b);
+}
+
struct ref *fetch_pack(struct fetch_pack_args *my_args,
int fd[], struct child_process *conn,
const struct ref *ref,@@ -1076,6 +1081,8 @@ struct ref *fetch_pack(struct fetch_pack_args *my_args,
st.st_mtime = 0;
}
+ qsort(heads, nr_heads, sizeof(*heads), compare_heads);
+
if (heads && nr_heads)
nr_heads = remove_duplicates(nr_heads, heads);
Hrm, could heads and/or nr_heads be NULL/0 here when we try to run qsort()
in this codepath?
if (!ref) {
On Tue, May 22, 2012 at 01:08:42PM -0700, Junio C Hamano wrote:
quoted
@@ -1076,6 +1081,8 @@ struct ref *fetch_pack(struct fetch_pack_args *my_args,
st.st_mtime = 0;
}
+ qsort(heads, nr_heads, sizeof(*heads), compare_heads);
+
if (heads && nr_heads)
nr_heads = remove_duplicates(nr_heads, heads);
Hrm, could heads and/or nr_heads be NULL/0 here when we try to run qsort()
in this codepath?
Good catch. I had originally put the qsort into remove_duplicates, but
hoisted it out, as the second optimization depends on the sorting, too.
heads can be NULL here (for example, if you run fetch-pack without any
arguments, and without --stdin; though why you would do so is a
mystery, we should protect against it).
A sane qsort would see that its second parameter is 0 and never try to
dereference the array. But I'm not sure all qsort implementations we
will see are sane, so it's probably better to protect it by putting it
inside the conditional block just below.
-Peff
On Tue, May 22, 2012 at 04:23:36PM -0400, Jeff King wrote:
On Tue, May 22, 2012 at 01:08:42PM -0700, Junio C Hamano wrote:
quoted
quoted
@@ -1076,6 +1081,8 @@ struct ref *fetch_pack(struct fetch_pack_args *my_args,
st.st_mtime = 0;
}
+ qsort(heads, nr_heads, sizeof(*heads), compare_heads);
+
if (heads && nr_heads)
nr_heads = remove_duplicates(nr_heads, heads);
Hrm, could heads and/or nr_heads be NULL/0 here when we try to run qsort()
in this codepath?
[...]
A sane qsort would see that its second parameter is 0 and never try to
dereference the array. But I'm not sure all qsort implementations we
will see are sane, so it's probably better to protect it by putting it
inside the conditional block just below.
I eye-balled what you queued in pu, and I wonder if you mis-read my
"just below" as "just below the existing line in the conditional" and
not "in the conditional that is just below the code we are talking
about".
I think we need this on top (or squashed in, but it looks like it is
already in next):
-- >8 --
Subject: fetch-pack: sort incoming heads list earlier
Commit 4435968 started sorting heads fed to fetch-pack so
that later commits could use more optimized algorithms;
commit 7db8d53 switched the remove_duplicates function to
such an algorithm.
Of course, the sorting is more effective if you do it
_before_ the algorithm in question.
Signed-off-by: Jeff King <redacted>
---
I suspect that all parts of git feed the refs in sorted order already,
which is why there were no test failures. But we should handle arbitrary
order from the command-line.
builtin/fetch-pack.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c
index 8a72473..b18ba05 100644
--- a/builtin/fetch-pack.c
+++ b/builtin/fetch-pack.c
@@ -1082,8 +1082,8 @@ struct ref *fetch_pack(struct fetch_pack_args *my_args,
}
if (heads && nr_heads) {
- nr_heads = remove_duplicates(nr_heads, heads);
qsort(heads, nr_heads, sizeof(*heads), compare_heads);
+ nr_heads = remove_duplicates(nr_heads, heads);
}
if (!ref) {--
1.7.10.1.25.g7031a0f