On Mon, Oct 22, 2007 at 02:40:08AM -0700, Andy C wrote:

quoted text
> I just subscribed to this list, so sorry I can't respond to the
> threads already started here.  I'm the guy that was mailing Linus
> about this algorithm to do similarity detection in linear time,
> mentioned here:

Great, welcome aboard. :)

quoted text
> To avoid the m*n memory usage of step 2, I use a hash table which maps
> 2-tuples to counts to represent the sparse similarity matrix, instead
> of representing it directly.  The 2-tuple is a pair of filenames,
> corresponding to the row/column of the matrix, and the counts/values
> are the entries in the matrix.

OK, makes sense (that's what I was trying to propose near the end of my
mail).

quoted text
> You can also prune entries which have a long "postings list" (using
> the term in the IR sense here:
> http://www.xapian.org/docs/intro_ir.html).  This has the nice side
> effect of getting rid of quadratic behavior, *and* making the
> algorithm more accurate because it stops considering common lines like
> "#endif" as contributing to similarity.

Ah, very clever. I think that should have nice behavior most of the
time, though I wonder about a pathological case where we have many
files, all very similar to each other, and then have a commit where they
all start to diverge, but just by a small amount, while getting moved.
We would end up with an artificially low score between renamed files
(because we've thrown out all of the commonality) which may lead us to
believe there was no rename at all.

But it might be worth ignoring that case.

quoted text
> This pruning of common lines from the index makes step 3 linear.  In
> fact, I prune the index to only include lines which occur just *once*.
>  Nearly every line of code in real data sets is unique, so this works
> well in practice.

Makes sense.

quoted text
> http://marc.info/?l=git&m=118975452330644&w=2
> "Of course, 2 minutes for a git-status is still way too slow, so there we
> might still need a limiter. It also looks like 57% of my time is spent
> in spanhash_find, and another 29% in diffcore_count_changes."
> 
> I know there have been a couple fixes since you posted that, but if it
> was the O(m*n) behavior that was causing your problem, it should still
> be reproducible.  Linus suggested that this is a good data set to try
> things out with.  Is there there a repository I can clone with git
> commands to run to repro this?

Yes, I still have the problem (the 2 minutes was _after_ we did fixes,
down from 20 minutes; the latest patch from Linus just covers the "exact
match" case where two files have identical SHA1s).

It's a 1.2G repo at the end of a slow DSL line, so rather than cloning
it, here's a way to reproduce a repo with similar properties:

-- >8 --
#!/bin/sh
rm -rf repo
mkdir repo && cd repo

# seq and openssl aren't portable, but the
# point is to generate 200 random 1M files
for i in `seq -f %03g 1 600`; do
  openssl rand 100000 >$i.rand
done

# make repo, fully packed
# we don't bother trying to delta in the pack
# since the files are all random
git-init
git-add .
git-commit -q -m one
git-repack -a -d --window=0

# move every file
mkdir new
git-mv *.rand new

# modify every file
for i in new/*.rand; do
  echo foo >>$i
done
git-add new

# this is the operation of interest
time git-diff --cached --raw -M -l0 >/dev/null

-- >8 --

The idea is to have a large number of files that are slightly changed
and moved, and to try to find the pairs.  The diff takes about 20
seconds to run for me (the real repo has 1M files rather than 100K
files, but it's nice to have the tests take a lot less time). If you
want a bigger test, bump up the file size (or increase the number of
files, which will emphasize the quadratic behavior).

quoted text
> 3) Compute the similarity metric, which I've defined here as
> max(c/|left file|, c/|right file|), where c the entry in the matrix
> for the file pair.  Note that the files are treated as *sets* of lines
> (unordered, unique).  The similarity score is a number between 0.0 and
> 1.0.  Other similarity metrics are certainly possible.

We have to handle binary files, too. In the current implementation, we
consider either lines or "chunks", and similarity is increased by the
size of the chunk.

quoted text
> * Some people might be concerned that it treats files as unordered
> sets of lines.  The first thought might be to do this as a
> preprocessing step to cull the list of candidates, and then do a real
> delta.  But in my experience, I haven't encountered a case where
> there's all that much to gain by doing that.

I think we are already treating the files as unordered sets of lines.
And really, I think there is some value in that, anyway. If I reverse
the order of all lines in a file, it might be useful for git to say
"this file came from that file".

quoted text
> * This can be run on all files, not just adds/deletes.  If I have a

Great. git has a "look for copies also" flag, but it is usually disabled
because of the computational cost. If we can get it low enough, it might
actually become a lot more useful.

quoted text
> If anything about the explanation is unclear, let me know and I will
> try to clarify it.  Playing around with the demo should illuminate
> what it does.  You can run it on data sets of your own.  All you need
> is 2 source trees and the "find" command to produce input to the
> script (see setup_demo.sh).

I'll try it on my test data, but it sounds like it doesn't really handle
binary files.

quoted text
> As mentioned, I will try to do some tests on this, perhaps with Jeff's
> hard data set, and show that the results are good and that the
> algorithm is faster because the quadratic behavior is gone (if Linus
> doesn't beat me to it!).

Trying to fit it into the C git code would be useful, but I doubt I'll
have time to work on it tonight, since it's getting onto dawn here.

-Peff
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html