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

> 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;
> +};

> +
> +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;

> +
> +	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;
>  
>  		/*