Re: [PATCH 3/3 v2] use cache for function names in hunk headers

["René Scharfe" <rene.scharfe@lsrfire.ath.cx>]

Am 23.09.2010 09:04, schrieb Clemens Buchacher:
> For each hunk, xdl_find_func searches the preimage
> for a function name until the beginning of the
> file. If the file does not contain any function
> names, this search has complexity O(n2) in the
> number of hunks n.
> 
> The timing test in t3419 creates a file with 50000
> lines and a one-line change every 10 lines, i.e.,
> about 5000 hunks. Since none of the lines matches
> a function definition the file is searched 5000
> times.
> 
> Instead of searching the entire file for each hunk
> individually, cache and reuse the search result
> from previous hunks.
> 
> Diff performance for the test described above
> before and after this optimization:
> 
> 2.78user 0.01system 0:02.82elapsed 99%CPU
> 0.05user 0.01system 0:00.06elapsed 96%CPU
> 
> Signed-off-by: Clemens Buchacher <drizzd@aon.at>
> ---
> 
> I have added the test description as requested by
> Sverre. There are no code changes with respect to
> the previous version of the patch.
> 
> The test scenario might seem quite obscure.  But I
> have this case in some text files which are not
> edited directly by humans.
> 
> Clemens
> 
>  xdiff/xemit.c |   44 ++++++++++++++++++++++++++++++++------------
>  1 files changed, 32 insertions(+), 12 deletions(-)
> 
> diff --git a/xdiff/xemit.c b/xdiff/xemit.c
> index c4bedf0..349bd6b 100644
> --- a/xdiff/xemit.c
> +++ b/xdiff/xemit.c
> @@ -85,8 +85,15 @@ static long def_ff(const char *rec, long len, char *buf, long sz, void *priv)
>  	return -1;
>  }
>  
> -static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll,
> -		find_func_t ff, void *ff_priv) {
> +struct xdl_find_func_cache {
> +	char buf[80];
> +	long len;
> +	xdfile_t *xf;
> +	int line;
> +};

Is xf needed?  Does xdl_emit_diff() handle multiple files in one go?

If you inline xdl_find_func() the struct isn't needed anymore.

> +
> +static void xdl_find_func(xdfile_t *xf, long line, find_func_t ff,
> +		          void *ff_priv, struct xdl_find_func_cache *cache) {
>  
>  	/*
>  	 * Be quite stupid about this for now.  Find a line in the old file
> @@ -96,13 +103,28 @@ static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll,
>  
>  	const char *rec;
>  	long len;
> +	int i, l;
>  
> -	while (i-- > 0) {
> -		len = xdl_get_rec(xf, i, &rec);
> -		if ((*ll = ff(rec, len, buf, sz, ff_priv)) >= 0)
> +	if (line < cache->line)
> +		cache->xf = 0;

NULL is preferred.

> +
> +	i = line;
> +	l = -1;
> +	while (--i >= 0 && l < 0) {
> +		if (xf == cache->xf && i < cache->line) {
> +			cache->line = line;
>  			return;
> +		}
> +
> +		len = xdl_get_rec(xf, i, &rec);
> +		l = ff(rec, len, cache->buf, sizeof(cache->buf), ff_priv);
>  	}
> -	*ll = 0;
> +	if (l < 0)
> +		l = 0;
> +
> +	cache->xf = xf;
> +	cache->len = l;
> +	cache->line = line;
>  }
>  
>  
> @@ -125,8 +147,7 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
>  		  xdemitconf_t const *xecfg) {
>  	long s1, s2, e1, e2, lctx;
>  	xdchange_t *xch, *xche;
> -	char funcbuf[80];
> -	long funclen = 0;
> +	struct xdl_find_func_cache func_cache = { "", 0, NULL, -1 };
>  	find_func_t ff = xecfg->find_func ?  xecfg->find_func : def_ff;
>  
>  	if (xecfg->flags & XDL_EMIT_COMMON)
> @@ -150,12 +171,11 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
>  		 */
>  
>  		if (xecfg->flags & XDL_EMIT_FUNCNAMES) {
> -			xdl_find_func(&xe->xdf1, s1, funcbuf,
> -				      sizeof(funcbuf), &funclen,
> -				      ff, xecfg->find_func_priv);
> +			xdl_find_func(&xe->xdf1, s1, ff, xecfg->find_func_priv,
> +					&func_cache);
>  		}
>  		if (xdl_emit_hunk_hdr(s1 + 1, e1 - s1, s2 + 1, e2 - s2,
> -				      funcbuf, funclen, ecb) < 0)
> +				      func_cache.buf, func_cache.len, ecb) < 0)
>  			return -1;
>  
>  		/*

How about something like this?  It also removes an outdated comment.  The
inlining part should probably split out in its own patch..

 xdiff/xemit.c |   38 ++++++++++++++------------------------
 1 files changed, 14 insertions(+), 24 deletions(-)

diff --git a/xdiff/xemit.c b/xdiff/xemit.c
index c4bedf0..a663f21 100644
--- a/xdiff/xemit.c
+++ b/xdiff/xemit.c
@@ -85,27 +85,6 @@ static long def_ff(const char *rec, long len, char *buf, long sz, void *priv)
 	return -1;
 }
 
-static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll,
-		find_func_t ff, void *ff_priv) {
-
-	/*
-	 * Be quite stupid about this for now.  Find a line in the old file
-	 * before the start of the hunk (and context) which starts with a
-	 * plausible character.
-	 */
-
-	const char *rec;
-	long len;
-
-	while (i-- > 0) {
-		len = xdl_get_rec(xf, i, &rec);
-		if ((*ll = ff(rec, len, buf, sz, ff_priv)) >= 0)
-			return;
-	}
-	*ll = 0;
-}
-
-
 static int xdl_emit_common(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
                            xdemitconf_t const *xecfg) {
 	xdfile_t *xdf = &xe->xdf1;
@@ -127,6 +106,7 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
 	xdchange_t *xch, *xche;
 	char funcbuf[80];
 	long funclen = 0;
+	long funclineprev = -1;
 	find_func_t ff = xecfg->find_func ?  xecfg->find_func : def_ff;
 
 	if (xecfg->flags & XDL_EMIT_COMMON)
@@ -150,9 +130,19 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
 		 */
 
 		if (xecfg->flags & XDL_EMIT_FUNCNAMES) {
-			xdl_find_func(&xe->xdf1, s1, funcbuf,
-				      sizeof(funcbuf), &funclen,
-				      ff, xecfg->find_func_priv);
+			long l;
+			for (l = s1 - 1; l >= 0 && l > funclineprev; l--) {
+				const char *rec;
+				long reclen = xdl_get_rec(&xe->xdf1, l, &rec);
+				long newfunclen = ff(rec, reclen, funcbuf,
+						     sizeof(funcbuf),
+						     xecfg->find_func_priv);
+				if (newfunclen >= 0) {
+					funclen = newfunclen;
+					break;
+				}
+			}
+			funclineprev = s1 - 1;
 		}
 		if (xdl_emit_hunk_hdr(s1 + 1, e1 - s1, s2 + 1, e2 - s2,
 				      funcbuf, funclen, ecb) < 0)