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

Re: [PATCH 0/3] Teach Git about the patience diff algorithm

From
Johannes Schindelin <johannes.schindelin@gmx.de>
Date
Jan 7, 2009, 22:00 UTC
Message-ID
<alpine.DEB.1.00.0901072213570.7496@intel-tinevez-2-302>
In-Reply-To
<7v63kqall2.fsf@gitster.siamese.dyndns.org>
Hi,
On Wed, 7 Jan 2009, Junio C Hamano wrote:
Show 31 quoted lines
> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> 
> > After compiling and installing, something like this should be fun to 
> > watch:
> >
> > 	$ git rev-list --all --parents | \
> > 	  grep " .* " | \
> > 	  while read commit parent1 parent2 otherparents
> > 	  do
> > 		test -z "$otherparents" || continue
> > 		git checkout $parent1 &&
> > 		git merge $parent2 &&
> > 		git diff > without-patience.txt &&
> > ...
> > 		if ! cmp without-patience.txt with-patience.txt
> > 		then
> > 			echo '==============================='
> > 			echo "differences found in merge $commit"
> > ...
> > 			cat with-patience.txt
> > 		fi ||
> > 		exit
> > 	  done | tee patience-merge.out
> 
> An even more interesting test would be possible by dropping "&&" from the
> two "git merge" invocations.
> 
>  - Your sample will exit at the first conflicting merge otherwise.
> 
>  - You may find cases where one resolves cleanly while the other leaves
>    conflicts.

Yeah, that's why I always put "like" into that phrase "something like this"... :-)

Actually, I had to read something and did not want my box to sit idle while I was doing that, so...

The most interesting thing to me was: of the 4072 merges I have in my local git.git clone, only 66 show a difference.

The next interesting thing: none -- I repeat, none! -- resulted in only one of both methods having conflicts. In all cases, if patience merge had conflicts, so had the classical merge, and vice versa. I would have expected patience merge to handle some conflicts more gracefully.

So let's go on to the next metric: what are the differences in the --cc diffs' line counts?

On average, patience merge produced 1.03225806451613 more lines of --cc diff, and the standard deviation between the line counts is 42.9823669772587.

So from the line counts' point of view, the difference is lost in the noise.

So let's look at a concrete example. I take 41a3e3aa9bdaede9ab7afed206428c1b071060d2, as it is one of the three merges with minimal --cc diff line counts (they all have 33 lines) and where patience merge makes a difference.

This is the --cc diff without patience merge:

-- snip -- diff --cc git-am.sh index a391254,5a7695e..0000000

--- a/git-am.sh
+++ b/git-am.sh
@@@ -327,11 -327,20 +327,28 @@@ d
  			echo "Patch is empty.  Was it split wrong?"
  			stop_here $this
  		}
++<<<<<<< HEAD:git-am.sh
 +		SUBJECT="$(sed -n '/^Subject/ s/Subject: //p' "$dotest/info")"
 +		case "$keep_subject" in -k)  SUBJECT="[PATCH] $SUBJECT" ;; esac
 +
 +		(printf '%s\n\n' "$SUBJECT"; cat "$dotest/msg") |
 +			git stripspace > "$dotest/msg-clean"
++=======
+ 		if test -f "$dotest/rebasing" &&
+ 			commit=$(sed -e 's/^From \([0-9a-f]*\) .*/\1/' \
+ 				-e q "$dotest/$msgnum") &&
+ 			test "$(git cat-file -t "$commit")" = commit
+ 		then
+ 			git cat-file commit "$commit" |
+ 			sed -e '1,/^$/d' >"$dotest/msg-clean"
+ 		else
+ 			SUBJECT="$(sed -n '/^Subject/ s/Subject: //p' "$dotest/info")"
+ 			case "$keep_subject" in -k)  SUBJECT="[PATCH] $SUBJECT" ;; esac
+ 
+ 			(echo "$SUBJECT" ; echo ; cat "$dotest/msg") |
+ 				git stripspace > "$dotest/msg-clean"
+ 		fi
++>>>>>>> 5e835cac8622373724235d299f1331ac4cf81ccf:git-am.sh
  		;;
  	esac
  
-- snap --

Compare this with the --cc diff _with_ patience merge:

-- snip --
diff --cc git-am.sh
index a391254,5a7695e..0000000
--- a/git-am.sh
+++ b/git-am.sh
@@@ -327,11 -327,20 +327,25 @@@ d
  			echo "Patch is empty.  Was it split wrong?"
  			stop_here $this
  		}
