{"thread":{"id":"10427","subject":"Linear time/space rename logic for *inexact* case","startedAt":"2007-10-22T09:40:08Z","lastAt":"2007-10-23T00:49:39Z","messageCount":5,"participants":["Andy C","Jeff King","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"56844","messageId":"596909b30710220240g665054d8hc40bc5d2234ba9e1@mail.gmail.com","threadId":"10427","inReplyTo":null,"subject":"Linear time/space rename logic for *inexact* case","fromName":"Andy C","fromEmail":"andychup@gmail.com","sentAt":"2007-10-22T09:40:08Z","receivedAt":"2007-10-22T09:40:08Z","isPatch":false,"sender":{"key":"andychup@gmail.com","avatar":null},"body":"I just subscribed to this list, so sorry I can't respond to the\nthreads already started here.  I'm the guy that was mailing Linus\nabout this algorithm to do similarity detection in linear time,\nmentioned here:\n\nSubject:    [PATCH] Split out \"exact content match\" phase of rename detection\nhttp://marc.info/?l=git&m=119299209323278&w=2\n\nSubject:    [PATCH, take 1] Linear-time/space rename logic (exact renames\nhttp://marc.info/?l=git&m=119301122908852&w=2\n\n\nJeff, in this message http://marc.info/?l=git&m=119303566130201&w=2 I\nthink you basically hit on the first half of what I was getting at.\n\nThe step 1 you describe is the first step of the algorithm -- make an\ninverted index of lines (and you can use a hash code of the line to\nstand in for the line).\n\nTo avoid the m*n memory usage of step 2, I use a hash table which maps\n2-tuples to counts to represent the sparse similarity matrix, instead\nof representing it directly.  The 2-tuple is a pair of filenames,\ncorresponding to the row/column of the matrix, and the counts/values\nare the entries in the matrix.\n\nYou can also prune entries which have a long \"postings list\" (using\nthe term in the IR sense here:\nhttp://www.xapian.org/docs/intro_ir.html).  This has the nice side\neffect of getting rid of quadratic behavior, *and* making the\nalgorithm more accurate because it stops considering common lines like\n\"#endif\" as contributing to similarity.\n\nThis pruning of common lines from the index makes step 3 linear.  In\nfact, I prune the index to only include lines which occur just *once*.\n Nearly every line of code in real data sets is unique, so this works\nwell in practice.\n\n\nI already sent this demo to Linus, but I think it's worth sending to\nthe list as well.  I am just going to copy parts of my earlier e-mails\nbelow, and attach the same demos (hopefully it is kosher to send\nattachments to this list).\n\nBefore I do that, Jeff, can you still reproduce this problem:\n\nhttp://marc.info/?l=git&m=118975452330644&w=2\n\"Of course, 2 minutes for a git-status is still way too slow, so there we\nmight still need a limiter. It also looks like 57% of my time is spent\nin spanhash_find, and another 29% in diffcore_count_changes.\"\n\nI know there have been a couple fixes since you posted that, but if it\nwas the O(m*n) behavior that was causing your problem, it should still\nbe reproducible.  Linus suggested that this is a good data set to try\nthings out with.  Is there there a repository I can clone with git\ncommands to run to repro this?\n\n\nOK, so attached is a little demo of the algorithm, which is (very\nlittle) Python code, but with comments so non-Python people can\nhopefully follow it.  Because of this the timings are not very\nmeaningful, but it proves that the algorithm doesn't blow up.\n\nI ran it on the entire Linux 2.4 vs. Linux 2.6 codebases.  It is\n*only* considering file content.  You can rename every file in both\nsource trees to completely random strings and it will still match\nfiles up.  There is nothing about filenames, or identical files, and\nyou can consider the whole 2.4 side \"all deletes\" and the whole 2.6\nside \"all adds\".  The size of the matrix would be around 286 million\ncells, but here I only represent the non-zero entries in the matrix,\nwhich is only 15,406 cells.\n\n$ wc -l similarity_demo.py\n233 similarity_demo.py\n\n$ ./similarity_demo.py in-all-*\n12697 * 22530 = 286063410 total possible pairs of files\nIndexing the first set of 12697 files (threshold=1)\nIndexing the second set of 22530 files (threshold=1)\nSum of file sizes in first set: 2134249 lines\nSum of file sizes in second set: 3424338 lines\nSize of index over first set: 2134249\nSize of index over second set: 3424338\nComputing union of lines in the indices\nTotal unique lines in both indices: 4384375\nMaking sparse common line matrix\nCalculating similarity for 15406 pairs of files\nSorting 15406 similar pairs\nWriting similarity report\nWrote out-in-all-24-vs-in-all-26.1.txt\nEnd\n------\nReport\n------\nIndexing the first set of 12697 files (threshold=1)          29.540s\nIndexing the second set of 22530 files (threshold=1)         111.041s\nComputing union of lines in the indices                      7.450s\nMaking sparse common line matrix                             13.468s\nCalculating similarity for 15406 pairs of files              0.055s\nSorting 15406 similar pairs                                  0.030s\nWriting similarity report                                    0.249s\nTotal time                                                   161.834s\n\nThe script outputs a text file with 15,406 similar pairs, in order of\nsimilarity (1.0's are at the top):\n\nandychu demo$ wc -l out-in-all-24-vs-in-all-26.1.txt\n15406 out-in-all-24-vs-in-all-26.1.txt\n\nandychu demo$ head -n3 out-in-all-24-vs-in-all-26.1.txt\n(  51) linux-2.4.35.3/include/asm-m68k/apollodma.h\n(  51) linux-2.6.23.1/include/asm-m68k/apollodma.h   51 1.000\n\n(  94) linux-2.4.35.3/fs/jfs/jfs_btree.h\n(  94) linux-2.6.23.1/fs/jfs/jfs_btree.h   94 1.000\n\n(  21) linux-2.4.35.3/Documentation/fb/00-INDEX\n(  21) linux-2.6.23.1/Documentation/fb/00-INDEX   21 1.000\n...\n\n\nAnd here is my explanation from an earlier mail, with some slight edits:\n\nSo the algorithm is:\n\n1) Make an inverted index of the left set and right set.  That is {\nline => [\"postings list\", i.e. the list of files the line appears in]\n}.  To get rid of common lines like \"} else {\" or \"#endif\", there is\nan arbitrary \"line threshold\".\n\n2) Combine the 2 indices into a (sparse) rectangular matrix.  For each\nline, iterate over all pairs in the postings list, and increment the\ncell in the matrix for that pair by 1.  The index is extremely\nshallow, since nearly all lines of code are unique.  The common case\nis that the postings list is of length 1.  And the line threshold caps\nthe length of the postings list.\n\nIn the code the matrix represented by a hash of filename pairs to\ninteger counts.  So then the count is the number of lines that the 2\nfiles have in common.\n\n3) Compute the similarity metric, which I've defined here as\nmax(c/|left file|, c/|right file|), where c the entry in the matrix\nfor the file pair.  Note that the files are treated as *sets* of lines\n(unordered, unique).  The similarity score is a number between 0.0 and\n1.0.  Other similarity metrics are certainly possible.\n\nA few things to notice about this algorithm:\n\n* It takes advantage of the fact that code edits are typically\nline-oriented, and nearly every line of code is unique.  (This same\ntechnique can be used for arbitrary documents like English text, but\nit's a bit harder since you basically have to find a way to make a\n\"deep\" index of words shallow, to speed it up.  For code, the index of\nlines is already shallow.)\n\n* Some people might be concerned that it treats files as unordered\nsets of lines.  The first thought might be to do this as a\npreprocessing step to cull the list of candidates, and then do a real\ndelta.  But in my experience, I haven't encountered a case where\nthere's all that much to gain by doing that.\n\n* The line_threshold might appear to be a hack, but it actually\n*improves* accuracy.  If you think about it, lines like \"#endif\"\nshould not contribute to the similarity between 2 files.  It also\nmakes it impossible to construct pathological blow-up cases.  If you\nhave 1000 files on the left and 1000 files on the right that are all\nidentical to each other, then every line will get pruned, and thus the\nentire similarity matrix will be 0, which is arguably what you want.\nThere is a -l flag to the script to experiment with this threshold.\n\n* This can be run on all files, not just adds/deletes.  If I have a\nchange of only edits, it could be the case that I moved 500 lines from\none file 1000 line file to another 1000 line file, and changed 75\nlines within the 500.  It would be meaningful to see a diff in this\ncase, so that I can see those 75 edits (and a great feature!)\n\n* The similarity is defined that way so that if one file is completely\ncontained in another, the similarity is 1.0.  So if I move a 1000 line\nfile and add 9,000 lines to it, the similarity for the file pair will\nstill be 1.0.  I believe this is a feature, like the point above.\n\n* I don't have a C implementation but I believe the constant factors\nshould be very low.  You could use the same CRC you were talking about\nto reduce memory in storing the lines.  It seems like this algorithm\nis amenable to trading memory for speed, as you mention.  Since it is\nraw string manipulation, C should be at least 10x faster than Python,\nand I wouldn't be surprised if an optimized implementation is 50 or\n100x faster.\n\n...\n\nIf anything about the explanation is unclear, let me know and I will\ntry to clarify it.  Playing around with the demo should illuminate\nwhat it does.  You can run it on data sets of your own.  All you need\nis 2 source trees and the \"find\" command to produce input to the\nscript (see setup_demo.sh).\n\nAs mentioned, I will try to do some tests on this, perhaps with Jeff's\nhard data set, and show that the results are good and that the\nalgorithm is faster because the quadratic behavior is gone (if Linus\ndoesn't beat me to it!).\n\nthanks,\nAndy\n\n\n#!/usr/bin/python2.4\n\n\"\"\"\nDemo of linear-time code similarity calculation.\n\nAuthor: Andy Chu (andychu at google dot com)\n\"\"\"\n\nimport optparse\nimport os\nimport md5\nimport re\nimport sys\nimport time\nfrom pprint import pprint\n\n\nclass MultiTimer:\n  \"\"\"To give a general idea of how long each step takes.\"\"\"\n\n  def __init__(self, loud=False):\n    self.timestamps = []\n    self.descriptions = []\n\n  def checkpoint(self, description=''):\n    print description\n    self.timestamps.append(time.time())\n    self.descriptions.append(description)\n\n  def report(self):\n    print \"------\"\n    print \"Report\"\n    print \"------\"\n\n    # Compute time differences\n    format = \"%-60s %.3fs\"\n    for i in xrange(len(self.timestamps)-1):\n      interval = self.timestamps[i+1] - self.timestamps[i]\n      print format % (self.descriptions[i], interval)\n    print format % ('Total time', self.timestamps[-1] - self.timestamps[0])\n\n\ndef IndexFiles(files, line_threshold):\n  \"\"\"\n  Given a list of filenames, produce an inverted index.\n  \n  Any lines which occur in \"line_threshold\" files are thrown out.\n\n  Also, for similarity scoring, keep track of the number of important lines in\n  each file.  Files are treated as (unordered) *sets* of (unique) lines.\n  Unimportant lines are duplicates and lines which exceed line_threshold.\n  \"\"\"\n  # { line -> list of filenames the line appears in }\n  index = {}  \n  # { filename -> number of unique lines in the file }\n  sizes = {}\n\n  for filename in files:\n    try:\n      f = file(filename)\n    except IOError, e:\n      print e, filename\n      sys.exit(1)\n\n    for line in f:\n      line = line.strip()  # Could remove *all* whitespace here\n      if line:  # Skip blank lines\n        if line in index:\n          filelist = index[line]\n          # Stop keeping track once we reach the threshold\n          if len(filelist) == line_threshold + 1:\n            continue\n          # Only count the first occurrence of the line in the file\n          if filelist[-1] != filename:\n            filelist.append(filename)\n            sizes[filename] = sizes.get(filename, 0) + 1\n        else:\n          index[line] = [filename]\n          sizes[filename] = sizes.get(filename, 0) + 1\n    f.close()\n\n  # Now remove any lines that hit the threshold from the index, and adjust the\n  # file sizes.\n  to_remove = []\n  for line, filelist in index.iteritems():\n    if len(filelist) == line_threshold + 1:\n      to_remove.append(line)\n      for f in filelist:\n        sizes[f] -= 1\n  for line in to_remove:\n    del index[line]\n\n  return index, sizes\n\n\ndef FindSimilarPairs(set1, set2, reportfile, line_threshold):\n  \"\"\"Calculates pairwise similarity between two sets of files, using no other\n  information but the contents of the files (i.e. no filename information).\n\n  Args:\n    set1, set2: The 2 lists of file system paths to compare.\n    reportfile: name of the output text file\n    line_threshold:\n      We prune the index of entries that occur more than this number of times.\n      For example, the line \"} else {\" may occur very frequently in the code,\n      but we just throw it out, since the fact that 2 files have this line in\n      common is not very meaningful.\n      \n      Making line_threshold a constant also makes the algorithm linear.  In\n      practice, with real data sets, the results should be quite stable with\n      respect to this parameter.  That is, they should not vary very much at\n      all if line_threshold = 1 or 100 or 1000.\n  \"\"\"\n  mt = MultiTimer()\n\n  print '%s * %s = %s total possible pairs of files' % (\n      len(set1), len(set2), len(set1) * len(set2))\n\n  #\n  # 1. Generate inverted indices and size information for each set.\n  #\n  mt.checkpoint(\"Indexing the first set of %d files (threshold=%d)\" % (\n    len(set1), line_threshold))\n  index1, sizes1 = IndexFiles(set1, line_threshold)\n\n  mt.checkpoint(\"Indexing the second set of %d files (threshold=%d)\" % (\n    len(set2), line_threshold))\n  index2, sizes2 = IndexFiles(set2, line_threshold)\n\n  print \"Sum of file sizes in first set: %s lines\" % sum(sizes1.values())\n  print \"Sum of file sizes in second set: %s lines\" % sum(sizes2.values())\n  print \"Size of index over first set:\", len(index1)\n  print \"Size of index over second set:\", len(index2)\n\n  #\n  # 2. Combine the 2 indices to form sparse matrix that counts common lines.\n  #\n  # Pairs which do not appear have an implicit count of 0.\n  #\n  # This is a sparse matrix represented as a dictionary of 2-tuples:\n  # (filename # in set1, filename in set2) -> number of (unique) lines that\n  # they have in common\n\n  mt.checkpoint(\"Computing union of lines in the indices\")\n  all_lines = set(index1) | set(index2)\n  print 'Total unique lines in both indices: %s' % len(all_lines)\n\n  mt.checkpoint(\"Making sparse common line matrix\")\n\n  matrix = {}\n  for line in all_lines:\n    files1 = index1.get(line)\n    files2 = index2.get(line)\n    if files1 and files2:\n      # For every pair of files that contain this line, increment the\n      # corresponding cell in the common line matrix.  \n      #\n      # Since we pruned the index, this whole double loop is constant time.  If\n      # the line_threshold is 1 (default), then the whole thing is just a\n      # single iteration.  \n      for f1 in files1:\n        for f2 in files2:\n          matrix[(f1, f2)] = matrix.get((f1, f2), 0) + 1\n\n  mt.checkpoint(\"Calculating similarity for %s pairs of files\" % len(matrix))\n\n  #\n  # 3. Calculate the similarity of each cell in the matrix.\n  #\n  # The similarity metric is number of common lines divided by the file size\n  # (and take the greater of the 2).  Note that this means that if file1 is\n  # entirely *contained* in file2, then the similarity of the pair will be 1.0.\n  # This is desirable since you can detect if 99,000 lines were added to a 1,000\n  # line file, etc.  Other similarity metrics are possible.\n  #\n  similar_pairs = []\n  for (file1, file2), num_common in matrix.iteritems():\n    c = float(num_common)\n    # TODO: Write notes on similarity metric\n    similarity = max(c / sizes1[file1], c / sizes2[file2])\n    similar_pairs.append((file1, file2, num_common, similarity))\n\n  mt.checkpoint(\"Sorting %d similar pairs\" % len(similar_pairs))\n  similar_pairs.sort(key=lambda x: x[3], reverse=True)\n\n  mt.checkpoint(\"Writing similarity report\")\n  f = open(reportfile, 'w')\n  for file1, file2, num_common, similarity in similar_pairs:\n    # Put a * after entries where the relative paths are *not* the same, just\n    # for convenience when looking at the report.\n    if file1.split('/')[1:] != file2.split('/')[1:]:\n      mark = '*'\n    else:\n      mark = ''\n\n    print >> f, '(%4d) %-40s (%4d) %-40s %4d %.3f %s' % (\n        sizes1[file1], file1, sizes2[file2], file2, num_common, similarity,\n        mark)\n  f.close()\n  print 'Wrote %s' % reportfile\n\n  mt.checkpoint(\"End\")\n  mt.report()\n\n\nif __name__ == '__main__':\n  parser = optparse.OptionParser()\n\n  parser.add_option(\n      '-l', '--line-threshold', dest='line_threshold', type='int', default=1,\n      help='ignore lines that occur more than this number of times in either '\n      'set')\n  parser.add_option(\n      '-o', '--out', dest='reportfile', default=None,\n      help='Write output to this file instead of the default.')\n\n  (options, argv) = parser.parse_args()\n\n  try:\n    left, right = argv[:2]\n  except ValueError:\n    print 'Pass 2 files containing paths as arguments (left tree, right tree).'\n    sys.exit(1)\n\n  if not options.reportfile:\n    options.reportfile = 'out-%s-vs-%s.%s.txt' % (\n        os.path.splitext(os.path.basename(left))[0],\n        os.path.splitext(os.path.basename(right))[0],\n        options.line_threshold)\n\n  set1 = [f.strip() for f in open(left).readlines()]\n  set2 = [f.strip() for f in open(right).readlines()]\n  FindSimilarPairs(set1, set2, options.reportfile, options.line_threshold)\n"},{"id":"56846","messageId":"596909b30710220309l1a28e646r9fd47f967dc32574@mail.gmail.com","threadId":"10427","inReplyTo":"596909b30710220240g665054d8hc40bc5d2234ba9e1@mail.gmail.com","subject":"Re: Linear time/space rename logic for *inexact* case","fromName":"Andy C","fromEmail":"andychup@gmail.com","sentAt":"2007-10-22T10:09:37Z","receivedAt":"2007-10-22T10:09:37Z","isPatch":false,"sender":{"key":"andychup@gmail.com","avatar":null},"body":"On 10/22/07, Andy C <andychup@gmail.com> wrote:\n> So the algorithm is:\n\nI think I can make this a lot clearer than I did, while glossing over\nsome details and the line_threshold parameter.\n\n1) Make a \"left index\" and a \"right index\" out of the 2 sets of files,\n{ line => [list of docs] }.\n\n2) Remove any lines that appear in more than one doc from the left\nindex.  Do the same for the right index.  (this corresponds to\nline_threshold=1 case)\n\n3) For all lines, if the line appears in *both* the left index and the\nright index, increment the count of the (row=doc from left set,\ncolumn=doc from right set) entry in the similarity matrix by 1.  The\nmatrix is represented by a hash of 2-tuples => counts.\n\nAfter this is done for all lines, then the matrix is sparsely filled\nwith the count of common lines between every pair of files in the 2\nsets.  The vast majority of cells in the matrix are implicitly 0 and\nthus consume neither memory nor CPU with the hash table representation\nof matrix.\n\n4) Then you can use this to compute similarity scores.\n\nHopefully that is more clear... though I guess it might not be obvious\nthat it works for the problem that git has.  I am fairly sure it does,\nbut the demo should allow us to evaluate that.\n\nAndy\n"},{"id":"56851","messageId":"20071022103439.GA16648@coredump.intra.peff.net","threadId":"10427","inReplyTo":"596909b30710220240g665054d8hc40bc5d2234ba9e1@mail.gmail.com","subject":"Re: Linear time/space rename logic for *inexact* case","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-10-22T10:34:40Z","receivedAt":"2007-10-22T10:34:40Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Oct 22, 2007 at 02:40:08AM -0700, Andy C wrote:\n\n> I just subscribed to this list, so sorry I can't respond to the\n> threads already started here.  I'm the guy that was mailing Linus\n> about this algorithm to do similarity detection in linear time,\n> mentioned here:\n\nGreat, welcome aboard. :)\n\n> To avoid the m*n memory usage of step 2, I use a hash table which maps\n> 2-tuples to counts to represent the sparse similarity matrix, instead\n> of representing it directly.  The 2-tuple is a pair of filenames,\n> corresponding to the row/column of the matrix, and the counts/values\n> are the entries in the matrix.\n\nOK, makes sense (that's what I was trying to propose near the end of my\nmail).\n\n> You can also prune entries which have a long \"postings list\" (using\n> the term in the IR sense here:\n> http://www.xapian.org/docs/intro_ir.html).  This has the nice side\n> effect of getting rid of quadratic behavior, *and* making the\n> algorithm more accurate because it stops considering common lines like\n> \"#endif\" as contributing to similarity.\n\nAh, very clever. I think that should have nice behavior most of the\ntime, though I wonder about a pathological case where we have many\nfiles, all very similar to each other, and then have a commit where they\nall start to diverge, but just by a small amount, while getting moved.\nWe would end up with an artificially low score between renamed files\n(because we've thrown out all of the commonality) which may lead us to\nbelieve there was no rename at all.\n\nBut it might be worth ignoring that case.\n\n> This pruning of common lines from the index makes step 3 linear.  In\n> fact, I prune the index to only include lines which occur just *once*.\n>  Nearly every line of code in real data sets is unique, so this works\n> well in practice.\n\nMakes sense.\n\n> http://marc.info/?l=git&m=118975452330644&w=2\n> \"Of course, 2 minutes for a git-status is still way too slow, so there we\n> might still need a limiter. It also looks like 57% of my time is spent\n> in spanhash_find, and another 29% in diffcore_count_changes.\"\n> \n> I know there have been a couple fixes since you posted that, but if it\n> was the O(m*n) behavior that was causing your problem, it should still\n> be reproducible.  Linus suggested that this is a good data set to try\n> things out with.  Is there there a repository I can clone with git\n> commands to run to repro this?\n\nYes, I still have the problem (the 2 minutes was _after_ we did fixes,\ndown from 20 minutes; the latest patch from Linus just covers the \"exact\nmatch\" case where two files have identical SHA1s).\n\nIt's a 1.2G repo at the end of a slow DSL line, so rather than cloning\nit, here's a way to reproduce a repo with similar properties:\n\n-- >8 --\n#!/bin/sh\nrm -rf repo\nmkdir repo && cd repo\n\n# seq and openssl aren't portable, but the\n# point is to generate 200 random 1M files\nfor i in `seq -f %03g 1 600`; do\n  openssl rand 100000 >$i.rand\ndone\n\n# make repo, fully packed\n# we don't bother trying to delta in the pack\n# since the files are all random\ngit-init\ngit-add .\ngit-commit -q -m one\ngit-repack -a -d --window=0\n\n# move every file\nmkdir new\ngit-mv *.rand new\n\n# modify every file\nfor i in new/*.rand; do\n  echo foo >>$i\ndone\ngit-add new\n\n# this is the operation of interest\ntime git-diff --cached --raw -M -l0 >/dev/null\n\n-- >8 --\n\nThe idea is to have a large number of files that are slightly changed\nand moved, and to try to find the pairs.  The diff takes about 20\nseconds to run for me (the real repo has 1M files rather than 100K\nfiles, but it's nice to have the tests take a lot less time). If you\nwant a bigger test, bump up the file size (or increase the number of\nfiles, which will emphasize the quadratic behavior).\n\n> 3) Compute the similarity metric, which I've defined here as\n> max(c/|left file|, c/|right file|), where c the entry in the matrix\n> for the file pair.  Note that the files are treated as *sets* of lines\n> (unordered, unique).  The similarity score is a number between 0.0 and\n> 1.0.  Other similarity metrics are certainly possible.\n\nWe have to handle binary files, too. In the current implementation, we\nconsider either lines or \"chunks\", and similarity is increased by the\nsize of the chunk.\n\n> * Some people might be concerned that it treats files as unordered\n> sets of lines.  The first thought might be to do this as a\n> preprocessing step to cull the list of candidates, and then do a real\n> delta.  But in my experience, I haven't encountered a case where\n> there's all that much to gain by doing that.\n\nI think we are already treating the files as unordered sets of lines.\nAnd really, I think there is some value in that, anyway. If I reverse\nthe order of all lines in a file, it might be useful for git to say\n\"this file came from that file\".\n\n> * This can be run on all files, not just adds/deletes.  If I have a\n\nGreat. git has a \"look for copies also\" flag, but it is usually disabled\nbecause of the computational cost. If we can get it low enough, it might\nactually become a lot more useful.\n\n> If anything about the explanation is unclear, let me know and I will\n> try to clarify it.  Playing around with the demo should illuminate\n> what it does.  You can run it on data sets of your own.  All you need\n> is 2 source trees and the \"find\" command to produce input to the\n> script (see setup_demo.sh).\n\nI'll try it on my test data, but it sounds like it doesn't really handle\nbinary files.\n\n> As mentioned, I will try to do some tests on this, perhaps with Jeff's\n> hard data set, and show that the results are good and that the\n> algorithm is faster because the quadratic behavior is gone (if Linus\n> doesn't beat me to it!).\n\nTrying to fit it into the C git code would be useful, but I doubt I'll\nhave time to work on it tonight, since it's getting onto dawn here.\n\n-Peff\n"},{"id":"56929","messageId":"596909b30710221647y6a7481c5me41c31bbe1015e3a@mail.gmail.com","threadId":"10427","inReplyTo":"20071022103439.GA16648@coredump.intra.peff.net","subject":"Re: Linear time/space rename logic for *inexact* case","fromName":"Andy C","fromEmail":"andychup@gmail.com","sentAt":"2007-10-22T23:47:21Z","receivedAt":"2007-10-22T23:47:21Z","isPatch":false,"sender":{"key":"andychup@gmail.com","avatar":null},"body":"On 10/22/07, Jeff King <peff@peff.net> wrote:\n> On Mon, Oct 22, 2007 at 02:40:08AM -0700, Andy C wrote:\n> > You can also prune entries which have a long \"postings list\" (using\n> > the term in the IR sense here:\n> > http://www.xapian.org/docs/intro_ir.html).  This has the nice side\n> > effect of getting rid of quadratic behavior, *and* making the\n> > algorithm more accurate because it stops considering common lines like\n> > \"#endif\" as contributing to similarity.\n>\n> Ah, very clever. I think that should have nice behavior most of the\n> time, though I wonder about a pathological case where we have many\n> files, all very similar to each other, and then have a commit where they\n> all start to diverge, but just by a small amount, while getting moved.\n> We would end up with an artificially low score between renamed files\n> (because we've thrown out all of the commonality) which may lead us to\n> believe there was no rename at all.\n>\n> But it might be worth ignoring that case.\n\nWell I do adjust the file sizes when pruning.  In the .py demo code\nyou can see it at these lines:\n\n      for f in filelist:\n        sizes[f] -= 1\n\nThe similarity metric depends on the sizes, so that way it won't get\nout of whack if there are a lot of frequently occurring lines.\n\nI did mention that pathological case to Linus.  The worst thing is if\nyou have N adds and N deletes and every single file is identical.\nWell the convenient thing is that the pruning handles this gracefully.\n *Every* line in both indices will be pruned, and then the similarity\nmatrix will be completely empty, and no renames will be recorded.\nArguably that is what you want.  You don't want N^2 renames.  I guess\nyou could just assign them randomly to each other too for N renames.\n\n\n> > http://marc.info/?l=git&m=118975452330644&w=2\n> > \"Of course, 2 minutes for a git-status is still way too slow, so there we\n> > might still need a limiter. It also looks like 57% of my time is spent\n> > in spanhash_find, and another 29% in diffcore_count_changes.\"\n> >\n> > I know there have been a couple fixes since you posted that, but if it\n> > was the O(m*n) behavior that was causing your problem, it should still\n> > be reproducible.  Linus suggested that this is a good data set to try\n> > things out with.  Is there there a repository I can clone with git\n> > commands to run to repro this?\n>\n> Yes, I still have the problem (the 2 minutes was _after_ we did fixes,\n> down from 20 minutes; the latest patch from Linus just covers the \"exact\n> match\" case where two files have identical SHA1s).\n>\n> It's a 1.2G repo at the end of a slow DSL line, so rather than cloning\n> it, here's a way to reproduce a repo with similar properties:\n\nAh OK thanks.   This is a good test case for binary files, and my\nLinux 2.4 vs Linux 2.6 test seems reasonable for text files.\n\n> > 3) Compute the similarity metric, which I've defined here as\n> > max(c/|left file|, c/|right file|), where c the entry in the matrix\n> > for the file pair.  Note that the files are treated as *sets* of lines\n> > (unordered, unique).  The similarity score is a number between 0.0 and\n> > 1.0.  Other similarity metrics are certainly possible.\n>\n> We have to handle binary files, too. In the current implementation, we\n> consider either lines or \"chunks\", and similarity is increased by the\n> size of the chunk.\n\nYes, my thing doesn't handle binary files, but I have a variation of\nthe idea for that too which I'll explain below.\n\nCan you explain what the current implementation does for binary files\nin more detail, or point me to some docs?  I'm having a hard code\nfiguring out what the code is doing, even though the comments insist\nthat it is very simple : )\n\nfrom diffcore-delta.c:\n\"\n * Idea here is very simple.\n *\n * Almost all data we are interested in are text, but sometimes we have\n * to deal with binary data.  So we cut them into chunks delimited by\n * LF byte, or 64-byte sequence, whichever comes first, and hash them.\n\"\n\nWhat is the similarity metric for binary files?  Is it related to the\nnumber of 64 byte chunks they have in common?  How do you know that\nthe 64 byte chunks match up?  Suppose I have 10k file, and then I\ninsert 10 random bytes at positions, 1000, 2000, 3000, etc.   How does\nthat work?\n\n> > * This can be run on all files, not just adds/deletes.  If I have a\n>\n> Great. git has a \"look for copies also\" flag, but it is usually disabled\n> because of the computational cost. If we can get it low enough, it might\n> actually become a lot more useful.\n\nYes, there seem to be quite a few flags that have to do with trading\noff features for computational time/memory.  I believe this algorithm\ncould be made fast enough to simplify the user interface a bit.  I'm\nnot yet super familiar with git, but I imagine it's probably hard for\nsome users to intuit what these thresholds do.\n\n> > If anything about the explanation is unclear, let me know and I will\n> > try to clarify it.  Playing around with the demo should illuminate\n> > what it does.  You can run it on data sets of your own.  All you need\n> > is 2 source trees and the \"find\" command to produce input to the\n> > script (see setup_demo.sh).\n>\n> I'll try it on my test data, but it sounds like it doesn't really handle\n> binary files.\n\nYes, I think we should try it out for text files first, since that's\nprobably the more important case.  But at the risk of getting a bit\nahead of myself, I think you can do a similar thing for binary files.\n\nThis first part isn't my idea; I heard it at a talk by Udi Manber at\nGoogle, but I think it could be combined with my pruning and sparse\nsimilarity matrix thing.  And it looks like there are already some of\nthe same ideas in git, though I'm still deciphering the code (any docs\non this area would help).\n\nBasically his idea is that you take a rolling window of say 64 bytes\nand create an inverted index, just like you do for text files.  So if\nyou have a 10,000 byte file, then there are (10,000 - 64) hashes to be\nmade.\n\nThis could be a lot, so you can speed it up by sampling.  But you want\nto sample in such a way that preserves commonality.  That is, you\ndon't want to sample a given 64-byte sequence in one doc but miss it\nin the other one.  So then all you do is keep all windows where the\nhash code is 0 mod k (and you can adjust k that to achieve the\nsampling rate you want).  If a given sequence is sampled in *one* doc,\nthen it's guaranteed to be sampled in *all* docs.\n\nThe second point is that you can do this rolling window hashing very\nfast with a polynomial hash.  You can use the results of the previous\nhash to compute the next hash.  I think you already have this in\ndiff-delta.c, but I'm not quite sure.  I'm not sure exactly what that\ncode is used for either (I don't think it is for the rename matching,\nbecause that is done by estimate_similarity and\ndiffcore_count_changes?).\n\nOnce you have these 2 inverted indices of { sampled subset of 64-byte\nsubstrings -> [list of documents] }  then you simply do the same thing\nas I suggested for text files.  The logic is more or less the same.\nIf 2 files have many 64-byte substrings in common compared to their\nsizes, then they are similar.  If a given 64-byte sequence (say\n0000000000000...000) appears in many docs, then it's not a good\ndifferentiator or indicator of similarity -- so throw it out.\n\n(It occurs to me that it might be useful to do this with a small\nwindow (8 bytes?) and a larger one (>64), and somehow combine the\nresults.  I guess some experimentation is in order, or maybe there is\nsome theory about that.)\n\nSo this is a linear algorithm too.  The hashing could have a high\nconstant factor, but the sampling and polynomial hashing should\nbasically eliminate that, I believe.\n\nBut like I said, it's probably better to concentrate on the text part\nbefore anyone tackles that (at least I will look at the text case\nfirst).  I have less experience with this algorithm, but it seems like\nit should work just as well, and is quite simple.  I think both of\nthese algorithms are a bit more general and should lead to a net\nreduction in lines of code, which is a good thing.\n\nAndy\n"},{"id":"56933","messageId":"alpine.LFD.0.999.0710221745160.30120@woody.linux-foundation.org","threadId":"10427","inReplyTo":"596909b30710221647y6a7481c5me41c31bbe1015e3a@mail.gmail.com","subject":"Re: Linear time/space rename logic for *inexact* case","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-23T00:49:39Z","receivedAt":"2007-10-23T00:49:39Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 22 Oct 2007, Andy C wrote:\n> \n> from diffcore-delta.c:\n> \"\n>  * Idea here is very simple.\n>  *\n>  * Almost all data we are interested in are text, but sometimes we have\n>  * to deal with binary data.  So we cut them into chunks delimited by\n>  * LF byte, or 64-byte sequence, whichever comes first, and hash them.\n> \"\n> \n> What is the similarity metric for binary files?  Is it related to the\n> number of 64 byte chunks they have in common?  How do you know that\n> the 64 byte chunks match up?  Suppose I have 10k file, and then I\n> insert 10 random bytes at positions, 1000, 2000, 3000, etc.   How does\n> that work?\n\nThe 'LF' byte will start a new window, so even with binary files (assuming \nsome random-enough distribution that you have *some* 'LF' bytes!), you \nbasically get a synchronization event on each LF.\n\nSo the 64-byte hunks \"line up\" automatically, even for binary files. Maybe \nnot immediately, but soon enough (ie on average, assuming some reasonably \ncompressed - ie virtually random - binary format) you should find a LF \nroughly every fourth hunk.\n\nThere are probably smarter ways to guarantee it even in the absense of \ncertain bit-patterns, but I bet the \"break every 64 bytes or when you see \na LF\" thing works well for any reasonable binary file too.\n\nBut text files are obviously the most important case. Diffs on binaries \nare somewhat hit-and-miss regardless.\n\n\t\t\tLinus\n"}]}