From 26a8ad25b28a1cb906c88bdf539d840774ca5aeb Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Sun, 16 Jul 2006 00:00:09 -0700 Subject: [PATCH] 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 --- builtin-show-branch.c | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) diff --git a/builtin-show-branch.c b/builtin-show-branch.c index 260cb221b..3d240ca43 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); -- 2.26.2