branch --contains is unbearably slow [Re: [PATCHv2] Warnings before rebasing -i published history]

From: Thomas Rast <trast@student.ethz.ch>
Date: Jun 11, 2012, 11:46 UTC
Message-ID: <87r4tmhy12.fsf_-_@thomas.inf.ethz.ch>
In-Reply-To: <1339409091-28150-1-git-send-email-Lucien.Kong@ensimag.imag.fr>

[+Cc Junio who wrote branch --contains, and Peff who sped up tag --contains in ffc4b801.]

Lucien Kong <Lucien.Kong@ensimag.imag.fr> writes:

Show 5 quoted lines

> "git rebase -i" can be very dangerous if used on an already published
> history. This code detects that one is rewriting a commit that is an
> ancestor of a remote-tracking branch, and warns the user through the
> editor. This feature is controlled by a new config key
> rebase.checkremoterefs.

[...]

Show 7 quoted lines

> +# Add the name the branches after each pick, fixup or squash commit that
> +# is an ancestor of a remote-tracking branch.
> +add_remoterefs () {
> +	while read -r command sha1 message
> +	do
> +		printf '%s\n' "$command $sha1 $message"
> +		git branch -r --contains "$sha1" >"$1.branch"

[...]

> +	done >"$1.published" <"$1"
> +	cat "$1.published" >"$1"
> +	rm -f "$1.published" "$1.branch"
> +}

While I like the idea, I think it unfortunately needs some changes in 'git branch --contains'. That command is unbelievably slow on a repository with many remote branches, like my git.git:

  $ g remote -v | wc -l  # note that each appears twice, for fetch/push
  28
  $ git branch -r | wc -l
  364

  $ time git branch -r --contains origin/next
    origin/next

  real    0m32.060s
  user    0m31.895s
  sys     0m0.036s

I think an upper bound for the runtime of any 'git branch --contains' should be generating the *complete* topology like this:

  $ time git log --graph --oneline --all >/dev/null

  real    0m2.637s
  user    0m2.246s
  sys     0m0.364s

It should also be possible to generate the --contains output for several commits at the same time. Otherwise the feature will be too painfully slow for all but the simplest rebases. Currently the startup time for 'rebase -i' to show an editor is near-instantaneous for me; adding N*2s would be too much on most of my topics, where I tend to gather a handful of fixups and improvements before the next 'rebase -i' round.

-- 
Thomas Rast
trast@{inf,student}.ethz.ch