Patch id tests and diff performance optimization
Hi,
I finally came around to de-bashify my patch ID test script. Here we go.
[PATCH 1/3] add rebase patch id tests
[PATCH 2/3] do not search functions for patch ID [PATCH 3/3] use cache for function names in hunk headers
The first patch adds correctness and (optional) performance tests for the patch "hash binary sha1 into patch id"
http://thread.gmane.org/gmane.comp.version-control.git/153468/focus=155919 .
The test reveals a performance problem with the search for function names for the hunk headers. This is fixed for patch ID computation by the second patch and for diff in general by the third patch.
Clemens
---
diff.c | 2 +- t/t3419-rebase-patch-id.sh | 109 ++++++++++++++++++++++++++++++++++++++++++++ xdiff/xemit.c | 44 +++++++++++++----- 3 files changed, 142 insertions(+), 13 deletions(-)
PATCH 1/3 add rebase patch id tests
--- t/t3419-rebase-patch-id.sh | 109 ++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 109 insertions(+), 0 deletions(-) create mode 100755 t/t3419-rebase-patch-id.sh
t/t3419-rebase-patch-id.sh new file +109 -0
@@ -0,0 +1,109 @@ +#!/bin/bash + +test_description='git rebase - test patch id computation' + +. ./test-lib.sh + +test_set_prereq NOT_EXPENSIVE +test -n "$GIT_PATCHID_TIMING_TESTS" && test_set_prereq EXPENSIVE +test -x /usr/bin/time && test_set_prereq USR_BIN_TIME + +count() +{ + i=0 + while test $i -lt $1 + do + echo "$i" + i=$(($i+1)) + done +} + +scramble() +{ + i=0 + while read x + do + if test $i -ne 0 + then + echo "$x" + fi + i=$(((i+1) % 10)) + done < "$1" > "$1.new" + mv -f "$1.new" "$1" +} + +run() +{ + echo \$ "$@" + /usr/bin/time "$@" >/dev/null +} + +test_expect_success 'setup' ' + git commit --allow-empty -m initial + git tag root +' + +do_tests() +{ + pr=$1 + nlines=$2 + + test_expect_success $pr "setup: $nlines lines" " + rm -f .gitattributes && + git checkout -q -f master && + git reset --hard root && + count $nlines >file && + git add file && + git commit -q -m initial && + git branch -f other && + + scramble file && + git add file && + git commit -q -m 'change big file' && + + git checkout -q other && + : >newfile && + git add newfile && + git commit -q -m 'add small file' && + + git cherry-pick master >/dev/null 2>&1 + " + + test_debug " + run git diff master^\! + " + + test_expect_success $pr 'setup attributes' " + echo 'file binary' >.gitattributes + " + + test_debug " + run git format-patch --stdout master && + run git format-patch --stdout --ignore-if-in-upstream master + " + + test_expect_success $pr 'detect upstream patch' " + git checkout -q master && + scramble file && + git add file && + git commit -q -m 'change big file again' && + git checkout -q other^{} && + git rebase master && + test_must_fail test -n \"\$(git rev-list master...HEAD~)\" + " + + test_expect_success $pr 'do not drop patch' " + git branch -f squashed master && + git checkout -q -f squashed && + git reset -q --soft HEAD~2 && + git commit -q -m squashed && + git checkout -q other^{} && + test_must_fail git rebase squashed && + rm -rf .git/rebase-apply + " +} + +do_tests NOT_EXPENSIVE 500 +do_tests EXPENSIVE 50000 + +test_done
Signature · 1 line
1.7.1.571.gba4d01
PATCH 2/3 do not search functions for patch ID
In reply to Clemens BuchacherVisual aids, such as the function name in the hunk header, are not necessary for the purposes of computing a patch ID.
This is a performance optimization.
--- diff.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-)
diff.c +1 -1
@@ -3865,7 +3865,7 @@ static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1) xpp.flags =0 ; xecfg.ctxlen =3 ; - xecfg.flags =XDL_EMIT_FUNCNAMES ; + xecfg.flags =0 ;xdi_diff_outf (&mf1, &mf2, patch_id_consume, &data, &xpp, &xecfg); }
Signature · 1 line
1.7.1.571.gba4d01
PATCH 3/3 use cache for function names in hunk headers
In reply to Clemens BuchacherFor 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(n^2) in the number of hunks n.
Instead of searching the entire file for each hunk individually, cache and reuse the search result from previous hunks.
Diff performance for the 50000 line test in t3419 before and after this patch:
2.78user 0.01system 0:02.82elapsed 99%CPU 0.05user 0.01system 0:00.06elapsed 96%CPU
--- xdiff/xemit.c | 44 ++++++++++++++++++++++++++++++++------------ 1 files changed, 32 insertions(+), 12 deletions(-)
xdiff/xemit.c +32 -12
@@ -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 ;/*
Signature · 1 line
1.7.1.571.gba4d01
Re: [PATCH 3/3] use cache for function names in hunk headers
Heya,
Quoted 2 lines · Clemens Buchacher
2.78user 0.01system 0:02.82elapsed 99%CPU
0.05user 0.01system 0:00.06elapsed 96%CPU
Very nice. It would improve the commit message if you could explain what exactly it is this optimizes though, saving the reader from having to read through t3419 to find out.
Signature · 3 lines
Cheers, Sverre Rabbelier
Re: [PATCH 3/3] use cache for function names in hunk headers
Quoted 8 lines · Sverre Rabbelier
Quoted 2 lines · Clemens Buchacher
2.78user 0.01system 0:02.82elapsed 99%CPU
0.05user 0.01system 0:00.06elapsed 96%CPUVery nice. It would improve the commit message if you could explain what exactly it is this optimizes though, saving the reader from having to read through t3419 to find out.
Ok.
The test 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, previous to this optimization, the file was searched 5000 times.
Clemens
Re: [PATCH 3/3] use cache for function names in hunk headers
Heya,
Quoted 4 lines · Clemens Buchacher
The test 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, previous to this optimization, the file was searched 5000 times.
Ah, that makes sense, please add (something like) that to the commit message :).
Signature · 3 lines
Cheers, Sverre Rabbelier
PATCH v2 3/3 use cache for function names in hunk headers
In reply to Clemens BuchacherFor 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(n^2) 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
---
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(-)
xdiff/xemit.c +32 -12
@@ -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 ;/*
Signature · 1 line
1.7.1.571.gba4d01
Re: [PATCH 3/3 v2] use cache for function names in hunk headers
Am 23.09.2010 09:04, schrieb Clemens Buchacher:
Quoted 44 lines
For each hunk,
xdl_find_funcsearches 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 <[email protected]>---
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(-)xdiff/xemit.c +0
-0@@ -85,8 +85,15 @@ static long def_ff(const char *rec, long len, char *buf, long sz, void *priv)return -1 ;
xdiff/xemit.c static long def_ff(const char *rec, long len, char *buf, long sz, void *priv) · line 93
Quoted 10 lines
xdiff/xemit.c +6
-2} -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.
Quoted 7 lines
xdiff/xemit.c +3
-0+ +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
xdiff/xemit.c static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll, · line 109
Quoted 10 lines
xdiff/xemit.c +3
-3@@ -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.
Quoted 38 lines
xdiff/xemit.c +17
-5+ + 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,
xdiff/xemit.c int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, · line 181
Quoted 10 lines
xdiff/xemit.c +3
-2- 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(-)
xdiff/xemit.c +14 -24
@@ -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 )
Re: [PATCH 3/3 v2] use cache for function names in hunk headers
Quoted 2 lines · René Scharfe
Is xf needed? Does
xdl_emit_diff()handle multiple files in one go?
Right now it does not.
Quoted 1 line
If you inline
xdl_find_func()the struct isn't needed anymore.
[...]
Quoted 2 lines
How about something like this?
Yes, that's better. Thanks.
Quoted 7 lines
xdiff/xemit.c +0
-5-/* -* 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. -*/ It also removes an outdated comment.
Actually, in the default case, the comment is still correct and helpful IMO.
Quoted 1 line
The inlining part should probably split out in its own patch..
I am not sure what you mean here. Do you want to add the parameter funclineprev to the function and remove the function in the next page, or do you want to refactor the below into an inline function?
Clemens
Re: [PATCH 3/3 v2] use cache for function names in hunk headers
Am 26.09.2010 22:43, schrieb Clemens Buchacher:
Quoted 11 lines · René Scharfe
Quoted 7 lines
xdiff/xemit.c +0
-5-/* -* 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. -*/ It also removes an outdated comment.
Actually, in the default case, the comment is still correct and helpful IMO.
The first sentence was probably written before the match function became configurable. The second one could be moved to def_ff().
Quoted 5 lines
Quoted 1 line
The inlining part should probably split out in its own patch..
I am not sure what you mean here. Do you want to add the parameter funclineprev to the function and remove the function in the next page, or do you want to refactor the below into an inline function?
I'd suggest having a first patch for folding xdl_find_func() into xdl_emit_diff() without any functional change (manually inlining it) and a second one for adding funclineprev etc..
René
Re: [PATCH 3/3 v2] use cache for function names in hunk headers
In reply to René ScharfeQuoted 59 lines · René Scharfe
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(-)xdiff/xemit.c +7
-24@@ -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),
xdiff/xemit.c int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, · line 148
Quoted 10 lines
xdiff/xemit.c +7
-0+ 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 )
Looks much more straightforward ;-)
Re: [PATCH 3/3 v2] use cache for function names in hunk headers
In reply to René ScharfeQuoted 6 lines · René Scharfe
Am 23.09.2010 09:04, schrieb Clemens Buchacher:
Quoted 5 lines
For each hunk,
xdl_find_funcsearches 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.
Quoted 6 lines
...
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(-)
I had to wonder if this optimization closes a door for us to extend the function header patterns to allow inspecting multiple lines.
Suppose that a rule says that a header line is a first non-blank line that follows two or more blank lines. E.g.
... the end of a paragraph that is not followed by two blank lines. (blank line)
This is not a header, but is part of the previous paragraph group. ... body of the paragraph here ...
and this is the tail of the paragraph group.
(blank line)
(blank line)
This begins a new paragraph group.
And this is the second line of it.
Under such a rule, "This begins a new paragraph group." is a header line. If the first hunk begins at the second blank line before that header, we will scan down to the beginning of the file and will find a header that comes before that header line, and remember it in funclen/funcbuf[]. The next scan will stop after looking at one blank line before "This begins a new paragraph group.", instead of going down to the beginning, and would not to have a chance to notice that "This begins a new paragraph group." indeed has two blank lines before it. It would instead keep returning the header we found before this header.
I do not think this is such a big issue, though. In order to allow such a multi-line matching, the loop in xdl_find_func(), now inlined, needs to be restructured anyway, and whoever is doing such an enhancement hopefully will notice that s/he needs to look behind beyond (s1-1) at that point.
So an Ack from me.
Thanks.
Quoted 63 lines
xdiff/xemit.c +14
-24@@ -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 )