builtin-branch.c: optimize --merged and --no-merged

"git branch --no-merged $commit" used to compute the merge base between
the tip of each and every branch with the named $commit, but this was
wasteful when you have many branches.  Inside append_ref() we literally
ran has_commit() between the tip of the branch and the merge_filter_ref.

Instead, we can let the revision machinery traverse the history as if we
are running:

    $ git rev-list --branches --not $commit

by queueing the tips of branches we encounter as positive refs (this
mimicks the "--branches" option in the above command line) and then
appending the merge_filter_ref commit as a negative one, and finally
calling prepare_revision_walk() to limit the list..

After the traversal is done, branch tips that are reachable from $commit
are painted UNINTERESTING; they are already fully contained in $commit
(i.e. --merged).  Tips that are not painted UNINTERESTING still have
commits that are not reachable from $commit, thus "--no-merged" will show
them.

With an artificial repository that has "master" and 1000 test-$i branches
where they were created by "git branch test-$i master~$i":

    (with patch)
    $ /usr/bin/time git-branch --no-merged master >/dev/null
    0.12user 0.02system 0:00.15elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
    0inputs+0outputs (0major+1588minor)pagefaults 0swaps

    $ /usr/bin/time git-branch --no-merged test-200 >/dev/null
    0.15user 0.03system 0:00.18elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
    0inputs+0outputs (0major+1711minor)pagefaults 0swaps

    (without patch)
    $ /usr/bin/time git-branch --no-merged master >/dev/null
    0.69user 0.03system 0:00.72elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
    0inputs+0outputs (0major+2229minor)pagefaults 0swaps

    $ /usr/bin/time git-branch --no-merged test-200 >/dev/null
    0.58user 0.03system 0:00.61elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
    0inputs+0outputs (0major+2248minor)pagefaults 0swaps

Signed-off-by: Junio C Hamano <gitster@pobox.com>

0 files changed, 0 insertions, 0 deletions