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

[PATCH 19/19] combine-diff: speed it up, by using multiparent diff tree-walker directly

From
Kirill Smelkov <kirr@mns.spb.ru>
Date
Feb 24, 2014, 16:21 UTC
Message-ID
<7636e51f1efa3ca7e651e9a51ce5810aa9f5693b.1393257006.git.kirr@mns.spb.ru>
In-Reply-To
<cover.1393257006.git.kirr@mns.spb.ru>

As was recently shown in "combine-diff: optimize combine_diff_path sets intersection", combine-diff runs very slowly. In that commit we optimized paths sets intersection, but that accounted only for ~ 25% of the slowness, and as my tracing showed, for linux.git v3.10..v3.11, for merges a lot of time is spent computing diff(commit,commit^2) just to only then intersect that huge diff to almost small set of files from diff(commit,commit^1).

In previous commit, we described the problem in more details, and reworked the diff tree-walker to be general one - i.e. to work in multiple parent case too. Now is the time to take advantage of it for finding paths for combine diff.

The implementation is straightforward - if we know, we can get generated diff paths directly, and at present that means no diff filtering or rename/copy detection was requested(*), we can call multiparent tree-walker directly and get ready paths.

(*) because e.g. at present, all diffcore transformations work on
    diff_filepair queues, but in the future, that limitation can be
    lifted, if filters would operate directly on combine_diff_paths.

Timings for `git log --raw --no-abbrev --no-renames` without `-c` ("git log") and with `-c` ("git log -c") and with `-c --merges` ("git log -c --merges") before and after the patch are as follows:

                linux.git v3.10..v3.11
            log     log -c     log -c --merges
    before  1.9s    16.4s      15.2s
    after   1.9s     2.4s       1.1s
The result stayed the same.
Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
( re-posting without change )
 combine-diff.c | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 diff.c         |  1 +
 2 files changed, 84 insertions(+), 5 deletions(-)
diff --git a/combine-diff.c b/combine-diff.c
index 1732dfd..12764fb 100644
--- a/combine-diff.c
+++ b/combine-diff.c
@@ -1303,7 +1303,7 @@ static const char *path_path(void *obj)
 
 
 /* find set of paths that every parent touches */
