git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH 12/12] Optimize diff-tree -[CM] --stdin

From
Junio C Hamano <junkio@cox.net>
Date
May 27, 2005, 22:56 UTC
Message-ID
<7vhdgo2s7t.fsf_-_@assigned-by-dhcp.cox.net>
In-Reply-To
<7vk6lk5lxt.fsf_-_@assigned-by-dhcp.cox.net>

This attempts to optimize "diff-tree -[CM] --stdin", which compares successible tree pairs. This optimization does not make much sense for other commands in the diff-* brothers.

When reading from --stdin and using rename/copy detection, the patch makes diff-tree to read the current index file first. This is done to reuse the optimization used by diff-cache in the non-cached case. Similarity estimator can avoid expanding a blob if the index says what is in the work tree has an exact copy of that blob already expanded.

Another optimization the patch makes is to check only file sizes first to terminate similarity estimation early. In order for this to work, it needs a way to tell the size of the blob without expanding it. Since an obvious way of doing it, which is to keep all the blobs previously used in the memory, is too costly, it does so by keeping the filesize for each object it has already seen in memory.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---

diff-tree.c | 3 + diff.c | 83 +++++++++++++++++++++++++++++++++++++++++++++++++++-- diff.h | 2 + diffcore-pickaxe.c | 2 - diffcore-rename.c | 19 ++++++++---- diffcore.h | 2 - 6 files changed, 102 insertions(+), 9 deletions(-)

diff --git a/diff-tree.c b/diff-tree.c
--- a/diff-tree.c
+++ b/diff-tree.c
@@ -578,6 +578,9 @@ int main(int argc, const char **argv)
 	if (!read_stdin)
 		return 0;
 
+	if (detect_rename)
+		diff_setup_opt |= (DIFF_SETUP_USE_SIZE_CACHE |
+				   DIFF_SETUP_USE_CACHE);
 	while (fgets(line, sizeof(line), stdin))
 		diff_tree_stdin(line);
 
diff --git a/diff.c b/diff.c
--- a/diff.c
+++ b/diff.c
@@ -12,6 +12,7 @@ static const char *diff_opts = "-pu";
 static unsigned char null_sha1[20] = { 0, };
 
 static int reverse_diff;
