[PATCH] combine-diff: reuse diff from the same blob.

When dealing with an insanely large Octopus, it is possible to
optimize by noticing that more than one parents have the same
blob and avoid running diff between a parent and the merge
result by reusing an earlier result.

Signed-off-by: Junio C Hamano <redacted>

---

 Junio C Hamano [off-list ref] writes:

 > One trivial thing I should be able to do to speed things up is
 > to reuse previous diff with other parents.  For example, that
 > commit does this to kernel/sys.c from its 12 parents.
 >
 > :100644 100644 d09cac2... 0929c69... M  kernel/sys.c
 > :100644 100644 eecf845... 0929c69... M  kernel/sys.c
 > :100644 100644 c3b1874... 0929c69... M  kernel/sys.c
 > :100644 100644 bce933e... 0929c69... M  kernel/sys.c
 > :100644 100644 eecf845... 0929c69... M  kernel/sys.c
 > :100644 100644 bce933e... 0929c69... M  kernel/sys.c
 > :100644 100644 bce933e... 0929c69... M  kernel/sys.c
 > :100644 100644 bce933e... 0929c69... M  kernel/sys.c
 > :100644 100644 eecf845... 0929c69... M  kernel/sys.c
 > :100644 100644 eecf845... 0929c69... M  kernel/sys.c
 > :100644 100644 eecf845... 0929c69... M  kernel/sys.c
 > :100644 100644 eecf845... 0929c69... M  kernel/sys.c
 >
 > Running "sort -u" on these would leave only 4 lines.
 >
 > I did not expect anybody to be _that_ sick (eh, pardon my
 > language) to do a 12-way octpus, so I did not consider this
 > optimization possibility, but I should be doing only 4 diffs to
 > format -c for this commit.  Currently I do 12.

 On my Duron 750 w/ 770MB RAM here is the results.

 Without this optimization:
 real	0m11.117s	user	0m9.230s	sys	0m1.860s
 With this optimization:
 real	0m7.339s	user	0m6.730s	sys	0m0.610s

 combine-diff.c |   39 +++++++++++++++++++++++++++++++++++++--
 1 files changed, 37 insertions(+), 2 deletions(-)

7bf761b73cfb74917454e179d95f0dab1cab8f0b

diff --git a/combine-diff.c b/combine-diff.c
index 243f967..0cc18fe 100644
--- a/combine-diff.c
+++ b/combine-diff.c

@@ -523,6 +523,30 @@ static void dump_sline(struct sline *sli
 	}
 }
 
+static void reuse_combine_diff(struct sline *sline, unsigned long cnt,
+			       int i, int j)
+{
+	/* We have already examined parent j and we know parent i
+	 * and parent j are the same, so reuse the combined result
+	 * of parent j for parent i.
+	 */
+	unsigned long lno, imask, jmask;
+	imask = (1UL<<i);
+	jmask = (1UL<<j);
+
+	for (lno = 0; lno < cnt; lno++) {
+		struct lline *ll = sline->lost_head;
+		while (ll) {
+			if (ll->parent_map & jmask)
+				ll->parent_map |= imask;
+			ll = ll->next;
+		}
+		if (!(sline->flag & jmask))
+			sline->flag &= ~imask;
+		sline++;
+	}
+}
+
 int show_combined_diff(struct combine_diff_path *elem, int num_parent,
 		       int dense, const char *header, int show_empty)
 {

@@ -596,8 +620,19 @@ int show_combined_diff(struct combine_di
 		sline[cnt-1].flag = (1UL<<num_parent) - 1;
 	}
 
-	for (i = 0; i < num_parent; i++)
-		combine_diff(elem->parent_sha1[i], ourtmp, sline, cnt, i);
+	for (i = 0; i < num_parent; i++) {
+		int j;
+		for (j = 0; j < i; j++) {
+			if (!memcmp(elem->parent_sha1[i],
+				    elem->parent_sha1[j], 20)) {
+				reuse_combine_diff(sline, cnt, i, j);
+				break;
+			}
+		}
+		if (i <= j)
+			combine_diff(elem->parent_sha1[i], ourtmp, sline,
+				     cnt, i);
+	}
 
 	show_hunks = make_hunks(sline, cnt, num_parent, dense);
 

-- 
1.1.6.g2672