-static struct combine_diff_path *find_paths(const unsigned char *sha1,
+static struct combine_diff_path *find_paths_generic(const unsigned char *sha1,
 	const struct sha1_array *parents, struct diff_options *opt)
 {
 	struct combine_diff_path *paths = NULL;
@@ -1316,6 +1316,7 @@ static struct combine_diff_path *find_paths(const unsigned char *sha1,
 	/* tell diff_tree to emit paths in sorted (=tree) order */
 	opt->orderfile = NULL;
 
+	/* D(A,P1...Pn) = D(A,P1) ^ ... ^ D(A,Pn)  (wrt paths) */
 	for (i = 0; i < num_parent; i++) {
 		/*
 		 * show stat against the first parent even when doing
@@ -1346,6 +1347,35 @@ static struct combine_diff_path *find_paths(const unsigned char *sha1,
 }
 
 
+/*
+ * find set of paths that everybody touches, assuming diff is run without
+ * rename/copy detection, etc, comparing all trees simultaneously (= faster).
+ */
+static struct combine_diff_path *find_paths_multitree(
+	const unsigned char *sha1, const struct sha1_array *parents,
+	struct diff_options *opt)
+{
+	int i, nparent = parents->nr;
+	const unsigned char **parents_sha1;
+	struct combine_diff_path paths_head;
+	struct strbuf base;
+
+	parents_sha1 = xmalloc(nparent * sizeof(parents_sha1[0]));
+	for (i = 0; i < nparent; i++)
+		parents_sha1[i] = parents->sha1[i];
+
+	/* fake list head, so worker can assume it is non-NULL */
+	paths_head.next = NULL;
+
+	strbuf_init(&base, PATH_MAX);
+	diff_tree_paths(&paths_head, sha1, parents_sha1, nparent, &base, opt);
+
+	strbuf_release(&base);
+	free(parents_sha1);
+	return paths_head.next;
+}
+
+
 void diff_tree_combined(const unsigned char *sha1,
 			const struct sha1_array *parents,
 			int dense,
@@ -1355,6 +1385,7 @@ void diff_tree_combined(const unsigned char *sha1,
 	struct diff_options diffopts;
 	struct combine_diff_path *p, *paths;
 	int i, num_paths, needsep, show_log_first, num_parent = parents->nr;
+	int need_generic_pathscan;
 
 	/* nothing to do, if no parents */
 	if (!num_parent)
@@ -1377,11 +1408,58 @@ void diff_tree_combined(const unsigned char *sha1,
 
 	/* find set of paths that everybody touches
 	 *
-	 * NOTE find_paths() also handles --stat, as it computes
-	 * diff(sha1,parent_i) for all i to do the job, specifically
-	 * for parent0.
+	 * NOTE
+	 *
+	 * Diffcore transformations are bound to diff_filespec and logic
+	 * comparing two entries - i.e. they do not apply directly to combine
+	 * diff.
+	 *
+	 * If some of such transformations is requested - we launch generic
+	 * path scanning, which works significantly slower compared to
+	 * simultaneous all-trees-in-one-go scan in find_paths_multitree().
+	 *
+	 * TODO some of the filters could be ported to work on
+	 * combine_diff_paths - i.e. all functionality that skips paths, so in
+	 * theory, we could end up having only multitree path scanning.
+	 *
+	 * NOTE please keep this semantically in sync with diffcore_std()
 	 */
-	paths = find_paths(sha1, parents, &diffopts);
+	need_generic_pathscan = opt->skip_stat_unmatch	||
+			DIFF_OPT_TST(opt, FOLLOW_RENAMES)	||
+			opt->break_opt != -1	||
+			opt->detect_rename	||
+			opt->pickaxe		||
+			opt->filter;
+
+
+	if (need_generic_pathscan) {
+		/*
+		 * NOTE generic case also handles --stat, as it computes
+		 * diff(sha1,parent_i) for all i to do the job, specifically
+		 * for parent0.
+		 */
+		paths = find_paths_generic(sha1, parents, &diffopts);
+	}
+	else {
+		int stat_opt;
+		paths = find_paths_multitree(sha1, parents, &diffopts);
+
+		/*
+		 * show stat against the first parent even
+		 * when doing combined diff.
+		 */
+		stat_opt = (opt->output_format &
+				(DIFF_FORMAT_NUMSTAT|DIFF_FORMAT_DIFFSTAT));
+		if (stat_opt) {
+			diffopts.output_format = stat_opt;
+
+			diff_tree_sha1(parents->sha1[0], sha1, "", &diffopts);
+			diffcore_std(&diffopts);
+			if (opt->orderfile)
+				diffcore_order(opt->orderfile);
+			diff_flush(&diffopts);
+		}
+	}
 
 	/* find out number of surviving paths */
 	for (num_paths = 0, p = paths; p; p = p->next)
diff --git a/diff.c b/diff.c
index cda4aa8..f2fff46 100644
--- a/diff.c
+++ b/diff.c
@@ -4764,6 +4764,7 @@ void diffcore_fix_diff_index(struct diff_options *options)
 
 void diffcore_std(struct diff_options *options)
 {
+	/* NOTE please keep the following in sync with diff_tree_combined() */
 	if (options->skip_stat_unmatch)
 		diffcore_skip_stat_unmatch(options);
 	if (!options->found_follow) {

-- 
1.9.rc1.181.g641f458
Previous: Kirill SmelkovNext: Duy Nguyen
Message 62 of 64 in “Multiparent diff tree-walker + combine-diff speedup”
  1. 00/19 Multiparent diff tree-walker + combine-diff speedupKirill Smelkov, Feb 24, 2014
  2. 01/19 combine-diff: move show_log_first logic/action out of paths scanningKirill Smelkov, Feb 24, 2014
  3. 02/19 combine-diff: move changed-paths scanning logic into its own functionKirill Smelkov, Feb 24, 2014
  4. 03/19 tree-diff: no need to manually verify that there is no mode change for a pathKirill Smelkov, Feb 24, 2014
  5. 04/19 tree-diff: no need to pass match to skip_uninteresting()Kirill Smelkov, Feb 24, 2014
  6. 05/19 tree-diff: show_tree() is not neededKirill Smelkov, Feb 24, 2014
  7. 06/19 tree-diff: consolidate code for emitting diffs and recursion in one placeKirill Smelkov, Feb 24, 2014
  8. 07/19 tree-diff: don't assume compare_tree_entry() returns -1,0,1Kirill Smelkov, Feb 24, 2014
  9. 08/19 tree-diff: move all action-taking code out of compare_tree_entry()Kirill Smelkov, Feb 24, 2014
  10. 09/19 tree-diff: rename compare_tree_entry -> tree_entry_pathcmpKirill Smelkov, Feb 24, 2014
  11. 10/19 tree-diff: show_path prototype is not needed anymoreKirill Smelkov, Feb 24, 2014
  12. 11/19 tree-diff: simplify tree_entry_pathcmpKirill Smelkov, Feb 24, 2014
  13. Junio C HamanoMar 24, 2014
  14. Kirill SmelkovMar 25, 2014
  15. 12/19 tree-diff: remove special-case diff-emitting code for empty-tree casesKirill Smelkov, Feb 24, 2014
  16. Junio C HamanoMar 24, 2014
  17. Kirill SmelkovMar 25, 2014
  18. Junio C HamanoMar 25, 2014
  19. Junio C HamanoMar 25, 2014
  20. Kirill SmelkovMar 26, 2014
  21. 13/19 tree-diff: diff_tree() should now be staticKirill Smelkov, Feb 24, 2014
  22. 14/19 tree-diff: rework diff_tree interface to be sha1 basedKirill Smelkov, Feb 24, 2014
  23. Junio C HamanoMar 24, 2014
  24. Kirill SmelkovMar 25, 2014
  25. Junio C HamanoMar 25, 2014
  26. Kirill SmelkovMar 26, 2014
  27. Junio C HamanoMar 26, 2014
  28. Kirill SmelkovMar 27, 2014
  29. Junio C HamanoMar 27, 2014
  30. Kirill SmelkovMar 27, 2014
  31. Johannes SixtMar 28, 2014
  32. Junio C HamanoMar 28, 2014
  33. Johannes SixtMar 28, 2014
  34. Junio C HamanoMar 28, 2014
  35. Johannes SixtMar 28, 2014
  36. Junio C HamanoMar 28, 2014
  37. 15/19 tree-diff: no need to call "full" diff_tree_sha1 from show_path()Kirill Smelkov, Feb 24, 2014
  38. Kirill SmelkovMar 27, 2014
  39. 16/19 tree-diff: reuse base str(buf) memory on sub-tree recursionKirill Smelkov, Feb 24, 2014
  40. Junio C HamanoMar 24, 2014
  41. Kirill SmelkovMar 25, 2014
  42. Kirill SmelkovMar 27, 2014
  43. 17/19 Portable alloca for GitKirill Smelkov, Feb 24, 2014
  44. Thomas SchwingeFeb 28, 2014
  45. Erik Faye-LundFeb 28, 2014
  46. Erik Faye-LundFeb 28, 2014
  47. Kirill SmelkovFeb 28, 2014
  48. Erik Faye-LundFeb 28, 2014
  49. Kirill SmelkovMar 5, 2014
  50. Junio C HamanoMar 24, 2014
  51. Kirill SmelkovMar 27, 2014
  52. Kirill SmelkovApr 9, 2014
  53. Erik Faye-LundApr 9, 2014
  54. Junio C HamanoApr 10, 2014
  55. 18/19 tree-diff: rework diff_tree() to generate diffs for multiparent cases as wellKirill Smelkov, Feb 24, 2014
  56. Kirill SmelkovMar 27, 2014
  57. Junio C HamanoApr 4, 2014
  58. Kirill SmelkovApr 6, 2014
  59. Junio C HamanoApr 7, 2014
  60. Junio C HamanoApr 7, 2014
  61. Kirill SmelkovApr 7, 2014
  62. 19/19 combine-diff: speed it up, by using multiparent diff tree-walker directlyKirill Smelkov, Feb 24, 2014
  63. Duy NguyenFeb 24, 2014
  64. Kirill SmelkovFeb 25, 2014

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.