show-branch: fix performance problem.
The core function used in show-branch, join_revs(), was supposed
to be exactly the same algorithm as merge_bases(), except that
it was a version enhanced for use with more than two heads.
However, it needed to mark and keep a list of all the commits it
has seen, because it needed them for its semi-graphical output.
The function to implement this list, mark_seen(), stupidly used
insert_by_date(), when it did not need to keep the list sorted
during its processing. This made "show-branch --merge-base"
more than 20x slower compared to "merge-base --all" in some
cases (e.g. between b5032a5 and 48ce8b0 in the Linux 2.6 kernel
archive). The performance of "show-branch --independent"
suffered from the same reason.
This patch sorts the resulting list after the list traversal
just once to fix these problems.
Signed-off-by: Junio C Hamano <junkio@cox.net>
diff --git a/builtin-show-branch.c b/builtin-show-branch.c
index 260cb22..3d240ca 100644
--- a/builtin-show-branch.c
+++ b/builtin-show-branch.c
@@ -172,7 +172,7 @@
static int mark_seen(struct commit *commit, struct commit_list **seen_p)
{
if (!commit->object.flags) {
- insert_by_date(commit, seen_p);
+ commit_list_insert(commit, seen_p);
return 1;
}
return 0;
@@ -218,9 +218,8 @@
* Postprocess to complete well-poisoning.
*
* At this point we have all the commits we have seen in
- * seen_p list (which happens to be sorted chronologically but
- * it does not really matter). Mark anything that can be
- * reached from uninteresting commits not interesting.
+ * seen_p list. Mark anything that can be reached from
+ * uninteresting commits not interesting.
*/
for (;;) {
int changed = 0;
@@ -701,6 +700,8 @@
if (0 <= extra)
join_revs(&list, &seen, num_rev, extra);
+ sort_by_date(&seen);
+
if (merge_base)
return show_merge_base(seen, num_rev);