- 		SUBJECT="$(sed -n '/^Subject/ s/Subject: //p' "$dotest/info")"
- 		case "$keep_subject" in -k)  SUBJECT="[PATCH] $SUBJECT" ;; esac
- 
+ 		if test -f "$dotest/rebasing" &&
+ 			commit=$(sed -e 's/^From \([0-9a-f]*\) .*/\1/' \
+ 				-e q "$dotest/$msgnum") &&
+ 			test "$(git cat-file -t "$commit")" = commit
+ 		then
+ 			git cat-file commit "$commit" |
+ 			sed -e '1,/^$/d' >"$dotest/msg-clean"
+ 		else
+ 			SUBJECT="$(sed -n '/^Subject/ s/Subject: //p' "$dotest/info")"
+ 			case "$keep_subject" in -k)  SUBJECT="[PATCH] $SUBJECT" ;; esac
+ 
++<<<<<<< HEAD:git-am.sh
 +		(printf '%s\n\n' "$SUBJECT"; cat "$dotest/msg") |
 +			git stripspace > "$dotest/msg-clean"
++=======
+ 			(echo "$SUBJECT" ; echo ; cat "$dotest/msg") |
+ 				git stripspace > "$dotest/msg-clean"
+ 		fi
++>>>>>>> 5e835cac8622373724235d299f1331ac4cf81ccf:git-am.sh
  		;;
  	esac
  
-- snap --

So, the patience merge resulted in a much smaller _conflict_.

However, another such merge is 276328ffb87cefdc515bee5f09916aea6e0244ed.  
This is the --cc diff without patience merge:

