diff options
| author |  Junio C Hamano <junkio@cox.net> | 2006-07-16 00:00:09 -0700 |
|---|---|---|
| committer | Junio C Hamano <junkio@cox.net> | 2006-07-16 00:00:09 -0700 |
| commit | 26a8ad25b28a1cb906c88bdf539d840774ca5aeb (patch) | |
| tree | b31462d05ec33b532468ed6bd51fce56c5b08e99 | |
| parent | Documentation/urls.txt: Use substitution to escape square brackets (diff) | |
| download | tgif-26a8ad25b28a1cb906c88bdf539d840774ca5aeb.tar.xz | |
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>
| -rw-r--r-- | builtin-show-branch.c | 9 |
1 files changed, 5 insertions, 4 deletions
diff --git a/builtin-show-branch.c b/builtin-show-branch.c index 260cb221b9..3d240ca435 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); |