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

[Thomas Rast <trast@student.ethz.ch>]

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

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

> "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.
[...]
> +# 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