author | Junio C Hamano <gitster@pobox.com> | |
Wed, 23 Jul 2008 22:13:41 +0000 (15:13 -0700) | ||
committer | Junio C Hamano <gitster@pobox.com> | |
Wed, 23 Jul 2008 23:57:04 +0000 (16:57 -0700) | ||
commit | 68067ca1efcbb0408b931e08654a5e32de975ced | |
tree | c3134230b49126d45de05398867cb730dc17a58a | tree | snapshot |
parent | 0f31d68030752b0c1e02a1a092c18094a98202f0 | commit | diff |
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>
"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>
builtin-branch.c | diff | blob | history |