bzr 0.11 takes an inordinate amount of time to process a commit

[Daniel Silverstone]

Sesse on #bzr said that he had a 10 minute commit with no feedback.
CPU bound, no syscalls

He can reproduce it with the files in http://www.sesse.net/download/bzr-slowness.tar.bz2 and claims the process is approximately:

17:55 < Sesse> yeah, this triggers it
17:55 < Sesse> cp a.txt file.txt ; rm -rf .bzr/ ; bzr init ; bzr add file.txt ;
               bzr commit -m "." ; cp b.txt file.txt ; bzr commit -m "."
17:55 < Sesse> and from there it hangs

I've not confirmed this, I'm just filing it because Sesse can't get logged into launchpad due to a bug in the people management stuff interacting with the DebianDeveloper import.

He can be contacted at <email address hidden>

[John A Meinel (jameinel)]

I can confirm that this happens.

My best guess is that it is related to bug 6373.
We use a slightly modified sequence matcher for committing hunks into knits (bzrlib/knit.py KnitSequenceMatcher). Because we tuned it for the case of knits. That also seemed to fix the earlier bug 6373.

However, we have another possibility which we use bzrlib.patiencediff.PatienceSequenceMatcher, which we should probably switch to. It is the algorithm used by 'bzr diff', and seems to avoid this behavior. (Though why it would have a problem when there are no common lines between the source files, I'm not sure).

It may just be that python's difflib is O(N^2) in the number of lines, and these b.txt has 262,000 lines.

[John A Meinel (jameinel)]

In bzr-0.13 we switch to using patiencediff rather than difflib for inserting texts into knits.

This should give us O(N^2) performance rather than O(N^3).