Why doesn't Git rebase take exponential time like Darcs?

Question

So according to the this Wikipedia page about merges in version control, Darcs uses patch commutation and so does Git when it rebases.

I'm curious to know why doesn't Git rebase take exponential time in some cases the same way Darcs does?

This page lists a bunch cases of when it could happen with Darcs and how to try and tackle them.

Answer 1

I have not used darcs and could be off base here, but scanning through the Wikipedia article, I observe that its claim here is misleading:

Patch commutation is used in Darcs to merge changes, and is also implemented in git (but called "rebasing"). Patch commutation merge means changing the order of patches (i.e. descriptions of changes) so that they form a linear history. In effect, when two patches are made in the context of a common situation, upon merging, one of them is rewritten so that it appears to be done in the context of the other.

Git neither stores patches, nor reorders them.¹ You can reorder patches manually if you like. When you use git rebase to convert commits—which are snapshots—into changesets, the conversion itself is done in a simple manner that is worst-case O(nd) where n is the number of lines and d is the length of the edit script. (Whether this is handled as a patch or as a cherry-pick, which is a merge, depends on which rebase algorithm you choose; the merge case tends to use more CPU time as it also looks for treewide rename operations.)

Hence, if you have C total commits, the worst case for a git rebase -i is roughly O(Cnd).² Git is not going to try any other order for the commits: it's up to you to do any reordering. If your rebase fails, you could try all possible reorderings, which would be a factorial function on the number of commits, but Git won't do that for you.

---

¹If you do a git rebase on a group of commits that has one or more merges inside itself, Git does "flatten" them and eliminate the merges—but it doesn't try many orders, it just does one topological walk of the whole thing. There is no attempt to be smart about it, and often this will lead to terrible merge conflicts, i.e., it's often a bad idea. If you use the new --rebase-merges flag, Git will try to keep the merges, but does so by re-performing them. It just builds an identical topology, using a mini scripting language, and then lets you edit it manually if you like.

²If rename-detection gets involved, that is O(n²) in the number of files that could be rename-detected. Git tries to limit this in several ways, including having a maximum length for the rename queue, with the current default being 4000 files.

Answer 2

You can see what's going on in an example I recall from somewhere: start with six lines A B C D E F, on one branch insert three lines G G G at the front then insert six more lines A B C D E F at the front; on another branch (from that first patch/commit) change C to C4. Now merge the two branches.

Git will produce A B C4 D E F G G G A B C D E F; darcs will change the second C, based on the premise that its identity tracking produces a better result than Git's context-and-location tracking. If the "4" is initialization code for the block, Git's result is wrong; if it's initialization code for the function or file, darcs's is wrong.

It's that identity tracking that eats the time.