From: Phillip Wood via GitGitGadget <hidden> Date: 2021-06-14 13:04:54
The current implementation of diff --color-moved-ws=allow-indentation-change
is considerably slower that the implementation of diff --color-moved which
is in turn slower than a regular diff. This patch series starts with a
couple of bug fixes and then reworks the implementation of diff
--color-moved and diff --color-moved-ws=allow-indentation-change to speed
them up on large diffs. The time to run git diff --color-moved
--no-color-moved-ws v2.28.0 v2.29.0 is reduced by 33% and the time to run
git diff --color-moved --color-moved-ws=allow-indentation-change v2.28.0
v2.29.0 is reduced by 88%. There is a small slowdown for commit sized diffs
with --color-moved - the time to run git log -p --color-moved
--no-color-moved-ws --no-merges -n1000 v2.29.0 is increased by 2% on recent
processors. On older processors these patches reduce the running time in all
cases that I've tested. In general the larger the diff the larger the speed
up. As an extreme example the time to run diff --color-moved
--color-moved-ws=allow-indentation-change v2.25.0 v2.30.0 goes down from 8
minutes to 6 seconds.
Phillip Wood (10):
diff --color-moved=zerba: fix alternate coloring
diff --color-moved: avoid false short line matches and bad zerba
coloring
diff: simplify allow-indentation-change delta calculation
diff --color-moved-ws=allow-indentation-change: simplify and optimize
diff --color-moved: call comparison function directly
diff --color-moved: unify moved block growth functions
diff --color-moved: shrink potential moved blocks as we go
diff --color-moved: stop clearing potential moved blocks
diff --color-moved-ws=allow-indentation-change: improve hash lookups
diff --color-moved: intern strings
diff.c | 375 ++++++++++++++-----------------------
t/t4015-diff-whitespace.sh | 137 ++++++++++++++
2 files changed, 276 insertions(+), 236 deletions(-)
base-commit: 211eca0895794362184da2be2a2d812d070719d3
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-981%2Fphillipwood%2Fwip%2Fdiff-color-moved-tweaks-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-981/phillipwood/wip/diff-color-moved-tweaks-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/981
--
gitgitgadget
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-06-14 13:04:55
From: Phillip Wood <redacted>
b0a2ba4776 ("diff --color-moved=zebra: be stricter with color
alternation", 2018-11-23) sought to avoid using the alternate colors
unless there are two adjacent moved blocks of the same
sign. Unfortunately it contains two bugs that prevented it from fixing
the problem properly. Firstly `last_symbol` is reset at the start of
each iteration of the loop losing the symbol of the last line and
secondly when deciding whether to use the alternate color it should be
checking if the current line is the same sign of the last line, not a
different sign. The combination of the two errors means that we still
use the alternate color when we should do but we also use it when we
shouldn't. This is most noticable when using
--color-moved-ws=allow-indentation-change with hunks like
-this line gets indented
+ this line gets indented
where the post image is colored with newMovedAlternate rather than
newMoved. While this does not matter much, the next commit will change
the coloring to be correct in this case, so lets fix the bug here to
make it clear why the output is changing and add a regression test.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 4 +--
t/t4015-diff-whitespace.sh | 72 ++++++++++++++++++++++++++++++++++++++
2 files changed, 74 insertions(+), 2 deletions(-)
@@ -1442,6 +1442,78 @@ test_expect_success 'detect permutations inside moved code -- dimmed-zebra' 'test_cmpexpectedactual'+test_expect_success'zebra alternate color is only used when necessary''+cat>old.txt<<-\EOF&&+line1AshouldbemarkedasoldMovednewMovedAlternate+line1BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line2AshouldbemarkedasoldMovednewMovedAlternate+line2BshouldbemarkedasoldMovednewMovedAlternate+line3AshouldbemarkedasoldMovedAlternatenewMoved+line3BshouldbemarkedasoldMovedAlternatenewMoved+unchanged+line4AshouldbemarkedasoldMovednewMovedAlternate+line4BshouldbemarkedasoldMovednewMovedAlternate+line5AshouldbemarkedasoldMovedAlternatenewMoved+line5BshouldbemarkedasoldMovedAlternatenewMoved+line6AshouldbemarkedasoldMovednewMoved+line6BshouldbemarkedasoldMovednewMoved+EOF+cat>new.txt<<-\EOF&&+line1AshouldbemarkedasoldMovednewMovedAlternate+line1BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line3AshouldbemarkedasoldMovedAlternatenewMoved+line3BshouldbemarkedasoldMovedAlternatenewMoved+line2AshouldbemarkedasoldMovednewMovedAlternate+line2BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line6AshouldbemarkedasoldMovednewMoved+line6BshouldbemarkedasoldMovednewMoved+line4AshouldbemarkedasoldMovednewMovedAlternate+line4BshouldbemarkedasoldMovednewMovedAlternate+line5AshouldbemarkedasoldMovedAlternatenewMoved+line5BshouldbemarkedasoldMovedAlternatenewMoved+EOF+test_expect_code1gitdiff--no-index--color--color-moved=zebra\+--color-moved-ws=allow-indentation-change\+old.txtnew.txt>output&&+grep-vindexoutput|test_decode_color>actual&&+cat>expected<<-\EOF&&+<BOLD>diff--gita/old.txtb/new.txt<RESET>+<BOLD>---a/old.txt<RESET>+<BOLD>+++b/new.txt<RESET>+<CYAN>@@-1,14+1,14@@<RESET>+<BOLD;MAGENTA>-line1AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line1BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line1AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line1BshouldbemarkedasoldMovednewMovedAlternate<RESET>+unchanged<RESET>+<BOLD;MAGENTA>-line2AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line2BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;BLUE>-line3AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;BLUE>-line3BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line3AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line3BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line2AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line2BshouldbemarkedasoldMovednewMovedAlternate<RESET>+unchanged<RESET>+<BOLD;MAGENTA>-line4AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line4BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;BLUE>-line5AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;BLUE>-line5BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;MAGENTA>-line6AshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;MAGENTA>-line6BshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line6AshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line6BshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line4AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line4BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line5AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line5BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+EOF+test_cmpexpectedactual+'+ test_expect_success'cmd option assumes configured colored-moved''test_configcolor.diff.oldMoved"magenta"&&test_configcolor.diff.newMoved"cyan"&&
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-06-14 13:05:05
From: Phillip Wood <redacted>
Rather than setting `match` to NULL and then looping over the list of
potential matched blocks for a second time to remove blocks with no
matches just filter out the blocks with no matches as we go.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 42 ++++++------------------------------------
1 file changed, 6 insertions(+), 36 deletions(-)
@@ -1017,37 +1017,9 @@ static void pmb_advance_or_null(struct diff_options *o,xdiff_compare_lines(cur->es->line,cur->es->len,l->line,l->len,flags);if(match)-pmb[i].match=cur;-else-moved_block_clear(&pmb[i]);+pmb[j++].match=cur;}-}--staticintshrink_potential_moved_blocks(structmoved_block*pmb,-intpmb_nr)-{-intlp,rp;--/* Shrink the set of potential block to the remaining running */-for(lp=0,rp=pmb_nr-1;lp<=rp;){-while(lp<pmb_nr&&pmb[lp].match)-lp++;-/* lp points at the first NULL now */--while(rp>-1&&!pmb[rp].match)-rp--;-/* rp points at the last non-NULL */--if(lp<pmb_nr&&rp>-1&&lp<rp){-pmb[lp]=pmb[rp];-memset(&pmb[rp],0,sizeof(pmb[rp]));-rp--;-lp++;-}-}--/* Remember the number of running sets */-returnrp+1;+*pmb_nr=j;}/*
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-06-14 13:05:07
From: Phillip Wood <redacted>
As libxdiff does not have a whitespace flag to ignore the indentation
the code for --color-moved-ws=allow-indentation-change uses
XDF_IGNORE_WHITESPACE and then filters out any hash lookups where
there are non-indentation changes. This is filtering is inefficient as
we have to perform another string comparison.
By using the offset data that we have already computed to skip the
indentation we can avoid using XDF_IGNORE_WHITESPACE and safely remove
the extra checks which improves the performance by 14% and paves the
way for the elimination of string comparisons in the next commit.
This change slightly increases the runtime of other --color-moved
modes. This could be avoided by using different comparison functions
for the different modes but after the changes in the next commit there
is no measurable benefit.
Before this change
Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
Time (mean ± σ): 1.116 s ± 0.005 s [User: 1.057 s, System: 0.056 s]
Range (min … max): 1.109 s … 1.123 s 10 runs
Benchmark #2: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
Time (mean ± σ): 1.216 s ± 0.005 s [User: 1.155 s, System: 0.059 s]
Range (min … max): 1.206 s … 1.223 s 10 runs
After this change
Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
Time (mean ± σ): 1.147 s ± 0.005 s [User: 1.085 s, System: 0.059 s]
Range (min … max): 1.140 s … 1.154 s 10 runs
Benchmark #2: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
Time (mean ± σ): 1.048 s ± 0.005 s [User: 987.4 ms, System: 58.8 ms]
Range (min … max): 1.043 s … 1.056 s 10 runs
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 66 +++++++++++++++++-----------------------------------------
1 file changed, 19 insertions(+), 47 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-06-14 13:05:17
From: Phillip Wood <redacted>
When marking moved lines it is possible for a block of potential
matched lines to extend past a change in sign when there is a sequence
of added lines whose text matches the text of a sequence of deleted
and added lines. Most of the time either `match` will be NULL or
`pmb_advance_or_null()` will fail when the loop encounters a change of
sign but there are corner cases where `match` is non-NULL and
`pmb_advance_or_null()` successfully advances the moved block despite
the change in sign.
One consequence of this is highlighting a short line as moved when it
should not be. For example
-moved line # Correctly highlighted as moved
+short line # Wrongly highlighted as moved
context
+moved line # Correctly highlighted as moved
+short line
context
-short line
The other consequence is coloring a moved addition following a moved
deletion in the wrong color. In the example below the first "+moved
line 3" should be highlighted as newMoved not newMovedAlternate.
-moved line 1 # Correctly highlighted as oldMoved
-moved line 2 # Correctly highlighted as oldMovedAlternate
+moved line 3 # Wrongly highlighted as newMovedAlternate
context # Everything else is highlighted correctly
+moved line 2
+moved line 3
context
+moved line 1
-moved line 3
These false matches are more likely when using --color-moved-ws with
the exception of --color-moved-ws=allow-indentation-change which ties
the sign of the current whitespace delta to the sign of the line to
avoid this problem. The fix is to check that the sign of the new line
being matched is the same as the sign of the line that started the
block of potential matches.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 17 ++++++----
t/t4015-diff-whitespace.sh | 65 ++++++++++++++++++++++++++++++++++++++
2 files changed, 76 insertions(+), 6 deletions(-)
@@ -1514,6 +1514,71 @@ test_expect_success 'zebra alternate color is only used when necessary' 'test_cmpexpectedactual'+test_expect_success'short lines of opposite sign do not get marked as moved''+cat>old.txt<<-\EOF&&+thislineshouldbemarkedasmoved+unchanged+unchanged+unchanged+unchanged+tooshort+thislineshouldbemarkedasoldMovednewMoved+thislineshouldbemarkedasoldMovedAlternatenewMoved+unchanged1+unchanged2+unchanged3+unchanged4+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+EOF+cat>new.txt<<-\EOF&&+tooshort+unchanged+unchanged+thislineshouldbemarkedasmoved+tooshort+unchanged+unchanged+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+unchanged1+unchanged2+thislineshouldbemarkedasoldMovedAlternatenewMoved+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+unchanged3+thislineshouldbemarkedasoldMovednewMoved+unchanged4+EOF+test_expect_code1gitdiff--no-index--color--color-moved=zebra\+old.txtnew.txt>output&&catoutput&&+grep-vindexoutput|test_decode_color>actual&&+cat>expect<<-\EOF&&+<BOLD>diff--gita/old.txtb/new.txt<RESET>+<BOLD>---a/old.txt<RESET>+<BOLD>+++b/new.txt<RESET>+<CYAN>@@-1,13+1,15@@<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasmoved<RESET>+<GREEN>+<RESET><GREEN>tooshort<RESET>+unchanged<RESET>+unchanged<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasmoved<RESET>+<GREEN>+<RESET><GREEN>tooshort<RESET>+unchanged<RESET>+unchanged<RESET>+<RED>-tooshort<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;BLUE>-thislineshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+unchanged1<RESET>+unchanged2<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+unchanged3<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovednewMoved<RESET>+unchanged4<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+EOF+test_cmpexpectactual+'+ test_expect_success'cmd option assumes configured colored-moved''test_configcolor.diff.oldMoved"magenta"&&test_configcolor.diff.newMoved"cyan"&&
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-06-14 13:05:54
From: Phillip Wood <redacted>
Now that we reliably end a block when the sign changes we don't need
the whitespace delta calculation to rely on the sign.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 13 ++-----------
1 file changed, 2 insertions(+), 11 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-06-14 13:05:55
From: Phillip Wood <redacted>
If we already have a block of potentially moved lines then as we move
down the diff we need to check if the next line of each potentially
moved line matches the current line of the diff. The implementation of
--color-moved-ws=allow-indentation-change was needlessly performing
this check on all the lines in the diff that matched the current line
rather than just the current line. To exacerbate the problem finding
all the other lines in the diff that match the current line involves a
fuzzy lookup so we were wasting even more time performing a second
comparison to filter out the non-matching lines. Fixing this reduces
time to run
git diff --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
by 88% and simplifies the code.
Before this change
Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
Time (mean ± σ): 9.978 s ± 0.042 s [User: 9.905 s, System: 0.057 s]
Range (min … max): 9.917 s … 10.037 s 10 runs
After this change
Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
Time (mean ± σ): 1.220 s ± 0.004 s [User: 1.160 s, System: 0.058 s]
Range (min … max): 1.214 s … 1.226 s 10 runs
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 65 ++++++++++++++++------------------------------------------
1 file changed, 18 insertions(+), 47 deletions(-)
@@ -881,35 +881,20 @@ static int compute_ws_delta(const struct emitted_diff_symbol *a,staticintcmp_in_block_with_wsd(conststructdiff_options*o,conststructmoved_entry*cur,-conststructmoved_entry*match,-structmoved_block*pmb,-intn)+conststructemitted_diff_symbol*l,+structmoved_block*pmb){-structemitted_diff_symbol*l=&o->emitted_symbols->buf[n];-intal=cur->es->len,bl=match->es->len,cl=l->len;+intal=cur->es->len,bl=l->len;constchar*a=cur->es->line,-*b=match->es->line,-*c=l->line;+*b=l->line;inta_off=cur->es->indent_off,a_width=cur->es->indent_width,-c_off=l->indent_off,-c_width=l->indent_width;+b_off=l->indent_off,+b_width=l->indent_width;intdelta;-/*-*Weneedtocheckif'cur'isequalto'match'.Asthose-*arefromthesame(+/-)side,wedonotneedtoadjustfor-*indentchanges.Howeverthesewerefoundusingfuzzy-*matchingsowedohavetocheckiftheyareequal.Herewe-*justcheckthelengths.Wedelaycallingmemcmp()tocheck-*thecontentsuntillaterasifthelengthcomparisonfora-*andcfailswecanavoidthecallalltogether.-*/-if(al!=bl)-return1;-/* If 'l' and 'cur' are both blank then they match. */-if(a_width==INDENT_BLANKLINE&&c_width==INDENT_BLANKLINE)+if(a_width==INDENT_BLANKLINE&&b_width==INDENT_BLANKLINE)return0;/*
@@ -918,7 +903,7 @@ static int cmp_in_block_with_wsd(const struct diff_options *o,*matchthoseofthecurrentblockandthatthetextof'l'and'cur'*aftertheindentationmatch.*/-delta=c_width-a_width;+delta=b_width-a_width;/**Ifthepreviouslinesofthisblockwereallblankthensetits
@@ -927,9 +912,8 @@ static int cmp_in_block_with_wsd(const struct diff_options *o,if(pmb->wsd==INDENT_BLANKLINE)pmb->wsd=delta;-return!(delta==pmb->wsd&&al-a_off==cl-c_off&&-!memcmp(a,b,al)&&!-memcmp(a+a_off,c+c_off,al-a_off));+return!(delta==pmb->wsd&&al-a_off==bl-b_off&&+!memcmp(a+a_off,b+b_off,al-a_off));}staticintmoved_entry_cmp(constvoid*hashmap_cmp_fn_data,
@@ -1030,36 +1014,23 @@ static void pmb_advance_or_null(struct diff_options *o,}staticvoidpmb_advance_or_null_multi_match(structdiff_options*o,-structmoved_entry*match,-structhashmap*hm,+structemitted_diff_symbol*l,structmoved_block*pmb,-intpmb_nr,intn)+intpmb_nr){inti;-char*got_match=xcalloc(1,pmb_nr);--hashmap_for_each_entry_from(hm,match,ent){-for(i=0;i<pmb_nr;i++){-structmoved_entry*prev=pmb[i].match;-structmoved_entry*cur=(prev&&prev->next_line)?-prev->next_line:NULL;-if(!cur)-continue;-if(!cmp_in_block_with_wsd(o,cur,match,&pmb[i],n))-got_match[i]|=1;-}-}for(i=0;i<pmb_nr;i++){-if(got_match[i]){+structmoved_entry*prev=pmb[i].match;+structmoved_entry*cur=(prev&&prev->next_line)?+prev->next_line:NULL;+if(cur&&!cmp_in_block_with_wsd(o,cur,l,&pmb[i])){/* Advance to the next line */-pmb[i].match=pmb[i].match->next_line;+pmb[i].match=cur;}else{moved_block_clear(&pmb[i]);}}--free(got_match);}staticintshrink_potential_moved_blocks(structmoved_block*pmb,
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-06-14 13:05:55
From: Phillip Wood <redacted>
Calling xdiff_compare_lines() directly rather than using a function
pointer from the hash map reduces the time very slightly but more
importantly it will allow us to easily combine pmb_advance_or_null()
and pmb_advance_or_null_multi_match() in the next commit.
Before this change
Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
Time (mean ± σ): 1.136 s ± 0.004 s [User: 1.079 s, System: 0.053 s]
Range (min … max): 1.130 s … 1.141 s 10 runs
After this change
Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
Time (mean ± σ): 1.118 s ± 0.003 s [User: 1.062 s, System: 0.053 s]
Range (min … max): 1.114 s … 1.121 s 10 runs
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 11 +++++++----
1 file changed, 7 insertions(+), 4 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-06-14 13:06:00
From: Phillip Wood <redacted>
After the last two commits pmb_advance_or_null() and
pmb_advance_or_null_multi_match() differ only in the comparison they
perform. Lets simplify the code by combining them into a single
function.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 41 ++++++++++++-----------------------------
1 file changed, 12 insertions(+), 29 deletions(-)
@@ -1003,36 +1003,23 @@ static void pmb_advance_or_null(struct diff_options *o,unsignedflags=o->color_moved_ws_handling&XDF_WHITESPACE_FLAGS;for(i=0;i<pmb_nr;i++){+intmatch;structmoved_entry*prev=pmb[i].match;structmoved_entry*cur=(prev&&prev->next_line)?prev->next_line:NULL;-if(cur&&xdiff_compare_lines(cur->es->line,cur->es->len,-l->line,l->len,-flags)){-pmb[i].match=cur;-}else{-pmb[i].match=NULL;-}-}-}-staticvoidpmb_advance_or_null_multi_match(structdiff_options*o,-structemitted_diff_symbol*l,-structmoved_block*pmb,-intpmb_nr)-{-inti;--for(i=0;i<pmb_nr;i++){-structmoved_entry*prev=pmb[i].match;-structmoved_entry*cur=(prev&&prev->next_line)?-prev->next_line:NULL;-if(cur&&!cmp_in_block_with_wsd(o,cur,l,&pmb[i])){-/* Advance to the next line */+if(o->color_moved_ws_handling&+COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE)+match=cur&&+!cmp_in_block_with_wsd(o,cur,l,&pmb[i]);+else+match=cur&&+xdiff_compare_lines(cur->es->line,cur->es->len,+l->line,l->len,flags);+if(match)pmb[i].match=cur;-}else{+elsemoved_block_clear(&pmb[i]);-}}}
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-06-14 13:06:01
From: Phillip Wood <redacted>
Taking inspiration from xdl_classify_record() assign an id to each
addition and deletion such that lines that match for the current
--color-moved-ws mode share the same unique id. This reduces the
number of hash lookups a little (calculating the ids still involves
one hash lookup per line) but the main benefit is that when growing
blocks of potentially moved lines we can replace string comparisons
which involve chasing a pointer with a simple integer comparison. On
a large diff this commit reduces the time to run 'diff --color-moved'
by 33% and 'diff --color-moved-ws=allow-indentation-change' by 20%.
Compared to master the time to run 'git log --patch --color-moved' is
increased by 2% and 'git log --patch
--color-moved-ws=allow-indentation-change' in reduced by 14%. These
timings were performed on an i5-7200U, on an i5-3470 both commands are
faster than master. The small speed decrease on commit sized diffs is
unfortunate but I think it is small enough to be worth it for the
gains on larger diffs.
Large diff before this change:
Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
Time (mean ± σ): 1.147 s ± 0.005 s [User: 1.085 s, System: 0.059 s]
Range (min … max): 1.140 s … 1.154 s 10 runs
Benchmark #2: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
Time (mean ± σ): 1.048 s ± 0.005 s [User: 987.4 ms, System: 58.8 ms]
Range (min … max): 1.043 s … 1.056 s 10 runs
Large diff after this change
Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
Time (mean ± σ): 762.7 ms ± 2.8 ms [User: 707.5 ms, System: 53.7 ms]
Range (min … max): 758.0 ms … 767.0 ms 10 runs
Benchmark #2: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
Time (mean ± σ): 831.7 ms ± 1.7 ms [User: 776.5 ms, System: 53.3 ms]
Range (min … max): 829.2 ms … 835.1 ms 10 runs
Small diffs on master
Benchmark #1: bin-wrappers/git log -p --diff-algorithm=myers --color-moved --no-color-moved-ws --no-merges -n1000 v2.29.0
Time (mean ± σ): 1.567 s ± 0.001 s [User: 1.443 s, System: 0.121 s]
Range (min … max): 1.566 s … 1.571 s 10 runs
Benchmark #2: bin-wrappers/git log -p --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change -n1000 --no-merges v2.29.0
Time (mean ± σ): 1.865 s ± 0.008 s [User: 1.748 s, System: 0.112 s]
Range (min … max): 1.857 s … 1.881 s 10 runs
Small diffs after this change
Benchmark #1: bin-wrappers/git log -p --diff-algorithm=myers --color-moved --no-color-moved-ws --no-merges -n1000 v2.29.0
Time (mean ± σ): 1.597 s ± 0.003 s [User: 1.413 s, System: 0.179 s]
Range (min … max): 1.591 s … 1.601 s 10 runs
Benchmark #2: bin-wrappers/git log -p --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change -n1000 --no-merges v2.29.0
Time (mean ± σ): 1.606 s ± 0.006 s [User: 1.420 s, System: 0.181 s]
Range (min … max): 1.601 s … 1.622 s 10 runs
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 173 ++++++++++++++++++++++++++++++++-------------------------
1 file changed, 96 insertions(+), 77 deletions(-)
@@ -772,6 +773,7 @@ struct emitted_diff_symbol {intflags;intindent_off;/* Offset to first non-whitespace character */intindent_width;/* The visual width of the indentation */+unsignedid;enumdiff_symbols;};#define EMITTED_DIFF_SYMBOL_INIT {NULL}
@@ -866,24 +868,24 @@ static int cmp_in_block_with_wsd(const struct diff_options *o,conststructemitted_diff_symbol*l,structmoved_block*pmb){-intal=cur->es->len,bl=l->len;-constchar*a=cur->es->line,-*b=l->line;-inta_off=cur->es->indent_off,-a_width=cur->es->indent_width,-b_off=l->indent_off,-b_width=l->indent_width;+inta_width=cur->es->indent_width,b_width=l->indent_width;intdelta;-/* If 'l' and 'cur' are both blank then they match. */-if(a_width==INDENT_BLANKLINE&&b_width==INDENT_BLANKLINE)+/* The text of each line must match */+if(cur->es->id!=l->id)+return1;++/*+*If'l'and'cur'arebothblankthenwedon'tneedtocheckthe+*indent.Weonlyneedtocheckcurasweknowthestringsmatch.+**/+if(a_width==INDENT_BLANKLINE)return0;/**Theindentchangesoftheblockareknownandstoredinpmb->wsd;*howeverweneedtocheckiftheindentchangesofthecurrentline-*matchthoseofthecurrentblockandthatthetextof'l'and'cur'-*aftertheindentationmatch.+*matchthoseofthecurrentblock.*/delta=b_width-a_width;
@@ -894,22 +896,26 @@ static int cmp_in_block_with_wsd(const struct diff_options *o,if(pmb->wsd==INDENT_BLANKLINE)pmb->wsd=delta;-return!(delta==pmb->wsd&&al-a_off==bl-b_off&&-!memcmp(a+a_off,b+b_off,al-a_off));+returndelta!=pmb->wsd;}-staticintmoved_entry_cmp(constvoid*hashmap_cmp_fn_data,-conststructhashmap_entry*eptr,-conststructhashmap_entry*entry_or_key,-constvoid*keydata)+structinterned_diff_symbol{+structhashmap_entryent;+structemitted_diff_symbol*es;+};++staticintinterned_diff_symbol_cmp(constvoid*hashmap_cmp_fn_data,+conststructhashmap_entry*eptr,+conststructhashmap_entry*entry_or_key,+constvoid*keydata){conststructdiff_options*diffopt=hashmap_cmp_fn_data;conststructemitted_diff_symbol*a,*b;unsignedflags=diffopt->color_moved_ws_handling&XDF_WHITESPACE_FLAGS;-a=container_of(eptr,conststructmoved_entry,ent)->es;-b=container_of(entry_or_key,conststructmoved_entry,ent)->es;+a=container_of(eptr,conststructinterned_diff_symbol,ent)->es;+b=container_of(entry_or_key,conststructinterned_diff_symbol,ent)->es;return!xdiff_compare_lines(a->line+a->indent_off,a->len-a->indent_off,
@@ -917,55 +923,81 @@ static int moved_entry_cmp(const void *hashmap_cmp_fn_data,b->len-b->indent_off,flags);}-staticstructmoved_entry*prepare_entry(structdiff_options*o,-intline_no)+staticvoidprepare_entry(structdiff_options*o,structemitted_diff_symbol*l,+structinterned_diff_symbol*s){-structmoved_entry*ret=xmalloc(sizeof(*ret));-structemitted_diff_symbol*l=&o->emitted_symbols->buf[line_no];unsignedflags=o->color_moved_ws_handling&XDF_WHITESPACE_FLAGS;unsignedinthash=xdiff_hash_string(l->line+l->indent_off,l->len-l->indent_off,flags);-hashmap_entry_init(&ret->ent,hash);-ret->es=l;-ret->next_line=NULL;--returnret;+hashmap_entry_init(&s->ent,hash);+s->es=l;}-staticvoidadd_lines_to_move_detection(structdiff_options*o,-structhashmap*add_lines,-structhashmap*del_lines)+structmoved_entry_list{+structmoved_entry*add,*del;+};++staticstructmoved_entry_list*add_lines_to_move_detection(structdiff_options*o,+structmem_pool*entry_mem_pool){structmoved_entry*prev_line=NULL;-+structmem_poolinterned_pool;+structhashmapinterned_map;+structmoved_entry_list*entry_list=NULL;+size_tentry_list_alloc=0;+unsignedid=0;intn;++hashmap_init(&interned_map,interned_diff_symbol_cmp,o,8096);+mem_pool_init(&interned_pool,1024*1024);+for(n=0;n<o->emitted_symbols->nr;n++){-structhashmap*hm;-structmoved_entry*key;+structinterned_diff_symbolkey;+structemitted_diff_symbol*l=&o->emitted_symbols->buf[n];+structinterned_diff_symbol*s;+structmoved_entry*entry;-switch(o->emitted_symbols->buf[n].s){-caseDIFF_SYMBOL_PLUS:-hm=add_lines;-break;-caseDIFF_SYMBOL_MINUS:-hm=del_lines;-break;-default:+if(l->s!=DIFF_SYMBOL_PLUS&&l->s!=DIFF_SYMBOL_MINUS){prev_line=NULL;continue;}if(o->color_moved_ws_handling&COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE)-fill_es_indent_data(&o->emitted_symbols->buf[n]);-key=prepare_entry(o,n);-if(prev_line&&prev_line->es->s==o->emitted_symbols->buf[n].s)-prev_line->next_line=key;+fill_es_indent_data(l);-hashmap_add(hm,&key->ent);-prev_line=key;+prepare_entry(o,l,&key);+s=hashmap_get_entry(&interned_map,&key,ent,&key.ent);+if(s){+l->id=s->es->id;+}else{+l->id=id;+ALLOC_GROW_BY(entry_list,id,1,entry_list_alloc);+hashmap_add(&interned_map,+memcpy(mem_pool_alloc(&interned_pool,+sizeof(key)),+&key,sizeof(key)));+}+entry=mem_pool_alloc(entry_mem_pool,sizeof(*entry));+entry->es=l;+entry->next_line=NULL;+if(prev_line&&prev_line->es->s==l->s)+prev_line->next_line=entry;+prev_line=entry;+if(l->s==DIFF_SYMBOL_PLUS){+entry->next_match=entry_list[l->id].add;+entry_list[l->id].add=entry;+}else{+entry->next_match=entry_list[l->id].del;+entry_list[l->id].del=entry;+}}++hashmap_clear(&interned_map);+mem_pool_discard(&interned_pool,0);++returnentry_list;}staticvoidpmb_advance_or_null(structdiff_options*o,
@@ -1034,8 +1064,7 @@ static int adjust_last_block(struct diff_options *o, int n, int block_length)/* Find blocks of moved code, delegate actual coloring decision to helper */staticvoidmark_color_as_moved(structdiff_options*o,-structhashmap*add_lines,-structhashmap*del_lines)+structmoved_entry_list*entry_list){structmoved_block*pmb=NULL;/* potentially moved blocks */intpmb_nr=0,pmb_alloc=0;
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-06-14 13:06:17
From: Phillip Wood <redacted>
moved_block_clear() was introduced in 74d156f4a1 ("diff
--color-moved-ws: fix double free crash", 2018-10-04) to free the
memory that was allocated when initializing a potential moved
block. However since 21536d077f ("diff --color-moved-ws: modify
allow-indentation-change", 2018-11-23) initializing a potential moved
block no longer allocates any memory. Up until the last commit we were
relying on moved_block_clear() to set the `match` pointer to NULL when
a block stopped matching, but since that commit we do not clear a
moved block that does not match so it does not make sense to clear
them elsewhere.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 11 -----------
1 file changed, 11 deletions(-)
On Mon, Jun 14 2021, Phillip Wood via GitGitGadget wrote:
The current implementation of diff --color-moved-ws=allow-indentation-change
is considerably slower that the implementation of diff --color-moved which
is in turn slower than a regular diff. This patch series starts with a
couple of bug fixes and then reworks the implementation of diff
--color-moved and diff --color-moved-ws=allow-indentation-change to speed
them up on large diffs. The time to run git diff --color-moved
--no-color-moved-ws v2.28.0 v2.29.0 is reduced by 33% and the time to run
git diff --color-moved --color-moved-ws=allow-indentation-change v2.28.0
v2.29.0 is reduced by 88%. There is a small slowdown for commit sized diffs
with --color-moved - the time to run git log -p --color-moved
--no-color-moved-ws --no-merges -n1000 v2.29.0 is increased by 2% on recent
processors. On older processors these patches reduce the running time in all
cases that I've tested. In general the larger the diff the larger the speed
up. As an extreme example the time to run diff --color-moved
--color-moved-ws=allow-indentation-change v2.25.0 v2.30.0 goes down from 8
minutes to 6 seconds.
Phillip Wood (10):
diff --color-moved=zerba: fix alternate coloring
diff --color-moved: avoid false short line matches and bad zerba
coloring
diff: simplify allow-indentation-change delta calculation
diff --color-moved-ws=allow-indentation-change: simplify and optimize
diff --color-moved: call comparison function directly
diff --color-moved: unify moved block growth functions
diff --color-moved: shrink potential moved blocks as we go
diff --color-moved: stop clearing potential moved blocks
diff --color-moved-ws=allow-indentation-change: improve hash lookups
diff --color-moved: intern strings
Nice to see these land after the earlier on-list reference to them.
I skimmed these mostly, and am not familiar with this code, but didn't
see any glaring things missing. There was one existing oddity with
assigning a 0 to an "enum diff_symbol", don't we want
DIFF_SYMBOL_BINARY_DIFF_HEADER? In any case, it's just a line you touch
in 02/10, and pre-dates these changes.
One thing I would very much like to see here is a conversion of the
existing ad-hoc benchmarks you note in commit messages to something that
lives in t/perf/, it really helps future maintenance of perf-sensitive
code to be able to re-run those, and I for one find the output much
easier to read than whatever tool you're using to produce your
benchmarks.
On 16/06/2021 15:24, Ævar Arnfjörð Bjarmason wrote:
On Mon, Jun 14 2021, Phillip Wood via GitGitGadget wrote:
quoted
The current implementation of diff --color-moved-ws=allow-indentation-change
is considerably slower that the implementation of diff --color-moved which
is in turn slower than a regular diff. This patch series starts with a
couple of bug fixes and then reworks the implementation of diff
--color-moved and diff --color-moved-ws=allow-indentation-change to speed
them up on large diffs. The time to run git diff --color-moved
--no-color-moved-ws v2.28.0 v2.29.0 is reduced by 33% and the time to run
git diff --color-moved --color-moved-ws=allow-indentation-change v2.28.0
v2.29.0 is reduced by 88%. There is a small slowdown for commit sized diffs
with --color-moved - the time to run git log -p --color-moved
--no-color-moved-ws --no-merges -n1000 v2.29.0 is increased by 2% on recent
processors. On older processors these patches reduce the running time in all
cases that I've tested. In general the larger the diff the larger the speed
up. As an extreme example the time to run diff --color-moved
--color-moved-ws=allow-indentation-change v2.25.0 v2.30.0 goes down from 8
minutes to 6 seconds.
Phillip Wood (10):
diff --color-moved=zerba: fix alternate coloring
diff --color-moved: avoid false short line matches and bad zerba
coloring
diff: simplify allow-indentation-change delta calculation
diff --color-moved-ws=allow-indentation-change: simplify and optimize
diff --color-moved: call comparison function directly
diff --color-moved: unify moved block growth functions
diff --color-moved: shrink potential moved blocks as we go
diff --color-moved: stop clearing potential moved blocks
diff --color-moved-ws=allow-indentation-change: improve hash lookups
diff --color-moved: intern strings
Nice to see these land after the earlier on-list reference to them.
I skimmed these mostly, and am not familiar with this code, but didn't
see any glaring things missing. There was one existing oddity with
assigning a 0 to an "enum diff_symbol", don't we want
DIFF_SYMBOL_BINARY_DIFF_HEADER? In any case, it's just a line you touch
in 02/10, and pre-dates these changes.
Thanks for taking a look at these patches. I take your point about the
assignment, I don't think the actual value matters so long as it's not
DIFF_SYMBOL_PLUS or DIFF_SYMBOL_MINUS.
One thing I would very much like to see here is a conversion of the
existing ad-hoc benchmarks you note in commit messages to something that
lives in t/perf/, it really helps future maintenance of perf-sensitive
code to be able to re-run those, and I for one find the output much
easier to read than whatever tool you're using to produce your
benchmarks.
Adding some perf tests is a good idea, I'll do that when I reroll which
may take a couple of weeks as I'm going offline for a while at the end
of the week. The tool I have been using is hyperfine[1], it has been
used by a few other contributors (see `git log --grep σ` if you're
interested)
[1] https://github.com/sharkdp/hyperfine
Best Wishes
Phillip
On Mon, Jun 14, 2021 at 6:06 AM Phillip Wood via GitGitGadget
[off-list ref] wrote:
From: Phillip Wood <redacted>
As libxdiff does not have a whitespace flag to ignore the indentation
the code for --color-moved-ws=allow-indentation-change uses
XDF_IGNORE_WHITESPACE and then filters out any hash lookups where
there are non-indentation changes. This is filtering is inefficient as
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-07-20 10:39:02
Thanks to Ævar and Elijah for their comments, I've reworded the commit
messages, addressed the enum initialization issue in patch 2 (now 3) and
added some perf tests.
There are two new patches in this round. The first patch is new and adds the
perf tests suggested by Ævar, the penultimate patch is also new and coverts
the existing code to use a designated initializer.
I've converted the benchmark results in the commit messages to use the new
tests, the percentage changes are broadly similar to the previous results
though I ended up running them on a different computer this time.
V1 cover letter:
The current implementation of diff --color-moved-ws=allow-indentation-change
is considerably slower that the implementation of diff --color-moved which
is in turn slower than a regular diff. This patch series starts with a
couple of bug fixes and then reworks the implementation of diff
--color-moved and diff --color-moved-ws=allow-indentation-change to speed
them up on large diffs. The time to run git diff --color-moved
--no-color-moved-ws v2.28.0 v2.29.0 is reduced by 33% and the time to run
git diff --color-moved --color-moved-ws=allow-indentation-change v2.28.0
v2.29.0 is reduced by 88%. There is a small slowdown for commit sized diffs
with --color-moved - the time to run git log -p --color-moved
--no-color-moved-ws --no-merges -n1000 v2.29.0 is increased by 2% on recent
processors. On older processors these patches reduce the running time in all
cases that I've tested. In general the larger the diff the larger the speed
up. As an extreme example the time to run diff --color-moved
--color-moved-ws=allow-indentation-change v2.25.0 v2.30.0 goes down from 8
minutes to 6 seconds.
Phillip Wood (12):
diff --color-moved: add perf tests
diff --color-moved=zebra: fix alternate coloring
diff --color-moved: avoid false short line matches and bad zerba
coloring
diff: simplify allow-indentation-change delta calculation
diff --color-moved-ws=allow-indentation-change: simplify and optimize
diff --color-moved: call comparison function directly
diff --color-moved: unify moved block growth functions
diff --color-moved: shrink potential moved blocks as we go
diff --color-moved: stop clearing potential moved blocks
diff --color-moved-ws=allow-indentation-change: improve hash lookups
diff: use designated initializers for emitted_diff_symbol
diff --color-moved: intern strings
diff.c | 377 ++++++++++++-------------------
t/perf/p4002-diff-color-moved.sh | 45 ++++
t/t4015-diff-whitespace.sh | 137 +++++++++++
3 files changed, 323 insertions(+), 236 deletions(-)
create mode 100755 t/perf/p4002-diff-color-moved.sh
base-commit: 211eca0895794362184da2be2a2d812d070719d3
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-981%2Fphillipwood%2Fwip%2Fdiff-color-moved-tweaks-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-981/phillipwood/wip/diff-color-moved-tweaks-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/981
Range-diff vs v1:
-: ----------- > 1: 8fc8914a37b diff --color-moved: add perf tests
1: 374dbebcbf2 ! 2: 9b4e4d2674a diff --color-moved=zerba: fix alternate coloring
@@ Metadata
Author: Phillip Wood [off-list ref]
## Commit message ##
- diff --color-moved=zerba: fix alternate coloring
+ diff --color-moved=zebra: fix alternate coloring
b0a2ba4776 ("diff --color-moved=zebra: be stricter with color
alternation", 2018-11-23) sought to avoid using the alternate colors
2: 3d02a0a91a0 ! 3: 5512145c70f diff --color-moved: avoid false short line matches and bad zerba coloring
@@ diff.c: static void mark_color_as_moved(struct diff_options *o,
int pmb_nr = 0, pmb_alloc = 0;
int n, flipped_block = 0, block_length = 0;
- enum diff_symbol last_symbol = 0;
-+ enum diff_symbol moved_symbol = 0;
++ enum diff_symbol moved_symbol = DIFF_SYMBOL_BINARY_DIFF_HEADER;
for (n = 0; n < o->emitted_symbols->nr; n++) {
@@ diff.c: static void mark_color_as_moved(struct diff_options *o,
- last_symbol = l->s;
+ }
+ if (!match) {
-+ moved_symbol = 0;
++ moved_symbol = DIFF_SYMBOL_BINARY_DIFF_HEADER;
continue;
}
@@ diff.c: static void mark_color_as_moved(struct diff_options *o,
+ if (pmb_nr)
+ moved_symbol = l->s;
+ else
-+ moved_symbol = 0;
++ moved_symbol = DIFF_SYMBOL_BINARY_DIFF_HEADER;
+
block_length = 0;
}
3: 30f0ed44768 = 4: 93fdef30d64 diff: simplify allow-indentation-change delta calculation
4: ebb6eec1d92 ! 5: 6b7a8aed4ec diff --color-moved-ws=allow-indentation-change: simplify and optimize
@@ Commit message
comparison to filter out the non-matching lines. Fixing this reduces
time to run
git diff --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
- by 88% and simplifies the code.
+ by 93% compared to master and simplifies the code.
- Before this change
- Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
- Time (mean ± σ): 9.978 s ± 0.042 s [User: 9.905 s, System: 0.057 s]
- Range (min … max): 9.917 s … 10.037 s 10 runs
-
- After this change
- Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
- Time (mean ± σ): 1.220 s ± 0.004 s [User: 1.160 s, System: 0.058 s]
- Range (min … max): 1.214 s … 1.226 s 10 runs
+ Test HEAD^ HEAD
+ ---------------------------------------------------------------------------------------------------------------
+ 4002.1: diff --no-color-moved --no-color-moved-ws large change 0.41( 0.38+0.03) 0.41(0.37+0.04) +0.0%
+ 4002.2: diff --color-moved --no-color-moved-ws large change 0.83( 0.79+0.04) 0.82(0.79+0.02) -1.2%
+ 4002.3: diff --color-moved-ws=allow-indentation-change large change 13.68(13.59+0.07) 0.92(0.89+0.03) -93.3%
+ 4002.4: log --no-color-moved --no-color-moved-ws 1.31( 1.22+0.08) 1.31(1.21+0.10) +0.0%
+ 4002.5: log --color-moved --no-color-moved-ws 1.47( 1.40+0.07) 1.47(1.36+0.10) +0.0%
+ 4002.6: log --color-moved-ws=allow-indentation-change 1.87( 1.77+0.09) 1.50(1.41+0.09) -19.8%
Signed-off-by: Phillip Wood [off-list ref]
5: cec0c2d04d7 ! 6: cfbdd447eee diff --color-moved: call comparison function directly
@@ Metadata
## Commit message ##
diff --color-moved: call comparison function directly
- Calling xdiff_compare_lines() directly rather than using a function
- pointer from the hash map reduces the time very slightly but more
- importantly it will allow us to easily combine pmb_advance_or_null()
- and pmb_advance_or_null_multi_match() in the next commit.
+ This change will allow us to easily combine pmb_advance_or_null() and
+ pmb_advance_or_null_multi_match() in the next commit. Calling
+ xdiff_compare_lines() directly rather than using a function pointer
+ from the hash map has little effect on the run time.
- Before this change
- Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
- Time (mean ± σ): 1.136 s ± 0.004 s [User: 1.079 s, System: 0.053 s]
- Range (min … max): 1.130 s … 1.141 s 10 runs
-
- After this change
- Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
- Time (mean ± σ): 1.118 s ± 0.003 s [User: 1.062 s, System: 0.053 s]
- Range (min … max): 1.114 s … 1.121 s 10 runs
+ Test HEAD^ HEAD
+ -------------------------------------------------------------------------------------------------------------
+ 4002.1: diff --no-color-moved --no-color-moved-ws large change 0.41(0.37+0.04) 0.41(0.39+0.02) +0.0%
+ 4002.2: diff --color-moved --no-color-moved-ws large change 0.82(0.79+0.02) 0.83(0.79+0.03) +1.2%
+ 4002.3: diff --color-moved-ws=allow-indentation-change large change 0.92(0.89+0.03) 0.91(0.85+0.05) -1.1%
+ 4002.4: log --no-color-moved --no-color-moved-ws 1.31(1.21+0.10) 1.33(1.22+0.10) +1.5%
+ 4002.5: log --color-moved --no-color-moved-ws 1.47(1.36+0.10) 1.47(1.39+0.08) +0.0%
+ 4002.6: log --color-moved-ws=allow-indentation-change 1.50(1.41+0.09) 1.51(1.42+0.09) +0.7%
Signed-off-by: Phillip Wood [off-list ref]
6: 050cef0081d = 7: 73ce9b54e86 diff --color-moved: unify moved block growth functions
7: 9390e9a66eb = 8: ef8ce0e6ebc diff --color-moved: shrink potential moved blocks as we go
8: 1de99ac2bc3 = 9: 9d0a042eae1 diff --color-moved: stop clearing potential moved blocks
9: 41cdedd6090 ! 10: dd365ad115f diff --color-moved-ws=allow-indentation-change: improve hash lookups
@@ Commit message
As libxdiff does not have a whitespace flag to ignore the indentation
the code for --color-moved-ws=allow-indentation-change uses
XDF_IGNORE_WHITESPACE and then filters out any hash lookups where
- there are non-indentation changes. This is filtering is inefficient as
+ there are non-indentation changes. This filtering is inefficient as
we have to perform another string comparison.
By using the offset data that we have already computed to skip the
indentation we can avoid using XDF_IGNORE_WHITESPACE and safely remove
- the extra checks which improves the performance by 14% and paves the
+ the extra checks which improves the performance by 11% and paves the
way for the elimination of string comparisons in the next commit.
- This change slightly increases the runtime of other --color-moved
+ This change slightly increases the run time of other --color-moved
modes. This could be avoided by using different comparison functions
- for the different modes but after the changes in the next commit there
- is no measurable benefit.
+ for the different modes but after the next two commits there is no
+ measurable benefit in doing so.
- Before this change
- Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
- Time (mean ± σ): 1.116 s ± 0.005 s [User: 1.057 s, System: 0.056 s]
- Range (min … max): 1.109 s … 1.123 s 10 runs
-
- Benchmark #2: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
- Time (mean ± σ): 1.216 s ± 0.005 s [User: 1.155 s, System: 0.059 s]
- Range (min … max): 1.206 s … 1.223 s 10 runs
-
- After this change
- Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
- Time (mean ± σ): 1.147 s ± 0.005 s [User: 1.085 s, System: 0.059 s]
- Range (min … max): 1.140 s … 1.154 s 10 runs
-
- Benchmark #2: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
- Time (mean ± σ): 1.048 s ± 0.005 s [User: 987.4 ms, System: 58.8 ms]
- Range (min … max): 1.043 s … 1.056 s 10 runs
+ Test HEAD^ HEAD
+ --------------------------------------------------------------------------------------------------------------
+ 4002.1: diff --no-color-moved --no-color-moved-ws large change 0.41(0.38+0.03) 0.41(0.36+0.04) +0.0%
+ 4002.2: diff --color-moved --no-color-moved-ws large change 0.82(0.76+0.05) 0.84(0.79+0.04) +2.4%
+ 4002.3: diff --color-moved-ws=allow-indentation-change large change 0.91(0.88+0.03) 0.81(0.74+0.06) -11.0%
+ 4002.4: log --no-color-moved --no-color-moved-ws 1.32(1.21+0.10) 1.31(1.19+0.11) -0.8%
+ 4002.5: log --color-moved --no-color-moved-ws 1.47(1.37+0.10) 1.47(1.36+0.11) +0.0%
+ 4002.6: log --color-moved-ws=allow-indentation-change 1.51(1.42+0.09) 1.48(1.37+0.10) -2.0%
Signed-off-by: Phillip Wood [off-list ref]
-: ----------- > 11: c160222ab3c diff: use designated initializers for emitted_diff_symbol
10: 220664dd907 ! 12: 753554587f9 diff --color-moved: intern strings
@@ Commit message
number of hash lookups a little (calculating the ids still involves
one hash lookup per line) but the main benefit is that when growing
blocks of potentially moved lines we can replace string comparisons
- which involve chasing a pointer with a simple integer comparison. On
- a large diff this commit reduces the time to run 'diff --color-moved'
- by 33% and 'diff --color-moved-ws=allow-indentation-change' by 20%.
+ which involve chasing a pointer with a simple integer comparison.
- Compared to master the time to run 'git log --patch --color-moved' is
- increased by 2% and 'git log --patch
- --color-moved-ws=allow-indentation-change' in reduced by 14%. These
- timings were performed on an i5-7200U, on an i5-3470 both commands are
- faster than master. The small speed decrease on commit sized diffs is
- unfortunate but I think it is small enough to be worth it for the
- gains on larger diffs.
+ On a large diff this commit reduces the time to run
+ diff --color-moved
+ by 33% and
+ diff --color-moved-ws=allow-indentation-change
+ by 26%. Compared to master the time to run
+ diff --color-moved-ws=allow-indentation-change
+ is now reduced by 95% and the overhead compared to --no-color-moved is
+ reduced to 50%.
- Large diff before this change:
- Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
- Time (mean ± σ): 1.147 s ± 0.005 s [User: 1.085 s, System: 0.059 s]
- Range (min … max): 1.140 s … 1.154 s 10 runs
+ Compared to the previous commit the time to run
+ git log --patch --color-moved
+ is increased slightly, but compared to master there is no change in
+ run time.
- Benchmark #2: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
- Time (mean ± σ): 1.048 s ± 0.005 s [User: 987.4 ms, System: 58.8 ms]
- Range (min … max): 1.043 s … 1.056 s 10 runs
+ Test HEAD^ HEAD
+ --------------------------------------------------------------------------------------------------------------
+ 4002.1: diff --no-color-moved --no-color-moved-ws large change 0.41(0.36+0.04) 0.41(0.37+0.03) +0.0%
+ 4002.2: diff --color-moved --no-color-moved-ws large change 0.83(0.79+0.03) 0.55(0.52+0.03) -33.7%
+ 4002.3: diff --color-moved-ws=allow-indentation-change large change 0.81(0.77+0.04) 0.60(0.55+0.05) -25.9%
+ 4002.4: log --no-color-moved --no-color-moved-ws 1.30(1.20+0.09) 1.31(1.22+0.08) +0.8%
+ 4002.5: log --color-moved --no-color-moved-ws 1.46(1.35+0.11) 1.47(1.30+0.16) +0.7%
+ 4002.6: log --color-moved-ws=allow-indentation-change 1.46(1.38+0.07) 1.47(1.34+0.13) +0.7%
- Large diff after this change
- Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
- Time (mean ± σ): 762.7 ms ± 2.8 ms [User: 707.5 ms, System: 53.7 ms]
- Range (min … max): 758.0 ms … 767.0 ms 10 runs
-
- Benchmark #2: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
- Time (mean ± σ): 831.7 ms ± 1.7 ms [User: 776.5 ms, System: 53.3 ms]
- Range (min … max): 829.2 ms … 835.1 ms 10 runs
-
- Small diffs on master
- Benchmark #1: bin-wrappers/git log -p --diff-algorithm=myers --color-moved --no-color-moved-ws --no-merges -n1000 v2.29.0
- Time (mean ± σ): 1.567 s ± 0.001 s [User: 1.443 s, System: 0.121 s]
- Range (min … max): 1.566 s … 1.571 s 10 runs
-
- Benchmark #2: bin-wrappers/git log -p --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change -n1000 --no-merges v2.29.0
- Time (mean ± σ): 1.865 s ± 0.008 s [User: 1.748 s, System: 0.112 s]
- Range (min … max): 1.857 s … 1.881 s 10 runs
-
- Small diffs after this change
- Benchmark #1: bin-wrappers/git log -p --diff-algorithm=myers --color-moved --no-color-moved-ws --no-merges -n1000 v2.29.0
- Time (mean ± σ): 1.597 s ± 0.003 s [User: 1.413 s, System: 0.179 s]
- Range (min … max): 1.591 s … 1.601 s 10 runs
-
- Benchmark #2: bin-wrappers/git log -p --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change -n1000 --no-merges v2.29.0
- Time (mean ± σ): 1.606 s ± 0.006 s [User: 1.420 s, System: 0.181 s]
- Range (min … max): 1.601 s … 1.622 s 10 runs
+ Test master HEAD
+ --------------------------------------------------------------------------------------------------------------
+ 4002.1: diff --no-color-moved --no-color-moved-ws large change 0.40( 0.36+0.03) 0.41(0.37+0.03) +2.5%
+ 4002.2: diff --color-moved --no-color-moved-ws large change 0.82( 0.77+0.04) 0.55(0.52+0.03) -32.9%
+ 4002.3: diff --color-moved-ws=allow-indentation-change large change 14.10(14.04+0.04) 0.60(0.55+0.05) -95.7%
+ 4002.4: log --no-color-moved --no-color-moved-ws 1.31( 1.21+0.09) 1.31(1.22+0.08) +0.0%
+ 4002.5: log --color-moved --no-color-moved-ws 1.47( 1.37+0.09) 1.47(1.30+0.16) +0.0%
+ 4002.6: log --color-moved-ws=allow-indentation-change 1.86( 1.76+0.10) 1.47(1.34+0.13) -21.0%
Signed-off-by: Phillip Wood [off-list ref]
@@ diff.c: static void mark_color_as_moved(struct diff_options *o,
ALLOC_GROW(pmb, pmb_nr + 1, pmb_alloc);
if (o->color_moved_ws_handling &
COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE)
-@@ diff.c: static void emit_diff_symbol_from_struct(struct diff_options *o,
- static void emit_diff_symbol(struct diff_options *o, enum diff_symbol s,
- const char *line, int len, unsigned flags)
- {
-- struct emitted_diff_symbol e = {line, len, flags, 0, 0, s};
-+ struct emitted_diff_symbol e = {line, len, flags, 0, 0, 0, s};
-
- if (o->emitted_symbols)
- append_emitted_diff_symbol(o, &e);
@@ diff.c: static void diff_flush_patch_all_file_pairs(struct diff_options *o)
if (o->emitted_symbols) {
--
gitgitgadget
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-07-20 10:39:17
From: Phillip Wood <redacted>
If we already have a block of potentially moved lines then as we move
down the diff we need to check if the next line of each potentially
moved line matches the current line of the diff. The implementation of
--color-moved-ws=allow-indentation-change was needlessly performing
this check on all the lines in the diff that matched the current line
rather than just the current line. To exacerbate the problem finding
all the other lines in the diff that match the current line involves a
fuzzy lookup so we were wasting even more time performing a second
comparison to filter out the non-matching lines. Fixing this reduces
time to run
git diff --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
by 93% compared to master and simplifies the code.
Test HEAD^ HEAD
---------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.41( 0.38+0.03) 0.41(0.37+0.04) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.83( 0.79+0.04) 0.82(0.79+0.02) -1.2%
4002.3: diff --color-moved-ws=allow-indentation-change large change 13.68(13.59+0.07) 0.92(0.89+0.03) -93.3%
4002.4: log --no-color-moved --no-color-moved-ws 1.31( 1.22+0.08) 1.31(1.21+0.10) +0.0%
4002.5: log --color-moved --no-color-moved-ws 1.47( 1.40+0.07) 1.47(1.36+0.10) +0.0%
4002.6: log --color-moved-ws=allow-indentation-change 1.87( 1.77+0.09) 1.50(1.41+0.09) -19.8%
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 65 ++++++++++++++++------------------------------------------
1 file changed, 18 insertions(+), 47 deletions(-)
@@ -881,35 +881,20 @@ static int compute_ws_delta(const struct emitted_diff_symbol *a,staticintcmp_in_block_with_wsd(conststructdiff_options*o,conststructmoved_entry*cur,-conststructmoved_entry*match,-structmoved_block*pmb,-intn)+conststructemitted_diff_symbol*l,+structmoved_block*pmb){-structemitted_diff_symbol*l=&o->emitted_symbols->buf[n];-intal=cur->es->len,bl=match->es->len,cl=l->len;+intal=cur->es->len,bl=l->len;constchar*a=cur->es->line,-*b=match->es->line,-*c=l->line;+*b=l->line;inta_off=cur->es->indent_off,a_width=cur->es->indent_width,-c_off=l->indent_off,-c_width=l->indent_width;+b_off=l->indent_off,+b_width=l->indent_width;intdelta;-/*-*Weneedtocheckif'cur'isequalto'match'.Asthose-*arefromthesame(+/-)side,wedonotneedtoadjustfor-*indentchanges.Howeverthesewerefoundusingfuzzy-*matchingsowedohavetocheckiftheyareequal.Herewe-*justcheckthelengths.Wedelaycallingmemcmp()tocheck-*thecontentsuntillaterasifthelengthcomparisonfora-*andcfailswecanavoidthecallalltogether.-*/-if(al!=bl)-return1;-/* If 'l' and 'cur' are both blank then they match. */-if(a_width==INDENT_BLANKLINE&&c_width==INDENT_BLANKLINE)+if(a_width==INDENT_BLANKLINE&&b_width==INDENT_BLANKLINE)return0;/*
@@ -918,7 +903,7 @@ static int cmp_in_block_with_wsd(const struct diff_options *o,*matchthoseofthecurrentblockandthatthetextof'l'and'cur'*aftertheindentationmatch.*/-delta=c_width-a_width;+delta=b_width-a_width;/**Ifthepreviouslinesofthisblockwereallblankthensetits
@@ -927,9 +912,8 @@ static int cmp_in_block_with_wsd(const struct diff_options *o,if(pmb->wsd==INDENT_BLANKLINE)pmb->wsd=delta;-return!(delta==pmb->wsd&&al-a_off==cl-c_off&&-!memcmp(a,b,al)&&!-memcmp(a+a_off,c+c_off,al-a_off));+return!(delta==pmb->wsd&&al-a_off==bl-b_off&&+!memcmp(a+a_off,b+b_off,al-a_off));}staticintmoved_entry_cmp(constvoid*hashmap_cmp_fn_data,
@@ -1030,36 +1014,23 @@ static void pmb_advance_or_null(struct diff_options *o,}staticvoidpmb_advance_or_null_multi_match(structdiff_options*o,-structmoved_entry*match,-structhashmap*hm,+structemitted_diff_symbol*l,structmoved_block*pmb,-intpmb_nr,intn)+intpmb_nr){inti;-char*got_match=xcalloc(1,pmb_nr);--hashmap_for_each_entry_from(hm,match,ent){-for(i=0;i<pmb_nr;i++){-structmoved_entry*prev=pmb[i].match;-structmoved_entry*cur=(prev&&prev->next_line)?-prev->next_line:NULL;-if(!cur)-continue;-if(!cmp_in_block_with_wsd(o,cur,match,&pmb[i],n))-got_match[i]|=1;-}-}for(i=0;i<pmb_nr;i++){-if(got_match[i]){+structmoved_entry*prev=pmb[i].match;+structmoved_entry*cur=(prev&&prev->next_line)?+prev->next_line:NULL;+if(cur&&!cmp_in_block_with_wsd(o,cur,l,&pmb[i])){/* Advance to the next line */-pmb[i].match=pmb[i].match->next_line;+pmb[i].match=cur;}else{moved_block_clear(&pmb[i]);}}--free(got_match);}staticintshrink_potential_moved_blocks(structmoved_block*pmb,
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-07-20 10:39:25
From: Phillip Wood <redacted>
Now that we reliably end a block when the sign changes we don't need
the whitespace delta calculation to rely on the sign.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 13 ++-----------
1 file changed, 2 insertions(+), 11 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-07-20 10:39:33
From: Phillip Wood <redacted>
When marking moved lines it is possible for a block of potential
matched lines to extend past a change in sign when there is a sequence
of added lines whose text matches the text of a sequence of deleted
and added lines. Most of the time either `match` will be NULL or
`pmb_advance_or_null()` will fail when the loop encounters a change of
sign but there are corner cases where `match` is non-NULL and
`pmb_advance_or_null()` successfully advances the moved block despite
the change in sign.
One consequence of this is highlighting a short line as moved when it
should not be. For example
-moved line # Correctly highlighted as moved
+short line # Wrongly highlighted as moved
context
+moved line # Correctly highlighted as moved
+short line
context
-short line
The other consequence is coloring a moved addition following a moved
deletion in the wrong color. In the example below the first "+moved
line 3" should be highlighted as newMoved not newMovedAlternate.
-moved line 1 # Correctly highlighted as oldMoved
-moved line 2 # Correctly highlighted as oldMovedAlternate
+moved line 3 # Wrongly highlighted as newMovedAlternate
context # Everything else is highlighted correctly
+moved line 2
+moved line 3
context
+moved line 1
-moved line 3
These false matches are more likely when using --color-moved-ws with
the exception of --color-moved-ws=allow-indentation-change which ties
the sign of the current whitespace delta to the sign of the line to
avoid this problem. The fix is to check that the sign of the new line
being matched is the same as the sign of the line that started the
block of potential matches.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 17 ++++++----
t/t4015-diff-whitespace.sh | 65 ++++++++++++++++++++++++++++++++++++++
2 files changed, 76 insertions(+), 6 deletions(-)
@@ -1514,6 +1514,71 @@ test_expect_success 'zebra alternate color is only used when necessary' 'test_cmpexpectedactual'+test_expect_success'short lines of opposite sign do not get marked as moved''+cat>old.txt<<-\EOF&&+thislineshouldbemarkedasmoved+unchanged+unchanged+unchanged+unchanged+tooshort+thislineshouldbemarkedasoldMovednewMoved+thislineshouldbemarkedasoldMovedAlternatenewMoved+unchanged1+unchanged2+unchanged3+unchanged4+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+EOF+cat>new.txt<<-\EOF&&+tooshort+unchanged+unchanged+thislineshouldbemarkedasmoved+tooshort+unchanged+unchanged+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+unchanged1+unchanged2+thislineshouldbemarkedasoldMovedAlternatenewMoved+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+unchanged3+thislineshouldbemarkedasoldMovednewMoved+unchanged4+EOF+test_expect_code1gitdiff--no-index--color--color-moved=zebra\+old.txtnew.txt>output&&catoutput&&+grep-vindexoutput|test_decode_color>actual&&+cat>expect<<-\EOF&&+<BOLD>diff--gita/old.txtb/new.txt<RESET>+<BOLD>---a/old.txt<RESET>+<BOLD>+++b/new.txt<RESET>+<CYAN>@@-1,13+1,15@@<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasmoved<RESET>+<GREEN>+<RESET><GREEN>tooshort<RESET>+unchanged<RESET>+unchanged<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasmoved<RESET>+<GREEN>+<RESET><GREEN>tooshort<RESET>+unchanged<RESET>+unchanged<RESET>+<RED>-tooshort<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;BLUE>-thislineshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+unchanged1<RESET>+unchanged2<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+unchanged3<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovednewMoved<RESET>+unchanged4<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+EOF+test_cmpexpectactual+'+ test_expect_success'cmd option assumes configured colored-moved''test_configcolor.diff.oldMoved"magenta"&&test_configcolor.diff.newMoved"cyan"&&
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-07-20 10:39:45
From: Phillip Wood <redacted>
b0a2ba4776 ("diff --color-moved=zebra: be stricter with color
alternation", 2018-11-23) sought to avoid using the alternate colors
unless there are two adjacent moved blocks of the same
sign. Unfortunately it contains two bugs that prevented it from fixing
the problem properly. Firstly `last_symbol` is reset at the start of
each iteration of the loop losing the symbol of the last line and
secondly when deciding whether to use the alternate color it should be
checking if the current line is the same sign of the last line, not a
different sign. The combination of the two errors means that we still
use the alternate color when we should do but we also use it when we
shouldn't. This is most noticable when using
--color-moved-ws=allow-indentation-change with hunks like
-this line gets indented
+ this line gets indented
where the post image is colored with newMovedAlternate rather than
newMoved. While this does not matter much, the next commit will change
the coloring to be correct in this case, so lets fix the bug here to
make it clear why the output is changing and add a regression test.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 4 +--
t/t4015-diff-whitespace.sh | 72 ++++++++++++++++++++++++++++++++++++++
2 files changed, 74 insertions(+), 2 deletions(-)
@@ -1442,6 +1442,78 @@ test_expect_success 'detect permutations inside moved code -- dimmed-zebra' 'test_cmpexpectedactual'+test_expect_success'zebra alternate color is only used when necessary''+cat>old.txt<<-\EOF&&+line1AshouldbemarkedasoldMovednewMovedAlternate+line1BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line2AshouldbemarkedasoldMovednewMovedAlternate+line2BshouldbemarkedasoldMovednewMovedAlternate+line3AshouldbemarkedasoldMovedAlternatenewMoved+line3BshouldbemarkedasoldMovedAlternatenewMoved+unchanged+line4AshouldbemarkedasoldMovednewMovedAlternate+line4BshouldbemarkedasoldMovednewMovedAlternate+line5AshouldbemarkedasoldMovedAlternatenewMoved+line5BshouldbemarkedasoldMovedAlternatenewMoved+line6AshouldbemarkedasoldMovednewMoved+line6BshouldbemarkedasoldMovednewMoved+EOF+cat>new.txt<<-\EOF&&+line1AshouldbemarkedasoldMovednewMovedAlternate+line1BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line3AshouldbemarkedasoldMovedAlternatenewMoved+line3BshouldbemarkedasoldMovedAlternatenewMoved+line2AshouldbemarkedasoldMovednewMovedAlternate+line2BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line6AshouldbemarkedasoldMovednewMoved+line6BshouldbemarkedasoldMovednewMoved+line4AshouldbemarkedasoldMovednewMovedAlternate+line4BshouldbemarkedasoldMovednewMovedAlternate+line5AshouldbemarkedasoldMovedAlternatenewMoved+line5BshouldbemarkedasoldMovedAlternatenewMoved+EOF+test_expect_code1gitdiff--no-index--color--color-moved=zebra\+--color-moved-ws=allow-indentation-change\+old.txtnew.txt>output&&+grep-vindexoutput|test_decode_color>actual&&+cat>expected<<-\EOF&&+<BOLD>diff--gita/old.txtb/new.txt<RESET>+<BOLD>---a/old.txt<RESET>+<BOLD>+++b/new.txt<RESET>+<CYAN>@@-1,14+1,14@@<RESET>+<BOLD;MAGENTA>-line1AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line1BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line1AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line1BshouldbemarkedasoldMovednewMovedAlternate<RESET>+unchanged<RESET>+<BOLD;MAGENTA>-line2AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line2BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;BLUE>-line3AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;BLUE>-line3BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line3AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line3BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line2AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line2BshouldbemarkedasoldMovednewMovedAlternate<RESET>+unchanged<RESET>+<BOLD;MAGENTA>-line4AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line4BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;BLUE>-line5AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;BLUE>-line5BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;MAGENTA>-line6AshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;MAGENTA>-line6BshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line6AshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line6BshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line4AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line4BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line5AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line5BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+EOF+test_cmpexpectedactual+'+ test_expect_success'cmd option assumes configured colored-moved''test_configcolor.diff.oldMoved"magenta"&&test_configcolor.diff.newMoved"cyan"&&
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-07-20 10:39:48
From: Phillip Wood <redacted>
Add some tests so we can monitor changes to the performance of the
move detection code. The tests record the performance of a single
large diff and a sequence of smaller diffs.
Signed-off-by: Phillip Wood <redacted>
---
t/perf/p4002-diff-color-moved.sh | 45 ++++++++++++++++++++++++++++++++
1 file changed, 45 insertions(+)
create mode 100755 t/perf/p4002-diff-color-moved.sh
@@ -0,0 +1,45 @@+#!/bin/sh++test_description='Tests diff --color-moved performance'+../perf-lib.sh++test_perf_default_repo++if!gitrev-parse--verifyv2.29.0^{commit}>/dev/null+then+skip_all='skipping because tag v2.29.0 was not found'+test_done+fi++GIT_PAGER_IN_USE=1+test_exportGIT_PAGER_IN_USE++test_perf'diff --no-color-moved --no-color-moved-ws large change''+gitdiff--no-color-moved--no-color-moved-wsv2.28.0v2.29.0+'++test_perf'diff --color-moved --no-color-moved-ws large change''+gitdiff--color-moved=zebra--no-color-moved-wsv2.28.0v2.29.0+'++test_perf'diff --color-moved-ws=allow-indentation-change large change''+gitdiff--color-moved=zebra--color-moved-ws=allow-indentation-change\+v2.28.0v2.29.0+'++test_perf'log --no-color-moved --no-color-moved-ws''+gitlog--no-color-moved--no-color-moved-ws--no-merges--patch\+-n1000v2.29.0+'++test_perf'log --color-moved --no-color-moved-ws''+gitlog--color-moved=zebra--no-color-moved-ws--no-merges--patch\+-n1000v2.29.0+'++test_perf'log --color-moved-ws=allow-indentation-change''+gitlog--color-moved=zebra--color-moved-ws=allow-indentation-change\+--no-merges--patch-n1000v2.29.0+'++test_done
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-07-20 10:40:34
From: Phillip Wood <redacted>
After the last two commits pmb_advance_or_null() and
pmb_advance_or_null_multi_match() differ only in the comparison they
perform. Lets simplify the code by combining them into a single
function.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 41 ++++++++++++-----------------------------
1 file changed, 12 insertions(+), 29 deletions(-)
@@ -1003,36 +1003,23 @@ static void pmb_advance_or_null(struct diff_options *o,unsignedflags=o->color_moved_ws_handling&XDF_WHITESPACE_FLAGS;for(i=0;i<pmb_nr;i++){+intmatch;structmoved_entry*prev=pmb[i].match;structmoved_entry*cur=(prev&&prev->next_line)?prev->next_line:NULL;-if(cur&&xdiff_compare_lines(cur->es->line,cur->es->len,-l->line,l->len,-flags)){-pmb[i].match=cur;-}else{-pmb[i].match=NULL;-}-}-}-staticvoidpmb_advance_or_null_multi_match(structdiff_options*o,-structemitted_diff_symbol*l,-structmoved_block*pmb,-intpmb_nr)-{-inti;--for(i=0;i<pmb_nr;i++){-structmoved_entry*prev=pmb[i].match;-structmoved_entry*cur=(prev&&prev->next_line)?-prev->next_line:NULL;-if(cur&&!cmp_in_block_with_wsd(o,cur,l,&pmb[i])){-/* Advance to the next line */+if(o->color_moved_ws_handling&+COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE)+match=cur&&+!cmp_in_block_with_wsd(o,cur,l,&pmb[i]);+else+match=cur&&+xdiff_compare_lines(cur->es->line,cur->es->len,+l->line,l->len,flags);+if(match)pmb[i].match=cur;-}else{+elsemoved_block_clear(&pmb[i]);-}}}
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-07-20 10:40:34
From: Phillip Wood <redacted>
This change will allow us to easily combine pmb_advance_or_null() and
pmb_advance_or_null_multi_match() in the next commit. Calling
xdiff_compare_lines() directly rather than using a function pointer
from the hash map has little effect on the run time.
Test HEAD^ HEAD
-------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.41(0.37+0.04) 0.41(0.39+0.02) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.82(0.79+0.02) 0.83(0.79+0.03) +1.2%
4002.3: diff --color-moved-ws=allow-indentation-change large change 0.92(0.89+0.03) 0.91(0.85+0.05) -1.1%
4002.4: log --no-color-moved --no-color-moved-ws 1.31(1.21+0.10) 1.33(1.22+0.10) +1.5%
4002.5: log --color-moved --no-color-moved-ws 1.47(1.36+0.10) 1.47(1.39+0.08) +0.0%
4002.6: log --color-moved-ws=allow-indentation-change 1.50(1.41+0.09) 1.51(1.42+0.09) +0.7%
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 11 +++++++----
1 file changed, 7 insertions(+), 4 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-07-20 10:40:46
From: Phillip Wood <redacted>
moved_block_clear() was introduced in 74d156f4a1 ("diff
--color-moved-ws: fix double free crash", 2018-10-04) to free the
memory that was allocated when initializing a potential moved
block. However since 21536d077f ("diff --color-moved-ws: modify
allow-indentation-change", 2018-11-23) initializing a potential moved
block no longer allocates any memory. Up until the last commit we were
relying on moved_block_clear() to set the `match` pointer to NULL when
a block stopped matching, but since that commit we do not clear a
moved block that does not match so it does not make sense to clear
them elsewhere.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 11 -----------
1 file changed, 11 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-07-20 10:40:52
From: Phillip Wood <redacted>
Rather than setting `match` to NULL and then looping over the list of
potential matched blocks for a second time to remove blocks with no
matches just filter out the blocks with no matches as we go.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 42 ++++++------------------------------------
1 file changed, 6 insertions(+), 36 deletions(-)
@@ -1017,37 +1017,9 @@ static void pmb_advance_or_null(struct diff_options *o,xdiff_compare_lines(cur->es->line,cur->es->len,l->line,l->len,flags);if(match)-pmb[i].match=cur;-else-moved_block_clear(&pmb[i]);+pmb[j++].match=cur;}-}--staticintshrink_potential_moved_blocks(structmoved_block*pmb,-intpmb_nr)-{-intlp,rp;--/* Shrink the set of potential block to the remaining running */-for(lp=0,rp=pmb_nr-1;lp<=rp;){-while(lp<pmb_nr&&pmb[lp].match)-lp++;-/* lp points at the first NULL now */--while(rp>-1&&!pmb[rp].match)-rp--;-/* rp points at the last non-NULL */--if(lp<pmb_nr&&rp>-1&&lp<rp){-pmb[lp]=pmb[rp];-memset(&pmb[rp],0,sizeof(pmb[rp]));-rp--;-lp++;-}-}--/* Remember the number of running sets */-returnrp+1;+*pmb_nr=j;}/*
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-07-20 10:41:11
From: Phillip Wood <redacted>
This makes it clearer which fields are being explicitly initialized
and will simplify the next commit where we add a new field to the
struct.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 4 +++-
1 file changed, 3 insertions(+), 1 deletion(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-07-20 10:41:33
From: Phillip Wood <redacted>
As libxdiff does not have a whitespace flag to ignore the indentation
the code for --color-moved-ws=allow-indentation-change uses
XDF_IGNORE_WHITESPACE and then filters out any hash lookups where
there are non-indentation changes. This filtering is inefficient as
we have to perform another string comparison.
By using the offset data that we have already computed to skip the
indentation we can avoid using XDF_IGNORE_WHITESPACE and safely remove
the extra checks which improves the performance by 11% and paves the
way for the elimination of string comparisons in the next commit.
This change slightly increases the run time of other --color-moved
modes. This could be avoided by using different comparison functions
for the different modes but after the next two commits there is no
measurable benefit in doing so.
Test HEAD^ HEAD
--------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.41(0.38+0.03) 0.41(0.36+0.04) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.82(0.76+0.05) 0.84(0.79+0.04) +2.4%
4002.3: diff --color-moved-ws=allow-indentation-change large change 0.91(0.88+0.03) 0.81(0.74+0.06) -11.0%
4002.4: log --no-color-moved --no-color-moved-ws 1.32(1.21+0.10) 1.31(1.19+0.11) -0.8%
4002.5: log --color-moved --no-color-moved-ws 1.47(1.37+0.10) 1.47(1.36+0.11) +0.0%
4002.6: log --color-moved-ws=allow-indentation-change 1.51(1.42+0.09) 1.48(1.37+0.10) -2.0%
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 66 +++++++++++++++++-----------------------------------------
1 file changed, 19 insertions(+), 47 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-07-20 10:41:44
From: Phillip Wood <redacted>
Taking inspiration from xdl_classify_record() assign an id to each
addition and deletion such that lines that match for the current
--color-moved-ws mode share the same unique id. This reduces the
number of hash lookups a little (calculating the ids still involves
one hash lookup per line) but the main benefit is that when growing
blocks of potentially moved lines we can replace string comparisons
which involve chasing a pointer with a simple integer comparison.
On a large diff this commit reduces the time to run
diff --color-moved
by 33% and
diff --color-moved-ws=allow-indentation-change
by 26%. Compared to master the time to run
diff --color-moved-ws=allow-indentation-change
is now reduced by 95% and the overhead compared to --no-color-moved is
reduced to 50%.
Compared to the previous commit the time to run
git log --patch --color-moved
is increased slightly, but compared to master there is no change in
run time.
Test HEAD^ HEAD
--------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.41(0.36+0.04) 0.41(0.37+0.03) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.83(0.79+0.03) 0.55(0.52+0.03) -33.7%
4002.3: diff --color-moved-ws=allow-indentation-change large change 0.81(0.77+0.04) 0.60(0.55+0.05) -25.9%
4002.4: log --no-color-moved --no-color-moved-ws 1.30(1.20+0.09) 1.31(1.22+0.08) +0.8%
4002.5: log --color-moved --no-color-moved-ws 1.46(1.35+0.11) 1.47(1.30+0.16) +0.7%
4002.6: log --color-moved-ws=allow-indentation-change 1.46(1.38+0.07) 1.47(1.34+0.13) +0.7%
Test master HEAD
--------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.40( 0.36+0.03) 0.41(0.37+0.03) +2.5%
4002.2: diff --color-moved --no-color-moved-ws large change 0.82( 0.77+0.04) 0.55(0.52+0.03) -32.9%
4002.3: diff --color-moved-ws=allow-indentation-change large change 14.10(14.04+0.04) 0.60(0.55+0.05) -95.7%
4002.4: log --no-color-moved --no-color-moved-ws 1.31( 1.21+0.09) 1.31(1.22+0.08) +0.0%
4002.5: log --color-moved --no-color-moved-ws 1.47( 1.37+0.09) 1.47(1.30+0.16) +0.0%
4002.6: log --color-moved-ws=allow-indentation-change 1.86( 1.76+0.10) 1.47(1.34+0.13) -21.0%
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 171 ++++++++++++++++++++++++++++++++-------------------------
1 file changed, 95 insertions(+), 76 deletions(-)
@@ -772,6 +773,7 @@ struct emitted_diff_symbol {intflags;intindent_off;/* Offset to first non-whitespace character */intindent_width;/* The visual width of the indentation */+unsignedid;enumdiff_symbols;};#define EMITTED_DIFF_SYMBOL_INIT {NULL}
@@ -866,24 +868,24 @@ static int cmp_in_block_with_wsd(const struct diff_options *o,conststructemitted_diff_symbol*l,structmoved_block*pmb){-intal=cur->es->len,bl=l->len;-constchar*a=cur->es->line,-*b=l->line;-inta_off=cur->es->indent_off,-a_width=cur->es->indent_width,-b_off=l->indent_off,-b_width=l->indent_width;+inta_width=cur->es->indent_width,b_width=l->indent_width;intdelta;-/* If 'l' and 'cur' are both blank then they match. */-if(a_width==INDENT_BLANKLINE&&b_width==INDENT_BLANKLINE)+/* The text of each line must match */+if(cur->es->id!=l->id)+return1;++/*+*If'l'and'cur'arebothblankthenwedon'tneedtocheckthe+*indent.Weonlyneedtocheckcurasweknowthestringsmatch.+**/+if(a_width==INDENT_BLANKLINE)return0;/**Theindentchangesoftheblockareknownandstoredinpmb->wsd;*howeverweneedtocheckiftheindentchangesofthecurrentline-*matchthoseofthecurrentblockandthatthetextof'l'and'cur'-*aftertheindentationmatch.+*matchthoseofthecurrentblock.*/delta=b_width-a_width;
@@ -894,22 +896,26 @@ static int cmp_in_block_with_wsd(const struct diff_options *o,if(pmb->wsd==INDENT_BLANKLINE)pmb->wsd=delta;-return!(delta==pmb->wsd&&al-a_off==bl-b_off&&-!memcmp(a+a_off,b+b_off,al-a_off));+returndelta!=pmb->wsd;}-staticintmoved_entry_cmp(constvoid*hashmap_cmp_fn_data,-conststructhashmap_entry*eptr,-conststructhashmap_entry*entry_or_key,-constvoid*keydata)+structinterned_diff_symbol{+structhashmap_entryent;+structemitted_diff_symbol*es;+};++staticintinterned_diff_symbol_cmp(constvoid*hashmap_cmp_fn_data,+conststructhashmap_entry*eptr,+conststructhashmap_entry*entry_or_key,+constvoid*keydata){conststructdiff_options*diffopt=hashmap_cmp_fn_data;conststructemitted_diff_symbol*a,*b;unsignedflags=diffopt->color_moved_ws_handling&XDF_WHITESPACE_FLAGS;-a=container_of(eptr,conststructmoved_entry,ent)->es;-b=container_of(entry_or_key,conststructmoved_entry,ent)->es;+a=container_of(eptr,conststructinterned_diff_symbol,ent)->es;+b=container_of(entry_or_key,conststructinterned_diff_symbol,ent)->es;return!xdiff_compare_lines(a->line+a->indent_off,a->len-a->indent_off,
@@ -917,55 +923,81 @@ static int moved_entry_cmp(const void *hashmap_cmp_fn_data,b->len-b->indent_off,flags);}-staticstructmoved_entry*prepare_entry(structdiff_options*o,-intline_no)+staticvoidprepare_entry(structdiff_options*o,structemitted_diff_symbol*l,+structinterned_diff_symbol*s){-structmoved_entry*ret=xmalloc(sizeof(*ret));-structemitted_diff_symbol*l=&o->emitted_symbols->buf[line_no];unsignedflags=o->color_moved_ws_handling&XDF_WHITESPACE_FLAGS;unsignedinthash=xdiff_hash_string(l->line+l->indent_off,l->len-l->indent_off,flags);-hashmap_entry_init(&ret->ent,hash);-ret->es=l;-ret->next_line=NULL;--returnret;+hashmap_entry_init(&s->ent,hash);+s->es=l;}-staticvoidadd_lines_to_move_detection(structdiff_options*o,-structhashmap*add_lines,-structhashmap*del_lines)+structmoved_entry_list{+structmoved_entry*add,*del;+};++staticstructmoved_entry_list*add_lines_to_move_detection(structdiff_options*o,+structmem_pool*entry_mem_pool){structmoved_entry*prev_line=NULL;-+structmem_poolinterned_pool;+structhashmapinterned_map;+structmoved_entry_list*entry_list=NULL;+size_tentry_list_alloc=0;+unsignedid=0;intn;++hashmap_init(&interned_map,interned_diff_symbol_cmp,o,8096);+mem_pool_init(&interned_pool,1024*1024);+for(n=0;n<o->emitted_symbols->nr;n++){-structhashmap*hm;-structmoved_entry*key;+structinterned_diff_symbolkey;+structemitted_diff_symbol*l=&o->emitted_symbols->buf[n];+structinterned_diff_symbol*s;+structmoved_entry*entry;-switch(o->emitted_symbols->buf[n].s){-caseDIFF_SYMBOL_PLUS:-hm=add_lines;-break;-caseDIFF_SYMBOL_MINUS:-hm=del_lines;-break;-default:+if(l->s!=DIFF_SYMBOL_PLUS&&l->s!=DIFF_SYMBOL_MINUS){prev_line=NULL;continue;}if(o->color_moved_ws_handling&COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE)-fill_es_indent_data(&o->emitted_symbols->buf[n]);-key=prepare_entry(o,n);-if(prev_line&&prev_line->es->s==o->emitted_symbols->buf[n].s)-prev_line->next_line=key;+fill_es_indent_data(l);-hashmap_add(hm,&key->ent);-prev_line=key;+prepare_entry(o,l,&key);+s=hashmap_get_entry(&interned_map,&key,ent,&key.ent);+if(s){+l->id=s->es->id;+}else{+l->id=id;+ALLOC_GROW_BY(entry_list,id,1,entry_list_alloc);+hashmap_add(&interned_map,+memcpy(mem_pool_alloc(&interned_pool,+sizeof(key)),+&key,sizeof(key)));+}+entry=mem_pool_alloc(entry_mem_pool,sizeof(*entry));+entry->es=l;+entry->next_line=NULL;+if(prev_line&&prev_line->es->s==l->s)+prev_line->next_line=entry;+prev_line=entry;+if(l->s==DIFF_SYMBOL_PLUS){+entry->next_match=entry_list[l->id].add;+entry_list[l->id].add=entry;+}else{+entry->next_match=entry_list[l->id].del;+entry_list[l->id].del=entry;+}}++hashmap_clear(&interned_map);+mem_pool_discard(&interned_pool,0);++returnentry_list;}staticvoidpmb_advance_or_null(structdiff_options*o,
@@ -1034,8 +1064,7 @@ static int adjust_last_block(struct diff_options *o, int n, int block_length)/* Find blocks of moved code, delegate actual coloring decision to helper */staticvoidmark_color_as_moved(structdiff_options*o,-structhashmap*add_lines,-structhashmap*del_lines)+structmoved_entry_list*entry_list){structmoved_block*pmb=NULL;/* potentially moved blocks */intpmb_nr=0,pmb_alloc=0;
Sorry Elijah I forgot to add you to the CC list on GitGitGadget
Best Wishes
Phillip
On 20/07/2021 11:36, Phillip Wood via GitGitGadget wrote:
Thanks to Ævar and Elijah for their comments, I've reworded the commit
messages, addressed the enum initialization issue in patch 2 (now 3) and
added some perf tests.
There are two new patches in this round. The first patch is new and adds the
perf tests suggested by Ævar, the penultimate patch is also new and coverts
the existing code to use a designated initializer.
I've converted the benchmark results in the commit messages to use the new
tests, the percentage changes are broadly similar to the previous results
though I ended up running them on a different computer this time.
V1 cover letter:
The current implementation of diff --color-moved-ws=allow-indentation-change
is considerably slower that the implementation of diff --color-moved which
is in turn slower than a regular diff. This patch series starts with a
couple of bug fixes and then reworks the implementation of diff
--color-moved and diff --color-moved-ws=allow-indentation-change to speed
them up on large diffs. The time to run git diff --color-moved
--no-color-moved-ws v2.28.0 v2.29.0 is reduced by 33% and the time to run
git diff --color-moved --color-moved-ws=allow-indentation-change v2.28.0
v2.29.0 is reduced by 88%. There is a small slowdown for commit sized diffs
with --color-moved - the time to run git log -p --color-moved
--no-color-moved-ws --no-merges -n1000 v2.29.0 is increased by 2% on recent
processors. On older processors these patches reduce the running time in all
cases that I've tested. In general the larger the diff the larger the speed
up. As an extreme example the time to run diff --color-moved
--color-moved-ws=allow-indentation-change v2.25.0 v2.30.0 goes down from 8
minutes to 6 seconds.
Phillip Wood (12):
diff --color-moved: add perf tests
diff --color-moved=zebra: fix alternate coloring
diff --color-moved: avoid false short line matches and bad zerba
coloring
diff: simplify allow-indentation-change delta calculation
diff --color-moved-ws=allow-indentation-change: simplify and optimize
diff --color-moved: call comparison function directly
diff --color-moved: unify moved block growth functions
diff --color-moved: shrink potential moved blocks as we go
diff --color-moved: stop clearing potential moved blocks
diff --color-moved-ws=allow-indentation-change: improve hash lookups
diff: use designated initializers for emitted_diff_symbol
diff --color-moved: intern strings
diff.c | 377 ++++++++++++-------------------
t/perf/p4002-diff-color-moved.sh | 45 ++++
t/t4015-diff-whitespace.sh | 137 +++++++++++
3 files changed, 323 insertions(+), 236 deletions(-)
create mode 100755 t/perf/p4002-diff-color-moved.sh
base-commit: 211eca0895794362184da2be2a2d812d070719d3
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-981%2Fphillipwood%2Fwip%2Fdiff-color-moved-tweaks-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-981/phillipwood/wip/diff-color-moved-tweaks-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/981
Range-diff vs v1:
-: ----------- > 1: 8fc8914a37b diff --color-moved: add perf tests
1: 374dbebcbf2 ! 2: 9b4e4d2674a diff --color-moved=zerba: fix alternate coloring
@@ Metadata
Author: Phillip Wood [off-list ref]
## Commit message ##
- diff --color-moved=zerba: fix alternate coloring
+ diff --color-moved=zebra: fix alternate coloring
b0a2ba4776 ("diff --color-moved=zebra: be stricter with color
alternation", 2018-11-23) sought to avoid using the alternate colors
2: 3d02a0a91a0 ! 3: 5512145c70f diff --color-moved: avoid false short line matches and bad zerba coloring
@@ diff.c: static void mark_color_as_moved(struct diff_options *o,
int pmb_nr = 0, pmb_alloc = 0;
int n, flipped_block = 0, block_length = 0;
- enum diff_symbol last_symbol = 0;
-+ enum diff_symbol moved_symbol = 0;
++ enum diff_symbol moved_symbol = DIFF_SYMBOL_BINARY_DIFF_HEADER;
for (n = 0; n < o->emitted_symbols->nr; n++) {
@@ diff.c: static void mark_color_as_moved(struct diff_options *o,
- last_symbol = l->s;
+ }
+ if (!match) {
-+ moved_symbol = 0;
++ moved_symbol = DIFF_SYMBOL_BINARY_DIFF_HEADER;
continue;
}
@@ diff.c: static void mark_color_as_moved(struct diff_options *o,
+ if (pmb_nr)
+ moved_symbol = l->s;
+ else
-+ moved_symbol = 0;
++ moved_symbol = DIFF_SYMBOL_BINARY_DIFF_HEADER;
+
block_length = 0;
}
3: 30f0ed44768 = 4: 93fdef30d64 diff: simplify allow-indentation-change delta calculation
4: ebb6eec1d92 ! 5: 6b7a8aed4ec diff --color-moved-ws=allow-indentation-change: simplify and optimize
@@ Commit message
comparison to filter out the non-matching lines. Fixing this reduces
time to run
git diff --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
- by 88% and simplifies the code.
+ by 93% compared to master and simplifies the code.
- Before this change
- Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
- Time (mean ± σ): 9.978 s ± 0.042 s [User: 9.905 s, System: 0.057 s]
- Range (min … max): 9.917 s … 10.037 s 10 runs
-
- After this change
- Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
- Time (mean ± σ): 1.220 s ± 0.004 s [User: 1.160 s, System: 0.058 s]
- Range (min … max): 1.214 s … 1.226 s 10 runs
+ Test HEAD^ HEAD
+ ---------------------------------------------------------------------------------------------------------------
+ 4002.1: diff --no-color-moved --no-color-moved-ws large change 0.41( 0.38+0.03) 0.41(0.37+0.04) +0.0%
+ 4002.2: diff --color-moved --no-color-moved-ws large change 0.83( 0.79+0.04) 0.82(0.79+0.02) -1.2%
+ 4002.3: diff --color-moved-ws=allow-indentation-change large change 13.68(13.59+0.07) 0.92(0.89+0.03) -93.3%
+ 4002.4: log --no-color-moved --no-color-moved-ws 1.31( 1.22+0.08) 1.31(1.21+0.10) +0.0%
+ 4002.5: log --color-moved --no-color-moved-ws 1.47( 1.40+0.07) 1.47(1.36+0.10) +0.0%
+ 4002.6: log --color-moved-ws=allow-indentation-change 1.87( 1.77+0.09) 1.50(1.41+0.09) -19.8%
Signed-off-by: Phillip Wood [off-list ref]
5: cec0c2d04d7 ! 6: cfbdd447eee diff --color-moved: call comparison function directly
@@ Metadata
## Commit message ##
diff --color-moved: call comparison function directly
- Calling xdiff_compare_lines() directly rather than using a function
- pointer from the hash map reduces the time very slightly but more
- importantly it will allow us to easily combine pmb_advance_or_null()
- and pmb_advance_or_null_multi_match() in the next commit.
+ This change will allow us to easily combine pmb_advance_or_null() and
+ pmb_advance_or_null_multi_match() in the next commit. Calling
+ xdiff_compare_lines() directly rather than using a function pointer
+ from the hash map has little effect on the run time.
- Before this change
- Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
- Time (mean ± σ): 1.136 s ± 0.004 s [User: 1.079 s, System: 0.053 s]
- Range (min … max): 1.130 s … 1.141 s 10 runs
-
- After this change
- Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
- Time (mean ± σ): 1.118 s ± 0.003 s [User: 1.062 s, System: 0.053 s]
- Range (min … max): 1.114 s … 1.121 s 10 runs
+ Test HEAD^ HEAD
+ -------------------------------------------------------------------------------------------------------------
+ 4002.1: diff --no-color-moved --no-color-moved-ws large change 0.41(0.37+0.04) 0.41(0.39+0.02) +0.0%
+ 4002.2: diff --color-moved --no-color-moved-ws large change 0.82(0.79+0.02) 0.83(0.79+0.03) +1.2%
+ 4002.3: diff --color-moved-ws=allow-indentation-change large change 0.92(0.89+0.03) 0.91(0.85+0.05) -1.1%
+ 4002.4: log --no-color-moved --no-color-moved-ws 1.31(1.21+0.10) 1.33(1.22+0.10) +1.5%
+ 4002.5: log --color-moved --no-color-moved-ws 1.47(1.36+0.10) 1.47(1.39+0.08) +0.0%
+ 4002.6: log --color-moved-ws=allow-indentation-change 1.50(1.41+0.09) 1.51(1.42+0.09) +0.7%
Signed-off-by: Phillip Wood [off-list ref]
6: 050cef0081d = 7: 73ce9b54e86 diff --color-moved: unify moved block growth functions
7: 9390e9a66eb = 8: ef8ce0e6ebc diff --color-moved: shrink potential moved blocks as we go
8: 1de99ac2bc3 = 9: 9d0a042eae1 diff --color-moved: stop clearing potential moved blocks
9: 41cdedd6090 ! 10: dd365ad115f diff --color-moved-ws=allow-indentation-change: improve hash lookups
@@ Commit message
As libxdiff does not have a whitespace flag to ignore the indentation
the code for --color-moved-ws=allow-indentation-change uses
XDF_IGNORE_WHITESPACE and then filters out any hash lookups where
- there are non-indentation changes. This is filtering is inefficient as
+ there are non-indentation changes. This filtering is inefficient as
we have to perform another string comparison.
By using the offset data that we have already computed to skip the
indentation we can avoid using XDF_IGNORE_WHITESPACE and safely remove
- the extra checks which improves the performance by 14% and paves the
+ the extra checks which improves the performance by 11% and paves the
way for the elimination of string comparisons in the next commit.
- This change slightly increases the runtime of other --color-moved
+ This change slightly increases the run time of other --color-moved
modes. This could be avoided by using different comparison functions
- for the different modes but after the changes in the next commit there
- is no measurable benefit.
+ for the different modes but after the next two commits there is no
+ measurable benefit in doing so.
- Before this change
- Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
- Time (mean ± σ): 1.116 s ± 0.005 s [User: 1.057 s, System: 0.056 s]
- Range (min … max): 1.109 s … 1.123 s 10 runs
-
- Benchmark #2: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
- Time (mean ± σ): 1.216 s ± 0.005 s [User: 1.155 s, System: 0.059 s]
- Range (min … max): 1.206 s … 1.223 s 10 runs
-
- After this change
- Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
- Time (mean ± σ): 1.147 s ± 0.005 s [User: 1.085 s, System: 0.059 s]
- Range (min … max): 1.140 s … 1.154 s 10 runs
-
- Benchmark #2: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
- Time (mean ± σ): 1.048 s ± 0.005 s [User: 987.4 ms, System: 58.8 ms]
- Range (min … max): 1.043 s … 1.056 s 10 runs
+ Test HEAD^ HEAD
+ --------------------------------------------------------------------------------------------------------------
+ 4002.1: diff --no-color-moved --no-color-moved-ws large change 0.41(0.38+0.03) 0.41(0.36+0.04) +0.0%
+ 4002.2: diff --color-moved --no-color-moved-ws large change 0.82(0.76+0.05) 0.84(0.79+0.04) +2.4%
+ 4002.3: diff --color-moved-ws=allow-indentation-change large change 0.91(0.88+0.03) 0.81(0.74+0.06) -11.0%
+ 4002.4: log --no-color-moved --no-color-moved-ws 1.32(1.21+0.10) 1.31(1.19+0.11) -0.8%
+ 4002.5: log --color-moved --no-color-moved-ws 1.47(1.37+0.10) 1.47(1.36+0.11) +0.0%
+ 4002.6: log --color-moved-ws=allow-indentation-change 1.51(1.42+0.09) 1.48(1.37+0.10) -2.0%
Signed-off-by: Phillip Wood [off-list ref]
-: ----------- > 11: c160222ab3c diff: use designated initializers for emitted_diff_symbol
10: 220664dd907 ! 12: 753554587f9 diff --color-moved: intern strings
@@ Commit message
number of hash lookups a little (calculating the ids still involves
one hash lookup per line) but the main benefit is that when growing
blocks of potentially moved lines we can replace string comparisons
- which involve chasing a pointer with a simple integer comparison. On
- a large diff this commit reduces the time to run 'diff --color-moved'
- by 33% and 'diff --color-moved-ws=allow-indentation-change' by 20%.
+ which involve chasing a pointer with a simple integer comparison.
- Compared to master the time to run 'git log --patch --color-moved' is
- increased by 2% and 'git log --patch
- --color-moved-ws=allow-indentation-change' in reduced by 14%. These
- timings were performed on an i5-7200U, on an i5-3470 both commands are
- faster than master. The small speed decrease on commit sized diffs is
- unfortunate but I think it is small enough to be worth it for the
- gains on larger diffs.
+ On a large diff this commit reduces the time to run
+ diff --color-moved
+ by 33% and
+ diff --color-moved-ws=allow-indentation-change
+ by 26%. Compared to master the time to run
+ diff --color-moved-ws=allow-indentation-change
+ is now reduced by 95% and the overhead compared to --no-color-moved is
+ reduced to 50%.
- Large diff before this change:
- Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
- Time (mean ± σ): 1.147 s ± 0.005 s [User: 1.085 s, System: 0.059 s]
- Range (min … max): 1.140 s … 1.154 s 10 runs
+ Compared to the previous commit the time to run
+ git log --patch --color-moved
+ is increased slightly, but compared to master there is no change in
+ run time.
- Benchmark #2: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
- Time (mean ± σ): 1.048 s ± 0.005 s [User: 987.4 ms, System: 58.8 ms]
- Range (min … max): 1.043 s … 1.056 s 10 runs
+ Test HEAD^ HEAD
+ --------------------------------------------------------------------------------------------------------------
+ 4002.1: diff --no-color-moved --no-color-moved-ws large change 0.41(0.36+0.04) 0.41(0.37+0.03) +0.0%
+ 4002.2: diff --color-moved --no-color-moved-ws large change 0.83(0.79+0.03) 0.55(0.52+0.03) -33.7%
+ 4002.3: diff --color-moved-ws=allow-indentation-change large change 0.81(0.77+0.04) 0.60(0.55+0.05) -25.9%
+ 4002.4: log --no-color-moved --no-color-moved-ws 1.30(1.20+0.09) 1.31(1.22+0.08) +0.8%
+ 4002.5: log --color-moved --no-color-moved-ws 1.46(1.35+0.11) 1.47(1.30+0.16) +0.7%
+ 4002.6: log --color-moved-ws=allow-indentation-change 1.46(1.38+0.07) 1.47(1.34+0.13) +0.7%
- Large diff after this change
- Benchmark #1: bin-wrappers/git diff --diff-algorithm=myers --color-moved --no-color-moved-ws v2.28.0 v2.29.0
- Time (mean ± σ): 762.7 ms ± 2.8 ms [User: 707.5 ms, System: 53.7 ms]
- Range (min … max): 758.0 ms … 767.0 ms 10 runs
-
- Benchmark #2: bin-wrappers/git diff --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
- Time (mean ± σ): 831.7 ms ± 1.7 ms [User: 776.5 ms, System: 53.3 ms]
- Range (min … max): 829.2 ms … 835.1 ms 10 runs
-
- Small diffs on master
- Benchmark #1: bin-wrappers/git log -p --diff-algorithm=myers --color-moved --no-color-moved-ws --no-merges -n1000 v2.29.0
- Time (mean ± σ): 1.567 s ± 0.001 s [User: 1.443 s, System: 0.121 s]
- Range (min … max): 1.566 s … 1.571 s 10 runs
-
- Benchmark #2: bin-wrappers/git log -p --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change -n1000 --no-merges v2.29.0
- Time (mean ± σ): 1.865 s ± 0.008 s [User: 1.748 s, System: 0.112 s]
- Range (min … max): 1.857 s … 1.881 s 10 runs
-
- Small diffs after this change
- Benchmark #1: bin-wrappers/git log -p --diff-algorithm=myers --color-moved --no-color-moved-ws --no-merges -n1000 v2.29.0
- Time (mean ± σ): 1.597 s ± 0.003 s [User: 1.413 s, System: 0.179 s]
- Range (min … max): 1.591 s … 1.601 s 10 runs
-
- Benchmark #2: bin-wrappers/git log -p --diff-algorithm=myers --color-moved --color-moved-ws=allow-indentation-change -n1000 --no-merges v2.29.0
- Time (mean ± σ): 1.606 s ± 0.006 s [User: 1.420 s, System: 0.181 s]
- Range (min … max): 1.601 s … 1.622 s 10 runs
+ Test master HEAD
+ --------------------------------------------------------------------------------------------------------------
+ 4002.1: diff --no-color-moved --no-color-moved-ws large change 0.40( 0.36+0.03) 0.41(0.37+0.03) +2.5%
+ 4002.2: diff --color-moved --no-color-moved-ws large change 0.82( 0.77+0.04) 0.55(0.52+0.03) -32.9%
+ 4002.3: diff --color-moved-ws=allow-indentation-change large change 14.10(14.04+0.04) 0.60(0.55+0.05) -95.7%
+ 4002.4: log --no-color-moved --no-color-moved-ws 1.31( 1.21+0.09) 1.31(1.22+0.08) +0.0%
+ 4002.5: log --color-moved --no-color-moved-ws 1.47( 1.37+0.09) 1.47(1.30+0.16) +0.0%
+ 4002.6: log --color-moved-ws=allow-indentation-change 1.86( 1.76+0.10) 1.47(1.34+0.13) -21.0%
Signed-off-by: Phillip Wood [off-list ref]
@@ diff.c: static void mark_color_as_moved(struct diff_options *o,
ALLOC_GROW(pmb, pmb_nr + 1, pmb_alloc);
if (o->color_moved_ws_handling &
COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE)
-@@ diff.c: static void emit_diff_symbol_from_struct(struct diff_options *o,
- static void emit_diff_symbol(struct diff_options *o, enum diff_symbol s,
- const char *line, int len, unsigned flags)
- {
-- struct emitted_diff_symbol e = {line, len, flags, 0, 0, s};
-+ struct emitted_diff_symbol e = {line, len, flags, 0, 0, 0, s};
-
- if (o->emitted_symbols)
- append_emitted_diff_symbol(o, &e);
@@ diff.c: static void diff_flush_patch_all_file_pairs(struct diff_options *o)
if (o->emitted_symbols) {
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-10-27 12:04:28
From: Phillip Wood <redacted>
Add some tests so we can monitor changes to the performance of the
move detection code. The tests record the performance of a single
large diff and a sequence of smaller diffs.
Signed-off-by: Phillip Wood <redacted>
---
t/perf/p4002-diff-color-moved.sh | 45 ++++++++++++++++++++++++++++++++
1 file changed, 45 insertions(+)
create mode 100755 t/perf/p4002-diff-color-moved.sh
@@ -0,0 +1,45 @@+#!/bin/sh++test_description='Tests diff --color-moved performance'+../perf-lib.sh++test_perf_default_repo++if!gitrev-parse--verifyv2.29.0^{commit}>/dev/null+then+skip_all='skipping because tag v2.29.0 was not found'+test_done+fi++GIT_PAGER_IN_USE=1+test_exportGIT_PAGER_IN_USE++test_perf'diff --no-color-moved --no-color-moved-ws large change''+gitdiff--no-color-moved--no-color-moved-wsv2.28.0v2.29.0+'++test_perf'diff --color-moved --no-color-moved-ws large change''+gitdiff--color-moved=zebra--no-color-moved-wsv2.28.0v2.29.0+'++test_perf'diff --color-moved-ws=allow-indentation-change large change''+gitdiff--color-moved=zebra--color-moved-ws=allow-indentation-change\+v2.28.0v2.29.0+'++test_perf'log --no-color-moved --no-color-moved-ws''+gitlog--no-color-moved--no-color-moved-ws--no-merges--patch\+-n1000v2.29.0+'++test_perf'log --color-moved --no-color-moved-ws''+gitlog--color-moved=zebra--no-color-moved-ws--no-merges--patch\+-n1000v2.29.0+'++test_perf'log --color-moved-ws=allow-indentation-change''+gitlog--color-moved=zebra--color-moved-ws=allow-indentation-change\+--no-merges--patch-n1000v2.29.0+'++test_done
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-10-27 12:04:31
From: Phillip Wood <redacted>
If a block of potentially moved lines is not long enough then the
DIFF_SYMBOL_MOVED_LINE flag is cleared on the matching lines so they
are not marked as moved. To avoid problems when we start rewinding
after an unsuccessful match in a couple of commits time make sure all
the move related flags are cleared, not just DIFF_SYMBOL_MOVED_LINE.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 6 +++---
1 file changed, 3 insertions(+), 3 deletions(-)
@@ -1130,7 +1132,7 @@ static int adjust_last_block(struct diff_options *o, int n, int block_length)}}for(i=1;i<block_length+1;i++)-o->emitted_symbols->buf[n-i].flags&=~DIFF_SYMBOL_MOVED_LINE;+o->emitted_symbols->buf[n-i].flags&=~DIFF_SYMBOL_MOVED_LINE_ZEBRA_MASK;return0;}
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-10-27 12:04:33
From: Phillip Wood <redacted>
This code is quite heavily indented and having it in its own function
simplifies an upcoming change.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 51 ++++++++++++++++++++++++++++++++++-----------------
1 file changed, 34 insertions(+), 17 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-10-27 12:04:34
From: Phillip Wood <redacted>
diff --color-moved colors the two sides of the diff separately. It
walks through the diff and tries to find matches on the other side of
the diff for the current line. When it finds one or more matches it
starts a "potential moved block" (pmb) and marks the current line as
moved. Then as it walks through the diff it only looks for matches for
the current line in the lines following those in the pmb. When none of
the lines in the pmb match it checks how long the match is and if it
is too short it unmarks the lines as matched and goes back to finding
all the lines that match the current line. As the process of finding
matching lines restarts from the end of the block that was too short
it is possible to miss the start of a matching block on on side but
not the other. In the test added here "-two" would not be colored as
moved but "+two" would be.
Fix this by rewinding the current line when we reach the end of a
block that is too short. This is quadratic in the length of the
discarded block. While the discarded blocks are quite short on a large
diff this still has a significant impact on the performance of
--color-moved-ws=allow-indentation-change. The following commits
optimize the performance of the --color-moved machinery which
mitigates the performance impact of this commit. After the
optimization this commit has a negligible impact on performance.
Test HEAD^ HEAD
------------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38 (0.33+0.05) 0.39 (0.34+0.04) +2.6%
4002.2: diff --color-moved --no-color-moved-ws large change 0.80 (0.76+0.03) 0.86 (0.82+0.04) +7.5%
4002.3: diff --color-moved-ws=allow-indentation-change large change 14.22(14.17+0.04) 19.01(18.93+0.05) +33.7%
4002.4: log --no-color-moved --no-color-moved-ws 1.16 (1.06+0.09) 1.16 (1.07+0.07) +0.0%
4002.5: log --color-moved --no-color-moved-ws 1.31 (1.22+0.09) 1.32 (1.22+0.09) +0.8%
4002.6: log --color-moved-ws=allow-indentation-change 1.71 (1.61+0.09) 1.72 (1.63+0.08) +0.6%
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 28 ++++++++++++++++++-----
t/t4015-diff-whitespace.sh | 46 ++++++++++++++++++++++++++++++++++++++
2 files changed, 69 insertions(+), 5 deletions(-)
@@ -1833,6 +1833,52 @@ test_expect_success '--color-moved treats adjacent blocks as separate for MIN_ALtest_cmpexpectedactual'+test_expect_success'--color-moved rewinds for MIN_ALNUM_COUNT''+gitreset--hard&&+test_write_lines>file\+ABConetwothreefourfivesixsevenDEFGHIJ&&+gitaddfile&&+test_write_lines>file\+onetwoABCDEFGHIJtwothreefourfivesixseven&&+gitdiff--color-moved=zebra--file&&++gitdiff--color-moved=zebra--color--file>actual.raw&&+grep-v"index"actual.raw|test_decode_color>actual&&+cat>expected<<-\EOF&&+<BOLD>diff--gita/fileb/file<RESET>+<BOLD>---a/file<RESET>+<BOLD>+++b/file<RESET>+<CYAN>@@-1,13+1,8@@<RESET>+<GREEN>+<RESET><GREEN>one<RESET>+<GREEN>+<RESET><GREEN>two<RESET>+A<RESET>+B<RESET>+C<RESET>+<RED>-one<RESET>+<BOLD;MAGENTA>-two<RESET>+<BOLD;MAGENTA>-three<RESET>+<BOLD;MAGENTA>-four<RESET>+<BOLD;MAGENTA>-five<RESET>+<BOLD;MAGENTA>-six<RESET>+<BOLD;MAGENTA>-seven<RESET>+D<RESET>+E<RESET>+F<RESET>+<CYAN>@@-15,3+10,9@@<RESET><RESET>G<RESET>+H<RESET>+I<RESET>+J<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>two<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>three<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>four<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>five<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>six<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>seven<RESET>+EOF++test_cmpexpectedactual+'+ test_expect_success'move detection with submodules''test_create_repobananas&&echoripe>bananas/recipe&&
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-10-27 12:04:35
From: Phillip Wood <redacted>
b0a2ba4776 ("diff --color-moved=zebra: be stricter with color
alternation", 2018-11-23) sought to avoid using the alternate colors
unless there are two adjacent moved blocks of the same
sign. Unfortunately it contains two bugs that prevented it from fixing
the problem properly. Firstly `last_symbol` is reset at the start of
each iteration of the loop losing the symbol of the last line and
secondly when deciding whether to use the alternate color it should be
checking if the current line is the same sign of the last line, not a
different sign. The combination of the two errors means that we still
use the alternate color when we should do but we also use it when we
shouldn't. This is most noticable when using
--color-moved-ws=allow-indentation-change with hunks like
-this line gets indented
+ this line gets indented
where the post image is colored with newMovedAlternate rather than
newMoved. While this does not matter much, the next commit will change
the coloring to be correct in this case, so lets fix the bug here to
make it clear why the output is changing and add a regression test.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 4 +--
t/t4015-diff-whitespace.sh | 72 ++++++++++++++++++++++++++++++++++++++
2 files changed, 74 insertions(+), 2 deletions(-)
@@ -1442,6 +1442,78 @@ test_expect_success 'detect permutations inside moved code -- dimmed-zebra' 'test_cmpexpectedactual'+test_expect_success'zebra alternate color is only used when necessary''+cat>old.txt<<-\EOF&&+line1AshouldbemarkedasoldMovednewMovedAlternate+line1BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line2AshouldbemarkedasoldMovednewMovedAlternate+line2BshouldbemarkedasoldMovednewMovedAlternate+line3AshouldbemarkedasoldMovedAlternatenewMoved+line3BshouldbemarkedasoldMovedAlternatenewMoved+unchanged+line4AshouldbemarkedasoldMovednewMovedAlternate+line4BshouldbemarkedasoldMovednewMovedAlternate+line5AshouldbemarkedasoldMovedAlternatenewMoved+line5BshouldbemarkedasoldMovedAlternatenewMoved+line6AshouldbemarkedasoldMovednewMoved+line6BshouldbemarkedasoldMovednewMoved+EOF+cat>new.txt<<-\EOF&&+line1AshouldbemarkedasoldMovednewMovedAlternate+line1BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line3AshouldbemarkedasoldMovedAlternatenewMoved+line3BshouldbemarkedasoldMovedAlternatenewMoved+line2AshouldbemarkedasoldMovednewMovedAlternate+line2BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line6AshouldbemarkedasoldMovednewMoved+line6BshouldbemarkedasoldMovednewMoved+line4AshouldbemarkedasoldMovednewMovedAlternate+line4BshouldbemarkedasoldMovednewMovedAlternate+line5AshouldbemarkedasoldMovedAlternatenewMoved+line5BshouldbemarkedasoldMovedAlternatenewMoved+EOF+test_expect_code1gitdiff--no-index--color--color-moved=zebra\+--color-moved-ws=allow-indentation-change\+old.txtnew.txt>output&&+grep-vindexoutput|test_decode_color>actual&&+cat>expected<<-\EOF&&+<BOLD>diff--gita/old.txtb/new.txt<RESET>+<BOLD>---a/old.txt<RESET>+<BOLD>+++b/new.txt<RESET>+<CYAN>@@-1,14+1,14@@<RESET>+<BOLD;MAGENTA>-line1AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line1BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line1AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line1BshouldbemarkedasoldMovednewMovedAlternate<RESET>+unchanged<RESET>+<BOLD;MAGENTA>-line2AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line2BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;BLUE>-line3AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;BLUE>-line3BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line3AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line3BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line2AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line2BshouldbemarkedasoldMovednewMovedAlternate<RESET>+unchanged<RESET>+<BOLD;MAGENTA>-line4AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line4BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;BLUE>-line5AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;BLUE>-line5BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;MAGENTA>-line6AshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;MAGENTA>-line6BshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line6AshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line6BshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line4AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line4BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line5AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line5BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+EOF+test_cmpexpectedactual+'+ test_expect_success'cmd option assumes configured colored-moved''test_configcolor.diff.oldMoved"magenta"&&test_configcolor.diff.newMoved"cyan"&&
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-10-27 12:04:37
From: Phillip Wood <redacted>
When marking moved lines it is possible for a block of potential
matched lines to extend past a change in sign when there is a sequence
of added lines whose text matches the text of a sequence of deleted
and added lines. Most of the time either `match` will be NULL or
`pmb_advance_or_null()` will fail when the loop encounters a change of
sign but there are corner cases where `match` is non-NULL and
`pmb_advance_or_null()` successfully advances the moved block despite
the change in sign.
One consequence of this is highlighting a short line as moved when it
should not be. For example
-moved line # Correctly highlighted as moved
+short line # Wrongly highlighted as moved
context
+moved line # Correctly highlighted as moved
+short line
context
-short line
The other consequence is coloring a moved addition following a moved
deletion in the wrong color. In the example below the first "+moved
line 3" should be highlighted as newMoved not newMovedAlternate.
-moved line 1 # Correctly highlighted as oldMoved
-moved line 2 # Correctly highlighted as oldMovedAlternate
+moved line 3 # Wrongly highlighted as newMovedAlternate
context # Everything else is highlighted correctly
+moved line 2
+moved line 3
context
+moved line 1
-moved line 3
These false matches are more likely when using --color-moved-ws with
the exception of --color-moved-ws=allow-indentation-change which ties
the sign of the current whitespace delta to the sign of the line to
avoid this problem. The fix is to check that the sign of the new line
being matched is the same as the sign of the line that started the
block of potential matches.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 17 ++++++----
t/t4015-diff-whitespace.sh | 65 ++++++++++++++++++++++++++++++++++++++
2 files changed, 76 insertions(+), 6 deletions(-)
@@ -1514,6 +1514,71 @@ test_expect_success 'zebra alternate color is only used when necessary' 'test_cmpexpectedactual'+test_expect_success'short lines of opposite sign do not get marked as moved''+cat>old.txt<<-\EOF&&+thislineshouldbemarkedasmoved+unchanged+unchanged+unchanged+unchanged+tooshort+thislineshouldbemarkedasoldMovednewMoved+thislineshouldbemarkedasoldMovedAlternatenewMoved+unchanged1+unchanged2+unchanged3+unchanged4+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+EOF+cat>new.txt<<-\EOF&&+tooshort+unchanged+unchanged+thislineshouldbemarkedasmoved+tooshort+unchanged+unchanged+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+unchanged1+unchanged2+thislineshouldbemarkedasoldMovedAlternatenewMoved+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+unchanged3+thislineshouldbemarkedasoldMovednewMoved+unchanged4+EOF+test_expect_code1gitdiff--no-index--color--color-moved=zebra\+old.txtnew.txt>output&&catoutput&&+grep-vindexoutput|test_decode_color>actual&&+cat>expect<<-\EOF&&+<BOLD>diff--gita/old.txtb/new.txt<RESET>+<BOLD>---a/old.txt<RESET>+<BOLD>+++b/new.txt<RESET>+<CYAN>@@-1,13+1,15@@<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasmoved<RESET>+<GREEN>+<RESET><GREEN>tooshort<RESET>+unchanged<RESET>+unchanged<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasmoved<RESET>+<GREEN>+<RESET><GREEN>tooshort<RESET>+unchanged<RESET>+unchanged<RESET>+<RED>-tooshort<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;BLUE>-thislineshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+unchanged1<RESET>+unchanged2<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+unchanged3<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovednewMoved<RESET>+unchanged4<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+EOF+test_cmpexpectactual+'+ test_expect_success'cmd option assumes configured colored-moved''test_configcolor.diff.oldMoved"magenta"&&test_configcolor.diff.newMoved"cyan"&&
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-10-27 12:04:39
From: Phillip Wood <redacted>
Now that we reliably end a block when the sign changes we don't need
the whitespace delta calculation to rely on the sign.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 13 ++-----------
1 file changed, 2 insertions(+), 11 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-10-27 12:04:40
From: Phillip Wood <redacted>
If we already have a block of potentially moved lines then as we move
down the diff we need to check if the next line of each potentially
moved line matches the current line of the diff. The implementation of
--color-moved-ws=allow-indentation-change was needlessly performing
this check on all the lines in the diff that matched the current line
rather than just the current line. To exacerbate the problem finding
all the other lines in the diff that match the current line involves a
fuzzy lookup so we were wasting even more time performing a second
comparison to filter out the non-matching lines. Fixing this reduces
time to run
git diff --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
by 93% compared to master and simplifies the code.
Test HEAD^ HEAD
---------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38 (0.35+0.03) 0.38(0.35+0.03) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.86 (0.80+0.06) 0.87(0.83+0.04) +1.2%
4002.3: diff --color-moved-ws=allow-indentation-change large change 19.01(18.93+0.06) 0.97(0.92+0.04) -94.9%
4002.4: log --no-color-moved --no-color-moved-ws 1.16 (1.06+0.09) 1.17(1.06+0.10) +0.9%
4002.5: log --color-moved --no-color-moved-ws 1.32 (1.25+0.07) 1.32(1.24+0.08) +0.0%
4002.6: log --color-moved-ws=allow-indentation-change 1.71 (1.64+0.06) 1.36(1.25+0.10) -20.5%
Test master HEAD
---------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38 (0.33+0.05) 0.38(0.35+0.03) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.80 (0.75+0.04) 0.87(0.83+0.04) +8.7%
4002.3: diff --color-moved-ws=allow-indentation-change large change 14.20(14.15+0.05) 0.97(0.92+0.04) -93.2%
4002.4: log --no-color-moved --no-color-moved-ws 1.15 (1.05+0.09) 1.17(1.06+0.10) +1.7%
4002.5: log --color-moved --no-color-moved-ws 1.30 (1.19+0.11) 1.32(1.24+0.08) +1.5%
4002.6: log --color-moved-ws=allow-indentation-change 1.70 (1.63+0.06) 1.36(1.25+0.10) -20.0%
Helped-by: Jeff King [off-list ref]
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 70 +++++++++++++++++-----------------------------------------
1 file changed, 20 insertions(+), 50 deletions(-)
@@ -879,37 +879,21 @@ static int compute_ws_delta(const struct emitted_diff_symbol *a,return1;}-staticintcmp_in_block_with_wsd(conststructdiff_options*o,-conststructmoved_entry*cur,-conststructmoved_entry*match,-structmoved_block*pmb,-intn)-{-structemitted_diff_symbol*l=&o->emitted_symbols->buf[n];-intal=cur->es->len,bl=match->es->len,cl=l->len;+staticintcmp_in_block_with_wsd(conststructmoved_entry*cur,+conststructemitted_diff_symbol*l,+structmoved_block*pmb)+{+intal=cur->es->len,bl=l->len;constchar*a=cur->es->line,-*b=match->es->line,-*c=l->line;+*b=l->line;inta_off=cur->es->indent_off,a_width=cur->es->indent_width,-c_off=l->indent_off,-c_width=l->indent_width;+b_off=l->indent_off,+b_width=l->indent_width;intdelta;-/*-*Weneedtocheckif'cur'isequalto'match'.Asthose-*arefromthesame(+/-)side,wedonotneedtoadjustfor-*indentchanges.Howeverthesewerefoundusingfuzzy-*matchingsowedohavetocheckiftheyareequal.Herewe-*justcheckthelengths.Wedelaycallingmemcmp()tocheck-*thecontentsuntillaterasifthelengthcomparisonfora-*andcfailswecanavoidthecallalltogether.-*/-if(al!=bl)-return1;-/* If 'l' and 'cur' are both blank then they match. */-if(a_width==INDENT_BLANKLINE&&c_width==INDENT_BLANKLINE)+if(a_width==INDENT_BLANKLINE&&b_width==INDENT_BLANKLINE)return0;/*
@@ -918,7 +902,7 @@ static int cmp_in_block_with_wsd(const struct diff_options *o,*matchthoseofthecurrentblockandthatthetextof'l'and'cur'*aftertheindentationmatch.*/-delta=c_width-a_width;+delta=b_width-a_width;/**Ifthepreviouslinesofthisblockwereallblankthensetits
@@ -927,9 +911,8 @@ static int cmp_in_block_with_wsd(const struct diff_options *o,if(pmb->wsd==INDENT_BLANKLINE)pmb->wsd=delta;-return!(delta==pmb->wsd&&al-a_off==cl-c_off&&-!memcmp(a,b,al)&&!-memcmp(a+a_off,c+c_off,al-a_off));+return!(delta==pmb->wsd&&al-a_off==bl-b_off&&+!memcmp(a+a_off,b+b_off,al-a_off));}staticintmoved_entry_cmp(constvoid*hashmap_cmp_fn_data,
@@ -1030,36 +1013,23 @@ static void pmb_advance_or_null(struct diff_options *o,}staticvoidpmb_advance_or_null_multi_match(structdiff_options*o,-structmoved_entry*match,-structhashmap*hm,+structemitted_diff_symbol*l,structmoved_block*pmb,-intpmb_nr,intn)+intpmb_nr){inti;-char*got_match=xcalloc(1,pmb_nr);--hashmap_for_each_entry_from(hm,match,ent){-for(i=0;i<pmb_nr;i++){-structmoved_entry*prev=pmb[i].match;-structmoved_entry*cur=(prev&&prev->next_line)?-prev->next_line:NULL;-if(!cur)-continue;-if(!cmp_in_block_with_wsd(o,cur,match,&pmb[i],n))-got_match[i]|=1;-}-}for(i=0;i<pmb_nr;i++){-if(got_match[i]){+structmoved_entry*prev=pmb[i].match;+structmoved_entry*cur=(prev&&prev->next_line)?+prev->next_line:NULL;+if(cur&&!cmp_in_block_with_wsd(cur,l,&pmb[i])){/* Advance to the next line */-pmb[i].match=pmb[i].match->next_line;+pmb[i].match=cur;}else{moved_block_clear(&pmb[i]);}}--free(got_match);}staticintshrink_potential_moved_blocks(structmoved_block*pmb,
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-10-27 12:04:45
From: Phillip Wood <redacted>
This change will allow us to easily combine pmb_advance_or_null() and
pmb_advance_or_null_multi_match() in the next commit. Calling
xdiff_compare_lines() directly rather than using a function pointer
from the hash map has little effect on the run time.
Test HEAD^ HEAD
-------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38(0.35+0.03) 0.38(0.32+0.06) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.87(0.83+0.04) 0.87(0.80+0.06) +0.0%
4002.3: diff --color-moved-ws=allow-indentation-change large change 0.97(0.92+0.04) 0.97(0.93+0.04) +0.0%
4002.4: log --no-color-moved --no-color-moved-ws 1.17(1.06+0.10) 1.16(1.10+0.05) -0.9%
4002.5: log --color-moved --no-color-moved-ws 1.32(1.24+0.08) 1.31(1.22+0.09) -0.8%
4002.6: log --color-moved-ws=allow-indentation-change 1.36(1.25+0.10) 1.35(1.25+0.10) -0.7%
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 11 +++++++----
1 file changed, 7 insertions(+), 4 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-10-27 12:04:47
From: Phillip Wood <redacted>
After the last two commits pmb_advance_or_null() and
pmb_advance_or_null_multi_match() differ only in the comparison they
perform. Lets simplify the code by combining them into a single
function.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 41 ++++++++++++-----------------------------
1 file changed, 12 insertions(+), 29 deletions(-)
@@ -1002,36 +1002,23 @@ static void pmb_advance_or_null(struct diff_options *o,unsignedflags=o->color_moved_ws_handling&XDF_WHITESPACE_FLAGS;for(i=0;i<pmb_nr;i++){+intmatch;structmoved_entry*prev=pmb[i].match;structmoved_entry*cur=(prev&&prev->next_line)?prev->next_line:NULL;-if(cur&&xdiff_compare_lines(cur->es->line,cur->es->len,-l->line,l->len,-flags)){-pmb[i].match=cur;-}else{-pmb[i].match=NULL;-}-}-}-staticvoidpmb_advance_or_null_multi_match(structdiff_options*o,-structemitted_diff_symbol*l,-structmoved_block*pmb,-intpmb_nr)-{-inti;--for(i=0;i<pmb_nr;i++){-structmoved_entry*prev=pmb[i].match;-structmoved_entry*cur=(prev&&prev->next_line)?-prev->next_line:NULL;-if(cur&&!cmp_in_block_with_wsd(cur,l,&pmb[i])){-/* Advance to the next line */+if(o->color_moved_ws_handling&+COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE)+match=cur&&+!cmp_in_block_with_wsd(cur,l,&pmb[i]);+else+match=cur&&+xdiff_compare_lines(cur->es->line,cur->es->len,+l->line,l->len,flags);+if(match)pmb[i].match=cur;-}else{+elsemoved_block_clear(&pmb[i]);-}}}
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-10-27 12:04:49
From: Phillip Wood <redacted>
Rather than setting `match` to NULL and then looping over the list of
potential matched blocks for a second time to remove blocks with no
matches just filter out the blocks with no matches as we go.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 44 ++++++++------------------------------------
1 file changed, 8 insertions(+), 36 deletions(-)
@@ -1015,38 +1015,12 @@ static void pmb_advance_or_null(struct diff_options *o,match=cur&&xdiff_compare_lines(cur->es->line,cur->es->len,l->line,l->len,flags);-if(match)-pmb[i].match=cur;-else-moved_block_clear(&pmb[i]);-}-}--staticintshrink_potential_moved_blocks(structmoved_block*pmb,-intpmb_nr)-{-intlp,rp;--/* Shrink the set of potential block to the remaining running */-for(lp=0,rp=pmb_nr-1;lp<=rp;){-while(lp<pmb_nr&&pmb[lp].match)-lp++;-/* lp points at the first NULL now */--while(rp>-1&&!pmb[rp].match)-rp--;-/* rp points at the last non-NULL */--if(lp<pmb_nr&&rp>-1&&lp<rp){-pmb[lp]=pmb[rp];-memset(&pmb[rp],0,sizeof(pmb[rp]));-rp--;-lp++;+if(match){+pmb[j]=pmb[i];+pmb[j++].match=cur;}}--/* Remember the number of running sets */-returnrp+1;+*pmb_nr=j;}staticvoidfill_potential_moved_blocks(structdiff_options*o,
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-10-27 12:04:50
From: Phillip Wood <redacted>
moved_block_clear() was introduced in 74d156f4a1 ("diff
--color-moved-ws: fix double free crash", 2018-10-04) to free the
memory that was allocated when initializing a potential moved
block. However since 21536d077f ("diff --color-moved-ws: modify
allow-indentation-change", 2018-11-23) initializing a potential moved
block no longer allocates any memory. Up until the last commit we were
relying on moved_block_clear() to set the `match` pointer to NULL when
a block stopped matching, but since that commit we do not clear a
moved block that does not match so it does not make sense to clear
them elsewhere.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 11 -----------
1 file changed, 11 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-10-27 12:04:52
From: Phillip Wood <redacted>
As libxdiff does not have a whitespace flag to ignore the indentation
the code for --color-moved-ws=allow-indentation-change uses
XDF_IGNORE_WHITESPACE and then filters out any hash lookups where
there are non-indentation changes. This filtering is inefficient as
we have to perform another string comparison.
By using the offset data that we have already computed to skip the
indentation we can avoid using XDF_IGNORE_WHITESPACE and safely remove
the extra checks which improves the performance by 11% and paves the
way for the elimination of string comparisons in the next commit.
This change slightly increases the run time of other --color-moved
modes. This could be avoided by using different comparison functions
for the different modes but after the next two commits there is no
measurable benefit in doing so.
There is a change in behavior for lines that begin with a form-feed or
vertical-tab character. Since b46054b374 ("xdiff: use
git-compat-util", 2019-04-11) xdiff does not treat '\f' or '\v' as
whitespace characters. This means that lines starting with those
characters are never considered to be blank and never match a line
that does not start with the same character. After this patch a line
matching "^[\f\v\r]*[ \t]*$" is considered to be blank by
--color-moved-ws=allow-indentation-change and lines beginning
"^[\f\v\r]*[ \t]*" can match another line if the suffixes match. This
changes the output of git show for d18f76dccf ("compat/regex: use the
regex engine from gawk for compat", 2010-08-17) as some lines in the
pre-image before a moved block that contain '\f' are now considered
moved as well as they match a blank line before the moved lines in the
post-image. This commit updates one of the tests to reflect this
change.
Test HEAD^ HEAD
--------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38(0.33+0.05) 0.38(0.33+0.05) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.86(0.82+0.04) 0.88(0.84+0.04) +2.3%
4002.3: diff --color-moved-ws=allow-indentation-change large change 0.97(0.94+0.03) 0.86(0.81+0.05) -11.3%
4002.4: log --no-color-moved --no-color-moved-ws 1.16(1.07+0.09) 1.16(1.06+0.09) +0.0%
4002.5: log --color-moved --no-color-moved-ws 1.32(1.26+0.06) 1.33(1.27+0.05) +0.8%
4002.6: log --color-moved-ws=allow-indentation-change 1.35(1.29+0.06) 1.33(1.24+0.08) -1.5%
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 65 +++++++++++---------------------------
t/t4015-diff-whitespace.sh | 22 ++++++-------
2 files changed, 30 insertions(+), 57 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-10-27 12:05:02
From: Phillip Wood <redacted>
This makes it clearer which fields are being explicitly initialized
and will simplify the next commit where we add a new field to the
struct.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 4 +++-
1 file changed, 3 insertions(+), 1 deletion(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-10-27 12:05:03
From: Phillip Wood <redacted>
Taking inspiration from xdl_classify_record() assign an id to each
addition and deletion such that lines that match for the current
--color-moved-ws mode share the same unique id. This reduces the
number of hash lookups a little (calculating the ids still involves
one hash lookup per line) but the main benefit is that when growing
blocks of potentially moved lines we can replace string comparisons
which involve chasing a pointer with a simple integer comparison. On a
large diff this commit reduces the time to run 'diff --color-moved' by
37% compared to the previous commit and 31% compared to master, for
'diff --color-moved-ws=allow-indentation-change' the reduction is 28%
compared to the previous commit and 96% compared to master. There is
little change in the performance of 'git log --patch' as the diffs are
smaller.
Test HEAD^ HEAD
---------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38(0.33+0.05) 0.38(0.33+0.05) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.88(0.81+0.06) 0.55(0.50+0.04) -37.5%
4002.3: diff --color-moved-ws=allow-indentation-change large change 0.85(0.79+0.06) 0.61(0.54+0.06) -28.2%
4002.4: log --no-color-moved --no-color-moved-ws 1.16(1.07+0.08) 1.15(1.09+0.05) -0.9%
4002.5: log --color-moved --no-color-moved-ws 1.31(1.22+0.08) 1.29(1.19+0.09) -1.5%
4002.6: log --color-moved-ws=allow-indentation-change 1.32(1.24+0.08) 1.31(1.18+0.13) -0.8%
Test master HEAD
---------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38 (0.33+0.05) 0.38(0.33+0.05) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.80 (0.75+0.04) 0.55(0.50+0.04) -31.2%
4002.3: diff --color-moved-ws=allow-indentation-change large change 14.20(14.15+0.05) 0.61(0.54+0.06) -95.7%
4002.4: log --no-color-moved --no-color-moved-ws 1.15 (1.05+0.09) 1.15(1.09+0.05) +0.0%
4002.5: log --color-moved --no-color-moved-ws 1.30 (1.19+0.11) 1.29(1.19+0.09) -0.8%
4002.6: log --color-moved-ws=allow-indentation-change 1.70 (1.63+0.06) 1.31(1.18+0.13) -22.9%
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 174 +++++++++++++++++++++++++++++++--------------------------
1 file changed, 96 insertions(+), 78 deletions(-)
@@ -772,6 +773,7 @@ struct emitted_diff_symbol {intflags;intindent_off;/* Offset to first non-whitespace character */intindent_width;/* The visual width of the indentation */+unsignedid;enumdiff_symbols;};#define EMITTED_DIFF_SYMBOL_INIT {NULL}
@@ -865,24 +867,24 @@ static int cmp_in_block_with_wsd(const struct moved_entry *cur,conststructemitted_diff_symbol*l,structmoved_block*pmb){-intal=cur->es->len,bl=l->len;-constchar*a=cur->es->line,-*b=l->line;-inta_off=cur->es->indent_off,-a_width=cur->es->indent_width,-b_off=l->indent_off,-b_width=l->indent_width;+inta_width=cur->es->indent_width,b_width=l->indent_width;intdelta;-/* If 'l' and 'cur' are both blank then they match. */-if(a_width==INDENT_BLANKLINE&&b_width==INDENT_BLANKLINE)+/* The text of each line must match */+if(cur->es->id!=l->id)+return1;++/*+*If'l'and'cur'arebothblankthenwedon'tneedtocheckthe+*indent.Weonlyneedtocheckcurasweknowthestringsmatch.+**/+if(a_width==INDENT_BLANKLINE)return0;/**Theindentchangesoftheblockareknownandstoredinpmb->wsd;*howeverweneedtocheckiftheindentchangesofthecurrentline-*matchthoseofthecurrentblockandthatthetextof'l'and'cur'-*aftertheindentationmatch.+*matchthoseofthecurrentblock.*/delta=b_width-a_width;
@@ -893,22 +895,26 @@ static int cmp_in_block_with_wsd(const struct moved_entry *cur,if(pmb->wsd==INDENT_BLANKLINE)pmb->wsd=delta;-return!(delta==pmb->wsd&&al-a_off==bl-b_off&&-!memcmp(a+a_off,b+b_off,al-a_off));+returndelta!=pmb->wsd;}-staticintmoved_entry_cmp(constvoid*hashmap_cmp_fn_data,-conststructhashmap_entry*eptr,-conststructhashmap_entry*entry_or_key,-constvoid*keydata)+structinterned_diff_symbol{+structhashmap_entryent;+structemitted_diff_symbol*es;+};++staticintinterned_diff_symbol_cmp(constvoid*hashmap_cmp_fn_data,+conststructhashmap_entry*eptr,+conststructhashmap_entry*entry_or_key,+constvoid*keydata){conststructdiff_options*diffopt=hashmap_cmp_fn_data;conststructemitted_diff_symbol*a,*b;unsignedflags=diffopt->color_moved_ws_handling&XDF_WHITESPACE_FLAGS;-a=container_of(eptr,conststructmoved_entry,ent)->es;-b=container_of(entry_or_key,conststructmoved_entry,ent)->es;+a=container_of(eptr,conststructinterned_diff_symbol,ent)->es;+b=container_of(entry_or_key,conststructinterned_diff_symbol,ent)->es;return!xdiff_compare_lines(a->line+a->indent_off,a->len-a->indent_off,
@@ -916,55 +922,81 @@ static int moved_entry_cmp(const void *hashmap_cmp_fn_data,b->len-b->indent_off,flags);}-staticstructmoved_entry*prepare_entry(structdiff_options*o,-intline_no)+staticvoidprepare_entry(structdiff_options*o,structemitted_diff_symbol*l,+structinterned_diff_symbol*s){-structmoved_entry*ret=xmalloc(sizeof(*ret));-structemitted_diff_symbol*l=&o->emitted_symbols->buf[line_no];unsignedflags=o->color_moved_ws_handling&XDF_WHITESPACE_FLAGS;unsignedinthash=xdiff_hash_string(l->line+l->indent_off,l->len-l->indent_off,flags);-hashmap_entry_init(&ret->ent,hash);-ret->es=l;-ret->next_line=NULL;--returnret;+hashmap_entry_init(&s->ent,hash);+s->es=l;}-staticvoidadd_lines_to_move_detection(structdiff_options*o,-structhashmap*add_lines,-structhashmap*del_lines)+structmoved_entry_list{+structmoved_entry*add,*del;+};++staticstructmoved_entry_list*add_lines_to_move_detection(structdiff_options*o,+structmem_pool*entry_mem_pool){structmoved_entry*prev_line=NULL;-+structmem_poolinterned_pool;+structhashmapinterned_map;+structmoved_entry_list*entry_list=NULL;+size_tentry_list_alloc=0;+unsignedid=0;intn;++hashmap_init(&interned_map,interned_diff_symbol_cmp,o,8096);+mem_pool_init(&interned_pool,1024*1024);+for(n=0;n<o->emitted_symbols->nr;n++){-structhashmap*hm;-structmoved_entry*key;+structinterned_diff_symbolkey;+structemitted_diff_symbol*l=&o->emitted_symbols->buf[n];+structinterned_diff_symbol*s;+structmoved_entry*entry;-switch(o->emitted_symbols->buf[n].s){-caseDIFF_SYMBOL_PLUS:-hm=add_lines;-break;-caseDIFF_SYMBOL_MINUS:-hm=del_lines;-break;-default:+if(l->s!=DIFF_SYMBOL_PLUS&&l->s!=DIFF_SYMBOL_MINUS){prev_line=NULL;continue;}if(o->color_moved_ws_handling&COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE)-fill_es_indent_data(&o->emitted_symbols->buf[n]);-key=prepare_entry(o,n);-if(prev_line&&prev_line->es->s==o->emitted_symbols->buf[n].s)-prev_line->next_line=key;+fill_es_indent_data(l);-hashmap_add(hm,&key->ent);-prev_line=key;+prepare_entry(o,l,&key);+s=hashmap_get_entry(&interned_map,&key,ent,&key.ent);+if(s){+l->id=s->es->id;+}else{+l->id=id;+ALLOC_GROW_BY(entry_list,id,1,entry_list_alloc);+hashmap_add(&interned_map,+memcpy(mem_pool_alloc(&interned_pool,+sizeof(key)),+&key,sizeof(key)));+}+entry=mem_pool_alloc(entry_mem_pool,sizeof(*entry));+entry->es=l;+entry->next_line=NULL;+if(prev_line&&prev_line->es->s==l->s)+prev_line->next_line=entry;+prev_line=entry;+if(l->s==DIFF_SYMBOL_PLUS){+entry->next_match=entry_list[l->id].add;+entry_list[l->id].add=entry;+}else{+entry->next_match=entry_list[l->id].del;+entry_list[l->id].del=entry;+}}++hashmap_clear(&interned_map);+mem_pool_discard(&interned_pool,0);++returnentry_list;}staticvoidpmb_advance_or_null(structdiff_options*o,
@@ -1067,8 +1096,7 @@ static int adjust_last_block(struct diff_options *o, int n, int block_length)/* Find blocks of moved code, delegate actual coloring decision to helper */staticvoidmark_color_as_moved(structdiff_options*o,-structhashmap*add_lines,-structhashmap*del_lines)+structmoved_entry_list*entry_list){structmoved_block*pmb=NULL;/* potentially moved blocks */intpmb_nr=0,pmb_alloc=0;
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-11-16 09:49:50
Changes since V3:
* Patch 1 now allows the user to choose different endpoints for the diff
perf tests to facilitate testing with different repositories.
* Fixed the alignment of the perf results column headers in a couple of
patches.
Changes since V2:
* Patches 1-3 are new and fix an existing bug.
* Patch 8 includes Peff's unused parameter fix.
* Patch 11 has been updated to fix a bug fix in V2.
* Patch 13 has an expanded commit message explaining a change in behavior
for lines starting with a form-feed.
* Updated benchmark results.
The bug fix in patch 3 degrades the performance, but by the end of the
series the timings are the same as V2 - see the range diff.
V2 Cover Letter: Thanks to Ævar and Elijah for their comments, I've reworded
the commit messages, addressed the enum initialization issue in patch 2 (now
3) and added some perf tests.
There are two new patches in this round. The first patch is new and adds the
perf tests suggested by Ævar, the penultimate patch is also new and coverts
the existing code to use a designated initializer.
I've converted the benchmark results in the commit messages to use the new
tests, the percentage changes are broadly similar to the previous results
though I ended up running them on a different computer this time.
V1 cover letter:
The current implementation of diff --color-moved-ws=allow-indentation-change
is considerably slower that the implementation of diff --color-moved which
is in turn slower than a regular diff. This patch series starts with a
couple of bug fixes and then reworks the implementation of diff
--color-moved and diff --color-moved-ws=allow-indentation-change to speed
them up on large diffs. The time to run git diff --color-moved
--no-color-moved-ws v2.28.0 v2.29.0 is reduced by 33% and the time to run
git diff --color-moved --color-moved-ws=allow-indentation-change v2.28.0
v2.29.0 is reduced by 88%. There is a small slowdown for commit sized diffs
with --color-moved - the time to run git log -p --color-moved
--no-color-moved-ws --no-merges -n1000 v2.29.0 is increased by 2% on recent
processors. On older processors these patches reduce the running time in all
cases that I've tested. In general the larger the diff the larger the speed
up. As an extreme example the time to run diff --color-moved
--color-moved-ws=allow-indentation-change v2.25.0 v2.30.0 goes down from 8
minutes to 6 seconds.
Phillip Wood (15):
diff --color-moved: add perf tests
diff --color-moved: clear all flags on blocks that are too short
diff --color-moved: factor out function
diff --color-moved: rewind when discarding pmb
diff --color-moved=zebra: fix alternate coloring
diff --color-moved: avoid false short line matches and bad zerba
coloring
diff: simplify allow-indentation-change delta calculation
diff --color-moved-ws=allow-indentation-change: simplify and optimize
diff --color-moved: call comparison function directly
diff --color-moved: unify moved block growth functions
diff --color-moved: shrink potential moved blocks as we go
diff --color-moved: stop clearing potential moved blocks
diff --color-moved-ws=allow-indentation-change: improve hash lookups
diff: use designated initializers for emitted_diff_symbol
diff --color-moved: intern strings
diff.c | 431 +++++++++++++------------------
t/perf/p4002-diff-color-moved.sh | 57 ++++
t/t4015-diff-whitespace.sh | 205 ++++++++++++++-
3 files changed, 437 insertions(+), 256 deletions(-)
create mode 100755 t/perf/p4002-diff-color-moved.sh
base-commit: 211eca0895794362184da2be2a2d812d070719d3
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-981%2Fphillipwood%2Fwip%2Fdiff-color-moved-tweaks-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-981/phillipwood/wip/diff-color-moved-tweaks-v4
Pull-Request: https://github.com/gitgitgadget/git/pull/981
Range-diff vs v3:
1: 8fc8914a37b ! 1: 48ee03cf52a diff --color-moved: add perf tests
@@ Commit message
diff --color-moved: add perf tests
Add some tests so we can monitor changes to the performance of the
- move detection code. The tests record the performance of a single
- large diff and a sequence of smaller diffs.
+ move detection code. The tests record the performance --color-moved
+ and --color-moved-ws=allow-indentation-change for a large diff and a
+ sequence of smaller diffs. The range of commits used for the large
+ diff can be customized by exporting TEST_REV_A and TEST_REV_B when
+ running the test.
Signed-off-by: Phillip Wood [off-list ref]
@@ t/perf/p4002-diff-color-moved.sh (new)
+
+test_perf_default_repo
+
-+if ! git rev-parse --verify v2.29.0^{commit} >/dev/null
++# The endpoints of the diff can be customized by setting TEST_REV_A
++# and TEST_REV_B in the environment when running this test.
++
++rev="${TEST_REV_A:-v2.28.0}"
++if ! rev_a="$(git rev-parse --quiet --verify "$rev")"
++then
++ skip_all="skipping because '$rev' was not found. \
++ Use TEST_REV_A and TEST_REV_B to set the revs to use"
++ test_done
++fi
++rev="${TEST_REV_B:-v2.29.0}"
++if ! rev_b="$(git rev-parse --quiet --verify "$rev")"
+then
-+ skip_all='skipping because tag v2.29.0 was not found'
++ skip_all="skipping because '$rev' was not found. \
++ Use TEST_REV_A and TEST_REV_B to set the revs to use"
+ test_done
+fi
+
+GIT_PAGER_IN_USE=1
-+test_export GIT_PAGER_IN_USE
++test_export GIT_PAGER_IN_USE rev_a rev_b
+
+test_perf 'diff --no-color-moved --no-color-moved-ws large change' '
-+ git diff --no-color-moved --no-color-moved-ws v2.28.0 v2.29.0
++ git diff --no-color-moved --no-color-moved-ws $rev_a $rev_b
+'
+
+test_perf 'diff --color-moved --no-color-moved-ws large change' '
-+ git diff --color-moved=zebra --no-color-moved-ws v2.28.0 v2.29.0
++ git diff --color-moved=zebra --no-color-moved-ws $rev_a $rev_b
+'
+
+test_perf 'diff --color-moved-ws=allow-indentation-change large change' '
+ git diff --color-moved=zebra --color-moved-ws=allow-indentation-change \
-+ v2.28.0 v2.29.0
++ $rev_a $rev_b
+'
+
+test_perf 'log --no-color-moved --no-color-moved-ws' '
+ git log --no-color-moved --no-color-moved-ws --no-merges --patch \
-+ -n1000 v2.29.0
++ -n1000 $rev_b
+'
+
+test_perf 'log --color-moved --no-color-moved-ws' '
+ git log --color-moved=zebra --no-color-moved-ws --no-merges --patch \
-+ -n1000 v2.29.0
++ -n1000 $rev_b
+'
+
+test_perf 'log --color-moved-ws=allow-indentation-change' '
+ git log --color-moved=zebra --color-moved-ws=allow-indentation-change \
-+ --no-merges --patch -n1000 v2.29.0
++ --no-merges --patch -n1000 $rev_b
+'
+
+test_done
2: e9daed2360c = 2: 47c652716e8 diff --color-moved: clear all flags on blocks that are too short
3: 658aec2670c = 3: 99e38ba9de9 diff --color-moved: factor out function
4: a30f52d7f15 ! 4: 9ca71db61ae diff --color-moved: rewind when discarding pmb
@@ Commit message
mitigates the performance impact of this commit. After the
optimization this commit has a negligible impact on performance.
- Test HEAD^ HEAD
- ------------------------------------------------------------------------------------------------------------------
+ Test HEAD^ HEAD
+ -----------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38 (0.33+0.05) 0.39 (0.34+0.04) +2.6%
4002.2: diff --color-moved --no-color-moved-ws large change 0.80 (0.76+0.03) 0.86 (0.82+0.04) +7.5%
4002.3: diff --color-moved-ws=allow-indentation-change large change 14.22(14.17+0.04) 19.01(18.93+0.05) +33.7%
5: 1dde206b7b1 = 5: 56bb69af36e diff --color-moved=zebra: fix alternate coloring
6: 2717ff500d2 = 6: 10b11526206 diff --color-moved: avoid false short line matches and bad zerba coloring
7: f96fa71d53c = 7: c2e7b347257 diff: simplify allow-indentation-change delta calculation
8: 324b689c915 ! 8: d7bbc0041e0 diff --color-moved-ws=allow-indentation-change: simplify and optimize
@@ Commit message
git diff --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
by 93% compared to master and simplifies the code.
- Test HEAD^ HEAD
+ Test HEAD^ HEAD
---------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38 (0.35+0.03) 0.38(0.35+0.03) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.86 (0.80+0.06) 0.87(0.83+0.04) +1.2%
@@ Commit message
4002.5: log --color-moved --no-color-moved-ws 1.32 (1.25+0.07) 1.32(1.24+0.08) +0.0%
4002.6: log --color-moved-ws=allow-indentation-change 1.71 (1.64+0.06) 1.36(1.25+0.10) -20.5%
- Test master HEAD
+ Test master HEAD
---------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38 (0.33+0.05) 0.38(0.35+0.03) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.80 (0.75+0.04) 0.87(0.83+0.04) +8.7%
9: f142f33276a = 9: c3e5dce1910 diff --color-moved: call comparison function directly
10: 8f3ea865dd3 = 10: 9eb8cecd52a diff --color-moved: unify moved block growth functions
11: 078c04d4a66 = 11: 35e204e1578 diff --color-moved: shrink potential moved blocks as we go
12: 618371471a0 = 12: ec329e7946d diff --color-moved: stop clearing potential moved blocks
13: 6a8e9a2724d = 13: 6ec94134aaf diff --color-moved-ws=allow-indentation-change: improve hash lookups
14: ef98a6e7015 = 14: d44c5d734c3 diff: use designated initializers for emitted_diff_symbol
15: ae78c05f08d ! 15: 5177f669423 diff --color-moved: intern strings
@@ Commit message
little change in the performance of 'git log --patch' as the diffs are
smaller.
- Test HEAD^ HEAD
+ Test HEAD^ HEAD
---------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38(0.33+0.05) 0.38(0.33+0.05) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.88(0.81+0.06) 0.55(0.50+0.04) -37.5%
@@ Commit message
4002.5: log --color-moved --no-color-moved-ws 1.31(1.22+0.08) 1.29(1.19+0.09) -1.5%
4002.6: log --color-moved-ws=allow-indentation-change 1.32(1.24+0.08) 1.31(1.18+0.13) -0.8%
- Test master HEAD
+ Test master HEAD
---------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38 (0.33+0.05) 0.38(0.33+0.05) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.80 (0.75+0.04) 0.55(0.50+0.04) -31.2%
--
gitgitgadget
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-11-16 09:49:51
From: Phillip Wood <redacted>
Add some tests so we can monitor changes to the performance of the
move detection code. The tests record the performance --color-moved
and --color-moved-ws=allow-indentation-change for a large diff and a
sequence of smaller diffs. The range of commits used for the large
diff can be customized by exporting TEST_REV_A and TEST_REV_B when
running the test.
Signed-off-by: Phillip Wood <redacted>
---
t/perf/p4002-diff-color-moved.sh | 57 ++++++++++++++++++++++++++++++++
1 file changed, 57 insertions(+)
create mode 100755 t/perf/p4002-diff-color-moved.sh
@@ -0,0 +1,57 @@+#!/bin/sh++test_description='Tests diff --color-moved performance'+../perf-lib.sh++test_perf_default_repo++# The endpoints of the diff can be customized by setting TEST_REV_A+# and TEST_REV_B in the environment when running this test.++rev="${TEST_REV_A:-v2.28.0}"+if!rev_a="$(gitrev-parse--quiet--verify"$rev")"+then+skip_all="skipping because '$rev' was not found. \+UseTEST_REV_AandTEST_REV_Btosettherevstouse"+test_done+fi+rev="${TEST_REV_B:-v2.29.0}"+if!rev_b="$(gitrev-parse--quiet--verify"$rev")"+then+skip_all="skipping because '$rev' was not found. \+UseTEST_REV_AandTEST_REV_Btosettherevstouse"+test_done+fi++GIT_PAGER_IN_USE=1+test_exportGIT_PAGER_IN_USErev_arev_b++test_perf'diff --no-color-moved --no-color-moved-ws large change''+gitdiff--no-color-moved--no-color-moved-ws$rev_a$rev_b+'++test_perf'diff --color-moved --no-color-moved-ws large change''+gitdiff--color-moved=zebra--no-color-moved-ws$rev_a$rev_b+'++test_perf'diff --color-moved-ws=allow-indentation-change large change''+gitdiff--color-moved=zebra--color-moved-ws=allow-indentation-change\+$rev_a$rev_b+'++test_perf'log --no-color-moved --no-color-moved-ws''+gitlog--no-color-moved--no-color-moved-ws--no-merges--patch\+-n1000$rev_b+'++test_perf'log --color-moved --no-color-moved-ws''+gitlog--color-moved=zebra--no-color-moved-ws--no-merges--patch\+-n1000$rev_b+'++test_perf'log --color-moved-ws=allow-indentation-change''+gitlog--color-moved=zebra--color-moved-ws=allow-indentation-change\+--no-merges--patch-n1000$rev_b+'++test_done
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-11-16 09:49:55
From: Phillip Wood <redacted>
If a block of potentially moved lines is not long enough then the
DIFF_SYMBOL_MOVED_LINE flag is cleared on the matching lines so they
are not marked as moved. To avoid problems when we start rewinding
after an unsuccessful match in a couple of commits time make sure all
the move related flags are cleared, not just DIFF_SYMBOL_MOVED_LINE.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 6 +++---
1 file changed, 3 insertions(+), 3 deletions(-)
@@ -1130,7 +1132,7 @@ static int adjust_last_block(struct diff_options *o, int n, int block_length)}}for(i=1;i<block_length+1;i++)-o->emitted_symbols->buf[n-i].flags&=~DIFF_SYMBOL_MOVED_LINE;+o->emitted_symbols->buf[n-i].flags&=~DIFF_SYMBOL_MOVED_LINE_ZEBRA_MASK;return0;}
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-11-16 09:49:59
From: Phillip Wood <redacted>
This code is quite heavily indented and having it in its own function
simplifies an upcoming change.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 51 ++++++++++++++++++++++++++++++++++-----------------
1 file changed, 34 insertions(+), 17 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-11-16 09:50:02
From: Phillip Wood <redacted>
diff --color-moved colors the two sides of the diff separately. It
walks through the diff and tries to find matches on the other side of
the diff for the current line. When it finds one or more matches it
starts a "potential moved block" (pmb) and marks the current line as
moved. Then as it walks through the diff it only looks for matches for
the current line in the lines following those in the pmb. When none of
the lines in the pmb match it checks how long the match is and if it
is too short it unmarks the lines as matched and goes back to finding
all the lines that match the current line. As the process of finding
matching lines restarts from the end of the block that was too short
it is possible to miss the start of a matching block on on side but
not the other. In the test added here "-two" would not be colored as
moved but "+two" would be.
Fix this by rewinding the current line when we reach the end of a
block that is too short. This is quadratic in the length of the
discarded block. While the discarded blocks are quite short on a large
diff this still has a significant impact on the performance of
--color-moved-ws=allow-indentation-change. The following commits
optimize the performance of the --color-moved machinery which
mitigates the performance impact of this commit. After the
optimization this commit has a negligible impact on performance.
Test HEAD^ HEAD
-----------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38 (0.33+0.05) 0.39 (0.34+0.04) +2.6%
4002.2: diff --color-moved --no-color-moved-ws large change 0.80 (0.76+0.03) 0.86 (0.82+0.04) +7.5%
4002.3: diff --color-moved-ws=allow-indentation-change large change 14.22(14.17+0.04) 19.01(18.93+0.05) +33.7%
4002.4: log --no-color-moved --no-color-moved-ws 1.16 (1.06+0.09) 1.16 (1.07+0.07) +0.0%
4002.5: log --color-moved --no-color-moved-ws 1.31 (1.22+0.09) 1.32 (1.22+0.09) +0.8%
4002.6: log --color-moved-ws=allow-indentation-change 1.71 (1.61+0.09) 1.72 (1.63+0.08) +0.6%
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 28 ++++++++++++++++++-----
t/t4015-diff-whitespace.sh | 46 ++++++++++++++++++++++++++++++++++++++
2 files changed, 69 insertions(+), 5 deletions(-)
@@ -1833,6 +1833,52 @@ test_expect_success '--color-moved treats adjacent blocks as separate for MIN_ALtest_cmpexpectedactual'+test_expect_success'--color-moved rewinds for MIN_ALNUM_COUNT''+gitreset--hard&&+test_write_lines>file\+ABConetwothreefourfivesixsevenDEFGHIJ&&+gitaddfile&&+test_write_lines>file\+onetwoABCDEFGHIJtwothreefourfivesixseven&&+gitdiff--color-moved=zebra--file&&++gitdiff--color-moved=zebra--color--file>actual.raw&&+grep-v"index"actual.raw|test_decode_color>actual&&+cat>expected<<-\EOF&&+<BOLD>diff--gita/fileb/file<RESET>+<BOLD>---a/file<RESET>+<BOLD>+++b/file<RESET>+<CYAN>@@-1,13+1,8@@<RESET>+<GREEN>+<RESET><GREEN>one<RESET>+<GREEN>+<RESET><GREEN>two<RESET>+A<RESET>+B<RESET>+C<RESET>+<RED>-one<RESET>+<BOLD;MAGENTA>-two<RESET>+<BOLD;MAGENTA>-three<RESET>+<BOLD;MAGENTA>-four<RESET>+<BOLD;MAGENTA>-five<RESET>+<BOLD;MAGENTA>-six<RESET>+<BOLD;MAGENTA>-seven<RESET>+D<RESET>+E<RESET>+F<RESET>+<CYAN>@@-15,3+10,9@@<RESET><RESET>G<RESET>+H<RESET>+I<RESET>+J<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>two<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>three<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>four<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>five<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>six<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>seven<RESET>+EOF++test_cmpexpectedactual+'+ test_expect_success'move detection with submodules''test_create_repobananas&&echoripe>bananas/recipe&&
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-11-16 09:50:04
From: Phillip Wood <redacted>
b0a2ba4776 ("diff --color-moved=zebra: be stricter with color
alternation", 2018-11-23) sought to avoid using the alternate colors
unless there are two adjacent moved blocks of the same
sign. Unfortunately it contains two bugs that prevented it from fixing
the problem properly. Firstly `last_symbol` is reset at the start of
each iteration of the loop losing the symbol of the last line and
secondly when deciding whether to use the alternate color it should be
checking if the current line is the same sign of the last line, not a
different sign. The combination of the two errors means that we still
use the alternate color when we should do but we also use it when we
shouldn't. This is most noticable when using
--color-moved-ws=allow-indentation-change with hunks like
-this line gets indented
+ this line gets indented
where the post image is colored with newMovedAlternate rather than
newMoved. While this does not matter much, the next commit will change
the coloring to be correct in this case, so lets fix the bug here to
make it clear why the output is changing and add a regression test.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 4 +--
t/t4015-diff-whitespace.sh | 72 ++++++++++++++++++++++++++++++++++++++
2 files changed, 74 insertions(+), 2 deletions(-)
@@ -1442,6 +1442,78 @@ test_expect_success 'detect permutations inside moved code -- dimmed-zebra' 'test_cmpexpectedactual'+test_expect_success'zebra alternate color is only used when necessary''+cat>old.txt<<-\EOF&&+line1AshouldbemarkedasoldMovednewMovedAlternate+line1BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line2AshouldbemarkedasoldMovednewMovedAlternate+line2BshouldbemarkedasoldMovednewMovedAlternate+line3AshouldbemarkedasoldMovedAlternatenewMoved+line3BshouldbemarkedasoldMovedAlternatenewMoved+unchanged+line4AshouldbemarkedasoldMovednewMovedAlternate+line4BshouldbemarkedasoldMovednewMovedAlternate+line5AshouldbemarkedasoldMovedAlternatenewMoved+line5BshouldbemarkedasoldMovedAlternatenewMoved+line6AshouldbemarkedasoldMovednewMoved+line6BshouldbemarkedasoldMovednewMoved+EOF+cat>new.txt<<-\EOF&&+line1AshouldbemarkedasoldMovednewMovedAlternate+line1BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line3AshouldbemarkedasoldMovedAlternatenewMoved+line3BshouldbemarkedasoldMovedAlternatenewMoved+line2AshouldbemarkedasoldMovednewMovedAlternate+line2BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line6AshouldbemarkedasoldMovednewMoved+line6BshouldbemarkedasoldMovednewMoved+line4AshouldbemarkedasoldMovednewMovedAlternate+line4BshouldbemarkedasoldMovednewMovedAlternate+line5AshouldbemarkedasoldMovedAlternatenewMoved+line5BshouldbemarkedasoldMovedAlternatenewMoved+EOF+test_expect_code1gitdiff--no-index--color--color-moved=zebra\+--color-moved-ws=allow-indentation-change\+old.txtnew.txt>output&&+grep-vindexoutput|test_decode_color>actual&&+cat>expected<<-\EOF&&+<BOLD>diff--gita/old.txtb/new.txt<RESET>+<BOLD>---a/old.txt<RESET>+<BOLD>+++b/new.txt<RESET>+<CYAN>@@-1,14+1,14@@<RESET>+<BOLD;MAGENTA>-line1AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line1BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line1AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line1BshouldbemarkedasoldMovednewMovedAlternate<RESET>+unchanged<RESET>+<BOLD;MAGENTA>-line2AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line2BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;BLUE>-line3AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;BLUE>-line3BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line3AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line3BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line2AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line2BshouldbemarkedasoldMovednewMovedAlternate<RESET>+unchanged<RESET>+<BOLD;MAGENTA>-line4AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line4BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;BLUE>-line5AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;BLUE>-line5BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;MAGENTA>-line6AshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;MAGENTA>-line6BshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line6AshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line6BshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line4AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line4BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line5AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line5BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+EOF+test_cmpexpectedactual+'+ test_expect_success'cmd option assumes configured colored-moved''test_configcolor.diff.oldMoved"magenta"&&test_configcolor.diff.newMoved"cyan"&&
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-11-16 09:50:06
From: Phillip Wood <redacted>
When marking moved lines it is possible for a block of potential
matched lines to extend past a change in sign when there is a sequence
of added lines whose text matches the text of a sequence of deleted
and added lines. Most of the time either `match` will be NULL or
`pmb_advance_or_null()` will fail when the loop encounters a change of
sign but there are corner cases where `match` is non-NULL and
`pmb_advance_or_null()` successfully advances the moved block despite
the change in sign.
One consequence of this is highlighting a short line as moved when it
should not be. For example
-moved line # Correctly highlighted as moved
+short line # Wrongly highlighted as moved
context
+moved line # Correctly highlighted as moved
+short line
context
-short line
The other consequence is coloring a moved addition following a moved
deletion in the wrong color. In the example below the first "+moved
line 3" should be highlighted as newMoved not newMovedAlternate.
-moved line 1 # Correctly highlighted as oldMoved
-moved line 2 # Correctly highlighted as oldMovedAlternate
+moved line 3 # Wrongly highlighted as newMovedAlternate
context # Everything else is highlighted correctly
+moved line 2
+moved line 3
context
+moved line 1
-moved line 3
These false matches are more likely when using --color-moved-ws with
the exception of --color-moved-ws=allow-indentation-change which ties
the sign of the current whitespace delta to the sign of the line to
avoid this problem. The fix is to check that the sign of the new line
being matched is the same as the sign of the line that started the
block of potential matches.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 17 ++++++----
t/t4015-diff-whitespace.sh | 65 ++++++++++++++++++++++++++++++++++++++
2 files changed, 76 insertions(+), 6 deletions(-)
@@ -1514,6 +1514,71 @@ test_expect_success 'zebra alternate color is only used when necessary' 'test_cmpexpectedactual'+test_expect_success'short lines of opposite sign do not get marked as moved''+cat>old.txt<<-\EOF&&+thislineshouldbemarkedasmoved+unchanged+unchanged+unchanged+unchanged+tooshort+thislineshouldbemarkedasoldMovednewMoved+thislineshouldbemarkedasoldMovedAlternatenewMoved+unchanged1+unchanged2+unchanged3+unchanged4+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+EOF+cat>new.txt<<-\EOF&&+tooshort+unchanged+unchanged+thislineshouldbemarkedasmoved+tooshort+unchanged+unchanged+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+unchanged1+unchanged2+thislineshouldbemarkedasoldMovedAlternatenewMoved+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+unchanged3+thislineshouldbemarkedasoldMovednewMoved+unchanged4+EOF+test_expect_code1gitdiff--no-index--color--color-moved=zebra\+old.txtnew.txt>output&&catoutput&&+grep-vindexoutput|test_decode_color>actual&&+cat>expect<<-\EOF&&+<BOLD>diff--gita/old.txtb/new.txt<RESET>+<BOLD>---a/old.txt<RESET>+<BOLD>+++b/new.txt<RESET>+<CYAN>@@-1,13+1,15@@<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasmoved<RESET>+<GREEN>+<RESET><GREEN>tooshort<RESET>+unchanged<RESET>+unchanged<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasmoved<RESET>+<GREEN>+<RESET><GREEN>tooshort<RESET>+unchanged<RESET>+unchanged<RESET>+<RED>-tooshort<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;BLUE>-thislineshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+unchanged1<RESET>+unchanged2<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+unchanged3<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovednewMoved<RESET>+unchanged4<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+EOF+test_cmpexpectactual+'+ test_expect_success'cmd option assumes configured colored-moved''test_configcolor.diff.oldMoved"magenta"&&test_configcolor.diff.newMoved"cyan"&&
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-11-16 09:50:08
From: Phillip Wood <redacted>
Now that we reliably end a block when the sign changes we don't need
the whitespace delta calculation to rely on the sign.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 13 ++-----------
1 file changed, 2 insertions(+), 11 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-11-16 09:50:26
From: Phillip Wood <redacted>
If we already have a block of potentially moved lines then as we move
down the diff we need to check if the next line of each potentially
moved line matches the current line of the diff. The implementation of
--color-moved-ws=allow-indentation-change was needlessly performing
this check on all the lines in the diff that matched the current line
rather than just the current line. To exacerbate the problem finding
all the other lines in the diff that match the current line involves a
fuzzy lookup so we were wasting even more time performing a second
comparison to filter out the non-matching lines. Fixing this reduces
time to run
git diff --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
by 93% compared to master and simplifies the code.
Test HEAD^ HEAD
---------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38 (0.35+0.03) 0.38(0.35+0.03) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.86 (0.80+0.06) 0.87(0.83+0.04) +1.2%
4002.3: diff --color-moved-ws=allow-indentation-change large change 19.01(18.93+0.06) 0.97(0.92+0.04) -94.9%
4002.4: log --no-color-moved --no-color-moved-ws 1.16 (1.06+0.09) 1.17(1.06+0.10) +0.9%
4002.5: log --color-moved --no-color-moved-ws 1.32 (1.25+0.07) 1.32(1.24+0.08) +0.0%
4002.6: log --color-moved-ws=allow-indentation-change 1.71 (1.64+0.06) 1.36(1.25+0.10) -20.5%
Test master HEAD
---------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38 (0.33+0.05) 0.38(0.35+0.03) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.80 (0.75+0.04) 0.87(0.83+0.04) +8.7%
4002.3: diff --color-moved-ws=allow-indentation-change large change 14.20(14.15+0.05) 0.97(0.92+0.04) -93.2%
4002.4: log --no-color-moved --no-color-moved-ws 1.15 (1.05+0.09) 1.17(1.06+0.10) +1.7%
4002.5: log --color-moved --no-color-moved-ws 1.30 (1.19+0.11) 1.32(1.24+0.08) +1.5%
4002.6: log --color-moved-ws=allow-indentation-change 1.70 (1.63+0.06) 1.36(1.25+0.10) -20.0%
Helped-by: Jeff King [off-list ref]
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 70 +++++++++++++++++-----------------------------------------
1 file changed, 20 insertions(+), 50 deletions(-)
@@ -879,37 +879,21 @@ static int compute_ws_delta(const struct emitted_diff_symbol *a,return1;}-staticintcmp_in_block_with_wsd(conststructdiff_options*o,-conststructmoved_entry*cur,-conststructmoved_entry*match,-structmoved_block*pmb,-intn)-{-structemitted_diff_symbol*l=&o->emitted_symbols->buf[n];-intal=cur->es->len,bl=match->es->len,cl=l->len;+staticintcmp_in_block_with_wsd(conststructmoved_entry*cur,+conststructemitted_diff_symbol*l,+structmoved_block*pmb)+{+intal=cur->es->len,bl=l->len;constchar*a=cur->es->line,-*b=match->es->line,-*c=l->line;+*b=l->line;inta_off=cur->es->indent_off,a_width=cur->es->indent_width,-c_off=l->indent_off,-c_width=l->indent_width;+b_off=l->indent_off,+b_width=l->indent_width;intdelta;-/*-*Weneedtocheckif'cur'isequalto'match'.Asthose-*arefromthesame(+/-)side,wedonotneedtoadjustfor-*indentchanges.Howeverthesewerefoundusingfuzzy-*matchingsowedohavetocheckiftheyareequal.Herewe-*justcheckthelengths.Wedelaycallingmemcmp()tocheck-*thecontentsuntillaterasifthelengthcomparisonfora-*andcfailswecanavoidthecallalltogether.-*/-if(al!=bl)-return1;-/* If 'l' and 'cur' are both blank then they match. */-if(a_width==INDENT_BLANKLINE&&c_width==INDENT_BLANKLINE)+if(a_width==INDENT_BLANKLINE&&b_width==INDENT_BLANKLINE)return0;/*
@@ -918,7 +902,7 @@ static int cmp_in_block_with_wsd(const struct diff_options *o,*matchthoseofthecurrentblockandthatthetextof'l'and'cur'*aftertheindentationmatch.*/-delta=c_width-a_width;+delta=b_width-a_width;/**Ifthepreviouslinesofthisblockwereallblankthensetits
@@ -927,9 +911,8 @@ static int cmp_in_block_with_wsd(const struct diff_options *o,if(pmb->wsd==INDENT_BLANKLINE)pmb->wsd=delta;-return!(delta==pmb->wsd&&al-a_off==cl-c_off&&-!memcmp(a,b,al)&&!-memcmp(a+a_off,c+c_off,al-a_off));+return!(delta==pmb->wsd&&al-a_off==bl-b_off&&+!memcmp(a+a_off,b+b_off,al-a_off));}staticintmoved_entry_cmp(constvoid*hashmap_cmp_fn_data,
@@ -1030,36 +1013,23 @@ static void pmb_advance_or_null(struct diff_options *o,}staticvoidpmb_advance_or_null_multi_match(structdiff_options*o,-structmoved_entry*match,-structhashmap*hm,+structemitted_diff_symbol*l,structmoved_block*pmb,-intpmb_nr,intn)+intpmb_nr){inti;-char*got_match=xcalloc(1,pmb_nr);--hashmap_for_each_entry_from(hm,match,ent){-for(i=0;i<pmb_nr;i++){-structmoved_entry*prev=pmb[i].match;-structmoved_entry*cur=(prev&&prev->next_line)?-prev->next_line:NULL;-if(!cur)-continue;-if(!cmp_in_block_with_wsd(o,cur,match,&pmb[i],n))-got_match[i]|=1;-}-}for(i=0;i<pmb_nr;i++){-if(got_match[i]){+structmoved_entry*prev=pmb[i].match;+structmoved_entry*cur=(prev&&prev->next_line)?+prev->next_line:NULL;+if(cur&&!cmp_in_block_with_wsd(cur,l,&pmb[i])){/* Advance to the next line */-pmb[i].match=pmb[i].match->next_line;+pmb[i].match=cur;}else{moved_block_clear(&pmb[i]);}}--free(got_match);}staticintshrink_potential_moved_blocks(structmoved_block*pmb,
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-11-16 09:50:28
From: Phillip Wood <redacted>
Rather than setting `match` to NULL and then looping over the list of
potential matched blocks for a second time to remove blocks with no
matches just filter out the blocks with no matches as we go.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 44 ++++++++------------------------------------
1 file changed, 8 insertions(+), 36 deletions(-)
@@ -1015,38 +1015,12 @@ static void pmb_advance_or_null(struct diff_options *o,match=cur&&xdiff_compare_lines(cur->es->line,cur->es->len,l->line,l->len,flags);-if(match)-pmb[i].match=cur;-else-moved_block_clear(&pmb[i]);-}-}--staticintshrink_potential_moved_blocks(structmoved_block*pmb,-intpmb_nr)-{-intlp,rp;--/* Shrink the set of potential block to the remaining running */-for(lp=0,rp=pmb_nr-1;lp<=rp;){-while(lp<pmb_nr&&pmb[lp].match)-lp++;-/* lp points at the first NULL now */--while(rp>-1&&!pmb[rp].match)-rp--;-/* rp points at the last non-NULL */--if(lp<pmb_nr&&rp>-1&&lp<rp){-pmb[lp]=pmb[rp];-memset(&pmb[rp],0,sizeof(pmb[rp]));-rp--;-lp++;+if(match){+pmb[j]=pmb[i];+pmb[j++].match=cur;}}--/* Remember the number of running sets */-returnrp+1;+*pmb_nr=j;}staticvoidfill_potential_moved_blocks(structdiff_options*o,
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-11-16 09:50:28
From: Phillip Wood <redacted>
After the last two commits pmb_advance_or_null() and
pmb_advance_or_null_multi_match() differ only in the comparison they
perform. Lets simplify the code by combining them into a single
function.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 41 ++++++++++++-----------------------------
1 file changed, 12 insertions(+), 29 deletions(-)
@@ -1002,36 +1002,23 @@ static void pmb_advance_or_null(struct diff_options *o,unsignedflags=o->color_moved_ws_handling&XDF_WHITESPACE_FLAGS;for(i=0;i<pmb_nr;i++){+intmatch;structmoved_entry*prev=pmb[i].match;structmoved_entry*cur=(prev&&prev->next_line)?prev->next_line:NULL;-if(cur&&xdiff_compare_lines(cur->es->line,cur->es->len,-l->line,l->len,-flags)){-pmb[i].match=cur;-}else{-pmb[i].match=NULL;-}-}-}-staticvoidpmb_advance_or_null_multi_match(structdiff_options*o,-structemitted_diff_symbol*l,-structmoved_block*pmb,-intpmb_nr)-{-inti;--for(i=0;i<pmb_nr;i++){-structmoved_entry*prev=pmb[i].match;-structmoved_entry*cur=(prev&&prev->next_line)?-prev->next_line:NULL;-if(cur&&!cmp_in_block_with_wsd(cur,l,&pmb[i])){-/* Advance to the next line */+if(o->color_moved_ws_handling&+COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE)+match=cur&&+!cmp_in_block_with_wsd(cur,l,&pmb[i]);+else+match=cur&&+xdiff_compare_lines(cur->es->line,cur->es->len,+l->line,l->len,flags);+if(match)pmb[i].match=cur;-}else{+elsemoved_block_clear(&pmb[i]);-}}}
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-11-16 09:50:28
From: Phillip Wood <redacted>
This change will allow us to easily combine pmb_advance_or_null() and
pmb_advance_or_null_multi_match() in the next commit. Calling
xdiff_compare_lines() directly rather than using a function pointer
from the hash map has little effect on the run time.
Test HEAD^ HEAD
-------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38(0.35+0.03) 0.38(0.32+0.06) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.87(0.83+0.04) 0.87(0.80+0.06) +0.0%
4002.3: diff --color-moved-ws=allow-indentation-change large change 0.97(0.92+0.04) 0.97(0.93+0.04) +0.0%
4002.4: log --no-color-moved --no-color-moved-ws 1.17(1.06+0.10) 1.16(1.10+0.05) -0.9%
4002.5: log --color-moved --no-color-moved-ws 1.32(1.24+0.08) 1.31(1.22+0.09) -0.8%
4002.6: log --color-moved-ws=allow-indentation-change 1.36(1.25+0.10) 1.35(1.25+0.10) -0.7%
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 11 +++++++----
1 file changed, 7 insertions(+), 4 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-11-16 09:50:28
From: Phillip Wood <redacted>
moved_block_clear() was introduced in 74d156f4a1 ("diff
--color-moved-ws: fix double free crash", 2018-10-04) to free the
memory that was allocated when initializing a potential moved
block. However since 21536d077f ("diff --color-moved-ws: modify
allow-indentation-change", 2018-11-23) initializing a potential moved
block no longer allocates any memory. Up until the last commit we were
relying on moved_block_clear() to set the `match` pointer to NULL when
a block stopped matching, but since that commit we do not clear a
moved block that does not match so it does not make sense to clear
them elsewhere.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 11 -----------
1 file changed, 11 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-11-16 09:50:28
From: Phillip Wood <redacted>
As libxdiff does not have a whitespace flag to ignore the indentation
the code for --color-moved-ws=allow-indentation-change uses
XDF_IGNORE_WHITESPACE and then filters out any hash lookups where
there are non-indentation changes. This filtering is inefficient as
we have to perform another string comparison.
By using the offset data that we have already computed to skip the
indentation we can avoid using XDF_IGNORE_WHITESPACE and safely remove
the extra checks which improves the performance by 11% and paves the
way for the elimination of string comparisons in the next commit.
This change slightly increases the run time of other --color-moved
modes. This could be avoided by using different comparison functions
for the different modes but after the next two commits there is no
measurable benefit in doing so.
There is a change in behavior for lines that begin with a form-feed or
vertical-tab character. Since b46054b374 ("xdiff: use
git-compat-util", 2019-04-11) xdiff does not treat '\f' or '\v' as
whitespace characters. This means that lines starting with those
characters are never considered to be blank and never match a line
that does not start with the same character. After this patch a line
matching "^[\f\v\r]*[ \t]*$" is considered to be blank by
--color-moved-ws=allow-indentation-change and lines beginning
"^[\f\v\r]*[ \t]*" can match another line if the suffixes match. This
changes the output of git show for d18f76dccf ("compat/regex: use the
regex engine from gawk for compat", 2010-08-17) as some lines in the
pre-image before a moved block that contain '\f' are now considered
moved as well as they match a blank line before the moved lines in the
post-image. This commit updates one of the tests to reflect this
change.
Test HEAD^ HEAD
--------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38(0.33+0.05) 0.38(0.33+0.05) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.86(0.82+0.04) 0.88(0.84+0.04) +2.3%
4002.3: diff --color-moved-ws=allow-indentation-change large change 0.97(0.94+0.03) 0.86(0.81+0.05) -11.3%
4002.4: log --no-color-moved --no-color-moved-ws 1.16(1.07+0.09) 1.16(1.06+0.09) +0.0%
4002.5: log --color-moved --no-color-moved-ws 1.32(1.26+0.06) 1.33(1.27+0.05) +0.8%
4002.6: log --color-moved-ws=allow-indentation-change 1.35(1.29+0.06) 1.33(1.24+0.08) -1.5%
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 65 +++++++++++---------------------------
t/t4015-diff-whitespace.sh | 22 ++++++-------
2 files changed, 30 insertions(+), 57 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-11-16 09:50:28
From: Phillip Wood <redacted>
This makes it clearer which fields are being explicitly initialized
and will simplify the next commit where we add a new field to the
struct.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 4 +++-
1 file changed, 3 insertions(+), 1 deletion(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-11-16 09:50:32
From: Phillip Wood <redacted>
Taking inspiration from xdl_classify_record() assign an id to each
addition and deletion such that lines that match for the current
--color-moved-ws mode share the same unique id. This reduces the
number of hash lookups a little (calculating the ids still involves
one hash lookup per line) but the main benefit is that when growing
blocks of potentially moved lines we can replace string comparisons
which involve chasing a pointer with a simple integer comparison. On a
large diff this commit reduces the time to run 'diff --color-moved' by
37% compared to the previous commit and 31% compared to master, for
'diff --color-moved-ws=allow-indentation-change' the reduction is 28%
compared to the previous commit and 96% compared to master. There is
little change in the performance of 'git log --patch' as the diffs are
smaller.
Test HEAD^ HEAD
---------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38(0.33+0.05) 0.38(0.33+0.05) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.88(0.81+0.06) 0.55(0.50+0.04) -37.5%
4002.3: diff --color-moved-ws=allow-indentation-change large change 0.85(0.79+0.06) 0.61(0.54+0.06) -28.2%
4002.4: log --no-color-moved --no-color-moved-ws 1.16(1.07+0.08) 1.15(1.09+0.05) -0.9%
4002.5: log --color-moved --no-color-moved-ws 1.31(1.22+0.08) 1.29(1.19+0.09) -1.5%
4002.6: log --color-moved-ws=allow-indentation-change 1.32(1.24+0.08) 1.31(1.18+0.13) -0.8%
Test master HEAD
---------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38 (0.33+0.05) 0.38(0.33+0.05) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.80 (0.75+0.04) 0.55(0.50+0.04) -31.2%
4002.3: diff --color-moved-ws=allow-indentation-change large change 14.20(14.15+0.05) 0.61(0.54+0.06) -95.7%
4002.4: log --no-color-moved --no-color-moved-ws 1.15 (1.05+0.09) 1.15(1.09+0.05) +0.0%
4002.5: log --color-moved --no-color-moved-ws 1.30 (1.19+0.11) 1.29(1.19+0.09) -0.8%
4002.6: log --color-moved-ws=allow-indentation-change 1.70 (1.63+0.06) 1.31(1.18+0.13) -22.9%
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 174 +++++++++++++++++++++++++++++++--------------------------
1 file changed, 96 insertions(+), 78 deletions(-)
@@ -772,6 +773,7 @@ struct emitted_diff_symbol {intflags;intindent_off;/* Offset to first non-whitespace character */intindent_width;/* The visual width of the indentation */+unsignedid;enumdiff_symbols;};#define EMITTED_DIFF_SYMBOL_INIT {NULL}
@@ -865,24 +867,24 @@ static int cmp_in_block_with_wsd(const struct moved_entry *cur,conststructemitted_diff_symbol*l,structmoved_block*pmb){-intal=cur->es->len,bl=l->len;-constchar*a=cur->es->line,-*b=l->line;-inta_off=cur->es->indent_off,-a_width=cur->es->indent_width,-b_off=l->indent_off,-b_width=l->indent_width;+inta_width=cur->es->indent_width,b_width=l->indent_width;intdelta;-/* If 'l' and 'cur' are both blank then they match. */-if(a_width==INDENT_BLANKLINE&&b_width==INDENT_BLANKLINE)+/* The text of each line must match */+if(cur->es->id!=l->id)+return1;++/*+*If'l'and'cur'arebothblankthenwedon'tneedtocheckthe+*indent.Weonlyneedtocheckcurasweknowthestringsmatch.+**/+if(a_width==INDENT_BLANKLINE)return0;/**Theindentchangesoftheblockareknownandstoredinpmb->wsd;*howeverweneedtocheckiftheindentchangesofthecurrentline-*matchthoseofthecurrentblockandthatthetextof'l'and'cur'-*aftertheindentationmatch.+*matchthoseofthecurrentblock.*/delta=b_width-a_width;
@@ -893,22 +895,26 @@ static int cmp_in_block_with_wsd(const struct moved_entry *cur,if(pmb->wsd==INDENT_BLANKLINE)pmb->wsd=delta;-return!(delta==pmb->wsd&&al-a_off==bl-b_off&&-!memcmp(a+a_off,b+b_off,al-a_off));+returndelta!=pmb->wsd;}-staticintmoved_entry_cmp(constvoid*hashmap_cmp_fn_data,-conststructhashmap_entry*eptr,-conststructhashmap_entry*entry_or_key,-constvoid*keydata)+structinterned_diff_symbol{+structhashmap_entryent;+structemitted_diff_symbol*es;+};++staticintinterned_diff_symbol_cmp(constvoid*hashmap_cmp_fn_data,+conststructhashmap_entry*eptr,+conststructhashmap_entry*entry_or_key,+constvoid*keydata){conststructdiff_options*diffopt=hashmap_cmp_fn_data;conststructemitted_diff_symbol*a,*b;unsignedflags=diffopt->color_moved_ws_handling&XDF_WHITESPACE_FLAGS;-a=container_of(eptr,conststructmoved_entry,ent)->es;-b=container_of(entry_or_key,conststructmoved_entry,ent)->es;+a=container_of(eptr,conststructinterned_diff_symbol,ent)->es;+b=container_of(entry_or_key,conststructinterned_diff_symbol,ent)->es;return!xdiff_compare_lines(a->line+a->indent_off,a->len-a->indent_off,
@@ -916,55 +922,81 @@ static int moved_entry_cmp(const void *hashmap_cmp_fn_data,b->len-b->indent_off,flags);}-staticstructmoved_entry*prepare_entry(structdiff_options*o,-intline_no)+staticvoidprepare_entry(structdiff_options*o,structemitted_diff_symbol*l,+structinterned_diff_symbol*s){-structmoved_entry*ret=xmalloc(sizeof(*ret));-structemitted_diff_symbol*l=&o->emitted_symbols->buf[line_no];unsignedflags=o->color_moved_ws_handling&XDF_WHITESPACE_FLAGS;unsignedinthash=xdiff_hash_string(l->line+l->indent_off,l->len-l->indent_off,flags);-hashmap_entry_init(&ret->ent,hash);-ret->es=l;-ret->next_line=NULL;--returnret;+hashmap_entry_init(&s->ent,hash);+s->es=l;}-staticvoidadd_lines_to_move_detection(structdiff_options*o,-structhashmap*add_lines,-structhashmap*del_lines)+structmoved_entry_list{+structmoved_entry*add,*del;+};++staticstructmoved_entry_list*add_lines_to_move_detection(structdiff_options*o,+structmem_pool*entry_mem_pool){structmoved_entry*prev_line=NULL;-+structmem_poolinterned_pool;+structhashmapinterned_map;+structmoved_entry_list*entry_list=NULL;+size_tentry_list_alloc=0;+unsignedid=0;intn;++hashmap_init(&interned_map,interned_diff_symbol_cmp,o,8096);+mem_pool_init(&interned_pool,1024*1024);+for(n=0;n<o->emitted_symbols->nr;n++){-structhashmap*hm;-structmoved_entry*key;+structinterned_diff_symbolkey;+structemitted_diff_symbol*l=&o->emitted_symbols->buf[n];+structinterned_diff_symbol*s;+structmoved_entry*entry;-switch(o->emitted_symbols->buf[n].s){-caseDIFF_SYMBOL_PLUS:-hm=add_lines;-break;-caseDIFF_SYMBOL_MINUS:-hm=del_lines;-break;-default:+if(l->s!=DIFF_SYMBOL_PLUS&&l->s!=DIFF_SYMBOL_MINUS){prev_line=NULL;continue;}if(o->color_moved_ws_handling&COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE)-fill_es_indent_data(&o->emitted_symbols->buf[n]);-key=prepare_entry(o,n);-if(prev_line&&prev_line->es->s==o->emitted_symbols->buf[n].s)-prev_line->next_line=key;+fill_es_indent_data(l);-hashmap_add(hm,&key->ent);-prev_line=key;+prepare_entry(o,l,&key);+s=hashmap_get_entry(&interned_map,&key,ent,&key.ent);+if(s){+l->id=s->es->id;+}else{+l->id=id;+ALLOC_GROW_BY(entry_list,id,1,entry_list_alloc);+hashmap_add(&interned_map,+memcpy(mem_pool_alloc(&interned_pool,+sizeof(key)),+&key,sizeof(key)));+}+entry=mem_pool_alloc(entry_mem_pool,sizeof(*entry));+entry->es=l;+entry->next_line=NULL;+if(prev_line&&prev_line->es->s==l->s)+prev_line->next_line=entry;+prev_line=entry;+if(l->s==DIFF_SYMBOL_PLUS){+entry->next_match=entry_list[l->id].add;+entry_list[l->id].add=entry;+}else{+entry->next_match=entry_list[l->id].del;+entry_list[l->id].del=entry;+}}++hashmap_clear(&interned_map);+mem_pool_discard(&interned_pool,0);++returnentry_list;}staticvoidpmb_advance_or_null(structdiff_options*o,
@@ -1067,8 +1096,7 @@ static int adjust_last_block(struct diff_options *o, int n, int block_length)/* Find blocks of moved code, delegate actual coloring decision to helper */staticvoidmark_color_as_moved(structdiff_options*o,-structhashmap*add_lines,-structhashmap*del_lines)+structmoved_entry_list*entry_list){structmoved_block*pmb=NULL;/* potentially moved blocks */intpmb_nr=0,pmb_alloc=0;
From: Johannes Schindelin <hidden> Date: 2021-11-22 13:35:04
Hi Phillip,
On Tue, 16 Nov 2021, Phillip Wood via GitGitGadget wrote:
From: Phillip Wood <redacted>
b0a2ba4776 ("diff --color-moved=zebra: be stricter with color
alternation", 2018-11-23) sought to avoid using the alternate colors
unless there are two adjacent moved blocks of the same
sign. Unfortunately it contains two bugs that prevented it from fixing
the problem properly. Firstly `last_symbol` is reset at the start of
each iteration of the loop losing the symbol of the last line and
secondly when deciding whether to use the alternate color it should be
checking if the current line is the same sign of the last line, not a
different sign. The combination of the two errors means that we still
use the alternate color when we should do but we also use it when we
shouldn't. This is most noticable when using
--color-moved-ws=allow-indentation-change with hunks like
-this line gets indented
+ this line gets indented
where the post image is colored with newMovedAlternate rather than
newMoved. While this does not matter much, the next commit will change
the coloring to be correct in this case, so lets fix the bug here to
make it clear why the output is changing and add a regression test.
What an excellent commit message!
Thank you,
Dscho
@@ -1442,6 +1442,78 @@ test_expect_success 'detect permutations inside moved code -- dimmed-zebra' 'test_cmpexpectedactual'+test_expect_success'zebra alternate color is only used when necessary''+cat>old.txt<<-\EOF&&+line1AshouldbemarkedasoldMovednewMovedAlternate+line1BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line2AshouldbemarkedasoldMovednewMovedAlternate+line2BshouldbemarkedasoldMovednewMovedAlternate+line3AshouldbemarkedasoldMovedAlternatenewMoved+line3BshouldbemarkedasoldMovedAlternatenewMoved+unchanged+line4AshouldbemarkedasoldMovednewMovedAlternate+line4BshouldbemarkedasoldMovednewMovedAlternate+line5AshouldbemarkedasoldMovedAlternatenewMoved+line5BshouldbemarkedasoldMovedAlternatenewMoved+line6AshouldbemarkedasoldMovednewMoved+line6BshouldbemarkedasoldMovednewMoved+EOF+cat>new.txt<<-\EOF&&+line1AshouldbemarkedasoldMovednewMovedAlternate+line1BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line3AshouldbemarkedasoldMovedAlternatenewMoved+line3BshouldbemarkedasoldMovedAlternatenewMoved+line2AshouldbemarkedasoldMovednewMovedAlternate+line2BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line6AshouldbemarkedasoldMovednewMoved+line6BshouldbemarkedasoldMovednewMoved+line4AshouldbemarkedasoldMovednewMovedAlternate+line4BshouldbemarkedasoldMovednewMovedAlternate+line5AshouldbemarkedasoldMovedAlternatenewMoved+line5BshouldbemarkedasoldMovedAlternatenewMoved+EOF+test_expect_code1gitdiff--no-index--color--color-moved=zebra\+--color-moved-ws=allow-indentation-change\+old.txtnew.txt>output&&+grep-vindexoutput|test_decode_color>actual&&+cat>expected<<-\EOF&&+<BOLD>diff--gita/old.txtb/new.txt<RESET>+<BOLD>---a/old.txt<RESET>+<BOLD>+++b/new.txt<RESET>+<CYAN>@@-1,14+1,14@@<RESET>+<BOLD;MAGENTA>-line1AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line1BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line1AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line1BshouldbemarkedasoldMovednewMovedAlternate<RESET>+unchanged<RESET>+<BOLD;MAGENTA>-line2AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line2BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;BLUE>-line3AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;BLUE>-line3BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line3AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line3BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line2AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line2BshouldbemarkedasoldMovednewMovedAlternate<RESET>+unchanged<RESET>+<BOLD;MAGENTA>-line4AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line4BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;BLUE>-line5AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;BLUE>-line5BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;MAGENTA>-line6AshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;MAGENTA>-line6BshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line6AshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line6BshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line4AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line4BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line5AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line5BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+EOF+test_cmpexpectedactual+'+ test_expect_success'cmd option assumes configured colored-moved''test_configcolor.diff.oldMoved"magenta"&&test_configcolor.diff.newMoved"cyan"&&--
From: Johannes Schindelin <hidden> Date: 2021-11-22 14:18:47
Hi Phillip,
The commit's oneline has a typo: zerba instead of zebra.
On Tue, 16 Nov 2021, Phillip Wood via GitGitGadget wrote:
quoted hunk
From: Phillip Wood <redacted>
When marking moved lines it is possible for a block of potential
matched lines to extend past a change in sign when there is a sequence
of added lines whose text matches the text of a sequence of deleted
and added lines. Most of the time either `match` will be NULL or
`pmb_advance_or_null()` will fail when the loop encounters a change of
sign but there are corner cases where `match` is non-NULL and
`pmb_advance_or_null()` successfully advances the moved block despite
the change in sign.
One consequence of this is highlighting a short line as moved when it
should not be. For example
-moved line # Correctly highlighted as moved
+short line # Wrongly highlighted as moved
context
+moved line # Correctly highlighted as moved
+short line
context
-short line
The other consequence is coloring a moved addition following a moved
deletion in the wrong color. In the example below the first "+moved
line 3" should be highlighted as newMoved not newMovedAlternate.
-moved line 1 # Correctly highlighted as oldMoved
-moved line 2 # Correctly highlighted as oldMovedAlternate
+moved line 3 # Wrongly highlighted as newMovedAlternate
context # Everything else is highlighted correctly
+moved line 2
+moved line 3
context
+moved line 1
-moved line 3
These false matches are more likely when using --color-moved-ws with
the exception of --color-moved-ws=allow-indentation-change which ties
the sign of the current whitespace delta to the sign of the line to
avoid this problem. The fix is to check that the sign of the new line
being matched is the same as the sign of the line that started the
block of potential matches.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 17 ++++++----
t/t4015-diff-whitespace.sh | 65 ++++++++++++++++++++++++++++++++++++++
2 files changed, 76 insertions(+), 6 deletions(-)
This is one of those instances where I dislike having the patch in a
static mail. I so want to have a _convenient_ way to expand the diff
context, to have a look around.
So I went over to
https://github.com/gitgitgadget/git/pull/981/commits/10b11526206d3b515ba08ac80ccf09ecb7a03420
to get the convenience I need for a pleasant reviewing experience.
In this instance, the `continue` that dropped out of that conditional
block gave me pause.
My understanding is that the diff makes it essentially a lot harder to
understand what is done here: this conditional block did two things, it
re-set the possibly-moved-block, and it skipped to the next loop
iteration. With this patch, we now re-set the possibly-moved-block in more
cases, but still skip to the next loop iteration under the same condition
as before:
+ if (!match) {
+ moved_symbol = DIFF_SYMBOL_BINARY_DIFF_HEADER;
continue;
}
However, after reading the commit message, I would have expected the
condition above to read `if (!match || l->s != moved_symbol)` instead of
`if (!match)`. Could you help me understand what I am missing?
I want to make sure that I understand why the `last_symbol` assignment
could be removed without any `moved_symbol` assignment in its place. But I
don't, I still do not see why we do not need a `moved_symbol = l->s;`
assignment here.
Unless, that is, we extended the `!match` condition above to also cover
the case where `l->s != moved_symbol`.
That makes sense: we only set `moved_symbol` when `pmb_nr` had been 0 now,
and don't want it to be overridden.
As I said, I do not quite understand this patch yet, and am looking for
your guidance to wrap my head around it.
Thank you for working on this!
Dscho
@@ -1514,6 +1514,71 @@ test_expect_success 'zebra alternate color is only used when necessary' 'test_cmpexpectedactual'+test_expect_success'short lines of opposite sign do not get marked as moved''+cat>old.txt<<-\EOF&&+thislineshouldbemarkedasmoved+unchanged+unchanged+unchanged+unchanged+tooshort+thislineshouldbemarkedasoldMovednewMoved+thislineshouldbemarkedasoldMovedAlternatenewMoved+unchanged1+unchanged2+unchanged3+unchanged4+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+EOF+cat>new.txt<<-\EOF&&+tooshort+unchanged+unchanged+thislineshouldbemarkedasmoved+tooshort+unchanged+unchanged+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+unchanged1+unchanged2+thislineshouldbemarkedasoldMovedAlternatenewMoved+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+unchanged3+thislineshouldbemarkedasoldMovednewMoved+unchanged4+EOF+test_expect_code1gitdiff--no-index--color--color-moved=zebra\+old.txtnew.txt>output&&catoutput&&+grep-vindexoutput|test_decode_color>actual&&+cat>expect<<-\EOF&&+<BOLD>diff--gita/old.txtb/new.txt<RESET>+<BOLD>---a/old.txt<RESET>+<BOLD>+++b/new.txt<RESET>+<CYAN>@@-1,13+1,15@@<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasmoved<RESET>+<GREEN>+<RESET><GREEN>tooshort<RESET>+unchanged<RESET>+unchanged<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasmoved<RESET>+<GREEN>+<RESET><GREEN>tooshort<RESET>+unchanged<RESET>+unchanged<RESET>+<RED>-tooshort<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;BLUE>-thislineshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+unchanged1<RESET>+unchanged2<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+unchanged3<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovednewMoved<RESET>+unchanged4<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+EOF+test_cmpexpectactual+'+ test_expect_success'cmd option assumes configured colored-moved''test_configcolor.diff.oldMoved"magenta"&&test_configcolor.diff.newMoved"cyan"&&--
Hi Dscho
Thanks ever so much for taking a detailed look at this series.
On 22/11/2021 14:18, Johannes Schindelin wrote:
Hi Phillip,
The commit's oneline has a typo: zerba instead of zebra.
Sigh, I thought I'd fixed that
On Tue, 16 Nov 2021, Phillip Wood via GitGitGadget wrote:
quoted
From: Phillip Wood <redacted>
When marking moved lines it is possible for a block of potential
matched lines to extend past a change in sign when there is a sequence
of added lines whose text matches the text of a sequence of deleted
and added lines. Most of the time either `match` will be NULL or
`pmb_advance_or_null()` will fail when the loop encounters a change of
sign but there are corner cases where `match` is non-NULL and
`pmb_advance_or_null()` successfully advances the moved block despite
the change in sign.
One consequence of this is highlighting a short line as moved when it
should not be. For example
-moved line # Correctly highlighted as moved
+short line # Wrongly highlighted as moved
context
+moved line # Correctly highlighted as moved
+short line
context
-short line
The other consequence is coloring a moved addition following a moved
deletion in the wrong color. In the example below the first "+moved
line 3" should be highlighted as newMoved not newMovedAlternate.
-moved line 1 # Correctly highlighted as oldMoved
-moved line 2 # Correctly highlighted as oldMovedAlternate
+moved line 3 # Wrongly highlighted as newMovedAlternate
context # Everything else is highlighted correctly
+moved line 2
+moved line 3
context
+moved line 1
-moved line 3
These false matches are more likely when using --color-moved-ws with
the exception of --color-moved-ws=allow-indentation-change which ties
the sign of the current whitespace delta to the sign of the line to
avoid this problem. The fix is to check that the sign of the new line
being matched is the same as the sign of the line that started the
block of potential matches.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 17 ++++++----
t/t4015-diff-whitespace.sh | 65 ++++++++++++++++++++++++++++++++++++++
2 files changed, 76 insertions(+), 6 deletions(-)
This is one of those instances where I dislike having the patch in a
static mail. I so want to have a _convenient_ way to expand the diff
context, to have a look around.
So I went over to
https://github.com/gitgitgadget/git/pull/981/commits/10b11526206d3b515ba08ac80ccf09ecb7a03420
to get the convenience I need for a pleasant reviewing experience.
In this instance, the `continue` that dropped out of that conditional
block gave me pause.
My understanding is that the diff makes it essentially a lot harder to
understand what is done here: this conditional block did two things, it
re-set the possibly-moved-block, and it skipped to the next loop
iteration. With this patch, we now re-set the possibly-moved-block in more
cases, but still skip to the next loop iteration under the same condition
as before:
quoted
+ if (!match) {
+ moved_symbol = DIFF_SYMBOL_BINARY_DIFF_HEADER;
continue;
}
However, after reading the commit message, I would have expected the
condition above to read `if (!match || l->s != moved_symbol)` instead of
`if (!match)`. Could you help me understand what I am missing?
If there is a match we want to carry on executing the body of the loop
to start a new block of moved lines. moved_symbol will be updated at the
end of the loop.
I want to make sure that I understand why the `last_symbol` assignment
could be removed without any `moved_symbol` assignment in its place. But I
don't, I still do not see why we do not need a `moved_symbol = l->s;`
assignment here.
I had to think about it but I think the answer is that COLOR_MOVED_PLAIN
does not care about moved_symbol - it is only used by the zebra coloring
modes.
Unless, that is, we extended the `!match` condition above to also cover
the case where `l->s != moved_symbol`.
This is totally not your fault, but I really wish we could have the much
simpler and much easier to understand `flipped_block = !flipped_block`
here.
It's partially my fault - I should have simplified it when I moved that
line in b0a2ba4776 ("diff --color-moved=zebra: be stricter with color
alternation", 2018-11-23)
@@ -1514,6 +1514,71 @@ test_expect_success 'zebra alternate color is only used when necessary' 'test_cmpexpectedactual'+test_expect_success'short lines of opposite sign do not get marked as moved''+cat>old.txt<<-\EOF&&+thislineshouldbemarkedasmoved+unchanged+unchanged+unchanged+unchanged+tooshort+thislineshouldbemarkedasoldMovednewMoved+thislineshouldbemarkedasoldMovedAlternatenewMoved+unchanged1+unchanged2+unchanged3+unchanged4+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+EOF+cat>new.txt<<-\EOF&&+tooshort+unchanged+unchanged+thislineshouldbemarkedasmoved+tooshort+unchanged+unchanged+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+unchanged1+unchanged2+thislineshouldbemarkedasoldMovedAlternatenewMoved+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+unchanged3+thislineshouldbemarkedasoldMovednewMoved+unchanged4+EOF+test_expect_code1gitdiff--no-index--color--color-moved=zebra\+old.txtnew.txt>output&&catoutput&&+grep-vindexoutput|test_decode_color>actual&&+cat>expect<<-\EOF&&+<BOLD>diff--gita/old.txtb/new.txt<RESET>+<BOLD>---a/old.txt<RESET>+<BOLD>+++b/new.txt<RESET>+<CYAN>@@-1,13+1,15@@<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasmoved<RESET>+<GREEN>+<RESET><GREEN>tooshort<RESET>+unchanged<RESET>+unchanged<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasmoved<RESET>+<GREEN>+<RESET><GREEN>tooshort<RESET>+unchanged<RESET>+unchanged<RESET>+<RED>-tooshort<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;BLUE>-thislineshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+unchanged1<RESET>+unchanged2<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+unchanged3<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovednewMoved<RESET>+unchanged4<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+EOF+test_cmpexpectactual+'+test_expect_success'cmd option assumes configured colored-moved''test_configcolor.diff.oldMoved"magenta"&&test_configcolor.diff.newMoved"cyan"&&--
From: Johannes Schindelin <hidden> Date: 2021-11-23 14:51:50
Hi Phillip,
tl;dr: the patch looks good to me (it is a bit tricky to review, though,
but that is not your fault, it is our code review process' fault).
On Tue, 16 Nov 2021, Phillip Wood via GitGitGadget wrote:
git diff --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0
by 93% compared to master and simplifies the code.
@@ -879,37 +879,21 @@ static int compute_ws_delta(const struct emitted_diff_symbol *a,return1;}-staticintcmp_in_block_with_wsd(conststructdiff_options*o,-conststructmoved_entry*cur,-conststructmoved_entry*match,-structmoved_block*pmb,-intn)-{-structemitted_diff_symbol*l=&o->emitted_symbols->buf[n];-intal=cur->es->len,bl=match->es->len,cl=l->len;+staticintcmp_in_block_with_wsd(conststructmoved_entry*cur,+conststructemitted_diff_symbol*l,+structmoved_block*pmb)+{+intal=cur->es->len,bl=l->len;
Once I realized that the old `b` was removed and the old `c` became the
new `b`, it was a breeze to validate this hunk.
const char *a = cur->es->line,
- *b = match->es->line,
- *c = l->line;
+ *b = l->line;
int a_off = cur->es->indent_off,
a_width = cur->es->indent_width,
- c_off = l->indent_off,
- c_width = l->indent_width;
+ b_off = l->indent_off,
+ b_width = l->indent_width;
int delta;
- /*
- * We need to check if 'cur' is equal to 'match'. As those
- * are from the same (+/-) side, we do not need to adjust for
- * indent changes. However these were found using fuzzy
- * matching so we do have to check if they are equal. Here we
- * just check the lengths. We delay calling memcmp() to check
- * the contents until later as if the length comparison for a
- * and c fails we can avoid the call all together.
- */
- if (al != bl)
- return 1;
The commit message really helped understanding why this is not needed.
Thank you!
quoted hunk
-
/* If 'l' and 'cur' are both blank then they match. */
- if (a_width == INDENT_BLANKLINE && c_width == INDENT_BLANKLINE)
+ if (a_width == INDENT_BLANKLINE && b_width == INDENT_BLANKLINE)
return 0;
/*
@@ -918,7 +902,7 @@ static int cmp_in_block_with_wsd(const struct diff_options *o, * match those of the current block and that the text of 'l' and 'cur' * after the indentation match. */- delta = c_width - a_width;+ delta = b_width - a_width; /* * If the previous lines of this block were all blank then set its
@@ -927,9 +911,8 @@ static int cmp_in_block_with_wsd(const struct diff_options *o, if (pmb->wsd == INDENT_BLANKLINE) pmb->wsd = delta;- return !(delta == pmb->wsd && al - a_off == cl - c_off &&- !memcmp(a, b, al) && !- memcmp(a + a_off, c + c_off, al - a_off));+ return !(delta == pmb->wsd && al - a_off == bl - b_off &&+ !memcmp(a + a_off, b + b_off, al - a_off)); }
Once again, I am sad that we have no better platform to do our code
contribution and review. Whatever you can say about GitHub's UI, it is
better than static diffs in mails.
But you used GitGitGadget, and I finally broke down and wrote a script
that allows me to magic my way from the mail into the correct commit in
the GitGitGadget PR in the browser. It is still shell script (at some
stage, I will need to extend the script to be much smarter than any shell
script can be, and probably convert it to node.js, but not today).
This helped me verify that there are no left-over references to the old
`b`. So all is good!
quoted hunk
static int moved_entry_cmp(const void *hashmap_cmp_fn_data,
@@ -1030,36 +1013,23 @@ static void pmb_advance_or_null(struct diff_options *o, } static void pmb_advance_or_null_multi_match(struct diff_options *o,- struct moved_entry *match,- struct hashmap *hm,+ struct emitted_diff_symbol *l, struct moved_block *pmb,- int pmb_nr, int n)+ int pmb_nr) { int i;- char *got_match = xcalloc(1, pmb_nr);-- hashmap_for_each_entry_from(hm, match, ent) {- for (i = 0; i < pmb_nr; i++) {- struct moved_entry *prev = pmb[i].match;- struct moved_entry *cur = (prev && prev->next_line) ?- prev->next_line : NULL;- if (!cur)- continue;- if (!cmp_in_block_with_wsd(o, cur, match, &pmb[i], n))- got_match[i] |= 1;- }- } for (i = 0; i < pmb_nr; i++) {- if (got_match[i]) {+ struct moved_entry *prev = pmb[i].match;+ struct moved_entry *cur = (prev && prev->next_line) ?+ prev->next_line : NULL;+ if (cur && !cmp_in_block_with_wsd(cur, l, &pmb[i])) { /* Advance to the next line */- pmb[i].match = pmb[i].match->next_line;+ pmb[i].match = cur; } else { moved_block_clear(&pmb[i]); } }-- free(got_match);
Even got rid of an allocation. Very nice.
quoted hunk
}
static int shrink_potential_moved_blocks(struct moved_block *pmb,
Again, magic button to the rescue! And I can verify that `l` is assigned
to `&o->emitted_symbols->buf[n]`, so: the patch does the correct thing.
Thank you,
Dscho
From: Johannes Schindelin <hidden> Date: 2021-11-23 15:09:38
Hi Phillip,
On Tue, 16 Nov 2021, Phillip Wood via GitGitGadget wrote:
From: Phillip Wood <redacted>
This change will allow us to easily combine pmb_advance_or_null() and
pmb_advance_or_null_multi_match() in the next commit. Calling
xdiff_compare_lines() directly rather than using a function pointer
from the hash map has little effect on the run time.
Test HEAD^ HEAD
-------------------------------------------------------------------------------------------------------------
4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38(0.35+0.03) 0.38(0.32+0.06) +0.0%
4002.2: diff --color-moved --no-color-moved-ws large change 0.87(0.83+0.04) 0.87(0.80+0.06) +0.0%
4002.3: diff --color-moved-ws=allow-indentation-change large change 0.97(0.92+0.04) 0.97(0.93+0.04) +0.0%
4002.4: log --no-color-moved --no-color-moved-ws 1.17(1.06+0.10) 1.16(1.10+0.05) -0.9%
4002.5: log --color-moved --no-color-moved-ws 1.32(1.24+0.08) 1.31(1.22+0.09) -0.8%
4002.6: log --color-moved-ws=allow-indentation-change 1.36(1.25+0.10) 1.35(1.25+0.10) -0.7%
Honestly, I would have expected an improvement, given that
`moved_entry_cmp()` has to do a few things before it can call
`xdiff_compare_lines()`.
I love your attention to detail, providing performance numbers in the
commit message to prove that it at least has no negative impact on the
speed.
Thanks,
Dscho
From: Johannes Schindelin <hidden> Date: 2021-12-08 12:30:44
Hi Phillip,
On Tue, 16 Nov 2021, Phillip Wood via GitGitGadget wrote:
Changes since V3:
* Patch 1 now allows the user to choose different endpoints for the diff
perf tests to facilitate testing with different repositories.
* Fixed the alignment of the perf results column headers in a couple of
patches.
I finished reading over the patches in this iteration. Although I did not
have the mental bandwidth to review in particular the last patch in the
series in detail, the regression tests seem comprehensive enough for me to
be confident in the correctness.
So: from my side, this patch series is good to go!
Thank you,
Dscho
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-12-09 10:30:14
Thanks to Dscho for his comments on V3. Changes since V4:
* Fixed a typo in the commit message to patch 6
Changes since V3:
* Patch 1 now allows the user to choose different endpoints for the diff
perf tests to facilitate testing with different repositories.
* Fixed the alignment of the perf results column headers in a couple of
patches.
Changes since V2:
* Patches 1-3 are new and fix an existing bug.
* Patch 8 includes Peff's unused parameter fix.
* Patch 11 has been updated to fix a bug fix in V2.
* Patch 13 has an expanded commit message explaining a change in behavior
for lines starting with a form-feed.
* Updated benchmark results.
The bug fix in patch 3 degrades the performance, but by the end of the
series the timings are the same as V2 - see the range diff.
V2 Cover Letter: Thanks to Ævar and Elijah for their comments, I've reworded
the commit messages, addressed the enum initialization issue in patch 2 (now
3) and added some perf tests.
There are two new patches in this round. The first patch is new and adds the
perf tests suggested by Ævar, the penultimate patch is also new and coverts
the existing code to use a designated initializer.
I've converted the benchmark results in the commit messages to use the new
tests, the percentage changes are broadly similar to the previous results
though I ended up running them on a different computer this time.
V1 cover letter:
The current implementation of diff --color-moved-ws=allow-indentation-change
is considerably slower that the implementation of diff --color-moved which
is in turn slower than a regular diff. This patch series starts with a
couple of bug fixes and then reworks the implementation of diff
--color-moved and diff --color-moved-ws=allow-indentation-change to speed
them up on large diffs. The time to run git diff --color-moved
--no-color-moved-ws v2.28.0 v2.29.0 is reduced by 33% and the time to run
git diff --color-moved --color-moved-ws=allow-indentation-change v2.28.0
v2.29.0 is reduced by 88%. There is a small slowdown for commit sized diffs
with --color-moved - the time to run git log -p --color-moved
--no-color-moved-ws --no-merges -n1000 v2.29.0 is increased by 2% on recent
processors. On older processors these patches reduce the running time in all
cases that I've tested. In general the larger the diff the larger the speed
up. As an extreme example the time to run diff --color-moved
--color-moved-ws=allow-indentation-change v2.25.0 v2.30.0 goes down from 8
minutes to 6 seconds.
Phillip Wood (15):
diff --color-moved: add perf tests
diff --color-moved: clear all flags on blocks that are too short
diff --color-moved: factor out function
diff --color-moved: rewind when discarding pmb
diff --color-moved=zebra: fix alternate coloring
diff --color-moved: avoid false short line matches and bad zebra
coloring
diff: simplify allow-indentation-change delta calculation
diff --color-moved-ws=allow-indentation-change: simplify and optimize
diff --color-moved: call comparison function directly
diff --color-moved: unify moved block growth functions
diff --color-moved: shrink potential moved blocks as we go
diff --color-moved: stop clearing potential moved blocks
diff --color-moved-ws=allow-indentation-change: improve hash lookups
diff: use designated initializers for emitted_diff_symbol
diff --color-moved: intern strings
diff.c | 431 +++++++++++++------------------
t/perf/p4002-diff-color-moved.sh | 57 ++++
t/t4015-diff-whitespace.sh | 205 ++++++++++++++-
3 files changed, 437 insertions(+), 256 deletions(-)
create mode 100755 t/perf/p4002-diff-color-moved.sh
base-commit: 211eca0895794362184da2be2a2d812d070719d3
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-981%2Fphillipwood%2Fwip%2Fdiff-color-moved-tweaks-v5
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-981/phillipwood/wip/diff-color-moved-tweaks-v5
Pull-Request: https://github.com/gitgitgadget/git/pull/981
Range-diff vs v4:
1: 48ee03cf52a = 1: 48ee03cf52a diff --color-moved: add perf tests
2: 47c652716e8 = 2: 47c652716e8 diff --color-moved: clear all flags on blocks that are too short
3: 99e38ba9de9 = 3: 99e38ba9de9 diff --color-moved: factor out function
4: 9ca71db61ae = 4: 9ca71db61ae diff --color-moved: rewind when discarding pmb
5: 56bb69af36e = 5: 56bb69af36e diff --color-moved=zebra: fix alternate coloring
6: 10b11526206 ! 6: ed62b980225 diff --color-moved: avoid false short line matches and bad zerba coloring
@@ Metadata
Author: Phillip Wood [off-list ref]
## Commit message ##
- diff --color-moved: avoid false short line matches and bad zerba coloring
+ diff --color-moved: avoid false short line matches and bad zebra coloring
When marking moved lines it is possible for a block of potential
matched lines to extend past a change in sign when there is a sequence
7: c2e7b347257 = 7: b8db6a1af7d diff: simplify allow-indentation-change delta calculation
8: d7bbc0041e0 = 8: eeb633063b7 diff --color-moved-ws=allow-indentation-change: simplify and optimize
9: c3e5dce1910 = 9: fb413cab3a8 diff --color-moved: call comparison function directly
10: 9eb8cecd52a = 10: ec8764082d5 diff --color-moved: unify moved block growth functions
11: 35e204e1578 = 11: 6199a014547 diff --color-moved: shrink potential moved blocks as we go
12: ec329e7946d = 12: 1db84490ee4 diff --color-moved: stop clearing potential moved blocks
13: 6ec94134aaf = 13: 3e769bab78c diff --color-moved-ws=allow-indentation-change: improve hash lookups
14: d44c5d734c3 = 14: b8869659664 diff: use designated initializers for emitted_diff_symbol
15: 5177f669423 = 15: 350fa55ce5e diff --color-moved: intern strings
--
gitgitgadget
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-12-09 10:30:21
From: Phillip Wood <redacted>
Add some tests so we can monitor changes to the performance of the
move detection code. The tests record the performance --color-moved
and --color-moved-ws=allow-indentation-change for a large diff and a
sequence of smaller diffs. The range of commits used for the large
diff can be customized by exporting TEST_REV_A and TEST_REV_B when
running the test.
Signed-off-by: Phillip Wood <redacted>
---
t/perf/p4002-diff-color-moved.sh | 57 ++++++++++++++++++++++++++++++++
1 file changed, 57 insertions(+)
create mode 100755 t/perf/p4002-diff-color-moved.sh
@@ -0,0 +1,57 @@+#!/bin/sh++test_description='Tests diff --color-moved performance'+../perf-lib.sh++test_perf_default_repo++# The endpoints of the diff can be customized by setting TEST_REV_A+# and TEST_REV_B in the environment when running this test.++rev="${TEST_REV_A:-v2.28.0}"+if!rev_a="$(gitrev-parse--quiet--verify"$rev")"+then+skip_all="skipping because '$rev' was not found. \+UseTEST_REV_AandTEST_REV_Btosettherevstouse"+test_done+fi+rev="${TEST_REV_B:-v2.29.0}"+if!rev_b="$(gitrev-parse--quiet--verify"$rev")"+then+skip_all="skipping because '$rev' was not found. \+UseTEST_REV_AandTEST_REV_Btosettherevstouse"+test_done+fi++GIT_PAGER_IN_USE=1+test_exportGIT_PAGER_IN_USErev_arev_b++test_perf'diff --no-color-moved --no-color-moved-ws large change''+gitdiff--no-color-moved--no-color-moved-ws$rev_a$rev_b+'++test_perf'diff --color-moved --no-color-moved-ws large change''+gitdiff--color-moved=zebra--no-color-moved-ws$rev_a$rev_b+'++test_perf'diff --color-moved-ws=allow-indentation-change large change''+gitdiff--color-moved=zebra--color-moved-ws=allow-indentation-change\+$rev_a$rev_b+'++test_perf'log --no-color-moved --no-color-moved-ws''+gitlog--no-color-moved--no-color-moved-ws--no-merges--patch\+-n1000$rev_b+'++test_perf'log --color-moved --no-color-moved-ws''+gitlog--color-moved=zebra--no-color-moved-ws--no-merges--patch\+-n1000$rev_b+'++test_perf'log --color-moved-ws=allow-indentation-change''+gitlog--color-moved=zebra--color-moved-ws=allow-indentation-change\+--no-merges--patch-n1000$rev_b+'++test_done
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-12-09 10:30:23
From: Phillip Wood <redacted>
If a block of potentially moved lines is not long enough then the
DIFF_SYMBOL_MOVED_LINE flag is cleared on the matching lines so they
are not marked as moved. To avoid problems when we start rewinding
after an unsuccessful match in a couple of commits time make sure all
the move related flags are cleared, not just DIFF_SYMBOL_MOVED_LINE.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 6 +++---
1 file changed, 3 insertions(+), 3 deletions(-)
@@ -1130,7 +1132,7 @@ static int adjust_last_block(struct diff_options *o, int n, int block_length)}}for(i=1;i<block_length+1;i++)-o->emitted_symbols->buf[n-i].flags&=~DIFF_SYMBOL_MOVED_LINE;+o->emitted_symbols->buf[n-i].flags&=~DIFF_SYMBOL_MOVED_LINE_ZEBRA_MASK;return0;}
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-12-09 10:30:23
From: Phillip Wood <redacted>
b0a2ba4776 ("diff --color-moved=zebra: be stricter with color
alternation", 2018-11-23) sought to avoid using the alternate colors
unless there are two adjacent moved blocks of the same
sign. Unfortunately it contains two bugs that prevented it from fixing
the problem properly. Firstly `last_symbol` is reset at the start of
each iteration of the loop losing the symbol of the last line and
secondly when deciding whether to use the alternate color it should be
checking if the current line is the same sign of the last line, not a
different sign. The combination of the two errors means that we still
use the alternate color when we should do but we also use it when we
shouldn't. This is most noticable when using
--color-moved-ws=allow-indentation-change with hunks like
-this line gets indented
+ this line gets indented
where the post image is colored with newMovedAlternate rather than
newMoved. While this does not matter much, the next commit will change
the coloring to be correct in this case, so lets fix the bug here to
make it clear why the output is changing and add a regression test.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 4 +--
t/t4015-diff-whitespace.sh | 72 ++++++++++++++++++++++++++++++++++++++
2 files changed, 74 insertions(+), 2 deletions(-)
@@ -1442,6 +1442,78 @@ test_expect_success 'detect permutations inside moved code -- dimmed-zebra' 'test_cmpexpectedactual'+test_expect_success'zebra alternate color is only used when necessary''+cat>old.txt<<-\EOF&&+line1AshouldbemarkedasoldMovednewMovedAlternate+line1BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line2AshouldbemarkedasoldMovednewMovedAlternate+line2BshouldbemarkedasoldMovednewMovedAlternate+line3AshouldbemarkedasoldMovedAlternatenewMoved+line3BshouldbemarkedasoldMovedAlternatenewMoved+unchanged+line4AshouldbemarkedasoldMovednewMovedAlternate+line4BshouldbemarkedasoldMovednewMovedAlternate+line5AshouldbemarkedasoldMovedAlternatenewMoved+line5BshouldbemarkedasoldMovedAlternatenewMoved+line6AshouldbemarkedasoldMovednewMoved+line6BshouldbemarkedasoldMovednewMoved+EOF+cat>new.txt<<-\EOF&&+line1AshouldbemarkedasoldMovednewMovedAlternate+line1BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line3AshouldbemarkedasoldMovedAlternatenewMoved+line3BshouldbemarkedasoldMovedAlternatenewMoved+line2AshouldbemarkedasoldMovednewMovedAlternate+line2BshouldbemarkedasoldMovednewMovedAlternate+unchanged+line6AshouldbemarkedasoldMovednewMoved+line6BshouldbemarkedasoldMovednewMoved+line4AshouldbemarkedasoldMovednewMovedAlternate+line4BshouldbemarkedasoldMovednewMovedAlternate+line5AshouldbemarkedasoldMovedAlternatenewMoved+line5BshouldbemarkedasoldMovedAlternatenewMoved+EOF+test_expect_code1gitdiff--no-index--color--color-moved=zebra\+--color-moved-ws=allow-indentation-change\+old.txtnew.txt>output&&+grep-vindexoutput|test_decode_color>actual&&+cat>expected<<-\EOF&&+<BOLD>diff--gita/old.txtb/new.txt<RESET>+<BOLD>---a/old.txt<RESET>+<BOLD>+++b/new.txt<RESET>+<CYAN>@@-1,14+1,14@@<RESET>+<BOLD;MAGENTA>-line1AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line1BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line1AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line1BshouldbemarkedasoldMovednewMovedAlternate<RESET>+unchanged<RESET>+<BOLD;MAGENTA>-line2AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line2BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;BLUE>-line3AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;BLUE>-line3BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line3AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line3BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line2AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line2BshouldbemarkedasoldMovednewMovedAlternate<RESET>+unchanged<RESET>+<BOLD;MAGENTA>-line4AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;MAGENTA>-line4BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;BLUE>-line5AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;BLUE>-line5BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;MAGENTA>-line6AshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;MAGENTA>-line6BshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line6AshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line6BshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line4AshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>line4BshouldbemarkedasoldMovednewMovedAlternate<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line5AshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>line5BshouldbemarkedasoldMovedAlternatenewMoved<RESET>+EOF+test_cmpexpectedactual+'+ test_expect_success'cmd option assumes configured colored-moved''test_configcolor.diff.oldMoved"magenta"&&test_configcolor.diff.newMoved"cyan"&&
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-12-09 10:30:25
From: Phillip Wood <redacted>
This code is quite heavily indented and having it in its own function
simplifies an upcoming change.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 51 ++++++++++++++++++++++++++++++++++-----------------
1 file changed, 34 insertions(+), 17 deletions(-)
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-12-09 10:30:26
From: Phillip Wood <redacted>
When marking moved lines it is possible for a block of potential
matched lines to extend past a change in sign when there is a sequence
of added lines whose text matches the text of a sequence of deleted
and added lines. Most of the time either `match` will be NULL or
`pmb_advance_or_null()` will fail when the loop encounters a change of
sign but there are corner cases where `match` is non-NULL and
`pmb_advance_or_null()` successfully advances the moved block despite
the change in sign.
One consequence of this is highlighting a short line as moved when it
should not be. For example
-moved line # Correctly highlighted as moved
+short line # Wrongly highlighted as moved
context
+moved line # Correctly highlighted as moved
+short line
context
-short line
The other consequence is coloring a moved addition following a moved
deletion in the wrong color. In the example below the first "+moved
line 3" should be highlighted as newMoved not newMovedAlternate.
-moved line 1 # Correctly highlighted as oldMoved
-moved line 2 # Correctly highlighted as oldMovedAlternate
+moved line 3 # Wrongly highlighted as newMovedAlternate
context # Everything else is highlighted correctly
+moved line 2
+moved line 3
context
+moved line 1
-moved line 3
These false matches are more likely when using --color-moved-ws with
the exception of --color-moved-ws=allow-indentation-change which ties
the sign of the current whitespace delta to the sign of the line to
avoid this problem. The fix is to check that the sign of the new line
being matched is the same as the sign of the line that started the
block of potential matches.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 17 ++++++----
t/t4015-diff-whitespace.sh | 65 ++++++++++++++++++++++++++++++++++++++
2 files changed, 76 insertions(+), 6 deletions(-)
@@ -1514,6 +1514,71 @@ test_expect_success 'zebra alternate color is only used when necessary' 'test_cmpexpectedactual'+test_expect_success'short lines of opposite sign do not get marked as moved''+cat>old.txt<<-\EOF&&+thislineshouldbemarkedasmoved+unchanged+unchanged+unchanged+unchanged+tooshort+thislineshouldbemarkedasoldMovednewMoved+thislineshouldbemarkedasoldMovedAlternatenewMoved+unchanged1+unchanged2+unchanged3+unchanged4+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+EOF+cat>new.txt<<-\EOF&&+tooshort+unchanged+unchanged+thislineshouldbemarkedasmoved+tooshort+unchanged+unchanged+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+unchanged1+unchanged2+thislineshouldbemarkedasoldMovedAlternatenewMoved+thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate+unchanged3+thislineshouldbemarkedasoldMovednewMoved+unchanged4+EOF+test_expect_code1gitdiff--no-index--color--color-moved=zebra\+old.txtnew.txt>output&&catoutput&&+grep-vindexoutput|test_decode_color>actual&&+cat>expect<<-\EOF&&+<BOLD>diff--gita/old.txtb/new.txt<RESET>+<BOLD>---a/old.txt<RESET>+<BOLD>+++b/new.txt<RESET>+<CYAN>@@-1,13+1,15@@<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasmoved<RESET>+<GREEN>+<RESET><GREEN>tooshort<RESET>+unchanged<RESET>+unchanged<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasmoved<RESET>+<GREEN>+<RESET><GREEN>tooshort<RESET>+unchanged<RESET>+unchanged<RESET>+<RED>-tooshort<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasoldMovednewMoved<RESET>+<BOLD;BLUE>-thislineshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+unchanged1<RESET>+unchanged2<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovedAlternatenewMoved<RESET>+<BOLD;YELLOW>+<RESET><BOLD;YELLOW>thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+unchanged3<RESET>+<BOLD;CYAN>+<RESET><BOLD;CYAN>thislineshouldbemarkedasoldMovednewMoved<RESET>+unchanged4<RESET>+<BOLD;MAGENTA>-thislineshouldbemarkedasoldMovednewMoved/newMovedAlternate<RESET>+EOF+test_cmpexpectactual+'+ test_expect_success'cmd option assumes configured colored-moved''test_configcolor.diff.oldMoved"magenta"&&test_configcolor.diff.newMoved"cyan"&&
From: Phillip Wood via GitGitGadget <hidden> Date: 2021-12-09 10:30:27
From: Phillip Wood <redacted>
Now that we reliably end a block when the sign changes we don't need
the whitespace delta calculation to rely on the sign.
Signed-off-by: Phillip Wood <redacted>
---
diff.c | 13 ++-----------
1 file changed, 2 insertions(+), 11 deletions(-)