Git has bad performance when traversing change-sets with large PPM files

Steps to reproduce:

1. Create a new git repo and add a 640x480 PPM image in ASCII format
2. Add a .gitattributes file with the line "*.ppm binary"
3. Commit the PPM file
4. Change the PPM image's contents
5. Add and commit
6. Try to do a git rebase -i to the initial commit
7. Watch the CPU peg at 100%

I'm using git version 1.6.3.3

Please CC me, I'm not on the list.

Thanks,

Ordinary 'rebase -i' reads the commits to rebase with (roughly)

  git rev-list --left-right --cherry-pick $upstream...

which gives it the feature of skipping commits that are already present in $upstream. However, in the common use-case of rewriting a few commits up to an ancestor, as in 'git rebase -i HEAD~3', the --cherry-pick is useless since there are no commits to compare to.

Add a check if $upstream is a direct ancestor of HEAD, and leave away the --cherry-pick if so. Since the --cherry-pick is already in $MERGES_OPTION, we need to decide this before setting the latter.

For simplicity we skip --root mode. In theory we could do the same optimization, but using --root --onto <ancestor> is probably even more rare than having performance issues with --cherry-pick.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---

The --cherry-pick mechanism itself could get a similar optimization, but I don't know that code.

 git-rebase--interactive.sh |    7 ++++++-
 1 files changed, 6 insertions(+), 1 deletions(-)

On Saturday 20 February 2010 00:30:52 Thomas Rast wrote:

[...]

Or maybe it's as simple as this?

On Sat, Feb 20, 2010 at 01:02:15AM +0100, Thomas Rast wrote:

ever looked at it, so who knows? :)

Also, I was curious whether we correctly respected gitattributes when calculating patch ids (specifically, do we actually treat this thing as binary). But it looks like patch-id's don't make any exceptions for binary files, and they get fed to xdiff. I think this is not buggy (the xdiff consumer seems to get the diff content with a length, so we are not treating the potentially binary data as a C-string anywhere that I see). But it is probably the source of the slowness to xdiff that gigantic files.

Does it really make sense to treat binary files as anything other than a blob for generating patch id? That is, should we simply turn it into:

  binary diff
  $from_sha1
  $to_sha1

and hash that for the patch id?

-Peff

The --cherry-pick logic starts by counting the commits on each side, so that it can filter away commits on the bigger one. However, so far it missed an opportunity for optimization: it doesn't need to do any work if either side is empty.

This in particular helps the common use-case 'git rebase -i HEAD~$n': it internally uses --cherry-pick, but since HEAD~$n is a direct ancestor the left side is always empty.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---

On Saturday 20 February 2010 08:27:28 Jeff King wrote:

Junio agreed too, so here's a real patch. To keep the complexity of git-rebase--interactive from exploding even further, you can drop the earlier one.

I tend to agree, but I can't seem to find out what flags to flip :-(

 revision.c |    3 +++
 1 files changed, 3 insertions(+), 0 deletions(-)

On Sat, Feb 20, 2010 at 12:42:04PM +0100, Thomas Rast wrote:

You would need to call diff_filespec_is_binary when flushing the diff queue, which handles both attributes and autodetection. Something like:

On Saturday 20 February 2010 08:27:28 Jeff King wrote:

BTW, here's a weird data point:

$ ls -l a b -rw-r--r-- 1 thomas users 3300765 2010-02-20 12:48 a -rw-r--r-- 1 thomas users 3253762 2010-02-20 12:48 b $ time diff -u a b | wc -l 54530

real 0m0.644s user 0m0.562s sys 0m0.044s $ time git diff --no-index a b >/dev/null

real 0m22.848s user 0m21.956s sys 0m0.137s $ time git diff --no-index --patience a b >/dev/null

real 0m19.508s user 0m18.673s sys 0m0.273s

'a' and 'b' are two pnm's as per the OPs specification, I made 'a' a gradient and 'b' the same with two crosses drawn over it. You can find them at

  http://thomasrast.ch/download/slow-diff-pnms.zip

if you want to reproduce.

So what on earth does 'diff' do that makes it 35 times as fast?

On Sat, Feb 20, 2010 at 02:38:29PM +0100, Thomas Rast wrote:

I was able to reproduce here. According to 'perf', git spends 70% of its time in xdl_split, which says:

/*
 * See "An O(ND) Difference Algorithm and its Variations", by Eugene Myers.
 * Basically considers a "box" (off1, off2, lim1, lim2) and scan from both
 * the forward diagonal starting from (off1, off2) and the backward diagonal
 * starting from (lim1, lim2). If the K values on the same diagonal crosses
 * returns the furthest point of reach. We might end up having to expensive
 * cases using this algorithm is full, so a little bit of heuristic is needed
 * to cut the search and to return a suboptimal point.
 */

GNU diff also seems to use the same basic Myers algorithm, but says:

   The basic algorithm is described in:
   "An O(ND) Difference Algorithm and its Variations", Eugene Myers,
   Algorithmica Vol. 1 No. 2, 1986, pp. 251-266;
   see especially section 4.2, which describes the variation used below.

   The basic algorithm was independently discovered as described in:
   "Algorithms for Approximate String Matching", E. Ukkonen,
   Information and Control Vol. 64, 1985, pp. 100-118.

   Unless the 'find_minimal' flag is set, this code uses the TOO_EXPENSIVE
   heuristic, by Paul Eggert, to limit the cost to O(N**1.5 log N)
   at the price of producing suboptimal output for large inputs with
   many differences.

So it may be that TOO_EXPENSIVE heuristic. I don't know enough about the diff code (git's or otherwise) to say how difficult it would be to adapt GNU diff's tricks.

-Peff