Performance Issues with Git Rebase

I have what appears to be a fairly straightforward rebase operation and I can't figure out why it seems to effectively hang 'git rebase'.

I have a handful of commits that I made last summer and haven't touched since.  I'm trying to rebase them against latest on upstream.

git status
On branch git_enhancements
Your branch and 'origin/smb' have diverged,
and have 4 and 4665 different commits each, respectively.
  (use "git pull" to merge the remote branch into yours)

If at this moment I type "git rebase" it will print out 

First, rewinding head to replay your work on top of it...

And then nothing will happen for approximately 30 minutes, and then it will complete.
  
If I instead type "git rebase --onto @{u} HEAD~4" it completes immediately.

I've narrowed it down to this line in git-rebase--am (approx. line 65)

	git format-patch -k --stdout --full-index --cherry-pick --right-only \
		--src-prefix=a/ --dst-prefix=b/ --no-renames --no-cover-letter \
		"$revisions" ${restrict_revision+^$restrict_revision} \
		>"$GIT_DIR/rebased-patches"

Which is turned into this in my particular case

git format-patch -k --stdout --full-index --cherry-pick --right-only --src-prefix=a/ --dst-prefix=b/ --no-renames --no-cover-letter 451da4975b25797fe54cd11e4796bbd3ee0911ce...ea3cf673d0e76504738bf130d48148d5b96cc406

If I time just that command I get 

real        32m10.324s user       26m21.296s sys          0m28.994s

If I change the triple do to a double dot I get 

real        0m4.276s user       0m0.096s sys          0m0.022s

Which is much more in line with how long I think the command should take.

The triple dot is coming from just earlier in the file here 

if test -z "$rebase_root"
	# this is now equivalent to ! -z "$upstream"
then
	revisions=$upstream...$orig_head
else
	revisions=$onto...$orig_head
fi

which seems to have been in place for 2+ years.  

I'm getting the same output with both the triple and double dot for my specific case, but I have no idea if that change makes sense for all cases or not.  Any guidance? 

Thanks much, -Andrew

"Crabtree, Andrew" <andrew.crabtree@hp.com> writes:

The difference only matters if any of your 4 patches have been sent to your upstream and accepted and appear among the 4665 changes they have.

The --cherry-pick option is about cross checking the combinations of 4 x 4665 and filter out matching ones (if any).

Ah gotcha.  That makes sense.

Default behavior is to do a patch-id check on all of them which is exactly what you would normally want to happen, and suppressing that speeds things up considerably at the risk of attempting to re-apply an already existing patch.

Thanks much for the explanation.   Perhaps I'll add a progress indicator since my organization will be doing a significant number of these types of rebases in the near future.

Regards, -Andrew