diff options
authorJunio C Hamano <>2006-07-16 07:00:09 (GMT)
committerJunio C Hamano <>2006-07-16 07:00:09 (GMT)
commit26a8ad25b28a1cb906c88bdf539d840774ca5aeb (patch)
parenta3e65d74ee7ec9e6f49de7688a1cdac052910bd4 (diff)
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 <>
1 files changed, 5 insertions, 4 deletions
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 void name_commits(struct commit_list *list,
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 @@ static void join_revs(struct commit_list **list_p,
* 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 @@ int cmd_show_branch(int ac, const char **av, char **envp)
if (0 <= extra)
join_revs(&list, &seen, num_rev, extra);
+ sort_by_date(&seen);
if (merge_base)
return show_merge_base(seen, num_rev);