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 260cb221b902aa05d389f79988434770ed8c9131..3d240ca435e3079530dd3515ce78bd20858e3a6f 100644 (file)
--- 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) {
 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;
                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
         * 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;
         */
        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);
 
        if (0 <= extra)
                join_revs(&list, &seen, num_rev, extra);
 

+       sort_by_date(&seen);
+

        if (merge_base)
                return show_merge_base(seen, num_rev);
 
        if (merge_base)
                return show_merge_base(seen, num_rev);