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

[Johannes Schindelin <Johannes.Schindelin@gmx.de>]

Hi,

On Fri, 2 Jan 2009, Linus Torvalds wrote:

> So I was hoping for something else than a single "in this case patience 
> diff works really well". I was hoping to see what it does in real life. 

Funnily, I think the test case you sent me is a pretty good example.  Look 
at this hunk (without patience diff):

@@ -4205,25 +4205,25 @@ out:
  */
 static int nfs4_xdr_dec_setattr(struct rpc_rqst *rqstp, __be32 *p, struct nfs_se
 {
-        struct xdr_stream xdr;
-        struct compound_hdr hdr;
-        int status;
-
-        xdr_init_decode(&xdr, &rqstp->rq_rcv_buf, p);
-        status = decode_compound_hdr(&xdr, &hdr);
-        if (status)
-                goto out;
-        status = decode_putfh(&xdr);
-        if (status)
-                goto out;
-        status = decode_setattr(&xdr, res);
-        if (status)
-                goto out;
+       struct xdr_stream xdr;
+       struct compound_hdr hdr;
+       int status;
+
+       xdr_init_decode(&xdr, &rqstp->rq_rcv_buf, p);

... and then it goes on with the whole reindented function.  Compare this 
to the same hunk _with_ patience diff:

@@ -4205,25 +4205,25 @@ out:
  */
 static int nfs4_xdr_dec_setattr(struct rpc_rqst *rqstp, __be32 *p, struct nfs_se
 {
-        struct xdr_stream xdr;
-        struct compound_hdr hdr;
-        int status;
+       struct xdr_stream xdr;
+       struct compound_hdr hdr;
+       int status;

-        xdr_init_decode(&xdr, &rqstp->rq_rcv_buf, p);
-        status = decode_compound_hdr(&xdr, &hdr);
-        if (status)
-                goto out;
-        status = decode_putfh(&xdr);
-        if (status)
-                goto out;
-        status = decode_setattr(&xdr, res);
-        if (status)
-                goto out;
+       xdr_init_decode(&xdr, &rqstp->rq_rcv_buf, p);
+       status = decode_compound_hdr(&xdr, &hdr);

... and again the rest is reindented code.

The difference?  The common empty line.  I actually find it more readable 
to have the separation between the declarations and the code also in the 
diff.

This is just a very feeble example, but you get the idea from there.

Oh, you might object that the empty line is not unique.  But actually it 
is, because the patience diff recurses into ever smaller line ranges until 
it finally comes to such a small range that the empty line _is_ unique.

And in my analysis of the complexity, I stupidly left out that recursion 
part.  So: patience diff is _substantially_ more expensive than Myers'.

> But when I tried it on the kernel archive, I get a core dump.

I also got this trying on the git.git repository, with commit 
be3cfa85([PATCH] Diff-tree-helper take two.)  Funnily, I almost got there 
trying the same before sending the first revision, but I got impatient and 
stopped early.  Tsk, tsk.

Now I tried with my complete clone of git.git together with all of my 
topic branches, and it runs through without segmentation fault.  Patch 
follows.

Ciao,
Dscho