-- snip --
diff --cc diff.c
index 4e4e439,f91f256..0000000
--- a/diff.c
+++ b/diff.c
@@@ -1498,19 -1464,13 +1498,28 @@@ static void builtin_diff(const char *na
  	char *a_one, *b_two;
  	const char *set = diff_get_color_opt(o, DIFF_METAINFO);
  	const char *reset = diff_get_color_opt(o, DIFF_RESET);
 +	const char *a_prefix, *b_prefix;
 +
 +	diff_set_mnemonic_prefix(o, "a/", "b/");
 +	if (DIFF_OPT_TST(o, REVERSE_DIFF)) {
 +		a_prefix = o->b_prefix;
 +		b_prefix = o->a_prefix;
 +	} else {
 +		a_prefix = o->a_prefix;
 +		b_prefix = o->b_prefix;
 +	}
  
++<<<<<<< HEAD:diff.c
 +	a_one = quote_two(a_prefix, name_a + (*name_a == '/'));
 +	b_two = quote_two(b_prefix, name_b + (*name_b == '/'));
++=======
+ 	/* Never use a non-valid filename anywhere if at all possible */
+ 	name_a = DIFF_FILE_VALID(one) ? name_a : name_b;
+ 	name_b = DIFF_FILE_VALID(two) ? name_b : name_a;
+ 
+ 	a_one = quote_two(o->a_prefix, name_a + (*name_a == '/'));
+ 	b_two = quote_two(o->b_prefix, name_b + (*name_b == '/'));
++>>>>>>> e261cf94848d31868c21fb11cade51c30dfcdbe7:diff.c
  	lbl[0] = DIFF_FILE_VALID(one) ? a_one : "/dev/null";
  	lbl[1] = DIFF_FILE_VALID(two) ? b_two : "/dev/null";
  	fprintf(o->file, "%sdiff --git %s %s%s\n", set, a_one, b_two, reset);
-- snap --

And this is _with_ patience merge:

-- snip --
diff --cc diff.c
index 4e4e439,f91f256..0000000
--- a/diff.c
+++ b/diff.c
@@@ -1498,19 -1464,13 +1498,28 @@@ static void builtin_diff(const char *na
  	char *a_one, *b_two;
  	const char *set = diff_get_color_opt(o, DIFF_METAINFO);
  	const char *reset = diff_get_color_opt(o, DIFF_RESET);
 +	const char *a_prefix, *b_prefix;
 +
++<<<<<<< HEAD:diff.c
 +	diff_set_mnemonic_prefix(o, "a/", "b/");
 +	if (DIFF_OPT_TST(o, REVERSE_DIFF)) {
 +		a_prefix = o->b_prefix;
 +		b_prefix = o->a_prefix;
 +	} else {
 +		a_prefix = o->a_prefix;
 +		b_prefix = o->b_prefix;
 +	}
  
 +	a_one = quote_two(a_prefix, name_a + (*name_a == '/'));
 +	b_two = quote_two(b_prefix, name_b + (*name_b == '/'));
++=======
+ 	/* Never use a non-valid filename anywhere if at all possible */
+ 	name_a = DIFF_FILE_VALID(one) ? name_a : name_b;
+ 	name_b = DIFF_FILE_VALID(two) ? name_b : name_a;
+ 
+ 	a_one = quote_two(o->a_prefix, name_a + (*name_a == '/'));
+ 	b_two = quote_two(o->b_prefix, name_b + (*name_b == '/'));
++>>>>>>> e261cf94848d31868c21fb11cade51c30dfcdbe7:diff.c
  	lbl[0] = DIFF_FILE_VALID(one) ? a_one : "/dev/null";
  	lbl[1] = DIFF_FILE_VALID(two) ? b_two : "/dev/null";
  	fprintf(o->file, "%sdiff --git %s %s%s\n", set, a_one, b_two, reset);
-- snap --

So again, we have no clear winner.

Therefore I counted the lines between conflict markers (actually, a perl 
script did).  Of these 66 merges, on average patience merge produced 
4.46774193548387 _fewer_ lines between conflict markers.

Take that with a grain of salt, though: the standard deviation of this 
difference is a hefty 121.163046639509 lines.

The worst case for patience diff was the merge 
4698ef555a1706fe322a68a02a21fb1087940ac3, where the --cc diff line counts 
are 1300 (without) vs 1301 (with patience merge), but the lines between 
conflict markers are 197 vs a ridiculous 826 lines!

But you should take that also with a grain of salt: this merge is a 
_subtree_ merge, and my test redid it as a _non-subtree_ merge.

So I restricted the analysis to the non-subtree merges, and now 
non-patience merge comes out 6.97297297297297 conflict lines fewer than 
patience merge, with a standard deviation of 58.941106657867 (with a total 
count of 37 merges).

Note that ~7 lines difference with a standard deviation of ~59 lines is 
pretty close to ~0 lines difference.

In the end, the additional expense of patience merge might just not be 
worth it.

Ciao,
Dscho
Previous: Junio C HamanoNext: Pierre Habouzit
Message 56 of 67 in “libxdiff and patience diff”
  1. Pierre HabouzitNov 4, 2008
  2. Davide LibenziNov 4, 2008
  3. Pierre HabouzitNov 4, 2008
  4. Johannes SchindelinNov 4, 2008
  5. Pierre HabouzitNov 4, 2008
  6. Johannes SchindelinNov 4, 2008
  7. Pierre HabouzitNov 4, 2008
  8. Johannes SchindelinNov 4, 2008
  9. Pierre HabouzitNov 4, 2008
  10. 0/3 Teach Git about the patience diff algorithmJohannes Schindelin, Jan 1, 2009
  11. 1/3 Implement the patience diff algorithmJohannes Schindelin, Jan 1, 2009
  12. 2/3 Introduce the diff option '--patience'Johannes Schindelin, Jan 1, 2009
  13. 3/3 bash completions: Add the --patience optionJohannes Schindelin, Jan 1, 2009
  14. Linus TorvaldsJan 1, 2009
  15. Linus TorvaldsJan 1, 2009
  16. Johannes SchindelinJan 2, 2009
  17. Linus TorvaldsJan 2, 2009
  18. Johannes SchindelinJan 2, 2009
  19. Jeff KingJan 2, 2009
  20. 1/3 Implement the patience diff algorithmJohannes Schindelin, Jan 2, 2009
  21. Johannes SchindelinJan 2, 2009
  22. Adeodato SimóJan 1, 2009
  23. Linus TorvaldsJan 2, 2009
  24. Clemens BuchacherJan 2, 2009
  25. Clemens BuchacherJan 2, 2009
  26. Linus TorvaldsJan 2, 2009
  27. Johannes SchindelinJan 2, 2009
  28. Linus TorvaldsJan 2, 2009
  29. Johannes SchindelinJan 2, 2009
  30. Jeff KingJan 2, 2009
  31. Jeff KingJan 2, 2009
  32. Jeff KingJan 2, 2009
  33. Linus TorvaldsJan 2, 2009
  34. Bazaar's patience diff as GIT_EXTERNAL_DIFFAdeodato Simó, Jan 3, 2009
  35. Johannes SchindelinJan 2, 2009
  36. Junio C HamanoJan 2, 2009
  37. Adeodato SimóJan 2, 2009
  38. Pierre HabouzitJan 6, 2009
  39. Pierre HabouzitJan 6, 2009
  40. Johannes SchindelinJan 6, 2009
  41. Pierre HabouzitJan 7, 2009
  42. Johannes SchindelinJan 7, 2009
  43. 1/3 Implement the patience diff algorithmJohannes Schindelin, Jan 7, 2009
  44. Davide LibenziJan 7, 2009
  45. Johannes SchindelinJan 7, 2009
  46. Davide LibenziJan 7, 2009
  47. Johannes SchindelinJan 7, 2009
  48. Linus TorvaldsJan 7, 2009
  49. Johannes SchindelinJan 7, 2009
  50. Davide LibenziJan 7, 2009
  51. Sam VilainJan 7, 2009
  52. Linus TorvaldsJan 7, 2009
  53. Sam VilainJan 8, 2009
  54. Johannes SchindelinJan 7, 2009
  55. Junio C HamanoJan 7, 2009
  56. Johannes SchindelinJan 7, 2009
  57. Pierre HabouzitJan 7, 2009
  58. Johannes SchindelinJan 7, 2009
  59. Adeodato SimóJan 8, 2009
  60. Adeodato SimóJan 8, 2009
  61. Junio C HamanoJan 9, 2009
  62. Johannes SchindelinJan 9, 2009
  63. Adeodato SimóJan 9, 2009
  64. Linus TorvaldsJan 9, 2009
  65. Linus TorvaldsJan 9, 2009
  66. Junio C HamanoJan 9, 2009
  67. Johannes SchindelinJan 10, 2009

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.