Re: What's cooking in git.git (topics)

From: Jeff King <peff@peff.net>
Date: Oct 2, 2007, 16:11 UTC
Message-ID: <20071002161114.GC6828@coredump.intra.peff.net>
In-Reply-To: <86ejge6o8b.fsf@lola.quinscape.zz>

On Tue, Oct 02, 2007 at 08:10:28AM +0200, David Kastrup wrote:

> I have not actually looked at the actual task that the structures are
> going to be used in, and whether "reusing" the information is likely
> to be worth the trouble.

The algorithm is something like this: We have N files, and we want to find "similar" candidates. So we go through each file and generate a table of fingperint hashes (diffcore-rename.c:hash_chars), and then compare each file with every other file, using the hash tables to do the comparison.

So the comparison step for two files is currently something like:

  for each hash in file1
    hash2 = look up hash in file2
    compare hash and hash2

and if they were sorted, perhaps we could do something merge-like:

  while hashes are left to compare
      compare file1.next, file2.next
      advance file1, file2, or both (depending on comparison)

> When we are talking about buzzword compliance, "keep sorted" with the
> meaning of "maintain sorted across modifications" has an O(n^2) or at
> least O(nm) ring to it.  However, if it is possible to sort it just
> once, and then then only merge with other lists...

It would be sort once. I.e.,:

  for each file
     generate file.hashes
     sort file.hashes
  for each file1
    for each file2
      compare file1.hashes to file2.hashes

where that 'compare' step is taking most of the CPU time (for the obvious reason that we call it in an O(n^2) loop).

I will try to implement this as time permits, but if you want to tinker with it in the meantime, feel free.

-Peff