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

[Pierre Habouzit <madcoder@xxxxxxxxxx>]

On Tue, Jan 06, 2009 at 07:40:02PM +0000, Johannes Schindelin wrote:
> Hi,
> 
> On Tue, 6 Jan 2009, Pierre Habouzit wrote:
> 
> > On jeu, jan 01, 2009 at 04:38:09 +0000, Johannes Schindelin wrote:
> > > 
> > > Nothing fancy, really, just a straight-forward implementation of the
> > > heavily under-documented and under-analyzed paience diff algorithm.
> > 
> > Btw, what is the status of this series ? I see it neither in pu nor in 
> > next. And I would gladly see it included in git.
> 
> AFAICT people wanted to be reasonably sure that it is worth the effort.

Fair enough.

> Although I would like to see it in once it is fleshed out -- even if it 
> does not meet our usefulness standard -- because people said Git is 
> inferior for not providing a patience diff.  If we have --patience, we can 
> say "but we have it, it's just not useful, check for yourself".

Well I believe it's useful, but maybe the standard algorithm could be
tweaked the way Linus proposes to make the "long" lines weight louder or
so.

> Due to the lines being much longer than 80 characters, this example was 
> not useful to me.

I hope the other one was ;)

WRT the leaks, you want to squash the attached patch on the proper
patches of your series (maybe the xdl_free on map.entries could be put
in a hasmap_destroy or similar btw, but valgrind reports no more leaks
in xdiff now). As of timings, with the current implementation, patience
diff is around 30% slower than the default implementation, which is a
bit worse than what I would expect, probably due to the fact that you
had to work around the libxdiff interface I guess.

-- 
·O·  Pierre Habouzit
··O                                                madcoder@xxxxxxxxxx
OOO                                                http://www.madism.org

diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c
index d01cbdd..c2ffb03 100644
--- a/xdiff/xpatience.c
+++ b/xdiff/xpatience.c
@@ -203,8 +203,10 @@ static struct entry *find_longest_common_sequence(struct hashmap *map)
 	}
 
 	/* No common unique lines were found */
-	if (!longest)
+	if (!longest) {
+		xdl_free(sequence);
 		return NULL;
+	}
 
 	/* Iterate starting at the last element, adjusting the "next" members */
 	entry = sequence[longest - 1];
@@ -213,6 +215,7 @@ static struct entry *find_longest_common_sequence(struct hashmap *map)
 		entry->previous->next = entry;
 		entry = entry->previous;
 	}
+	xdl_free(sequence);
 	return entry;
 }
 
@@ -350,6 +353,7 @@ static int patience_diff(mmfile_t *file1, mmfile_t *file2,
 			env->xdf1.rchg[line1++ - 1] = 1;
 		while(count2--)
 			env->xdf2.rchg[line2++ - 1] = 1;
+		xdl_free(map.entries);
 		return 0;
 	}
 
@@ -361,6 +365,7 @@ static int patience_diff(mmfile_t *file1, mmfile_t *file2,
 		result = fall_back_to_classic_diff(&map,
 			line1, count1, line2, count2);
 
+	xdl_free(map.entries);
 	return result;
 }

Attachment: pgpuW5iGrxs1k.pgp
Description: PGP signature