tree b31462d05ec33b532468ed6bd51fce56c5b08e99
parent a3e65d74ee7ec9e6f49de7688a1cdac052910bd4
author Junio C Hamano <junkio@cox.net> 1153033209 -0700
committer Junio C Hamano <junkio@cox.net> 1153033209 -0700

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>