+static int use_size_cache;
 
 static const char *external_diff(void)
 {
@@ -222,12 +223,60 @@ static int work_tree_matches(const char 
 	return 1;
 }
 
+static struct sha1_size_cache {
+	unsigned char sha1[20];
+	unsigned long size;
+} **sha1_size_cache;
+static int sha1_size_cache_nr, sha1_size_cache_alloc;
+
+static struct sha1_size_cache *locate_size_cache(unsigned char *sha1,
+						 unsigned long size)
+{
+	int first, last;
+	struct sha1_size_cache *e;
+
+	first = 0;
+	last = sha1_size_cache_nr;
+	while (last > first) {
+		int next = (last + first) >> 1;
+		e = sha1_size_cache[next];
+		int cmp = memcmp(e->sha1, sha1, 20);
+		if (!cmp)
+			return e;
+		if (cmp < 0) {
+			last = next;
+			continue;
+		}
+		first = next+1;
+	}
+	/* not found */
+	if (size == UINT_MAX)
+		return NULL;
+	/* insert to make it at "first" */
+	if (sha1_size_cache_alloc <= sha1_size_cache_nr) {
+		sha1_size_cache_alloc = alloc_nr(sha1_size_cache_alloc);
+		sha1_size_cache = xrealloc(sha1_size_cache,
+					   sha1_size_cache_alloc *
+					   sizeof(*sha1_size_cache));
+	}
+	sha1_size_cache_nr++;
+	if (first < sha1_size_cache_nr)
+		memmove(sha1_size_cache + first + 1, sha1_size_cache + first,
+			(sha1_size_cache_nr - first - 1) *
+			sizeof(*sha1_size_cache));
+	e = xmalloc(sizeof(struct sha1_size_cache));
+	sha1_size_cache[first] = e;
+	memcpy(e->sha1, sha1, 20);
+	e->size = size;
+	return e;
+}
+
 /*
  * While doing rename detection and pickaxe operation, we may need to
  * grab the data for the blob (or file) for our own in-core comparison.
  * diff_filespec has data and size fields for this purpose.
  */
-int diff_populate_filespec(struct diff_filespec *s)
+int diff_populate_filespec(struct diff_filespec *s, int size_only)
 {
 	int err = 0;
 	if (!DIFF_FILE_VALID(s))
@@ -235,6 +284,9 @@ int diff_populate_filespec(struct diff_f
 	if (S_ISDIR(s->mode))
 		return -1;
 
+	if (!use_size_cache)
+		size_only = 0;
+
 	if (s->data)
 		return err;
 	if (!s->sha1_valid ||
@@ -254,6 +306,8 @@ int diff_populate_filespec(struct diff_f
 		s->size = st.st_size;
 		if (!s->size)
 			goto empty;
+		if (size_only)
+			return 0;
 		if (S_ISLNK(st.st_mode)) {
 			int ret;
 			s->data = xmalloc(s->size);
@@ -273,9 +327,21 @@ int diff_populate_filespec(struct diff_f
 		close(fd);
 	}
 	else {
+		/* We cannot do size only for SHA1 blobs */
 		char type[20];
+		struct sha1_size_cache *e;
+
+		if (size_only) {
+			e = locate_size_cache(s->sha1, UINT_MAX);
+			if (e) {
+				s->size = e->size;
+				return 0;
+			}
+		}
 		s->data = read_sha1_file(s->sha1, type, &s->size);
 		s->should_free = 1;
+		if (s->data && size_only)
+			locate_size_cache(s->sha1, s->size);
 	}
 	return 0;
 }
@@ -361,7 +427,7 @@ static void prepare_temp_file(const char
 		return;
 	}
 	else {
-		if (diff_populate_filespec(one))
+		if (diff_populate_filespec(one, 0))
 			die("cannot read data blob for %s", one->path);
 		prep_temp_blob(temp, one->data, one->size,
 			       one->sha1, one->mode);
@@ -496,6 +562,19 @@ void diff_setup(int flags)
 {
 	if (flags & DIFF_SETUP_REVERSE)
 		reverse_diff = 1;
+	if (flags & DIFF_SETUP_USE_CACHE) {
+		if (!active_cache)
+			/* read-cache does not die even when it fails
+			 * so it is safe for us to do this here.  Also
+			 * it does not smudge active_cache or active_nr
+			 * when it fails, so we do not have to worry about
+			 * cleaning it up oufselves either.
+			 */
+			read_cache();
+	}
+	if (flags & DIFF_SETUP_USE_SIZE_CACHE)
+		use_size_cache = 1;
+	
 }
 
 struct diff_queue_struct diff_queued_diff;
diff --git a/diff.h b/diff.h
--- a/diff.h
+++ b/diff.h
@@ -29,6 +29,8 @@ extern void diff_unmerge(const char *pat
 extern int diff_scoreopt_parse(const char *opt);
 
 #define DIFF_SETUP_REVERSE      	1
+#define DIFF_SETUP_USE_CACHE		2
+#define DIFF_SETUP_USE_SIZE_CACHE	4
 extern void diff_setup(int flags);
 
 #define DIFF_DETECT_RENAME	1
diff --git a/diffcore-pickaxe.c b/diffcore-pickaxe.c
--- a/diffcore-pickaxe.c
+++ b/diffcore-pickaxe.c
@@ -11,7 +11,7 @@ static int contains(struct diff_filespec
 {
 	unsigned long offset, sz;
 	const char *data;
-	if (diff_populate_filespec(one))
+	if (diff_populate_filespec(one, 0))
 		return 0;
 	sz = one->size;
 	data = one->data;
diff --git a/diffcore-rename.c b/diffcore-rename.c
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -99,8 +99,11 @@ static int is_exact_match(struct diff_fi
 	if (src->sha1_valid && dst->sha1_valid &&
 	    !memcmp(src->sha1, dst->sha1, 20))
 		return 1;
-	if (diff_populate_filespec(src) || diff_populate_filespec(dst))
-		/* this is an error but will be caught downstream */
+	if (diff_populate_filespec(src, 1) || diff_populate_filespec(dst, 1))
+		return 0;
+	if (src->size != dst->size)
+		return 0;
+	if (diff_populate_filespec(src, 0) || diff_populate_filespec(dst, 0))
 		return 0;
 	if (src->size == dst->size &&
 	    !memcmp(src->data, dst->data, src->size))
@@ -125,9 +128,11 @@ static int estimate_similarity(struct di
 	 * dst, and then some edit has been applied to dst.
 	 *
 	 * Compare them and return how similar they are, representing
-	 * the score as an integer between 0 and 10000, except
-	 * where they match exactly it is considered better than anything
-	 * else.
+	 * the score as an integer between 0 and MAX_SCORE.
+	 *
+	 * When there is an exact match, it is considered a better
+	 * match than anything else; the destination does not even
+	 * call into this function in that case.
 	 */
 	void *delta;
 	unsigned long delta_size, base_size;
@@ -147,6 +152,7 @@ static int estimate_similarity(struct di
 	/* We would not consider edits that change the file size so
 	 * drastically.  delta_size must be smaller than
 	 * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size).
+	 *
 	 * Note that base_size == 0 case is handled here already
 	 * and the final score computation below would not have a
 	 * divide-by-zero issue.
@@ -154,6 +160,9 @@ static int estimate_similarity(struct di
 	if (base_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)
 		return 0;
 
+	if (diff_populate_filespec(src, 0) || diff_populate_filespec(dst, 0))
+		return 0; /* error but caught downstream */
+
 	delta = diff_delta(src->data, src->size,
 			   dst->data, dst->size,
 			   &delta_size);
diff --git a/diffcore.h b/diffcore.h
--- a/diffcore.h
+++ b/diffcore.h
@@ -33,7 +33,7 @@ extern struct diff_filespec *alloc_files
 extern void fill_filespec(struct diff_filespec *, const unsigned char *,
 			  unsigned short);
 
-extern int diff_populate_filespec(struct diff_filespec *);
+extern int diff_populate_filespec(struct diff_filespec *, int);
 extern void diff_free_filespec_data(struct diff_filespec *);
 
 struct diff_filepair {
------------------------------------------------
Previous: Junio C HamanoNext: Yoichi Yuasa
Message 20 of 45 in “Broken directory pathname pruning..”
  1. Linus TorvaldsMay 27, 2005
  2. Junio C HamanoMay 27, 2005
  3. allow pathspec to end with a slashJunio C Hamano, May 27, 2005
  4. allow pathspec to end with a slash (take #2)Junio C Hamano, May 27, 2005
  5. Diff updates, fixing pathspec and rename/copy interaction.Junio C Hamano, May 27, 2005
  6. Linus TorvaldsMay 27, 2005
  7. Junio C HamanoMay 27, 2005
  8. 00/12 Diff updatesJunio C Hamano, May 27, 2005
  9. 01/12 Fix math thinko in similarity estimator.Junio C Hamano, May 27, 2005
  10. 02/12 Introduce diff_free_filepair() funcion.Junio C Hamano, May 27, 2005
  11. 03/12 Make pathspec only care about the detination tree.Junio C Hamano, May 27, 2005
  12. 04/12 Remove unused rank field from diff_core structure.Junio C Hamano, May 27, 2005
  13. 05/12 Do not expose internal scaling to diff-helper.Junio C Hamano, May 27, 2005
  14. 06/12 Remove final newline from the value of xfrm_msg variable.Junio C Hamano, May 27, 2005
  15. 07/12 Clean up diff_setup() to make it more extensible.Junio C Hamano, May 27, 2005
  16. 08/12 Remove a function not used anymore.Junio C Hamano, May 27, 2005
  17. 09/12 Add --pickaxe-all to diff-* brothers.Junio C Hamano, May 27, 2005
  18. 10/12 Fix the way diffcore-rename records unremoved source.Junio C Hamano, May 27, 2005
  19. 11/12 Move pathspec to the beginning of the diffcore chain.Junio C Hamano, May 27, 2005
  20. 12/12 Optimize diff-tree -[CM] --stdinJunio C Hamano, May 27, 2005
  21. Yoichi YuasaJun 4, 2005
  22. Junio C HamanoMay 27, 2005
  23. Do not show empty diff in diff-cache uncached.Junio C Hamano, May 28, 2005
  24. Diff: two fixes.Junio C Hamano, May 28, 2005
  25. diff-helper: fix R/C score parsing under -z flag.Junio C Hamano, May 29, 2005
  26. diff-cache: diff-patch (-p) format fixes.Junio C Hamano, May 29, 2005
  27. diff: code clean-up.Junio C Hamano, May 29, 2005
  28. Linus TorvaldsMay 29, 2005
  29. Junio C HamanoMay 29, 2005
  30. Junio C HamanoMay 29, 2005
  31. 0/3 Leftover bits after 12-seriesJunio C Hamano, May 29, 2005
  32. 1/3 diff-helper: Fix R/C score parsing under -z flag.Junio C Hamano, May 29, 2005
  33. 2/3 diff: consolidate various calls into diffcore.Junio C Hamano, May 29, 2005
  34. 3/3 diff: code clean-up and removal of rename hack.Junio C Hamano, May 29, 2005
  35. 0/4 Junio C Hamano, May 30, 2005
  36. 1/4 diff: further cleanup.Junio C Hamano, May 30, 2005
  37. 2/4 diff: fix the culling of unneeded delete record.Junio C Hamano, May 30, 2005
  38. 3/4 Add -B flag to diff-* brothers.Junio C Hamano, May 30, 2005
  39. 4/4 Add -O<orderfile> option to diff-* brothers.Junio C Hamano, May 30, 2005
  40. Linus TorvaldsMay 30, 2005
  41. Junio C HamanoMay 30, 2005
  42. apply.c: tolerate diff from a dirty but unchanged pathJunio C Hamano, Jun 11, 2005
  43. Linus TorvaldsJun 12, 2005
  44. Linus TorvaldsJun 12, 2005
  45. Junio C HamanoJun 12, 2005

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.