Re: [PATCH 0/3] Teach Git about the patience diff algorithm
- From
Pierre Habouzit <madcoder@debian.org>
- Date
- Jan 7, 2009, 14:39 UTC
- Message-ID
- <20090107143926.GB831@artemis.corp>
- In-Reply-To
- <alpine.DEB.1.00.0901062037250.30769@pacific.mpi-cbg.de>
On Tue, Jan 06, 2009 at 07:40:02PM +0000, Johannes Schindelin wrote:
Show 13 quoted lines
> 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@debian.org
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;
}