From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-06 22:53:23
This series depends on ort-perf-batch-6[1], which has not yet appeared in
seen despite being reviewed by both Junio and Stolee.
This series uses file basenames in a basic fashion to guide rename
detection. It represents "Optimization #3" from my Git Merge 2020 talk[2],
and is based on the fact that real world repositories tend to have a large
majority of the renames they have done in history be ones that do not affect
the basenames of the renamed files (in other words, they are simply moving
files into different directories). For the testcases mentioned in commit
557ac0350d ("merge-ort: begin performance work; instrument with
trace2_region_* calls", 2020-10-28), the changes in just this series
improves the performance as follows:
Before Series After Series
no-renames: 13.815 s ± 0.062 s 13.138 s ± 0.086 s
mega-renames: 1799.937 s ± 0.493 s 169.488 s ± 0.494 s
just-one-mega: 51.289 s ± 0.019 s 5.061 s ± 0.017 s
As a reminder, before any merge-ort/diffcore-rename performance work, the
performance results we started with (as noted in the same commit message)
were:
no-renames-am: 6.940 s ± 0.485 s
no-renames: 18.912 s ± 0.174 s
mega-renames: 5964.031 s ± 10.459 s
just-one-mega: 149.583 s ± 0.751 s
[1] https://lore.kernel.org/git/xmqqlfc4byt6.fsf@gitster.c.googlers.com/ [2]
https://github.com/newren/presentations/blob/pdfs/merge-performance/merge-performance-slides.pdf
Elijah Newren (3):
diffcore-rename: compute basenames of all source and dest candidates
diffcore-rename: complete find_basename_matches()
diffcore-rename: guide inexact rename detection based on basenames
diffcore-rename.c | 181 +++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 177 insertions(+), 4 deletions(-)
base-commit: 7ae9460d3dba84122c2674b46e4339b9d42bdedd
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-843%2Fnewren%2Fort-perf-batch-7-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-843/newren/ort-perf-batch-7-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/843
--
gitgitgadget
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-06 22:53:10
From: Elijah Newren <redacted>
We want to make use of unique basenames to help inform rename detection,
so that more likely pairings can be checked first. Add a new function,
not yet used, which creates a map of the unique basenames within
rename_src and another within rename_dst, together with the indices
within rename_src/rename_dst where those basenames show up. Non-unique
basenames still show up in the map, but have an invalid index (-1).
Signed-off-by: Elijah Newren <redacted>
---
diffcore-rename.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 53 insertions(+)
@@ -367,6 +367,59 @@ static int find_exact_renames(struct diff_options *options)returnrenames;}+MAYBE_UNUSED+staticintfind_basename_matches(structdiff_options*options,+intminimum_score,+intnum_src)+{+inti;+structstrintmapsources;+structstrintmapdests;++/* Create maps of basename -> fullname(s) for sources and dests */+strintmap_init_with_options(&sources,-1,NULL,0);+strintmap_init_with_options(&dests,-1,NULL,0);+for(i=0;i<num_src;++i){+char*filename=rename_src[i].p->one->path;+char*base;++/* exact renames removed in remove_unneeded_paths_from_src() */+assert(!rename_src[i].p->one->rename_used);++base=strrchr(filename,'/');+base=(base?base+1:filename);++/* Record index within rename_src (i) if basename is unique */+if(strintmap_contains(&sources,base))+strintmap_set(&sources,base,-1);+else+strintmap_set(&sources,base,i);+}+for(i=0;i<rename_dst_nr;++i){+char*filename=rename_dst[i].p->two->path;+char*base;++if(rename_dst[i].is_rename)+continue;/* involved in exact match already. */++base=strrchr(filename,'/');+base=(base?base+1:filename);++/* Record index within rename_dst (i) if basename is unique */+if(strintmap_contains(&dests,base))+strintmap_set(&dests,base,-1);+else+strintmap_set(&dests,base,i);+}++/* TODO: Make use of basenames source and destination basenames */++strintmap_clear(&sources);+strintmap_clear(&dests);++return0;+}+#define NUM_CANDIDATE_PER_DST 4staticvoidrecord_if_better(structdiff_scorem[],structdiff_score*o){
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-06 22:53:22
From: Elijah Newren <redacted>
It is not uncommon in real world repositories for the majority of file
renames to not change the basename of the file; i.e. most "renames" are
just a move of files into different directories. We can make use of
this to avoid comparing all rename source candidates with all rename
destination candidates, by first comparing sources to destinations with
the same basenames. If two files with the same basename are
sufficiently similar, we record the rename; if not, we include those
files in the more exhaustive matrix comparison.
Note that this optimization might give us different results than without
the optimization, because it's possible that despite files with the same
basename being sufficiently similar to be considered a rename, there's
an even better match between files without the same basename. I think
that is okay for four reasons: (1) That seems somewhat unlikely in
practice, (2) it's easy to explain to the users what happened if it does
ever occur (or even for them to intuitively figure out), and (3) as the
next patch will show it provides such a large performance boost that
it's worth the tradeoff. Reason (4) takes a full paragraph to
explain...
If the previous three reasons aren't enough, consider what rename
detection already does. Break detection is not the default, meaning
that if files have the same _fullname_, then they are considered related
even if they are 0% similar. In fact, in such a case, we don't even
bother comparing the files to see if they are similar let alone
comparing them to all other files to see what they are most similar to.
Basically, we override content similarity based on sufficient filename
similarity. Without the filename similarity (currently implemented as
an exact match of filename), we swing the pendulum the opposite
direction and say that filename similarity is irrelevant and compare a
full N x M matrix of sources and destinations to find out which have the
most similar contents. This optimization just adds another form of
filename similarity comparison, but augments it with a file content
similarity check as well. Basically, if two files have the same
basename and are sufficiently similar to be considered a rename, mark
them as such without comparing the two to all other rename candidates.
We do not use this heuristic together with either break or copy
detection. The point of break detection is to say that filename
similarity does not imply file content similarity, and we only want to
know about file content similarity. The point of copy detection is to
use more resources to check for additional similarities, while this is
an optimization that uses far less resources but which might also result
in finding slightly fewer similarities. So the idea behind this
optimization goes against both of those features, and will be turned off
for both.
Note that this optimization is not yet effective in any situation, as
the function is still unused. The next commit will hook it into the
code so that it is used when rename detection is wanted, but neither
copy nor break detection are.
Signed-off-by: Elijah Newren <redacted>
---
diffcore-rename.c | 94 +++++++++++++++++++++++++++++++++++++++++++++--
1 file changed, 91 insertions(+), 3 deletions(-)
@@ -372,10 +372,48 @@ static int find_basename_matches(struct diff_options *options,intminimum_score,intnum_src){-inti;+/*+*WhenIchecked,over76%offilerenamesinlinuxjustmoved+*filestoadifferentdirectorybutkeptthesamebasename.gcc+*didthatwithover64%ofrenames,geckodiditwithover79%,+*andWebKitdiditwithover89%.+*+*ThereforewecanbypassthenormalexhaustiveNxMmatrix+*comparisonofsimilaritiesbetweenallpotentialrenamesources+*anddestinationsbyinsteadusingfilebasenameasahint,checking+*forsimilaritybetweenfileswiththesamebasename,andifwe+*findapairthataresufficientlysimilar,recordtherename+*pairandexcludethosetwofromtheNxMmatrix.+*+*This*might*causeustofindalessthanoptimalpairing(if+*thereisanotherfilethatweareevenmoresimilartobuthasa+*differentbasename).Giventhehugeperformanceadvantage+*basenamematchingprovides,andgiventhefrequencywithwhich+*peopleusethesamebasenameinrealworldprojects,that'sa+*trade-offwearewillingtoacceptwhendoingjustrename+*detection.However,ifsomeonewantscopydetectionthat+*impliestheyarewillingtospendmorecyclestofind+*similaritiesbetweenfiles,soitmaybelesslikelythatthis+*heuristiciswanted.+*/++inti,renames=0;structstrintmapsources;structstrintmapdests;+/*+*Theprefetechingstuffwantstoknowifitcanskipprefetchingblobs+*thatareunmodified.unmodifiedblobsareonlyrelevantwhendoing+*copydetection.find_basename_matches()isonlyusedwhendetecting+*renames,notwhendetectingcopies,soit'llonlybeusedwhenafile+*onlyexistedinthesource.Sincewealreadyknowthatthefile+*won'tbeunmodified,there'snopointcheckingforit;that'sjusta+*wasteofresources.Sosetskip_unmodifiedto0sothat+*estimate_similarity()andprefetch()won'twasteresourceschecking+*forsomethingwealreadyknowisfalse.+*/+intskip_unmodified=0;+/* Create maps of basename -> fullname(s) for sources and dests */strintmap_init_with_options(&sources,-1,NULL,0);strintmap_init_with_options(&dests,-1,NULL,0);
@@ -412,12 +450,62 @@ static int find_basename_matches(struct diff_options *options,strintmap_set(&dests,base,i);}-/* TODO: Make use of basenames source and destination basenames */+/* Now look for basename matchups and do similarity estimation */+for(i=0;i<num_src;++i){+char*filename=rename_src[i].p->one->path;+char*base=NULL;+intptr_tsrc_index;+intptr_tdst_index;++/* Get the basename */+base=strrchr(filename,'/');+base=(base?base+1:filename);++/* Find out if this basename is unique among sources */+src_index=strintmap_get(&sources,base);+if(src_index==-1)+continue;/* not a unique basename; skip it */+assert(src_index==i);++if(strintmap_contains(&dests,base)){+structdiff_filespec*one,*two;+intscore;++/* Find out if this basename is unique among dests */+dst_index=strintmap_get(&dests,base);+if(dst_index==-1)+continue;/* not a unique basename; skip it */++/* Ignore this dest if already used in a rename */+if(rename_dst[dst_index].is_rename)+continue;/* already used previously */++/* Estimate the similarity */+one=rename_src[src_index].p->one;+two=rename_dst[dst_index].p->two;+score=estimate_similarity(options->repo,one,two,+minimum_score,skip_unmodified);++/* If sufficiently similar, record as rename pair */+if(score<minimum_score)+continue;+record_rename_pair(dst_index,src_index,score);+renames++;++/*+*Foundarenamesodon'tneedtextanymore;ifwe+*didn'tfindarename,thefilespec_blobwouldget+*re-usedwhendoingthematrixofcomparisons.+*/+diff_free_filespec_blob(one);+diff_free_filespec_blob(two);+}+}strintmap_clear(&sources);strintmap_clear(&dests);-return0;+returnrenames;}#define NUM_CANDIDATE_PER_DST 4
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-06 22:53:31
From: Elijah Newren <redacted>
Make use of the new find_basename_matches() function added in the last
two patches, to find renames more rapidly in cases where we can match up
files based on basenames.
For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
this change improves the performance as follows:
Before After
no-renames: 13.815 s ± 0.062 s 13.138 s ± 0.086 s
mega-renames: 1799.937 s ± 0.493 s 169.488 s ± 0.494 s
just-one-mega: 51.289 s ± 0.019 s 5.061 s ± 0.017 s
Signed-off-by: Elijah Newren <redacted>
---
diffcore-rename.c | 42 +++++++++++++++++++++++++++++++++++++-----
1 file changed, 37 insertions(+), 5 deletions(-)
On 2/6/21 5:52 PM, Elijah Newren via GitGitGadget wrote:
From: Elijah Newren <redacted>
Make use of the new find_basename_matches() function added in the last
two patches, to find renames more rapidly in cases where we can match up
files based on basenames.
This is a valuable heuristic.
For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
this change improves the performance as follows:
Before After
no-renames: 13.815 s ± 0.062 s 13.138 s ± 0.086 s
mega-renames: 1799.937 s ± 0.493 s 169.488 s ± 0.494 s
just-one-mega: 51.289 s ± 0.019 s 5.061 s ± 0.017 s
These numbers are very impressive.
Before I get too deep into reviewing these patches, I do want
to make it clear that the speed-up is coming at the cost of
a behavior change. We are restricting the "best match" search
to be first among files with common base name (although maybe
I would use 'suffix'?). If we search for a rename among all
additions and deletions ending the ".txt" we might find a
similarity match that is 60% and declare that a rename, even
if there is a ".txt" -> ".md" pair that has a 70% match.
This could be documented in a test case, to demonstrate that
we are making this choice explicitly.
For example, here is a test that passes now, but would
start failing with your patches (if I understand them
correctly):
@@ -262,4 +262,21 @@ test_expect_success 'diff-tree -l0 defaults to a big rename limit, not zero' 'grep"myotherfile.*myfile"actual'+test_expect_success'multiple similarity choices''+test_write_linesline1line2line3line4line5\+line6line7line8line9line10>delete.txt&&+gitadddelete.txt&&+gitcommit-m"base txt"&&++rmdelete.txt&&+test_write_linesline1line2line3line4line5\+line6line7line8>add.txt&&+test_write_linesline1line2line3line4line5\+line6line7line8line9>add.md&&+gitaddadd.txtadd.md&&+gitcommit-a-m"rename"&&+gitdiff-tree-MHEADHEAD^>actual&&+grep"add.md delete.txt"actual+'+ test_done
Personally, I'm fine with making this assumption. All of
our renames are based on heuristics, so any opportunity
to reduce the number of content comparisons is a win in
my mind. We also don't report a rename unless there _is_
an add/delete pair that is sufficiently close in content.
So, in this way, we are changing the optimization function
that is used to determine the "best" rename available. It
might be good to update documentation for how we choose
renames:
An add/delete pair is marked as a rename based on the
following similarity function:
1. If the blob content is identical, then those files
are marked as a rename. (Should we break ties here
based on the basename?)
2. Among pairs whose content matches the minimum
similarity limit, we optimize for:
i. among files with the same basename (trailer
after final '.') select pairs with highest
similarity.
ii. if no files with the same basename have the
minimum similarity, then select pairs with
highest similarity across all filenames.
The above was written quickly as an attempt, so it will
require careful editing to actually make sense to end
users.
Thanks,
-Stolee
Hi,
On Sun, Feb 7, 2021 at 6:38 AM Derrick Stolee [off-list ref] wrote:
On 2/6/21 5:52 PM, Elijah Newren via GitGitGadget wrote:
quoted
From: Elijah Newren <redacted>
Make use of the new find_basename_matches() function added in the last
two patches, to find renames more rapidly in cases where we can match up
files based on basenames.
This is a valuable heuristic.
quoted
For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
this change improves the performance as follows:
Before After
no-renames: 13.815 s ± 0.062 s 13.138 s ± 0.086 s
mega-renames: 1799.937 s ± 0.493 s 169.488 s ± 0.494 s
just-one-mega: 51.289 s ± 0.019 s 5.061 s ± 0.017 s
These numbers are very impressive.
Before I get too deep into reviewing these patches, I do want
to make it clear that the speed-up is coming at the cost of
a behavior change. We are restricting the "best match" search
to be first among files with common base name (although maybe
I would use 'suffix'?). If we search for a rename among all
additions and deletions ending the ".txt" we might find a
similarity match that is 60% and declare that a rename, even
if there is a ".txt" -> ".md" pair that has a 70% match.
I'm glad you all are open to possible behavioral changes, but I was
proposing a much smaller behavioral change that is quite different
than what you have suggested here. Perhaps my wording was poor; I
apologize for forgetting that "basename" has different meanings in
different contexts. Let me try again; I am not treating the filename
extension as special in any manner here; by "basename" I just mean the
portion of the path ignoring any leading directories. Thus
src/foo.txt
might be a good match against
source/foo.txt
but this optimization as a preliminary step would not consider
matching src/foo.txt against any of
source/bar.txt
source/foo.md
since the basenames ('bar.txt' and 'foo.md') do not match our original
file's basename ('foo.txt').
Of course, if this preliminary optimization step fails to find another
"foo.txt" to match src/foo.txt against (or finds more than one and
thus doesn't compare against any of them), then the fallback inexact
rename detection matrix might match it against either of those two
latter paths, as it always has.
quoted hunk
This could be documented in a test case, to demonstrate that
we are making this choice explicitly.
For example, here is a test that passes now, but would
start failing with your patches (if I understand them
correctly):
@@ -262,4 +262,21 @@ test_expect_success 'diff-tree -l0 defaults to a big rename limit, not zero' 'grep"myotherfile.*myfile"actual'+test_expect_success'multiple similarity choices''+test_write_linesline1line2line3line4line5\+line6line7line8line9line10>delete.txt&&+gitadddelete.txt&&+gitcommit-m"base txt"&&++rmdelete.txt&&+test_write_linesline1line2line3line4line5\+line6line7line8>add.txt&&+test_write_linesline1line2line3line4line5\+line6line7line8line9>add.md&&+gitaddadd.txtadd.md&&+gitcommit-a-m"rename"&&+gitdiff-tree-MHEADHEAD^>actual&&+grep"add.md delete.txt"actual+'+ test_done
Personally, I'm fine with making this assumption. All of
our renames are based on heuristics, so any opportunity
to reduce the number of content comparisons is a win in
my mind. We also don't report a rename unless there _is_
an add/delete pair that is sufficiently close in content.
So, in this way, we are changing the optimization function
that is used to determine the "best" rename available. It
might be good to update documentation for how we choose
renames:
Seems reasonable; I'll add some commentary below on the rules...
An add/delete pair is marked as a rename based on the
following similarity function:
0. Unless break detection is on, files with the same fullname are
considered the same file even if their content is completely
different. (With break detection turned on, we can have e.g. both
src/foo.txt -> src/bar.txt and otherdir/baz.txt -> src/foo.txt, i.e.
src/foo.txt can be both a source and a destination of a rename.)
[The merge machinery never turns break detection on, but
diffcore-rename is used by git diff, git log, etc. too, so if we're
documenting the rules we should cover all the cases.]
1. If the blob content is identical, then those files
are marked as a rename. (Should we break ties here
based on the basename?)
find_identical_files() already breaks ties based on basename_same(),
yes. So there's another area of the code that uses basenames to guide
rename detection already, just in a much more limited fashion.
2. Among pairs whose content matches the minimum
similarity limit, we optimize for:
i. among files with the same basename (trailer
after final '.') select pairs with highest
similarity.
This is an interesting idea, but is not what I implemented. It is
possible that your suggestion is also a useful optimization; it'd be
hard to know without trying. However, as noted in optimization batch
8 that I'll be submitting later, I'm worried about having any
optimization pre-steps doing more than O(1) comparisons per path (and
here you suggest comparing each .txt file with all other .txt files);
doing that can interact badly with optimization batch 9.
Additionally, unless we do something to avoid re-comparing files again
when doing the later all-unmatched-files-against-each-other check,
then worst case behavior can approach twice as slow as the original
code.
Anyway, the explanation I'd use for the optimization I've added in
this series is:
i. if looking through the two sets (of add pairs, and of delete
pairs), there is exactly one file with the same basename from each
set, and they have the minimum similarity, then mark them as a rename
Optimization batch 8 will extend this particular rule.
Optimization batches 9 and 10 will optimize the rename detection more,
but instead of using rule changes, will instead pass in a list of
"irrelevant" sources that can be skipped. The trick is in determining
source files that are irrelevant and why. I'm not sure if we want to
also mention in the rules that different areas of the code (the merge
machinery, log --follow, etc.) can make the rename detection focus
just on some "relevant" subset of files. (Which will also touch on
optimization batch 12.)
ii. if no files with the same basename have the
minimum similarity, then select pairs with
highest similarity across all filenames.
Yes, this will remain as the fallback at the very end.
The above was written quickly as an attempt, so it will
require careful editing to actually make sense to end
users.
Yeah, and we probably also need to mention copy detection above
somehow too, and add more precise wording about how break detection is
involved.
Hi,
On Sun, Feb 7, 2021 at 6:38 AM Derrick Stolee [off-list ref] wrote:
quoted
On 2/6/21 5:52 PM, Elijah Newren via GitGitGadget wrote:
quoted
From: Elijah Newren <redacted>
Make use of the new find_basename_matches() function added in the last
two patches, to find renames more rapidly in cases where we can match up
files based on basenames.
This is a valuable heuristic.
quoted
For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
this change improves the performance as follows:
Before After
no-renames: 13.815 s ± 0.062 s 13.138 s ± 0.086 s
mega-renames: 1799.937 s ± 0.493 s 169.488 s ± 0.494 s
just-one-mega: 51.289 s ± 0.019 s 5.061 s ± 0.017 s
These numbers are very impressive.
Before I get too deep into reviewing these patches, I do want
to make it clear that the speed-up is coming at the cost of
a behavior change. We are restricting the "best match" search
to be first among files with common base name (although maybe
I would use 'suffix'?). If we search for a rename among all
additions and deletions ending the ".txt" we might find a
similarity match that is 60% and declare that a rename, even
if there is a ".txt" -> ".md" pair that has a 70% match.
I'm glad you all are open to possible behavioral changes, but I was
proposing a much smaller behavioral change that is quite different
than what you have suggested here. Perhaps my wording was poor; I
apologize for forgetting that "basename" has different meanings in
different contexts. Let me try again; I am not treating the filename
extension as special in any manner here; by "basename" I just mean the
portion of the path ignoring any leading directories. Thus
src/foo.txt
might be a good match against
source/foo.txt
but this optimization as a preliminary step would not consider
matching src/foo.txt against any of
source/bar.txt
source/foo.md
since the basenames ('bar.txt' and 'foo.md') do not match our original
file's basename ('foo.txt').
Of course, if this preliminary optimization step fails to find another
"foo.txt" to match src/foo.txt against (or finds more than one and
thus doesn't compare against any of them), then the fallback inexact
rename detection matrix might match it against either of those two
latter paths, as it always has.
Thank you for making it clear that I had misunderstood what the
optimization is actually doing. A much more narrow scope makes
more sense, and avoids the quadratic problem even when many files
of the same suffix are renamed.
quoted
This could be documented in a test case, to demonstrate that
we are making this choice explicitly.
My test is thus bogus, but you could have a similar one for
your actual optimization.
quoted
So, in this way, we are changing the optimization function
that is used to determine the "best" rename available. It
might be good to update documentation for how we choose
renames:
Seems reasonable; I'll add some commentary below on the rules...
Your commentary is helpful. I look forward to reading your
carefully-written docs in the next version ;).
quoted
i. among files with the same basename (trailer
after final '.') select pairs with highest
similarity.
This is an interesting idea, but is not what I implemented.
That's what I get for reading the commit messages quickly and
commenting on what I _think_ is going on instead of actually
reading the code carefully. Sorry about that.
It is
possible that your suggestion is also a useful optimization; it'd be
hard to know without trying. However, as noted in optimization batch
8 that I'll be submitting later, I'm worried about having any
optimization pre-steps doing more than O(1) comparisons per path (and
here you suggest comparing each .txt file with all other .txt files);
doing that can interact badly with optimization batch 9.
Additionally, unless we do something to avoid re-comparing files again
when doing the later all-unmatched-files-against-each-other check,
then worst case behavior can approach twice as slow as the original
code.
Right. If Git decides to reorganize all of its *.c files in one
commit, we would still get quadratic behavior in rename detection.
Maybe it's not _that_ much of an improvement.
Thanks,
-Stolee
On Mon, Feb 8, 2021 at 3:31 AM Derrick Stolee [off-list ref] wrote:
On 2/8/2021 3:27 AM, Elijah Newren wrote:
quoted
Hi,
On Sun, Feb 7, 2021 at 6:38 AM Derrick Stolee [off-list ref] wrote:
quoted
On 2/6/21 5:52 PM, Elijah Newren via GitGitGadget wrote:
quoted
From: Elijah Newren <redacted>
Make use of the new find_basename_matches() function added in the last
two patches, to find renames more rapidly in cases where we can match up
files based on basenames.
This is a valuable heuristic.
quoted
For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
this change improves the performance as follows:
Before After
no-renames: 13.815 s ± 0.062 s 13.138 s ± 0.086 s
mega-renames: 1799.937 s ± 0.493 s 169.488 s ± 0.494 s
just-one-mega: 51.289 s ± 0.019 s 5.061 s ± 0.017 s
These numbers are very impressive.
Before I get too deep into reviewing these patches, I do want
to make it clear that the speed-up is coming at the cost of
a behavior change. We are restricting the "best match" search
to be first among files with common base name (although maybe
I would use 'suffix'?). If we search for a rename among all
additions and deletions ending the ".txt" we might find a
similarity match that is 60% and declare that a rename, even
if there is a ".txt" -> ".md" pair that has a 70% match.
I'm glad you all are open to possible behavioral changes, but I was
proposing a much smaller behavioral change that is quite different
than what you have suggested here. Perhaps my wording was poor; I
apologize for forgetting that "basename" has different meanings in
different contexts. Let me try again; I am not treating the filename
extension as special in any manner here; by "basename" I just mean the
portion of the path ignoring any leading directories. Thus
src/foo.txt
might be a good match against
source/foo.txt
but this optimization as a preliminary step would not consider
matching src/foo.txt against any of
source/bar.txt
source/foo.md
since the basenames ('bar.txt' and 'foo.md') do not match our original
file's basename ('foo.txt').
Of course, if this preliminary optimization step fails to find another
"foo.txt" to match src/foo.txt against (or finds more than one and
thus doesn't compare against any of them), then the fallback inexact
rename detection matrix might match it against either of those two
latter paths, as it always has.
Thank you for making it clear that I had misunderstood what the
optimization is actually doing. A much more narrow scope makes
more sense, and avoids the quadratic problem even when many files
of the same suffix are renamed.
quoted
quoted
This could be documented in a test case, to demonstrate that
we are making this choice explicitly.
My test is thus bogus, but you could have a similar one for
your actual optimization.
Yes, good point.
quoted
quoted
So, in this way, we are changing the optimization function
that is used to determine the "best" rename available. It
might be good to update documentation for how we choose
renames:
Seems reasonable; I'll add some commentary below on the rules...
Your commentary is helpful. I look forward to reading your
carefully-written docs in the next version ;).
:-)
quoted
quoted
i. among files with the same basename (trailer
after final '.') select pairs with highest
similarity.
This is an interesting idea, but is not what I implemented.
That's what I get for reading the commit messages quickly and
commenting on what I _think_ is going on instead of actually
reading the code carefully. Sorry about that.
There's absolutely no need to apologize. If you read all three commit
messages and you didn't understand the idea, then clearly there's a
bug in my commit messages. Thanks for highlighting it; I'll figure
out how to reword or add extra verbiage to make it clear. Something
in these follow-up emails seemed to work, so I'll try to incorporate
stuff from them.
quoted
It is
possible that your suggestion is also a useful optimization; it'd be
hard to know without trying. However, as noted in optimization batch
8 that I'll be submitting later, I'm worried about having any
optimization pre-steps doing more than O(1) comparisons per path (and
here you suggest comparing each .txt file with all other .txt files);
doing that can interact badly with optimization batch 9.
Additionally, unless we do something to avoid re-comparing files again
when doing the later all-unmatched-files-against-each-other check,
then worst case behavior can approach twice as slow as the original
code.
Right. If Git decides to reorganize all of its *.c files in one
commit, we would still get quadratic behavior in rename detection.
Maybe it's not _that_ much of an improvement.
Thanks,
-Stolee
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-09 11:42:54
From: Elijah Newren <redacted>
It is not uncommon in real world repositories for the majority of file
renames to not change the basename of the file; i.e. most "renames" are
just a move of files into different directories. We can make use of
this to avoid comparing all rename source candidates with all rename
destination candidates, by first comparing sources to destinations with
the same basenames. If two files with the same basename are
sufficiently similar, we record the rename; if not, we include those
files in the more exhaustive matrix comparison.
This means we are adding a set of preliminary additional comparisons,
but for each file we only compare it with at most one other file. For
example, if there was a include/media/device.h that was deleted and a
src/module/media/device.h that was added, and there were no other
device.h files added or deleted between the commits being compared,
then these two files would be compared in the preliminary step.
This commit does not yet actually employ this new optimization, it
merely adds a function which can be used for this purpose. The next
commit will do the necessary plumbing to make use of it.
Note that this optimization might give us different results than without
the optimization, because it's possible that despite files with the same
basename being sufficiently similar to be considered a rename, there's
an even better match between files without the same basename. I think
that is okay for four reasons: (1) it's easy to explain to the users
what happened if it does ever occur (or even for them to intuitively
figure out), (2) as the next patch will show it provides such a large
performance boost that it's worth the tradeoff, and (3) it's somewhat
unlikely that despite having unique matching basenames that other files
serve as better matches. Reason (4) takes a full paragraph to
explain...
If the previous three reasons aren't enough, consider what rename
detection already does. Break detection is not the default, meaning
that if files have the same _fullname_, then they are considered related
even if they are 0% similar. In fact, in such a case, we don't even
bother comparing the files to see if they are similar let alone
comparing them to all other files to see what they are most similar to.
Basically, we override content similarity based on sufficient filename
similarity. Without the filename similarity (currently implemented as
an exact match of filename), we swing the pendulum the opposite
direction and say that filename similarity is irrelevant and compare a
full N x M matrix of sources and destinations to find out which have the
most similar contents. This optimization just adds another form of
filename similarity comparison, but augments it with a file content
similarity check as well. Basically, if two files have the same
basename and are sufficiently similar to be considered a rename, mark
them as such without comparing the two to all other rename candidates.
Signed-off-by: Elijah Newren <redacted>
---
diffcore-rename.c | 94 +++++++++++++++++++++++++++++++++++++++++++++--
1 file changed, 91 insertions(+), 3 deletions(-)
@@ -372,10 +372,48 @@ static int find_basename_matches(struct diff_options *options,intminimum_score,intnum_src){-inti;+/*+*WhenIchecked,over76%offilerenamesinlinuxjustmoved+*filestoadifferentdirectorybutkeptthesamebasename.gcc+*didthatwithover64%ofrenames,geckodiditwithover79%,+*andWebKitdiditwithover89%.+*+*ThereforewecanbypassthenormalexhaustiveNxMmatrix+*comparisonofsimilaritiesbetweenallpotentialrenamesources+*anddestinationsbyinsteadusingfilebasenameasahint,checking+*forsimilaritybetweenfileswiththesamebasename,andifwe+*findapairthataresufficientlysimilar,recordtherename+*pairandexcludethosetwofromtheNxMmatrix.+*+*This*might*causeustofindalessthanoptimalpairing(if+*thereisanotherfilethatweareevenmoresimilartobuthasa+*differentbasename).Giventhehugeperformanceadvantage+*basenamematchingprovides,andgiventhefrequencywithwhich+*peopleusethesamebasenameinrealworldprojects,that'sa+*trade-offwearewillingtoacceptwhendoingjustrename+*detection.However,ifsomeonewantscopydetectionthat+*impliestheyarewillingtospendmorecyclestofind+*similaritiesbetweenfiles,soitmaybelesslikelythatthis+*heuristiciswanted.+*/++inti,renames=0;structstrintmapsources;structstrintmapdests;+/*+*Theprefetechingstuffwantstoknowifitcanskipprefetchingblobs+*thatareunmodified.unmodifiedblobsareonlyrelevantwhendoing+*copydetection.find_basename_matches()isonlyusedwhendetecting+*renames,notwhendetectingcopies,soit'llonlybeusedwhenafile+*onlyexistedinthesource.Sincewealreadyknowthatthefile+*won'tbeunmodified,there'snopointcheckingforit;that'sjusta+*wasteofresources.Sosetskip_unmodifiedto0sothat+*estimate_similarity()andprefetch()won'twasteresourceschecking+*forsomethingwealreadyknowisfalse.+*/+intskip_unmodified=0;+/* Create maps of basename -> fullname(s) for sources and dests */strintmap_init_with_options(&sources,-1,NULL,0);strintmap_init_with_options(&dests,-1,NULL,0);
@@ -412,12 +450,62 @@ static int find_basename_matches(struct diff_options *options,strintmap_set(&dests,base,i);}-/* TODO: Make use of basenames source and destination basenames */+/* Now look for basename matchups and do similarity estimation */+for(i=0;i<num_src;++i){+char*filename=rename_src[i].p->one->path;+char*base=NULL;+intptr_tsrc_index;+intptr_tdst_index;++/* Get the basename */+base=strrchr(filename,'/');+base=(base?base+1:filename);++/* Find out if this basename is unique among sources */+src_index=strintmap_get(&sources,base);+if(src_index==-1)+continue;/* not a unique basename; skip it */+assert(src_index==i);++if(strintmap_contains(&dests,base)){+structdiff_filespec*one,*two;+intscore;++/* Find out if this basename is unique among dests */+dst_index=strintmap_get(&dests,base);+if(dst_index==-1)+continue;/* not a unique basename; skip it */++/* Ignore this dest if already used in a rename */+if(rename_dst[dst_index].is_rename)+continue;/* already used previously */++/* Estimate the similarity */+one=rename_src[src_index].p->one;+two=rename_dst[dst_index].p->two;+score=estimate_similarity(options->repo,one,two,+minimum_score,skip_unmodified);++/* If sufficiently similar, record as rename pair */+if(score<minimum_score)+continue;+record_rename_pair(dst_index,src_index,score);+renames++;++/*+*Foundarenamesodon'tneedtextanymore;ifwe+*didn'tfindarename,thefilespec_blobwouldget+*re-usedwhendoingthematrixofcomparisons.+*/+diff_free_filespec_blob(one);+diff_free_filespec_blob(two);+}+}strintmap_clear(&sources);strintmap_clear(&dests);-return0;+returnrenames;}#define NUM_CANDIDATE_PER_DST 4
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-09 11:42:58
From: Elijah Newren <redacted>
Make use of the new find_basename_matches() function added in the last
two patches, to find renames more rapidly in cases where we can match up
files based on basenames. As a quick reminder (see the last two commit
messages for more details), this means for example that
docs/extensions.txt and docs/config/extensions.txt are considered likely
renames if there are no 'extensions.txt' files elsewhere among the added
and deleted files, and if a similarity check confirms they are similar,
then they are marked as a rename without looking for a better similarity
match among other files. This is a behavioral change, as covered in
more detail in the previous commit message.
We do not use this heuristic together with either break or copy
detection. The point of break detection is to say that filename
similarity does not imply file content similarity, and we only want to
know about file content similarity. The point of copy detection is to
use more resources to check for additional similarities, while this is
an optimization that uses far less resources but which might also result
in finding slightly fewer similarities. So the idea behind this
optimization goes against both of those features, and will be turned off
for both.
For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
this change improves the performance as follows:
Before After
no-renames: 13.815 s ± 0.062 s 13.138 s ± 0.086 s
mega-renames: 1799.937 s ± 0.493 s 169.488 s ± 0.494 s
just-one-mega: 51.289 s ± 0.019 s 5.061 s ± 0.017 s
Signed-off-by: Elijah Newren <redacted>
---
diffcore-rename.c | 46 +++++++++++++++++++++++++++++++++++++++++-----
1 file changed, 41 insertions(+), 5 deletions(-)
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-09 11:43:57
From: Elijah Newren <redacted>
We want to make use of unique basenames to help inform rename detection,
so that more likely pairings can be checked first. (src/moduleA/foo.txt
and source/module/A/foo.txt are likely related if there are no other
'foo.txt' files among the deleted and added files.) Add a new function,
not yet used, which creates a map of the unique basenames within
rename_src and another within rename_dst, together with the indices
within rename_src/rename_dst where those basenames show up. Non-unique
basenames still show up in the map, but have an invalid index (-1).
This function was inspired by the fact that in real world repositories,
most renames often do not involve a basename change. Here are some
sample repositories and the percentage of their historical renames (as of
early 2020) that did not involve a basename change:
* linux: 76%
* gcc: 64%
* gecko: 79%
* webkit: 89%
Signed-off-by: Elijah Newren <redacted>
---
diffcore-rename.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 53 insertions(+)
@@ -367,6 +367,59 @@ static int find_exact_renames(struct diff_options *options)returnrenames;}+MAYBE_UNUSED+staticintfind_basename_matches(structdiff_options*options,+intminimum_score,+intnum_src)+{+inti;+structstrintmapsources;+structstrintmapdests;++/* Create maps of basename -> fullname(s) for sources and dests */+strintmap_init_with_options(&sources,-1,NULL,0);+strintmap_init_with_options(&dests,-1,NULL,0);+for(i=0;i<num_src;++i){+char*filename=rename_src[i].p->one->path;+char*base;++/* exact renames removed in remove_unneeded_paths_from_src() */+assert(!rename_src[i].p->one->rename_used);++base=strrchr(filename,'/');+base=(base?base+1:filename);++/* Record index within rename_src (i) if basename is unique */+if(strintmap_contains(&sources,base))+strintmap_set(&sources,base,-1);+else+strintmap_set(&sources,base,i);+}+for(i=0;i<rename_dst_nr;++i){+char*filename=rename_dst[i].p->two->path;+char*base;++if(rename_dst[i].is_rename)+continue;/* involved in exact match already. */++base=strrchr(filename,'/');+base=(base?base+1:filename);++/* Record index within rename_dst (i) if basename is unique */+if(strintmap_contains(&dests,base))+strintmap_set(&dests,base,-1);+else+strintmap_set(&dests,base,i);+}++/* TODO: Make use of basenames source and destination basenames */++strintmap_clear(&sources);+strintmap_clear(&dests);++return0;+}+#define NUM_CANDIDATE_PER_DST 4staticvoidrecord_if_better(structdiff_scorem[],structdiff_score*o){
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-09 11:44:05
From: Elijah Newren <redacted>
The last few patches have introduced a new preliminary step when rename
detection is on but both break detection and copy detection are off.
Document this new step. While we're at it, add a testcase that checks
the new behavior as well.
Signed-off-by: Elijah Newren <redacted>
---
Documentation/gitdiffcore.txt | 15 +++++++++++++++
t/t4001-diff-rename.sh | 24 ++++++++++++++++++++++++
2 files changed, 39 insertions(+)
@@ -168,6 +168,21 @@ a similarity score different from the default of 50% by giving a number after the "-M" or "-C" option (e.g. "-M8" to tell it to use 8/10 = 80%).+Note that when rename detection is on but both copy and break+detection are off, rename detection adds a preliminary step that first+checks files with the same basename. If files with the same basename+are sufficiently similar, it will mark them as renames and exclude+them from the later quadratic step (the one that pairwise compares all+unmatched files to find the "best" matches, determined by the highest+content similarity). So, for example, if docs/extensions.txt and+docs/config/extensions.txt have similar content, then they will be+marked as a rename even if it turns out that docs/extensions.txt was+more similar to src/extension-checks.c. At most, one comparison is+done per file in this preliminary pass; so if there are several+extensions.txt files throughout the directory hierarchy that were+added and deleted, this preliminary step will be skipped for those+files.+ Note. When the "-C" option is used with `--find-copies-harder` option, 'git diff-{asterisk}' commands feed unmodified filepairs to diffcore mechanism as well as modified ones. This lets the copy
@@ -262,4 +262,28 @@ test_expect_success 'diff-tree -l0 defaults to a big rename limit, not zero' 'grep"myotherfile.*myfile"actual'+test_expect_success'basename similarity vs best similarity''+mkdirsubdir&&+test_write_linesline1line2line3line4line5\+line6line7line8line9line10>subdir/file.txt&&+gitaddsubdir/file.txt&&+gitcommit-m"base txt"&&++gitrmsubdir/file.txt&&+test_write_linesline1line2line3line4line5\+line6line7line8>file.txt&&+test_write_linesline1line2line3line4line5\+line6line7line8line9>file.md&&+gitaddfile.txtfile.md&&+gitcommit-a-m"rename"&&+gitdiff-tree-r-M--name-statusHEAD^HEAD>actual&&+# subdir/file.txt is 89% similar to file.md, 78% similar to file.txt,+# but since same basenames are checked first...+cat>expected<<-\EOF&&+Afile.md+R078subdir/file.txtfile.txt+EOF+test_cmpexpectedactual+'+ test_done
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-09 11:46:16
This series depends on ort-perf-batch-6[1].
This series uses file basenames in a basic fashion to guide rename
detection.
Changes since v1:
* Significant edits to the commit messages to make them explain the basic
idea better and (hopefully) prevent misunderstandings.
* Add a commit at the end that updates the documentation and includes a new
testcase
* Modify the code to make it clearer that it can already handle using a
different score for basename comparison similarity, even if we don't use
that ability yet (see below)
Changes not yet included -- I need input about what is wanted:
* Stolee suggested not creating a separate score for basename comparisons,
at least not yet. Junio suggested it may be prudent to use a higher score
for that than whatever -M option the user provided for normal
comparisons...but didn't suggest whether it should be a separate
user-specified option, or some kind of weighted average of the -M option
and MAX_SCORE (e.g. use 60% if -M is 50%, or use 80% if -M is 75%). I
tweaked the code to make it clearer that it already is able to handle
such a score difference, but I'm not sure what whether we want an
automatically computed higher value or a user-controlled possibly higher
value.
[1] https://lore.kernel.org/git/xmqqlfc4byt6.fsf@gitster.c.googlers.com/ [2]
https://github.com/newren/presentations/blob/pdfs/merge-performance/merge-performance-slides.pdf
Elijah Newren (4):
diffcore-rename: compute basenames of all source and dest candidates
diffcore-rename: complete find_basename_matches()
diffcore-rename: guide inexact rename detection based on basenames
gitdiffcore doc: mention new preliminary step for rename detection
Documentation/gitdiffcore.txt | 15 +++
diffcore-rename.c | 185 +++++++++++++++++++++++++++++++++-
t/t4001-diff-rename.sh | 24 +++++
3 files changed, 220 insertions(+), 4 deletions(-)
base-commit: 7ae9460d3dba84122c2674b46e4339b9d42bdedd
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-843%2Fnewren%2Fort-perf-batch-7-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-843/newren/ort-perf-batch-7-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/843
Range-diff vs v1:
1: 377a4a39fa86 ! 1: 381a45d239bb diffcore-rename: compute basenames of all source and dest candidates
@@ Commit message
diffcore-rename: compute basenames of all source and dest candidates
We want to make use of unique basenames to help inform rename detection,
- so that more likely pairings can be checked first. Add a new function,
+ so that more likely pairings can be checked first. (src/moduleA/foo.txt
+ and source/module/A/foo.txt are likely related if there are no other
+ 'foo.txt' files among the deleted and added files.) Add a new function,
not yet used, which creates a map of the unique basenames within
rename_src and another within rename_dst, together with the indices
within rename_src/rename_dst where those basenames show up. Non-unique
basenames still show up in the map, but have an invalid index (-1).
+ This function was inspired by the fact that in real world repositories,
+ most renames often do not involve a basename change. Here are some
+ sample repositories and the percentage of their historical renames (as of
+ early 2020) that did not involve a basename change:
+ * linux: 76%
+ * gcc: 64%
+ * gecko: 79%
+ * webkit: 89%
+
Signed-off-by: Elijah Newren [off-list ref]
## diffcore-rename.c ##
2: 5fb4493247ff ! 2: dcd0175229aa diffcore-rename: complete find_basename_matches()
@@ Commit message
sufficiently similar, we record the rename; if not, we include those
files in the more exhaustive matrix comparison.
+ This means we are adding a set of preliminary additional comparisons,
+ but for each file we only compare it with at most one other file. For
+ example, if there was a include/media/device.h that was deleted and a
+ src/module/media/device.h that was added, and there were no other
+ device.h files added or deleted between the commits being compared,
+ then these two files would be compared in the preliminary step.
+
+ This commit does not yet actually employ this new optimization, it
+ merely adds a function which can be used for this purpose. The next
+ commit will do the necessary plumbing to make use of it.
+
Note that this optimization might give us different results than without
the optimization, because it's possible that despite files with the same
basename being sufficiently similar to be considered a rename, there's
an even better match between files without the same basename. I think
- that is okay for four reasons: (1) That seems somewhat unlikely in
- practice, (2) it's easy to explain to the users what happened if it does
- ever occur (or even for them to intuitively figure out), and (3) as the
- next patch will show it provides such a large performance boost that
- it's worth the tradeoff. Reason (4) takes a full paragraph to
+ that is okay for four reasons: (1) it's easy to explain to the users
+ what happened if it does ever occur (or even for them to intuitively
+ figure out), (2) as the next patch will show it provides such a large
+ performance boost that it's worth the tradeoff, and (3) it's somewhat
+ unlikely that despite having unique matching basenames that other files
+ serve as better matches. Reason (4) takes a full paragraph to
explain...
If the previous three reasons aren't enough, consider what rename
@@ Commit message
basename and are sufficiently similar to be considered a rename, mark
them as such without comparing the two to all other rename candidates.
- We do not use this heuristic together with either break or copy
- detection. The point of break detection is to say that filename
- similarity does not imply file content similarity, and we only want to
- know about file content similarity. The point of copy detection is to
- use more resources to check for additional similarities, while this is
- an optimization that uses far less resources but which might also result
- in finding slightly fewer similarities. So the idea behind this
- optimization goes against both of those features, and will be turned off
- for both.
-
- Note that this optimization is not yet effective in any situation, as
- the function is still unused. The next commit will hook it into the
- code so that it is used when rename detection is wanted, but neither
- copy nor break detection are.
-
Signed-off-by: Elijah Newren [off-list ref]
## diffcore-rename.c ##
3: 1d941c35076e ! 3: ce2173aa1fb7 diffcore-rename: guide inexact rename detection based on basenames
@@ Commit message
Make use of the new find_basename_matches() function added in the last
two patches, to find renames more rapidly in cases where we can match up
- files based on basenames.
+ files based on basenames. As a quick reminder (see the last two commit
+ messages for more details), this means for example that
+ docs/extensions.txt and docs/config/extensions.txt are considered likely
+ renames if there are no 'extensions.txt' files elsewhere among the added
+ and deleted files, and if a similarity check confirms they are similar,
+ then they are marked as a rename without looking for a better similarity
+ match among other files. This is a behavioral change, as covered in
+ more detail in the previous commit message.
+
+ We do not use this heuristic together with either break or copy
+ detection. The point of break detection is to say that filename
+ similarity does not imply file content similarity, and we only want to
+ know about file content similarity. The point of copy detection is to
+ use more resources to check for additional similarities, while this is
+ an optimization that uses far less resources but which might also result
+ in finding slightly fewer similarities. So the idea behind this
+ optimization goes against both of those features, and will be turned off
+ for both.
For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
@@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)
+ remove_unneeded_paths_from_src(want_copies);
+ trace2_region_leave("diff", "cull after exact", options->repo);
+ } else {
++ /* Determine minimum score to match basenames */
++ int min_basename_score = (int)(5*minimum_score + 0*MAX_SCORE)/5;
++
+ /*
+ * Cull sources:
+ * - remove ones involved in renames (found via exact match)
@@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)
+
+ /* Utilize file basenames to quickly find renames. */
+ trace2_region_enter("diff", "basename matches", options->repo);
-+ rename_count += find_basename_matches(options, minimum_score,
++ rename_count += find_basename_matches(options,
++ min_basename_score,
+ rename_src_nr);
+ trace2_region_leave("diff", "basename matches", options->repo);
+
-: ------------ > 4: a0e75d8cd6bd gitdiffcore doc: mention new preliminary step for rename detection
--
gitgitgadget
On 2/9/2021 6:32 AM, Elijah Newren via GitGitGadget wrote:
From: Elijah Newren <redacted>
The last few patches have introduced a new preliminary step when rename
detection is on but both break detection and copy detection are off.
Document this new step. While we're at it, add a testcase that checks
the new behavior as well.
Thanks for adding this documentation and test.
+Note that when rename detection is on but both copy and break
+detection are off, rename detection adds a preliminary step that first
+checks files with the same basename. If files with the same basename
I find myself wanting a definition of 'basename' here, but perhaps I'm
just being pedantic. A quick search clarifies this as a standard term [1]
of which I was just ignorant.
[1] https://man7.org/linux/man-pages/man3/basename.3.html
+are sufficiently similar, it will mark them as renames and exclude
+them from the later quadratic step (the one that pairwise compares all
+unmatched files to find the "best" matches, determined by the highest
+content similarity). So, for example, if docs/extensions.txt and
+docs/config/extensions.txt have similar content, then they will be
+marked as a rename even if it turns out that docs/extensions.txt was
+more similar to src/extension-checks.c. At most, one comparison is
+done per file in this preliminary pass; so if there are several
+extensions.txt files throughout the directory hierarchy that were
+added and deleted, this preliminary step will be skipped for those
+files.
+test_expect_success 'basename similarity vs best similarity' '
+ mkdir subdir &&
+ test_write_lines line1 line2 line3 line4 line5 \
+ line6 line7 line8 line9 line10 >subdir/file.txt &&
+ git add subdir/file.txt &&
+ git commit -m "base txt" &&
+
+ git rm subdir/file.txt &&
+ test_write_lines line1 line2 line3 line4 line5 \
+ line6 line7 line8 >file.txt &&
+ test_write_lines line1 line2 line3 line4 line5 \
+ line6 line7 line8 line9 >file.md &&
+ git add file.txt file.md &&
+ git commit -a -m "rename" &&
+ git diff-tree -r -M --name-status HEAD^ HEAD >actual &&
+ # subdir/file.txt is 89% similar to file.md, 78% similar to file.txt,
+ # but since same basenames are checked first...
+ cat >expected <<-\EOF &&
+ A file.md
+ R078 subdir/file.txt file.txt
+ EOF
+ test_cmp expected actual
+'
+
I appreciate the additional comments in this test to make it clear
what you are testing. A minor nit is that the test could have been
added at the start of the series to document the _old_ behavior.
The 'expected' file would have this content:
+ cat >expected <<-\EOF &&
+ A file.txt
+ R078 subdir/file.txt file.md
+ EOF
Then, this test case would change the expected output in the same
patch that introduces the behavior change.
Thanks,
-Stolee
On 2/9/2021 6:32 AM, Elijah Newren via GitGitGadget wrote:
From: Elijah Newren <redacted>
We want to make use of unique basenames to help inform rename detection,
so that more likely pairings can be checked first. (src/moduleA/foo.txt
and source/module/A/foo.txt are likely related if there are no other
'foo.txt' files among the deleted and added files.) Add a new function,
not yet used, which creates a map of the unique basenames within
rename_src and another within rename_dst, together with the indices
within rename_src/rename_dst where those basenames show up. Non-unique
basenames still show up in the map, but have an invalid index (-1).
This function was inspired by the fact that in real world repositories,
most renames often do not involve a basename change. Here are some
sample repositories and the percentage of their historical renames (as of
early 2020) that did not involve a basename change:
I found this difficult to parse. Perhaps instead
"the percentage of their renames that preserved basenames".
We might also need something stronger, though: which percentage of renames
preserved the basename but also had no other copy of that basename in the
scope of all add/deletes?
Is this reproducible from a shell command that could be documented here?
+MAYBE_UNUSED
+static int find_basename_matches(struct diff_options *options,
+ int minimum_score,
+ int num_src)
+{
+ int i;
+ struct strintmap sources;
+ struct strintmap dests;
+
+ /* Create maps of basename -> fullname(s) for sources and dests */
+ strintmap_init_with_options(&sources, -1, NULL, 0);
+ strintmap_init_with_options(&dests, -1, NULL, 0);
Initially, I was wondering why we need the map for each side, but we will need
to enforce uniqueness in each set, so OK.
+ for (i = 0; i < num_src; ++i) {
+ char *filename = rename_src[i].p->one->path;
+ char *base;
+
+ /* exact renames removed in remove_unneeded_paths_from_src() */
+ assert(!rename_src[i].p->one->rename_used);
+
+ base = strrchr(filename, '/');
+ base = (base ? base+1 : filename);
nit: "base + 1"
Also, this is used here and below. Perhaps it's worth pulling out as a
helper? I see similar code being duplicated in these existing spots:
* diff-no-index.c:append_basename()
* help.c:append_similar_ref()
* packfile.c:pack_basename()
* replace-object.c:register_replace_ref()
* setup.c:read_gitfile_gently()
* builtin/rebase.c:cmd_rebase()
* builtin/stash.c:do_create_stash()
* builtin/worktree.c:add_worktree()
* contrib/credential/gnome-keyring/git-credential-gnome-keyring.c:usage()
* contrib/credential/libsecret/git-credential-libsecret.c:usage()
* trace2/tr2_dst.c:tr2_dst_try_auto_path()
There are other places that use strchr(_, '/') but they seem to be related
to peeling basenames off of paths and using the leading portion of the path.
+ /* Record index within rename_src (i) if basename is unique */
+ if (strintmap_contains(&sources, base))
+ strintmap_set(&sources, base, -1);
+ else
+ strintmap_set(&sources, base, i);
+ }
+ for (i = 0; i < rename_dst_nr; ++i) {
+ char *filename = rename_dst[i].p->two->path;
+ char *base;
+
+ if (rename_dst[i].is_rename)
+ continue; /* involved in exact match already. */
+
+ base = strrchr(filename, '/');
+ base = (base ? base+1 : filename);
+
+ /* Record index within rename_dst (i) if basename is unique */
+ if (strintmap_contains(&dests, base))
+ strintmap_set(&dests, base, -1);
+ else
+ strintmap_set(&dests, base, i);
+ }
+
+ /* TODO: Make use of basenames source and destination basenames */
+
+ strintmap_clear(&sources);
+ strintmap_clear(&dests);
+
+ return 0;
+}
On 2/9/2021 6:32 AM, Elijah Newren via GitGitGadget wrote:
+ /*
+ * When I checked, over 76% of file renames in linux just moved
Perhaps "In late 2020," instead of "When I checked".
+ * files to a different directory but kept the same basename. gcc
+ * did that with over 64% of renames, gecko did it with over 79%,
+ * and WebKit did it with over 89%.
+ *
+ * Therefore we can bypass the normal exhaustive NxM matrix
+ * comparison of similarities between all potential rename sources
+ * and destinations by instead using file basename as a hint, checking
+ * for similarity between files with the same basename, and if we
+ * find a pair that are sufficiently similar, record the rename
+ * pair and exclude those two from the NxM matrix.
+ *
+ * This *might* cause us to find a less than optimal pairing (if
+ * there is another file that we are even more similar to but has a
+ * different basename). Given the huge performance advantage
+ * basename matching provides, and given the frequency with which
+ * people use the same basename in real world projects, that's a
+ * trade-off we are willing to accept when doing just rename
+ * detection. However, if someone wants copy detection that
+ * implies they are willing to spend more cycles to find
+ * similarities between files, so it may be less likely that this
+ * heuristic is wanted.
+ */
+
+ int i, renames = 0;
struct strintmap sources;
struct strintmap dests;
...
+ * copy detection. find_basename_matches() is only used when detecting
+ * renames, not when detecting copies, so it'll only be used when a file
+ * only existed in the source. Since we already know that the file
There are two "only"s in this sentence. Just awkward, not wrong.
+ * won't be unmodified, there's no point checking for it; that's just a
+ * waste of resources. So set skip_unmodified to 0 so that
+ * estimate_similarity() and prefetch() won't waste resources checking
+ * for something we already know is false.
+ */
+ int skip_unmodified = 0;
+
- /* TODO: Make use of basenames source and destination basenames */
+ /* Now look for basename matchups and do similarity estimation */
+ for (i = 0; i < num_src; ++i) {
+ char *filename = rename_src[i].p->one->path;
+ char *base = NULL;
+ intptr_t src_index;
+ intptr_t dst_index;
+
+ /* Get the basename */
+ base = strrchr(filename, '/');
+ base = (base ? base+1 : filename);
Here is the third instance of this in the same function. At minimum we should
extract a helper for you to consume.
+ /* Find out if this basename is unique among sources */
+ src_index = strintmap_get(&sources, base);
+ if (src_index == -1)
+ continue; /* not a unique basename; skip it */
+ assert(src_index == i);
+
+ if (strintmap_contains(&dests, base)) {
+ struct diff_filespec *one, *two;
+ int score;
+
+ /* Find out if this basename is unique among dests */
+ dst_index = strintmap_get(&dests, base);
+ if (dst_index == -1)
+ continue; /* not a unique basename; skip it */
+
+ /* Ignore this dest if already used in a rename */
+ if (rename_dst[dst_index].is_rename)
+ continue; /* already used previously */
+
+ /* Estimate the similarity */
+ one = rename_src[src_index].p->one;
+ two = rename_dst[dst_index].p->two;
+ score = estimate_similarity(options->repo, one, two,
+ minimum_score, skip_unmodified);
+
+ /* If sufficiently similar, record as rename pair */
+ if (score < minimum_score)
+ continue;
+ record_rename_pair(dst_index, src_index, score);
+ renames++;
+
+ /*
+ * Found a rename so don't need text anymore; if we
+ * didn't find a rename, the filespec_blob would get
+ * re-used when doing the matrix of comparisons.
+ */
+ diff_free_filespec_blob(one);
+ diff_free_filespec_blob(two);
+ }
+ }
...this? (except the regions are renamed)
Could this be simplified as:
+ num_sources = rename_src_nr;
+
+ trace2_region_enter("diff", "cull after exact", options->repo);
+ remove_unneeded_paths_from_src(want_copies);
+ trace2_region_leave("diff", "cull after exact", options->repo);
+
+ if (!want_copies && !break_idx) {
+ /* Determine minimum score to match basenames */
I realize you probably changed the region names on purpose to distinguish
that there are two "cull" regions in the case of no copies, but I think
that isn't really worth different names. Better to have a consistent region
name around the same activity in both cases.
+ int min_basename_score = (int)(5*minimum_score + 0*MAX_SCORE)/5;
Did you intend for this to be 5*min + 0*MAX? This seems wrong if you want
this value to be different from minimum_score.
Hi,
On Tue, Feb 9, 2021 at 5:17 AM Derrick Stolee [off-list ref] wrote:
On 2/9/2021 6:32 AM, Elijah Newren via GitGitGadget wrote:
quoted
From: Elijah Newren <redacted>
We want to make use of unique basenames to help inform rename detection,
so that more likely pairings can be checked first. (src/moduleA/foo.txt
and source/module/A/foo.txt are likely related if there are no other
'foo.txt' files among the deleted and added files.) Add a new function,
not yet used, which creates a map of the unique basenames within
rename_src and another within rename_dst, together with the indices
within rename_src/rename_dst where those basenames show up. Non-unique
basenames still show up in the map, but have an invalid index (-1).
This function was inspired by the fact that in real world repositories,
most renames often do not involve a basename change. Here are some
sample repositories and the percentage of their historical renames (as of
early 2020) that did not involve a basename change:
I found this difficult to parse. Perhaps instead
"the percentage of their renames that preserved basenames".
Ooh, I like it; happy to make that change.
We might also need something stronger, though: which percentage of renames
preserved the basename but also had no other copy of that basename in the
scope of all add/deletes?
I don't think it's useful to try to prove that this idea can save time
or how much time we can save before we try it; I think the only
purpose of these numbers should be to motivate the idea behind why it
was worth trying. If we attempt to prove how much we'll save apriori,
then what you have is also too weak. We would need "percentage of
total adds/deletes that are renames that preserved the basename but
also had no other copy of that basename in the scope of all
add/deletes". But that is also wrong, actually; we need "for any
given two commits that we are likely to diff, what is the average
percentage of total adds/deletes between them that are renames that
preserved the basename but also had no other copy of that basename in
the scope of all add/deletes". In particular, my script did not look
at the "any two given likely-to-be-diffed commits" viewpoint, I simply
added the number of renames within individual commits that preserved
renames, and divided by the total number of renames in individual
commits. But even if we could calculate the "any two given
likely-to-be-diffed commits" viewpoint in some sane manner, it'd still
be misleading. The next series is going to change the "no other copy
of that basename in the scope of all adds/deletes" caveat, by adding a
way to match up _some_ of those files (when it can find a way to
compare any given file to exactly one of the other files with the same
basename). And even if you consider all the above and calculated it
in order to try to show how much could be saved, you might need to
start worrying about details like the fact that the first comparison
between files in diffcore-rename.c is _much_ more expensive than
subsequent comparisons (due to the fact that the spanhash is cached).
Trying to account for all these details and describe them fully is
completely beside the point, though; I didn't bother to check any of
this before implementing the algorithm -- I just looked up these very
rough numbers and felt they provided sufficient motivation that there
was an optimization worth trying.
Is this reproducible from a shell command that could be documented here?
No, trying to parse log output with full handling of proper quoting in
the case of filenames with funny characters is too complex to attempt
in shell. I was surprised by how long it turned out to be in python.
(And I dread attempting to calculate "something stronger" in any
accurate way given how involved just this rough calculation was. That
idea seems harder to me than actually implementing this series.)
If you're curious, though, and don't care about
quickly-hacked-together-script-not-designed-for-reuse:
https://github.com/newren/git/blob/ort/rebase-testcase/count-renames.py
quoted
+MAYBE_UNUSED
+static int find_basename_matches(struct diff_options *options,
+ int minimum_score,
+ int num_src)
+{
+ int i;
+ struct strintmap sources;
+ struct strintmap dests;
+
+ /* Create maps of basename -> fullname(s) for sources and dests */
+ strintmap_init_with_options(&sources, -1, NULL, 0);
+ strintmap_init_with_options(&dests, -1, NULL, 0);
Initially, I was wondering why we need the map for each side, but we will need
to enforce uniqueness in each set, so OK.
Also, this is used here and below. Perhaps it's worth pulling out as a
helper? I see similar code being duplicated in these existing spots:
* diff-no-index.c:append_basename()
* help.c:append_similar_ref()
* packfile.c:pack_basename()
* replace-object.c:register_replace_ref()
* setup.c:read_gitfile_gently()
* builtin/rebase.c:cmd_rebase()
* builtin/stash.c:do_create_stash()
* builtin/worktree.c:add_worktree()
* contrib/credential/gnome-keyring/git-credential-gnome-keyring.c:usage()
* contrib/credential/libsecret/git-credential-libsecret.c:usage()
* trace2/tr2_dst.c:tr2_dst_try_auto_path()
Honestly asking: would anyone ever search for such a two-line helper
function? I wouldn't have even thought to look, since it seems so
simple.
However, my real concern here is that this type of change would risk
introducing conflicts with unrelated series. This series is the
second in what will be a 9-series deep dependency chain of
optimizations[1], and the later series are going to be longer than
these first two were (the latter ones are 6-11 patches each). We've
already discussed previously whether we possibly want to hold the
first couple optimization series out of the upcoming git-2.31 release
in order to keep the optimizations all together, but that might
increase the risk of conflicts with unrelated patches if we try a
bigger tree refactor like this. (Junio never commented on that,
though.) It might be better to keep the series touching only
merge-ort.c & diffcore-rename.c, and then do cleanups like the one you
suggest here after the whole series.
That said, it's not a difficult initial change, so I'm mostly
expressing this concern out of making things harder for Junio. It'd
be best to get his opinion -- Junio, your thoughts?
[1] https://github.com/gitgitgadget/git/pulls?q=is%3Apr+author%3Anewren+Optimization+batch
There are other places that use strchr(_, '/') but they seem to be related
to peeling basenames off of paths and using the leading portion of the path.
quoted
+ /* Record index within rename_src (i) if basename is unique */
+ if (strintmap_contains(&sources, base))
+ strintmap_set(&sources, base, -1);
+ else
+ strintmap_set(&sources, base, i);
+ }
+ for (i = 0; i < rename_dst_nr; ++i) {
+ char *filename = rename_dst[i].p->two->path;
+ char *base;
+
+ if (rename_dst[i].is_rename)
+ continue; /* involved in exact match already. */
+
+ base = strrchr(filename, '/');
+ base = (base ? base+1 : filename);
+
+ /* Record index within rename_dst (i) if basename is unique */
+ if (strintmap_contains(&dests, base))
+ strintmap_set(&dests, base, -1);
+ else
+ strintmap_set(&dests, base, i);
+ }
+
+ /* TODO: Make use of basenames source and destination basenames */
+
+ strintmap_clear(&sources);
+ strintmap_clear(&dests);
+
+ return 0;
+}
Also, this is used here and below. Perhaps it's worth pulling out as a
helper? I see similar code being duplicated in these existing spots:
* diff-no-index.c:append_basename()
* help.c:append_similar_ref()
* packfile.c:pack_basename()
* replace-object.c:register_replace_ref()
* setup.c:read_gitfile_gently()
* builtin/rebase.c:cmd_rebase()
* builtin/stash.c:do_create_stash()
* builtin/worktree.c:add_worktree()
* contrib/credential/gnome-keyring/git-credential-gnome-keyring.c:usage()
* contrib/credential/libsecret/git-credential-libsecret.c:usage()
* trace2/tr2_dst.c:tr2_dst_try_auto_path()
Honestly asking: would anyone ever search for such a two-line helper
function? I wouldn't have even thought to look, since it seems so
simple.
However, my real concern here is that this type of change would risk
introducing conflicts with unrelated series. This series is the
second in what will be a 9-series deep dependency chain of
optimizations[1], and the later series are going to be longer than
these first two were (the latter ones are 6-11 patches each). We've
already discussed previously whether we possibly want to hold the
first couple optimization series out of the upcoming git-2.31 release
in order to keep the optimizations all together, but that might
increase the risk of conflicts with unrelated patches if we try a
bigger tree refactor like this. (Junio never commented on that,
though.) It might be better to keep the series touching only
merge-ort.c & diffcore-rename.c, and then do cleanups like the one you
suggest here after the whole series.
That said, it's not a difficult initial change, so I'm mostly
expressing this concern out of making things harder for Junio. It'd
be best to get his opinion -- Junio, your thoughts?
[1] https://github.com/gitgitgadget/git/pulls?q=is%3Apr+author%3Anewren+Optimization+batch
I don't consider the step of "go put the helper in all these other
places" necessary for the current series. However, the "get basename"
code appears a total of three times in this series, so it would be
good to at least extract it to a static inline method to reduce
the duplication isolated to this change.
Thanks,
-Stolee
On Tue, Feb 9, 2021 at 5:25 AM Derrick Stolee [off-list ref] wrote:
On 2/9/2021 6:32 AM, Elijah Newren via GitGitGadget wrote:
quoted
+ /*
+ * When I checked, over 76% of file renames in linux just moved
Perhaps "In late 2020," instead of "When I checked".
In early 2020 (in fact, it might have been 2019, but I have no records
to verify the actual year), but sure I can change that.
quoted
+ * files to a different directory but kept the same basename. gcc
+ * did that with over 64% of renames, gecko did it with over 79%,
+ * and WebKit did it with over 89%.
+ *
+ * Therefore we can bypass the normal exhaustive NxM matrix
+ * comparison of similarities between all potential rename sources
+ * and destinations by instead using file basename as a hint, checking
+ * for similarity between files with the same basename, and if we
+ * find a pair that are sufficiently similar, record the rename
+ * pair and exclude those two from the NxM matrix.
+ *
+ * This *might* cause us to find a less than optimal pairing (if
+ * there is another file that we are even more similar to but has a
+ * different basename). Given the huge performance advantage
+ * basename matching provides, and given the frequency with which
+ * people use the same basename in real world projects, that's a
+ * trade-off we are willing to accept when doing just rename
+ * detection. However, if someone wants copy detection that
+ * implies they are willing to spend more cycles to find
+ * similarities between files, so it may be less likely that this
+ * heuristic is wanted.
+ */
+
+ int i, renames = 0;
struct strintmap sources;
struct strintmap dests;
...
quoted
+ * copy detection. find_basename_matches() is only used when detecting
+ * renames, not when detecting copies, so it'll only be used when a file
+ * only existed in the source. Since we already know that the file
There are two "only"s in this sentence. Just awkward, not wrong.
quoted
+ * won't be unmodified, there's no point checking for it; that's just a
+ * waste of resources. So set skip_unmodified to 0 so that
+ * estimate_similarity() and prefetch() won't waste resources checking
+ * for something we already know is false.
+ */
+ int skip_unmodified = 0;
+
quoted
- /* TODO: Make use of basenames source and destination basenames */
+ /* Now look for basename matchups and do similarity estimation */
+ for (i = 0; i < num_src; ++i) {
+ char *filename = rename_src[i].p->one->path;
+ char *base = NULL;
+ intptr_t src_index;
+ intptr_t dst_index;
+
+ /* Get the basename */
+ base = strrchr(filename, '/');
+ base = (base ? base+1 : filename);
Here is the third instance of this in the same function. At minimum we should
extract a helper for you to consume.
Where by "this" you mean these last two lines, right?
And perhaps explain why I'm not using either basename(3) or
gitbasename() from git-compat-util.h? (The latter of which I just
learned about while responding to the review of this patch.)
or maybe gitbasename can do the job, but the skip_dos_drive_prefix()
and the munging of the string passed in both worry me. And the
is_dir_sep() looks inefficient since I know I'm dealing with filenames
as stored in git internally, and thus can only use '/' characters.
Hmm...
Yeah, I think I'll add my own helper in this file, since you want one,
and just use it.
quoted
+ /* Find out if this basename is unique among sources */
+ src_index = strintmap_get(&sources, base);
+ if (src_index == -1)
+ continue; /* not a unique basename; skip it */
+ assert(src_index == i);
+
+ if (strintmap_contains(&dests, base)) {
+ struct diff_filespec *one, *two;
+ int score;
+
+ /* Find out if this basename is unique among dests */
+ dst_index = strintmap_get(&dests, base);
+ if (dst_index == -1)
+ continue; /* not a unique basename; skip it */
+
+ /* Ignore this dest if already used in a rename */
+ if (rename_dst[dst_index].is_rename)
+ continue; /* already used previously */
+
+ /* Estimate the similarity */
+ one = rename_src[src_index].p->one;
+ two = rename_dst[dst_index].p->two;
+ score = estimate_similarity(options->repo, one, two,
+ minimum_score, skip_unmodified);
+
+ /* If sufficiently similar, record as rename pair */
+ if (score < minimum_score)
+ continue;
+ record_rename_pair(dst_index, src_index, score);
+ renames++;
+
+ /*
+ * Found a rename so don't need text anymore; if we
+ * didn't find a rename, the filespec_blob would get
+ * re-used when doing the matrix of comparisons.
+ */
+ diff_free_filespec_blob(one);
+ diff_free_filespec_blob(two);
+ }
+ }
On Tue, Feb 9, 2021 at 5:25 AM Derrick Stolee [off-list ref] wrote:
quoted
On 2/9/2021 6:32 AM, Elijah Newren via GitGitGadget wrote:
quoted
+ /* Get the basename */
+ base = strrchr(filename, '/');
+ base = (base ? base+1 : filename);
Here is the third instance of this in the same function. At minimum we should
extract a helper for you to consume.
Where by "this" you mean these last two lines, right?
Correct. The reason to use a helper is to ease cognitive load when
reading the code. These lines are identical and serve the same
purpose. By making a "get_basename()" helper and using it as
base = get_basename(filename);
makes it easy to understand what is happening without needing
to think carefully about it. For example, I had to remember
that strrchr() returns NULL when '/' is not found, not the first
character of the string.
And perhaps explain why I'm not using either basename(3) or
gitbasename() from git-compat-util.h? (The latter of which I just
learned about while responding to the review of this patch.)
or maybe gitbasename can do the job, but the skip_dos_drive_prefix()
and the munging of the string passed in both worry me. And the
is_dir_sep() looks inefficient since I know I'm dealing with filenames
as stored in git internally, and thus can only use '/' characters.
Hmm...
Yeah, I think I'll add my own helper in this file, since you want one,
and just use it.
Right. I almost made a point to say "Don't use find_last_dir_sep()"
because it uses platform-specific directory separators. Your helper
is based on in-memory representation that always uses Unix-style paths.
Thanks,
-Stolee
...this? (except the regions are renamed)
Could this be simplified as:
+ num_sources = rename_src_nr;
+
+ trace2_region_enter("diff", "cull after exact", options->repo);
+ remove_unneeded_paths_from_src(want_copies);
+ trace2_region_leave("diff", "cull after exact", options->repo);
+
+ if (!want_copies && !break_idx) {
+ /* Determine minimum score to match basenames */
I realize you probably changed the region names on purpose to distinguish
that there are two "cull" regions in the case of no copies, but I think
that isn't really worth different names. Better to have a consistent region
name around the same activity in both cases.
Actually, the reason they were split is because a later series has to
call remove_unneeded_paths_from_src() differently for the two
branches. The patch history was so dirty that the easiest way to
clean things up was just to create completely new patches pulling off
relevant chunks of code and touching them up; while doing that, I
didn't notice that the changes I made to split out this early series
resulted in this near-duplication.
So, I can join them...but they would just need to be split back out in
my "Optimization batch 9" series.
I'm happy to fix the region name to make them the same. Is that good
enough, or would you rather these common code regions combined for
this patch and then split out later?
quoted
+ int min_basename_score = (int)(5*minimum_score + 0*MAX_SCORE)/5;
Did you intend for this to be 5*min + 0*MAX? This seems wrong if you want
this value to be different from minimum_score.
In my cover letter I noted that I didn't know what to set this to and
wanted input; yesterday you said it wasn't worth worrying about using
a different value, but Junio suggested we should use one (but didn't
state how much higher it should be or whether it should be user input
driven). This weird construct was here just to show that it is easy
to feed a different score into the basename comparison than what is
used elsewhere; I can fix it up once I get word on what Junio wants to
see.
Since I didn't know what to use, though, and I didn't want to get a
different set of numbers for the final commit message on the speedup
achieved if I'm just going to throw them away and recompute once I
find out what Junio wants here, I did intentionally set the
computation to just give us minimum_score, for now.
On Tue, Feb 9, 2021 at 9:02 AM Derrick Stolee [off-list ref] wrote:
On 2/9/2021 11:56 AM, Elijah Newren wrote:
quoted
quoted
Also, this is used here and below. Perhaps it's worth pulling out as a
helper? I see similar code being duplicated in these existing spots:
* diff-no-index.c:append_basename()
* help.c:append_similar_ref()
* packfile.c:pack_basename()
* replace-object.c:register_replace_ref()
* setup.c:read_gitfile_gently()
* builtin/rebase.c:cmd_rebase()
* builtin/stash.c:do_create_stash()
* builtin/worktree.c:add_worktree()
* contrib/credential/gnome-keyring/git-credential-gnome-keyring.c:usage()
* contrib/credential/libsecret/git-credential-libsecret.c:usage()
* trace2/tr2_dst.c:tr2_dst_try_auto_path()
Honestly asking: would anyone ever search for such a two-line helper
function? I wouldn't have even thought to look, since it seems so
simple.
However, my real concern here is that this type of change would risk
introducing conflicts with unrelated series. This series is the
second in what will be a 9-series deep dependency chain of
optimizations[1], and the later series are going to be longer than
these first two were (the latter ones are 6-11 patches each). We've
already discussed previously whether we possibly want to hold the
first couple optimization series out of the upcoming git-2.31 release
in order to keep the optimizations all together, but that might
increase the risk of conflicts with unrelated patches if we try a
bigger tree refactor like this. (Junio never commented on that,
though.) It might be better to keep the series touching only
merge-ort.c & diffcore-rename.c, and then do cleanups like the one you
suggest here after the whole series.
That said, it's not a difficult initial change, so I'm mostly
expressing this concern out of making things harder for Junio. It'd
be best to get his opinion -- Junio, your thoughts?
[1] https://github.com/gitgitgadget/git/pulls?q=is%3Apr+author%3Anewren+Optimization+batch
I don't consider the step of "go put the helper in all these other
places" necessary for the current series. However, the "get basename"
code appears a total of three times in this series, so it would be
good to at least extract it to a static inline method to reduce
the duplication isolated to this change.
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-10 15:16:44
This series depends on ort-perf-batch-6[1].
This series uses file basenames (portion of the path after final '/',
including extension) in a basic fashion to guide rename detection.
Changes since v2:
* insert a new patch at the beginning to test expected old behavior, then
have later patches change the test expectation
* tweak commit message wording to clarify that rename stats merely
motivated the optimization
* factor out a simple get_basename() helper; have it document why we don't
use gitbasename()
* use a higher required threshold to mark same-basename files as a rename,
defaulting to average of minimum_score and MAX_SCORE (since default
rename threshold is 50%, this implies default basename threshold is 75%)
* provide an environment variable (undocumented) that can be used to test
appropriate threshold for basename-sameness
* updated the timings based on the new threshold
* modify the documentation with Junio's suggested simpler and clearer
wording
* clean up the wording on a few comments
[1] https://lore.kernel.org/git/xmqqlfc4byt6.fsf@gitster.c.googlers.com/ [2]
https://github.com/newren/presentations/blob/pdfs/merge-performance/merge-performance-slides.pdf
Elijah Newren (5):
t4001: add a test comparing basename similarity and content similarity
diffcore-rename: compute basenames of all source and dest candidates
diffcore-rename: complete find_basename_matches()
diffcore-rename: guide inexact rename detection based on basenames
gitdiffcore doc: mention new preliminary step for rename detection
Documentation/gitdiffcore.txt | 17 +++
diffcore-rename.c | 202 +++++++++++++++++++++++++++++++++-
t/t4001-diff-rename.sh | 24 ++++
3 files changed, 239 insertions(+), 4 deletions(-)
base-commit: 7ae9460d3dba84122c2674b46e4339b9d42bdedd
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-843%2Fnewren%2Fort-perf-batch-7-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-843/newren/ort-perf-batch-7-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/843
Range-diff vs v2:
4: a0e75d8cd6bd ! 1: 3e6af929d135 gitdiffcore doc: mention new preliminary step for rename detection
@@ Metadata
Author: Elijah Newren [off-list ref]
## Commit message ##
- gitdiffcore doc: mention new preliminary step for rename detection
+ t4001: add a test comparing basename similarity and content similarity
- The last few patches have introduced a new preliminary step when rename
- detection is on but both break detection and copy detection are off.
- Document this new step. While we're at it, add a testcase that checks
- the new behavior as well.
+ Add a simple test where a removed file is similar to two different added
+ files; one of them has the same basename, and the other has a slightly
+ higher content similarity. Without break detection, filename similarity
+ of 100% trumps content similarity for pairing up related files. For
+ any filename similarity less than 100%, the opposite is true -- content
+ similarity is all that matters. Add a testcase that documents this.
- Signed-off-by: Elijah Newren [off-list ref]
+ Subsequent commits will add a new rule that includes an inbetween state,
+ where a mixture of filename similarity and content similarity are
+ weighed, and which will change the outcome of this testcase.
- ## Documentation/gitdiffcore.txt ##
-@@ Documentation/gitdiffcore.txt: a similarity score different from the default of 50% by giving a
- number after the "-M" or "-C" option (e.g. "-M8" to tell it to use
- 8/10 = 80%).
-
-+Note that when rename detection is on but both copy and break
-+detection are off, rename detection adds a preliminary step that first
-+checks files with the same basename. If files with the same basename
-+are sufficiently similar, it will mark them as renames and exclude
-+them from the later quadratic step (the one that pairwise compares all
-+unmatched files to find the "best" matches, determined by the highest
-+content similarity). So, for example, if docs/extensions.txt and
-+docs/config/extensions.txt have similar content, then they will be
-+marked as a rename even if it turns out that docs/extensions.txt was
-+more similar to src/extension-checks.c. At most, one comparison is
-+done per file in this preliminary pass; so if there are several
-+extensions.txt files throughout the directory hierarchy that were
-+added and deleted, this preliminary step will be skipped for those
-+files.
-+
- Note. When the "-C" option is used with `--find-copies-harder`
- option, 'git diff-{asterisk}' commands feed unmodified filepairs to
- diffcore mechanism as well as modified ones. This lets the copy
+ Signed-off-by: Elijah Newren [off-list ref]
## t/t4001-diff-rename.sh ##
@@ t/t4001-diff-rename.sh: test_expect_success 'diff-tree -l0 defaults to a big rename limit, not zero' '
@@ t/t4001-diff-rename.sh: test_expect_success 'diff-tree -l0 defaults to a big ren
+ # subdir/file.txt is 89% similar to file.md, 78% similar to file.txt,
+ # but since same basenames are checked first...
+ cat >expected <<-\EOF &&
-+ A file.md
-+ R078 subdir/file.txt file.txt
++ R088 subdir/file.txt file.md
++ A file.txt
+ EOF
+ test_cmp expected actual
+'
1: 381a45d239bb ! 2: 4fff9b1ff57b diffcore-rename: compute basenames of all source and dest candidates
@@ Commit message
basenames still show up in the map, but have an invalid index (-1).
This function was inspired by the fact that in real world repositories,
- most renames often do not involve a basename change. Here are some
- sample repositories and the percentage of their historical renames (as of
- early 2020) that did not involve a basename change:
+ files are often moved across directories without changing names. Here
+ are some sample repositories and the percentage of their historical
+ renames (as of early 2020) that preserved basenames:
* linux: 76%
* gcc: 64%
* gecko: 79%
* webkit: 89%
+ These statistics alone don't prove that an optimization in this area
+ will help or how much it will help, since there are also unpaired adds
+ and deletes, restrictions on which basenames we consider, etc., but it
+ certainly motivated the idea to try something in this area.
Signed-off-by: Elijah Newren [off-list ref]
@@ diffcore-rename.c: static int find_exact_renames(struct diff_options *options)
return renames;
}
++static const char *get_basename(const char *filename)
++{
++ /*
++ * gitbasename() has to worry about special drivers, multiple
++ * directory separator characters, trailing slashes, NULL or
++ * empty strings, etc. We only work on filenames as stored in
++ * git, and thus get to ignore all those complications.
++ */
++ const char *base = strrchr(filename, '/');
++ return base ? base + 1 : filename;
++}
++
+MAYBE_UNUSED
+static int find_basename_matches(struct diff_options *options,
+ int minimum_score,
@@ diffcore-rename.c: static int find_exact_renames(struct diff_options *options)
+ strintmap_init_with_options(&dests, -1, NULL, 0);
+ for (i = 0; i < num_src; ++i) {
+ char *filename = rename_src[i].p->one->path;
-+ char *base;
++ const char *base;
+
+ /* exact renames removed in remove_unneeded_paths_from_src() */
+ assert(!rename_src[i].p->one->rename_used);
+
-+ base = strrchr(filename, '/');
-+ base = (base ? base+1 : filename);
-+
+ /* Record index within rename_src (i) if basename is unique */
++ base = get_basename(filename);
+ if (strintmap_contains(&sources, base))
+ strintmap_set(&sources, base, -1);
+ else
@@ diffcore-rename.c: static int find_exact_renames(struct diff_options *options)
+ }
+ for (i = 0; i < rename_dst_nr; ++i) {
+ char *filename = rename_dst[i].p->two->path;
-+ char *base;
++ const char *base;
+
+ if (rename_dst[i].is_rename)
+ continue; /* involved in exact match already. */
+
-+ base = strrchr(filename, '/');
-+ base = (base ? base+1 : filename);
-+
+ /* Record index within rename_dst (i) if basename is unique */
++ base = get_basename(filename);
+ if (strintmap_contains(&dests, base))
+ strintmap_set(&dests, base, -1);
+ else
2: dcd0175229aa ! 3: dc26881e4ed3 diffcore-rename: complete find_basename_matches()
@@ diffcore-rename.c: static int find_basename_matches(struct diff_options *options
{
- int i;
+ /*
-+ * When I checked, over 76% of file renames in linux just moved
-+ * files to a different directory but kept the same basename. gcc
-+ * did that with over 64% of renames, gecko did it with over 79%,
-+ * and WebKit did it with over 89%.
++ * When I checked in early 2020, over 76% of file renames in linux
++ * just moved files to a different directory but kept the same
++ * basename. gcc did that with over 64% of renames, gecko did it
++ * with over 79%, and WebKit did it with over 89%.
+ *
+ * Therefore we can bypass the normal exhaustive NxM matrix
+ * comparison of similarities between all potential rename sources
-+ * and destinations by instead using file basename as a hint, checking
-+ * for similarity between files with the same basename, and if we
-+ * find a pair that are sufficiently similar, record the rename
-+ * pair and exclude those two from the NxM matrix.
++ * and destinations by instead using file basename as a hint (i.e.
++ * the portion of the filename after the last '/'), checking for
++ * similarity between files with the same basename, and if we find
++ * a pair that are sufficiently similar, record the rename pair and
++ * exclude those two from the NxM matrix.
+ *
+ * This *might* cause us to find a less than optimal pairing (if
+ * there is another file that we are even more similar to but has a
@@ diffcore-rename.c: static int find_basename_matches(struct diff_options *options
+ * basename matching provides, and given the frequency with which
+ * people use the same basename in real world projects, that's a
+ * trade-off we are willing to accept when doing just rename
-+ * detection. However, if someone wants copy detection that
-+ * implies they are willing to spend more cycles to find
-+ * similarities between files, so it may be less likely that this
-+ * heuristic is wanted.
++ * detection.
++ *
++ * If someone wants copy detection that implies they are willing to
++ * spend more cycles to find similarities between files, so it may
++ * be less likely that this heuristic is wanted. If someone is
++ * doing break detection, that means they do not want filename
++ * similarity to imply any form of content similiarity, and thus
++ * this heuristic would definitely be incompatible.
+ */
+
+ int i, renames = 0;
@@ diffcore-rename.c: static int find_basename_matches(struct diff_options *options
struct strintmap dests;
+ /*
-+ * The prefeteching stuff wants to know if it can skip prefetching blobs
-+ * that are unmodified. unmodified blobs are only relevant when doing
-+ * copy detection. find_basename_matches() is only used when detecting
-+ * renames, not when detecting copies, so it'll only be used when a file
-+ * only existed in the source. Since we already know that the file
-+ * won't be unmodified, there's no point checking for it; that's just a
-+ * waste of resources. So set skip_unmodified to 0 so that
-+ * estimate_similarity() and prefetch() won't waste resources checking
-+ * for something we already know is false.
++ * The prefeteching stuff wants to know if it can skip prefetching
++ * blobs that are unmodified...and will then do a little extra work
++ * to verify that the oids are indeed different before prefetching.
++ * Unmodified blobs are only relevant when doing copy detection;
++ * when limiting to rename detection, diffcore_rename[_extended]()
++ * will never be called with unmodified source paths fed to us, so
++ * the extra work necessary to check if rename_src entries are
++ * unmodified would be a small waste.
+ */
+ int skip_unmodified = 0;
+
@@ diffcore-rename.c: static int find_basename_matches(struct diff_options *options
+ /* Now look for basename matchups and do similarity estimation */
+ for (i = 0; i < num_src; ++i) {
+ char *filename = rename_src[i].p->one->path;
-+ char *base = NULL;
++ const char *base = NULL;
+ intptr_t src_index;
+ intptr_t dst_index;
+
-+ /* Get the basename */
-+ base = strrchr(filename, '/');
-+ base = (base ? base+1 : filename);
-+
+ /* Find out if this basename is unique among sources */
++ base = get_basename(filename);
+ src_index = strintmap_get(&sources, base);
+ if (src_index == -1)
+ continue; /* not a unique basename; skip it */
3: ce2173aa1fb7 ! 4: 2493f4b2f55d diffcore-rename: guide inexact rename detection based on basenames
@@ Commit message
this change improves the performance as follows:
Before After
- no-renames: 13.815 s ± 0.062 s 13.138 s ± 0.086 s
- mega-renames: 1799.937 s ± 0.493 s 169.488 s ± 0.494 s
- just-one-mega: 51.289 s ± 0.019 s 5.061 s ± 0.017 s
+ no-renames: 13.815 s ± 0.062 s 13.294 s ± 0.103 s
+ mega-renames: 1799.937 s ± 0.493 s 187.248 s ± 0.882 s
+ just-one-mega: 51.289 s ± 0.019 s 5.557 s ± 0.017 s
Signed-off-by: Elijah Newren [off-list ref]
## diffcore-rename.c ##
-@@ diffcore-rename.c: static int find_exact_renames(struct diff_options *options)
- return renames;
+@@ diffcore-rename.c: static const char *get_basename(const char *filename)
+ return base ? base + 1 : filename;
}
-MAYBE_UNUSED
@@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)
+ trace2_region_leave("diff", "cull after exact", options->repo);
+ } else {
+ /* Determine minimum score to match basenames */
-+ int min_basename_score = (int)(5*minimum_score + 0*MAX_SCORE)/5;
++ double factor = 0.5;
++ char *basename_factor = getenv("GIT_BASENAME_FACTOR");
++ int min_basename_score;
++
++ if (basename_factor)
++ factor = strtol(basename_factor, NULL, 10)/100.0;
++ assert(factor >= 0.0 && factor <= 1.0);
++ min_basename_score = minimum_score +
++ (int)(factor * (MAX_SCORE - minimum_score));
+
+ /*
+ * Cull sources:
+ * - remove ones involved in renames (found via exact match)
+ */
-+ trace2_region_enter("diff", "cull exact", options->repo);
++ trace2_region_enter("diff", "cull after exact", options->repo);
+ remove_unneeded_paths_from_src(want_copies);
-+ trace2_region_leave("diff", "cull exact", options->repo);
++ trace2_region_leave("diff", "cull after exact", options->repo);
+
+ /* Utilize file basenames to quickly find renames. */
+ trace2_region_enter("diff", "basename matches", options->repo);
@@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)
m = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];
for (j = 0; j < NUM_CANDIDATE_PER_DST; j++)
+
+ ## t/t4001-diff-rename.sh ##
+@@ t/t4001-diff-rename.sh: test_expect_success 'basename similarity vs best similarity' '
+ # subdir/file.txt is 89% similar to file.md, 78% similar to file.txt,
+ # but since same basenames are checked first...
+ cat >expected <<-\EOF &&
+- R088 subdir/file.txt file.md
+- A file.txt
++ A file.md
++ R078 subdir/file.txt file.txt
+ EOF
+ test_cmp expected actual
+ '
-: ------------ > 5: fc72d24a3358 gitdiffcore doc: mention new preliminary step for rename detection
--
gitgitgadget
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-10 15:16:48
From: Elijah Newren <redacted>
Add a simple test where a removed file is similar to two different added
files; one of them has the same basename, and the other has a slightly
higher content similarity. Without break detection, filename similarity
of 100% trumps content similarity for pairing up related files. For
any filename similarity less than 100%, the opposite is true -- content
similarity is all that matters. Add a testcase that documents this.
Subsequent commits will add a new rule that includes an inbetween state,
where a mixture of filename similarity and content similarity are
weighed, and which will change the outcome of this testcase.
Signed-off-by: Elijah Newren <redacted>
---
t/t4001-diff-rename.sh | 24 ++++++++++++++++++++++++
1 file changed, 24 insertions(+)
@@ -262,4 +262,28 @@ test_expect_success 'diff-tree -l0 defaults to a big rename limit, not zero' 'grep"myotherfile.*myfile"actual'+test_expect_success'basename similarity vs best similarity''+mkdirsubdir&&+test_write_linesline1line2line3line4line5\+line6line7line8line9line10>subdir/file.txt&&+gitaddsubdir/file.txt&&+gitcommit-m"base txt"&&++gitrmsubdir/file.txt&&+test_write_linesline1line2line3line4line5\+line6line7line8>file.txt&&+test_write_linesline1line2line3line4line5\+line6line7line8line9>file.md&&+gitaddfile.txtfile.md&&+gitcommit-a-m"rename"&&+gitdiff-tree-r-M--name-statusHEAD^HEAD>actual&&+# subdir/file.txt is 89% similar to file.md, 78% similar to file.txt,+# but since same basenames are checked first...+cat>expected<<-\EOF&&+R088subdir/file.txtfile.md+Afile.txt+EOF+test_cmpexpectedactual+'+ test_done
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-10 15:17:02
From: Elijah Newren <redacted>
We want to make use of unique basenames to help inform rename detection,
so that more likely pairings can be checked first. (src/moduleA/foo.txt
and source/module/A/foo.txt are likely related if there are no other
'foo.txt' files among the deleted and added files.) Add a new function,
not yet used, which creates a map of the unique basenames within
rename_src and another within rename_dst, together with the indices
within rename_src/rename_dst where those basenames show up. Non-unique
basenames still show up in the map, but have an invalid index (-1).
This function was inspired by the fact that in real world repositories,
files are often moved across directories without changing names. Here
are some sample repositories and the percentage of their historical
renames (as of early 2020) that preserved basenames:
* linux: 76%
* gcc: 64%
* gecko: 79%
* webkit: 89%
These statistics alone don't prove that an optimization in this area
will help or how much it will help, since there are also unpaired adds
and deletes, restrictions on which basenames we consider, etc., but it
certainly motivated the idea to try something in this area.
Signed-off-by: Elijah Newren <redacted>
---
diffcore-rename.c | 61 +++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 61 insertions(+)
@@ -367,6 +367,67 @@ static int find_exact_renames(struct diff_options *options)returnrenames;}+staticconstchar*get_basename(constchar*filename)+{+/*+*gitbasename()hastoworryaboutspecialdrivers,multiple+*directoryseparatorcharacters,trailingslashes,NULLor+*emptystrings,etc.Weonlyworkonfilenamesasstoredin+*git,andthusgettoignoreallthosecomplications.+*/+constchar*base=strrchr(filename,'/');+returnbase?base+1:filename;+}++MAYBE_UNUSED+staticintfind_basename_matches(structdiff_options*options,+intminimum_score,+intnum_src)+{+inti;+structstrintmapsources;+structstrintmapdests;++/* Create maps of basename -> fullname(s) for sources and dests */+strintmap_init_with_options(&sources,-1,NULL,0);+strintmap_init_with_options(&dests,-1,NULL,0);+for(i=0;i<num_src;++i){+char*filename=rename_src[i].p->one->path;+constchar*base;++/* exact renames removed in remove_unneeded_paths_from_src() */+assert(!rename_src[i].p->one->rename_used);++/* Record index within rename_src (i) if basename is unique */+base=get_basename(filename);+if(strintmap_contains(&sources,base))+strintmap_set(&sources,base,-1);+else+strintmap_set(&sources,base,i);+}+for(i=0;i<rename_dst_nr;++i){+char*filename=rename_dst[i].p->two->path;+constchar*base;++if(rename_dst[i].is_rename)+continue;/* involved in exact match already. */++/* Record index within rename_dst (i) if basename is unique */+base=get_basename(filename);+if(strintmap_contains(&dests,base))+strintmap_set(&dests,base,-1);+else+strintmap_set(&dests,base,i);+}++/* TODO: Make use of basenames source and destination basenames */++strintmap_clear(&sources);+strintmap_clear(&dests);++return0;+}+#define NUM_CANDIDATE_PER_DST 4staticvoidrecord_if_better(structdiff_scorem[],structdiff_score*o){
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-10 15:17:08
From: Elijah Newren <redacted>
Make use of the new find_basename_matches() function added in the last
two patches, to find renames more rapidly in cases where we can match up
files based on basenames. As a quick reminder (see the last two commit
messages for more details), this means for example that
docs/extensions.txt and docs/config/extensions.txt are considered likely
renames if there are no 'extensions.txt' files elsewhere among the added
and deleted files, and if a similarity check confirms they are similar,
then they are marked as a rename without looking for a better similarity
match among other files. This is a behavioral change, as covered in
more detail in the previous commit message.
We do not use this heuristic together with either break or copy
detection. The point of break detection is to say that filename
similarity does not imply file content similarity, and we only want to
know about file content similarity. The point of copy detection is to
use more resources to check for additional similarities, while this is
an optimization that uses far less resources but which might also result
in finding slightly fewer similarities. So the idea behind this
optimization goes against both of those features, and will be turned off
for both.
For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
this change improves the performance as follows:
Before After
no-renames: 13.815 s ± 0.062 s 13.294 s ± 0.103 s
mega-renames: 1799.937 s ± 0.493 s 187.248 s ± 0.882 s
just-one-mega: 51.289 s ± 0.019 s 5.557 s ± 0.017 s
Signed-off-by: Elijah Newren <redacted>
---
diffcore-rename.c | 54 ++++++++++++++++++++++++++++++++++++++----
t/t4001-diff-rename.sh | 4 ++--
2 files changed, 51 insertions(+), 7 deletions(-)
@@ -727,12 +726,57 @@ void diffcore_rename(struct diff_options *options)if(minimum_score==MAX_SCORE)gotocleanup;+num_sources=rename_src_nr;++if(want_copies||break_idx){+/*+*Cullsources:+*-removeonescorrespondingtoexactrenames+*/+trace2_region_enter("diff","cull after exact",options->repo);+remove_unneeded_paths_from_src(want_copies);+trace2_region_leave("diff","cull after exact",options->repo);+}else{+/* Determine minimum score to match basenames */+doublefactor=0.5;+char*basename_factor=getenv("GIT_BASENAME_FACTOR");+intmin_basename_score;++if(basename_factor)+factor=strtol(basename_factor,NULL,10)/100.0;+assert(factor>=0.0&&factor<=1.0);+min_basename_score=minimum_score++(int)(factor*(MAX_SCORE-minimum_score));++/*+*Cullsources:+*-removeonesinvolvedinrenames(foundviaexactmatch)+*/+trace2_region_enter("diff","cull after exact",options->repo);+remove_unneeded_paths_from_src(want_copies);+trace2_region_leave("diff","cull after exact",options->repo);++/* Utilize file basenames to quickly find renames. */+trace2_region_enter("diff","basename matches",options->repo);+rename_count+=find_basename_matches(options,+min_basename_score,+rename_src_nr);+trace2_region_leave("diff","basename matches",options->repo);++/*+*Cullsources,again:+*-removeonesinvolvedinrenames(foundviabasenames)+*/+trace2_region_enter("diff","cull basename",options->repo);+remove_unneeded_paths_from_src(want_copies);+trace2_region_leave("diff","cull basename",options->repo);+}+/*-*Calculatehowmanyrenamesareleft+*Calculatehowmanyrenamedestinationsareleft*/num_destinations=(rename_dst_nr-rename_count);-remove_unneeded_paths_from_src(want_copies);-num_sources=rename_src_nr;+num_sources=rename_src_nr;/* rename_src_nr reflects lower number *//* All done? */if(!num_destinations||!num_sources)
@@ -764,7 +808,7 @@ void diffcore_rename(struct diff_options *options)structdiff_score*m;if(rename_dst[i].is_rename)-continue;/* dealt with exact match already. */+continue;/* exact or basename match already handled */m=&mx[dst_cnt*NUM_CANDIDATE_PER_DST];for(j=0;j<NUM_CANDIDATE_PER_DST;j++)
@@ -280,8 +280,8 @@ test_expect_success 'basename similarity vs best similarity' '# subdir/file.txt is 89% similar to file.md, 78% similar to file.txt,# but since same basenames are checked first...cat>expected<<-\EOF&&-R088subdir/file.txtfile.md-Afile.txt+Afile.md+R078subdir/file.txtfile.txtEOFtest_cmpexpectedactual'
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-10 15:17:10
From: Elijah Newren <redacted>
It is not uncommon in real world repositories for the majority of file
renames to not change the basename of the file; i.e. most "renames" are
just a move of files into different directories. We can make use of
this to avoid comparing all rename source candidates with all rename
destination candidates, by first comparing sources to destinations with
the same basenames. If two files with the same basename are
sufficiently similar, we record the rename; if not, we include those
files in the more exhaustive matrix comparison.
This means we are adding a set of preliminary additional comparisons,
but for each file we only compare it with at most one other file. For
example, if there was a include/media/device.h that was deleted and a
src/module/media/device.h that was added, and there were no other
device.h files added or deleted between the commits being compared,
then these two files would be compared in the preliminary step.
This commit does not yet actually employ this new optimization, it
merely adds a function which can be used for this purpose. The next
commit will do the necessary plumbing to make use of it.
Note that this optimization might give us different results than without
the optimization, because it's possible that despite files with the same
basename being sufficiently similar to be considered a rename, there's
an even better match between files without the same basename. I think
that is okay for four reasons: (1) it's easy to explain to the users
what happened if it does ever occur (or even for them to intuitively
figure out), (2) as the next patch will show it provides such a large
performance boost that it's worth the tradeoff, and (3) it's somewhat
unlikely that despite having unique matching basenames that other files
serve as better matches. Reason (4) takes a full paragraph to
explain...
If the previous three reasons aren't enough, consider what rename
detection already does. Break detection is not the default, meaning
that if files have the same _fullname_, then they are considered related
even if they are 0% similar. In fact, in such a case, we don't even
bother comparing the files to see if they are similar let alone
comparing them to all other files to see what they are most similar to.
Basically, we override content similarity based on sufficient filename
similarity. Without the filename similarity (currently implemented as
an exact match of filename), we swing the pendulum the opposite
direction and say that filename similarity is irrelevant and compare a
full N x M matrix of sources and destinations to find out which have the
most similar contents. This optimization just adds another form of
filename similarity comparison, but augments it with a file content
similarity check as well. Basically, if two files have the same
basename and are sufficiently similar to be considered a rename, mark
them as such without comparing the two to all other rename candidates.
Signed-off-by: Elijah Newren <redacted>
---
diffcore-rename.c | 95 +++++++++++++++++++++++++++++++++++++++++++++--
1 file changed, 92 insertions(+), 3 deletions(-)
@@ -384,10 +384,52 @@ static int find_basename_matches(struct diff_options *options,intminimum_score,intnum_src){-inti;+/*+*WhenIcheckedinearly2020,over76%offilerenamesinlinux+*justmovedfilestoadifferentdirectorybutkeptthesame+*basename.gccdidthatwithover64%ofrenames,geckodidit+*withover79%,andWebKitdiditwithover89%.+*+*ThereforewecanbypassthenormalexhaustiveNxMmatrix+*comparisonofsimilaritiesbetweenallpotentialrenamesources+*anddestinationsbyinsteadusingfilebasenameasahint(i.e.+*theportionofthefilenameafterthelast'/'),checkingfor+*similaritybetweenfileswiththesamebasename,andifwefind+*apairthataresufficientlysimilar,recordtherenamepairand+*excludethosetwofromtheNxMmatrix.+*+*This*might*causeustofindalessthanoptimalpairing(if+*thereisanotherfilethatweareevenmoresimilartobuthasa+*differentbasename).Giventhehugeperformanceadvantage+*basenamematchingprovides,andgiventhefrequencywithwhich+*peopleusethesamebasenameinrealworldprojects,that'sa+*trade-offwearewillingtoacceptwhendoingjustrename+*detection.+*+*Ifsomeonewantscopydetectionthatimpliestheyarewillingto+*spendmorecyclestofindsimilaritiesbetweenfiles,soitmay+*belesslikelythatthisheuristiciswanted.Ifsomeoneis+*doingbreakdetection,thatmeanstheydonotwantfilename+*similaritytoimplyanyformofcontentsimiliarity,andthus+*thisheuristicwoulddefinitelybeincompatible.+*/++inti,renames=0;structstrintmapsources;structstrintmapdests;+/*+*Theprefetechingstuffwantstoknowifitcanskipprefetching+*blobsthatareunmodified...andwillthendoalittleextrawork+*toverifythattheoidsareindeeddifferentbeforeprefetching.+*Unmodifiedblobsareonlyrelevantwhendoingcopydetection;+*whenlimitingtorenamedetection,diffcore_rename[_extended]()+*willneverbecalledwithunmodifiedsourcepathsfedtous,so+*theextraworknecessarytocheckifrename_srcentriesare+*unmodifiedwouldbeasmallwaste.+*/+intskip_unmodified=0;+/* Create maps of basename -> fullname(s) for sources and dests */strintmap_init_with_options(&sources,-1,NULL,0);strintmap_init_with_options(&dests,-1,NULL,0);
@@ -420,12 +462,59 @@ static int find_basename_matches(struct diff_options *options,strintmap_set(&dests,base,i);}-/* TODO: Make use of basenames source and destination basenames */+/* Now look for basename matchups and do similarity estimation */+for(i=0;i<num_src;++i){+char*filename=rename_src[i].p->one->path;+constchar*base=NULL;+intptr_tsrc_index;+intptr_tdst_index;++/* Find out if this basename is unique among sources */+base=get_basename(filename);+src_index=strintmap_get(&sources,base);+if(src_index==-1)+continue;/* not a unique basename; skip it */+assert(src_index==i);++if(strintmap_contains(&dests,base)){+structdiff_filespec*one,*two;+intscore;++/* Find out if this basename is unique among dests */+dst_index=strintmap_get(&dests,base);+if(dst_index==-1)+continue;/* not a unique basename; skip it */++/* Ignore this dest if already used in a rename */+if(rename_dst[dst_index].is_rename)+continue;/* already used previously */++/* Estimate the similarity */+one=rename_src[src_index].p->one;+two=rename_dst[dst_index].p->two;+score=estimate_similarity(options->repo,one,two,+minimum_score,skip_unmodified);++/* If sufficiently similar, record as rename pair */+if(score<minimum_score)+continue;+record_rename_pair(dst_index,src_index,score);+renames++;++/*+*Foundarenamesodon'tneedtextanymore;ifwe+*didn'tfindarename,thefilespec_blobwouldget+*re-usedwhendoingthematrixofcomparisons.+*/+diff_free_filespec_blob(one);+diff_free_filespec_blob(two);+}+}strintmap_clear(&sources);strintmap_clear(&dests);-return0;+returnrenames;}#define NUM_CANDIDATE_PER_DST 4
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-10 15:17:30
From: Elijah Newren <redacted>
The last few patches have introduced a new preliminary step when rename
detection is on but both break detection and copy detection are off.
Document this new step. While we're at it, add a testcase that checks
the new behavior as well.
Signed-off-by: Elijah Newren <redacted>
---
Documentation/gitdiffcore.txt | 17 +++++++++++++++++
1 file changed, 17 insertions(+)
@@ -168,6 +168,23 @@ a similarity score different from the default of 50% by giving a number after the "-M" or "-C" option (e.g. "-M8" to tell it to use 8/10 = 80%).+Note that when rename detection is on but both copy and break+detection are off, rename detection adds a preliminary step that first+checks if files are moved across directories while keeping their+filename the same. If there is a file added to a directory whose+contents is sufficiently similar to a file with the same name that got+deleted from a different directory, it will mark them as renames and+exclude them from the later quadratic step (the one that pairwise+compares all unmatched files to find the "best" matches, determined by+the highest content similarity). So, for example, if+docs/extensions.txt and docs/config/extensions.txt have similar+content, then they will be marked as a rename even if it turns out+that docs/extensions.txt was more similar to src/extension-checks.c.+At most, one comparison is done per file in this preliminary pass; so+if there are several extensions.txt files throughout the directory+hierarchy that were added and deleted, this preliminary step will be+skipped for those files.+ Note. When the "-C" option is used with `--find-copies-harder` option, 'git diff-{asterisk}' commands feed unmodified filepairs to diffcore mechanism as well as modified ones. This lets the copy
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-11 08:16:41
This series depends on ort-perf-batch-6[1].
This series uses file basenames (portion of the path after final '/',
including extension) in a basic fashion to guide rename detection.
Changes since v3:
* update documentation as suggested by Junio
* NEW: add another patch at the end, to simplify patch series that will be
submitted later (please review!)
[1] https://lore.kernel.org/git/xmqqlfc4byt6.fsf@gitster.c.googlers.com/
Elijah Newren (6):
t4001: add a test comparing basename similarity and content similarity
diffcore-rename: compute basenames of all source and dest candidates
diffcore-rename: complete find_basename_matches()
diffcore-rename: guide inexact rename detection based on basenames
gitdiffcore doc: mention new preliminary step for rename detection
merge-ort: call diffcore_rename() directly
Documentation/gitdiffcore.txt | 20 ++++
diffcore-rename.c | 202 +++++++++++++++++++++++++++++++++-
merge-ort.c | 66 +++++++++--
t/t4001-diff-rename.sh | 24 ++++
4 files changed, 301 insertions(+), 11 deletions(-)
base-commit: 7ae9460d3dba84122c2674b46e4339b9d42bdedd
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-843%2Fnewren%2Fort-perf-batch-7-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-843/newren/ort-perf-batch-7-v4
Pull-Request: https://github.com/gitgitgadget/git/pull/843
Range-diff vs v3:
1: 3e6af929d135 = 1: 3e6af929d135 t4001: add a test comparing basename similarity and content similarity
2: 4fff9b1ff57b = 2: 4fff9b1ff57b diffcore-rename: compute basenames of all source and dest candidates
3: dc26881e4ed3 = 3: dc26881e4ed3 diffcore-rename: complete find_basename_matches()
4: 2493f4b2f55d = 4: 2493f4b2f55d diffcore-rename: guide inexact rename detection based on basenames
5: fc72d24a3358 ! 5: 4e86ed3f29d4 gitdiffcore doc: mention new preliminary step for rename detection
@@ Documentation/gitdiffcore.txt: a similarity score different from the default of
+deleted from a different directory, it will mark them as renames and
+exclude them from the later quadratic step (the one that pairwise
+compares all unmatched files to find the "best" matches, determined by
-+the highest content similarity). So, for example, if
-+docs/extensions.txt and docs/config/extensions.txt have similar
-+content, then they will be marked as a rename even if it turns out
-+that docs/extensions.txt was more similar to src/extension-checks.c.
-+At most, one comparison is done per file in this preliminary pass; so
-+if there are several extensions.txt files throughout the directory
-+hierarchy that were added and deleted, this preliminary step will be
-+skipped for those files.
++the highest content similarity). So, for example, if a deleted
++docs/ext.txt and an added docs/config/ext.txt are similar enough, they
++will be marked as a rename and prevent an added docs/ext.md that may
++be even more similar to the deleted docs/ext.txt from being considered
++as the rename destination in the later step. For this reason, the
++preliminary "match same filename" step uses a bit higher threshold to
++mark a file pair as a rename and stop considering other candidates for
++better matches. At most, one comparison is done per file in this
++preliminary pass; so if there are several ext.txt files throughout the
++directory hierarchy that were added and deleted, this preliminary step
++will be skipped for those files.
+
Note. When the "-C" option is used with `--find-copies-harder`
option, 'git diff-{asterisk}' commands feed unmodified filepairs to
-: ------------ > 6: fedb3d323d94 merge-ort: call diffcore_rename() directly
--
gitgitgadget
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-11 08:17:10
From: Elijah Newren <redacted>
Add a simple test where a removed file is similar to two different added
files; one of them has the same basename, and the other has a slightly
higher content similarity. Without break detection, filename similarity
of 100% trumps content similarity for pairing up related files. For
any filename similarity less than 100%, the opposite is true -- content
similarity is all that matters. Add a testcase that documents this.
Subsequent commits will add a new rule that includes an inbetween state,
where a mixture of filename similarity and content similarity are
weighed, and which will change the outcome of this testcase.
Signed-off-by: Elijah Newren <redacted>
---
t/t4001-diff-rename.sh | 24 ++++++++++++++++++++++++
1 file changed, 24 insertions(+)
@@ -262,4 +262,28 @@ test_expect_success 'diff-tree -l0 defaults to a big rename limit, not zero' 'grep"myotherfile.*myfile"actual'+test_expect_success'basename similarity vs best similarity''+mkdirsubdir&&+test_write_linesline1line2line3line4line5\+line6line7line8line9line10>subdir/file.txt&&+gitaddsubdir/file.txt&&+gitcommit-m"base txt"&&++gitrmsubdir/file.txt&&+test_write_linesline1line2line3line4line5\+line6line7line8>file.txt&&+test_write_linesline1line2line3line4line5\+line6line7line8line9>file.md&&+gitaddfile.txtfile.md&&+gitcommit-a-m"rename"&&+gitdiff-tree-r-M--name-statusHEAD^HEAD>actual&&+# subdir/file.txt is 89% similar to file.md, 78% similar to file.txt,+# but since same basenames are checked first...+cat>expected<<-\EOF&&+R088subdir/file.txtfile.md+Afile.txt+EOF+test_cmpexpectedactual+'+ test_done
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-11 08:17:13
From: Elijah Newren <redacted>
We want to make use of unique basenames to help inform rename detection,
so that more likely pairings can be checked first. (src/moduleA/foo.txt
and source/module/A/foo.txt are likely related if there are no other
'foo.txt' files among the deleted and added files.) Add a new function,
not yet used, which creates a map of the unique basenames within
rename_src and another within rename_dst, together with the indices
within rename_src/rename_dst where those basenames show up. Non-unique
basenames still show up in the map, but have an invalid index (-1).
This function was inspired by the fact that in real world repositories,
files are often moved across directories without changing names. Here
are some sample repositories and the percentage of their historical
renames (as of early 2020) that preserved basenames:
* linux: 76%
* gcc: 64%
* gecko: 79%
* webkit: 89%
These statistics alone don't prove that an optimization in this area
will help or how much it will help, since there are also unpaired adds
and deletes, restrictions on which basenames we consider, etc., but it
certainly motivated the idea to try something in this area.
Signed-off-by: Elijah Newren <redacted>
---
diffcore-rename.c | 61 +++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 61 insertions(+)
@@ -367,6 +367,67 @@ static int find_exact_renames(struct diff_options *options)returnrenames;}+staticconstchar*get_basename(constchar*filename)+{+/*+*gitbasename()hastoworryaboutspecialdrivers,multiple+*directoryseparatorcharacters,trailingslashes,NULLor+*emptystrings,etc.Weonlyworkonfilenamesasstoredin+*git,andthusgettoignoreallthosecomplications.+*/+constchar*base=strrchr(filename,'/');+returnbase?base+1:filename;+}++MAYBE_UNUSED+staticintfind_basename_matches(structdiff_options*options,+intminimum_score,+intnum_src)+{+inti;+structstrintmapsources;+structstrintmapdests;++/* Create maps of basename -> fullname(s) for sources and dests */+strintmap_init_with_options(&sources,-1,NULL,0);+strintmap_init_with_options(&dests,-1,NULL,0);+for(i=0;i<num_src;++i){+char*filename=rename_src[i].p->one->path;+constchar*base;++/* exact renames removed in remove_unneeded_paths_from_src() */+assert(!rename_src[i].p->one->rename_used);++/* Record index within rename_src (i) if basename is unique */+base=get_basename(filename);+if(strintmap_contains(&sources,base))+strintmap_set(&sources,base,-1);+else+strintmap_set(&sources,base,i);+}+for(i=0;i<rename_dst_nr;++i){+char*filename=rename_dst[i].p->two->path;+constchar*base;++if(rename_dst[i].is_rename)+continue;/* involved in exact match already. */++/* Record index within rename_dst (i) if basename is unique */+base=get_basename(filename);+if(strintmap_contains(&dests,base))+strintmap_set(&dests,base,-1);+else+strintmap_set(&dests,base,i);+}++/* TODO: Make use of basenames source and destination basenames */++strintmap_clear(&sources);+strintmap_clear(&dests);++return0;+}+#define NUM_CANDIDATE_PER_DST 4staticvoidrecord_if_better(structdiff_scorem[],structdiff_score*o){
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-11 08:17:13
From: Elijah Newren <redacted>
It is not uncommon in real world repositories for the majority of file
renames to not change the basename of the file; i.e. most "renames" are
just a move of files into different directories. We can make use of
this to avoid comparing all rename source candidates with all rename
destination candidates, by first comparing sources to destinations with
the same basenames. If two files with the same basename are
sufficiently similar, we record the rename; if not, we include those
files in the more exhaustive matrix comparison.
This means we are adding a set of preliminary additional comparisons,
but for each file we only compare it with at most one other file. For
example, if there was a include/media/device.h that was deleted and a
src/module/media/device.h that was added, and there were no other
device.h files added or deleted between the commits being compared,
then these two files would be compared in the preliminary step.
This commit does not yet actually employ this new optimization, it
merely adds a function which can be used for this purpose. The next
commit will do the necessary plumbing to make use of it.
Note that this optimization might give us different results than without
the optimization, because it's possible that despite files with the same
basename being sufficiently similar to be considered a rename, there's
an even better match between files without the same basename. I think
that is okay for four reasons: (1) it's easy to explain to the users
what happened if it does ever occur (or even for them to intuitively
figure out), (2) as the next patch will show it provides such a large
performance boost that it's worth the tradeoff, and (3) it's somewhat
unlikely that despite having unique matching basenames that other files
serve as better matches. Reason (4) takes a full paragraph to
explain...
If the previous three reasons aren't enough, consider what rename
detection already does. Break detection is not the default, meaning
that if files have the same _fullname_, then they are considered related
even if they are 0% similar. In fact, in such a case, we don't even
bother comparing the files to see if they are similar let alone
comparing them to all other files to see what they are most similar to.
Basically, we override content similarity based on sufficient filename
similarity. Without the filename similarity (currently implemented as
an exact match of filename), we swing the pendulum the opposite
direction and say that filename similarity is irrelevant and compare a
full N x M matrix of sources and destinations to find out which have the
most similar contents. This optimization just adds another form of
filename similarity comparison, but augments it with a file content
similarity check as well. Basically, if two files have the same
basename and are sufficiently similar to be considered a rename, mark
them as such without comparing the two to all other rename candidates.
Signed-off-by: Elijah Newren <redacted>
---
diffcore-rename.c | 95 +++++++++++++++++++++++++++++++++++++++++++++--
1 file changed, 92 insertions(+), 3 deletions(-)
@@ -384,10 +384,52 @@ static int find_basename_matches(struct diff_options *options,intminimum_score,intnum_src){-inti;+/*+*WhenIcheckedinearly2020,over76%offilerenamesinlinux+*justmovedfilestoadifferentdirectorybutkeptthesame+*basename.gccdidthatwithover64%ofrenames,geckodidit+*withover79%,andWebKitdiditwithover89%.+*+*ThereforewecanbypassthenormalexhaustiveNxMmatrix+*comparisonofsimilaritiesbetweenallpotentialrenamesources+*anddestinationsbyinsteadusingfilebasenameasahint(i.e.+*theportionofthefilenameafterthelast'/'),checkingfor+*similaritybetweenfileswiththesamebasename,andifwefind+*apairthataresufficientlysimilar,recordtherenamepairand+*excludethosetwofromtheNxMmatrix.+*+*This*might*causeustofindalessthanoptimalpairing(if+*thereisanotherfilethatweareevenmoresimilartobuthasa+*differentbasename).Giventhehugeperformanceadvantage+*basenamematchingprovides,andgiventhefrequencywithwhich+*peopleusethesamebasenameinrealworldprojects,that'sa+*trade-offwearewillingtoacceptwhendoingjustrename+*detection.+*+*Ifsomeonewantscopydetectionthatimpliestheyarewillingto+*spendmorecyclestofindsimilaritiesbetweenfiles,soitmay+*belesslikelythatthisheuristiciswanted.Ifsomeoneis+*doingbreakdetection,thatmeanstheydonotwantfilename+*similaritytoimplyanyformofcontentsimiliarity,andthus+*thisheuristicwoulddefinitelybeincompatible.+*/++inti,renames=0;structstrintmapsources;structstrintmapdests;+/*+*Theprefetechingstuffwantstoknowifitcanskipprefetching+*blobsthatareunmodified...andwillthendoalittleextrawork+*toverifythattheoidsareindeeddifferentbeforeprefetching.+*Unmodifiedblobsareonlyrelevantwhendoingcopydetection;+*whenlimitingtorenamedetection,diffcore_rename[_extended]()+*willneverbecalledwithunmodifiedsourcepathsfedtous,so+*theextraworknecessarytocheckifrename_srcentriesare+*unmodifiedwouldbeasmallwaste.+*/+intskip_unmodified=0;+/* Create maps of basename -> fullname(s) for sources and dests */strintmap_init_with_options(&sources,-1,NULL,0);strintmap_init_with_options(&dests,-1,NULL,0);
@@ -420,12 +462,59 @@ static int find_basename_matches(struct diff_options *options,strintmap_set(&dests,base,i);}-/* TODO: Make use of basenames source and destination basenames */+/* Now look for basename matchups and do similarity estimation */+for(i=0;i<num_src;++i){+char*filename=rename_src[i].p->one->path;+constchar*base=NULL;+intptr_tsrc_index;+intptr_tdst_index;++/* Find out if this basename is unique among sources */+base=get_basename(filename);+src_index=strintmap_get(&sources,base);+if(src_index==-1)+continue;/* not a unique basename; skip it */+assert(src_index==i);++if(strintmap_contains(&dests,base)){+structdiff_filespec*one,*two;+intscore;++/* Find out if this basename is unique among dests */+dst_index=strintmap_get(&dests,base);+if(dst_index==-1)+continue;/* not a unique basename; skip it */++/* Ignore this dest if already used in a rename */+if(rename_dst[dst_index].is_rename)+continue;/* already used previously */++/* Estimate the similarity */+one=rename_src[src_index].p->one;+two=rename_dst[dst_index].p->two;+score=estimate_similarity(options->repo,one,two,+minimum_score,skip_unmodified);++/* If sufficiently similar, record as rename pair */+if(score<minimum_score)+continue;+record_rename_pair(dst_index,src_index,score);+renames++;++/*+*Foundarenamesodon'tneedtextanymore;ifwe+*didn'tfindarename,thefilespec_blobwouldget+*re-usedwhendoingthematrixofcomparisons.+*/+diff_free_filespec_blob(one);+diff_free_filespec_blob(two);+}+}strintmap_clear(&sources);strintmap_clear(&dests);-return0;+returnrenames;}#define NUM_CANDIDATE_PER_DST 4
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-11 08:17:14
From: Elijah Newren <redacted>
The last few patches have introduced a new preliminary step when rename
detection is on but both break detection and copy detection are off.
Document this new step. While we're at it, add a testcase that checks
the new behavior as well.
Signed-off-by: Elijah Newren <redacted>
---
Documentation/gitdiffcore.txt | 20 ++++++++++++++++++++
1 file changed, 20 insertions(+)
@@ -168,6 +168,26 @@ a similarity score different from the default of 50% by giving a number after the "-M" or "-C" option (e.g. "-M8" to tell it to use 8/10 = 80%).+Note that when rename detection is on but both copy and break+detection are off, rename detection adds a preliminary step that first+checks if files are moved across directories while keeping their+filename the same. If there is a file added to a directory whose+contents is sufficiently similar to a file with the same name that got+deleted from a different directory, it will mark them as renames and+exclude them from the later quadratic step (the one that pairwise+compares all unmatched files to find the "best" matches, determined by+the highest content similarity). So, for example, if a deleted+docs/ext.txt and an added docs/config/ext.txt are similar enough, they+will be marked as a rename and prevent an added docs/ext.md that may+be even more similar to the deleted docs/ext.txt from being considered+as the rename destination in the later step. For this reason, the+preliminary "match same filename" step uses a bit higher threshold to+mark a file pair as a rename and stop considering other candidates for+better matches. At most, one comparison is done per file in this+preliminary pass; so if there are several ext.txt files throughout the+directory hierarchy that were added and deleted, this preliminary step+will be skipped for those files.+ Note. When the "-C" option is used with `--find-copies-harder` option, 'git diff-{asterisk}' commands feed unmodified filepairs to diffcore mechanism as well as modified ones. This lets the copy
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-11 08:17:14
From: Elijah Newren <redacted>
Make use of the new find_basename_matches() function added in the last
two patches, to find renames more rapidly in cases where we can match up
files based on basenames. As a quick reminder (see the last two commit
messages for more details), this means for example that
docs/extensions.txt and docs/config/extensions.txt are considered likely
renames if there are no 'extensions.txt' files elsewhere among the added
and deleted files, and if a similarity check confirms they are similar,
then they are marked as a rename without looking for a better similarity
match among other files. This is a behavioral change, as covered in
more detail in the previous commit message.
We do not use this heuristic together with either break or copy
detection. The point of break detection is to say that filename
similarity does not imply file content similarity, and we only want to
know about file content similarity. The point of copy detection is to
use more resources to check for additional similarities, while this is
an optimization that uses far less resources but which might also result
in finding slightly fewer similarities. So the idea behind this
optimization goes against both of those features, and will be turned off
for both.
For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
this change improves the performance as follows:
Before After
no-renames: 13.815 s ± 0.062 s 13.294 s ± 0.103 s
mega-renames: 1799.937 s ± 0.493 s 187.248 s ± 0.882 s
just-one-mega: 51.289 s ± 0.019 s 5.557 s ± 0.017 s
Signed-off-by: Elijah Newren <redacted>
---
diffcore-rename.c | 54 ++++++++++++++++++++++++++++++++++++++----
t/t4001-diff-rename.sh | 4 ++--
2 files changed, 51 insertions(+), 7 deletions(-)
@@ -727,12 +726,57 @@ void diffcore_rename(struct diff_options *options)if(minimum_score==MAX_SCORE)gotocleanup;+num_sources=rename_src_nr;++if(want_copies||break_idx){+/*+*Cullsources:+*-removeonescorrespondingtoexactrenames+*/+trace2_region_enter("diff","cull after exact",options->repo);+remove_unneeded_paths_from_src(want_copies);+trace2_region_leave("diff","cull after exact",options->repo);+}else{+/* Determine minimum score to match basenames */+doublefactor=0.5;+char*basename_factor=getenv("GIT_BASENAME_FACTOR");+intmin_basename_score;++if(basename_factor)+factor=strtol(basename_factor,NULL,10)/100.0;+assert(factor>=0.0&&factor<=1.0);+min_basename_score=minimum_score++(int)(factor*(MAX_SCORE-minimum_score));++/*+*Cullsources:+*-removeonesinvolvedinrenames(foundviaexactmatch)+*/+trace2_region_enter("diff","cull after exact",options->repo);+remove_unneeded_paths_from_src(want_copies);+trace2_region_leave("diff","cull after exact",options->repo);++/* Utilize file basenames to quickly find renames. */+trace2_region_enter("diff","basename matches",options->repo);+rename_count+=find_basename_matches(options,+min_basename_score,+rename_src_nr);+trace2_region_leave("diff","basename matches",options->repo);++/*+*Cullsources,again:+*-removeonesinvolvedinrenames(foundviabasenames)+*/+trace2_region_enter("diff","cull basename",options->repo);+remove_unneeded_paths_from_src(want_copies);+trace2_region_leave("diff","cull basename",options->repo);+}+/*-*Calculatehowmanyrenamesareleft+*Calculatehowmanyrenamedestinationsareleft*/num_destinations=(rename_dst_nr-rename_count);-remove_unneeded_paths_from_src(want_copies);-num_sources=rename_src_nr;+num_sources=rename_src_nr;/* rename_src_nr reflects lower number *//* All done? */if(!num_destinations||!num_sources)
@@ -764,7 +808,7 @@ void diffcore_rename(struct diff_options *options)structdiff_score*m;if(rename_dst[i].is_rename)-continue;/* dealt with exact match already. */+continue;/* exact or basename match already handled */m=&mx[dst_cnt*NUM_CANDIDATE_PER_DST];for(j=0;j<NUM_CANDIDATE_PER_DST;j++)
@@ -280,8 +280,8 @@ test_expect_success 'basename similarity vs best similarity' '# subdir/file.txt is 89% similar to file.md, 78% similar to file.txt,# but since same basenames are checked first...cat>expected<<-\EOF&&-R088subdir/file.txtfile.md-Afile.txt+Afile.md+R078subdir/file.txtfile.txtEOFtest_cmpexpectedactual'
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-11 08:17:26
From: Elijah Newren <redacted>
We want to pass additional information to diffcore_rename() (or some
variant thereof) without plumbing that extra information through
diff_tree_oid() and diffcore_std(). Further, since we will need to
gather additional special information related to diffs and are walking
the trees anyway in collect_merge_info(), it seems odd to have
diff_tree_oid()/diffcore_std() repeat those tree walks. And there may
be times where we can avoid traversing into a subtree in
collect_merge_info() (based on additional information at our disposal),
that the basic diff logic would be unable to take advantage of. For all
these reasons, just create the add and delete pairs ourself and then
call diffcore_rename() directly.
This change is primarily about enabling future optimizations; the
advantage of avoiding extra tree traversals is small compared to the
cost of rename detection, and the advantage of avoiding the extra tree
traversals is somewhat offset by the extra time spent in
collect_merge_info() collecting the additional data anyway. However...
For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
this change improves the performance as follows:
Before After
no-renames: 13.294 s ± 0.103 s 12.775 s ± 0.062 s
mega-renames: 187.248 s ± 0.882 s 188.754 s ± 0.284 s
just-one-mega: 5.557 s ± 0.017 s 5.599 s ± 0.019 s
Signed-off-by: Elijah Newren <redacted>
---
merge-ort.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++------
1 file changed, 59 insertions(+), 7 deletions(-)
@@ -554,6 +572,21 @@ static void collect_rename_info(struct merge_options *opt,if(sides&2)strset_add(&renames->dirs_removed[2],fullname);}++if(filemask==0||filemask==7)+return;++for(side=MERGE_SIDE1;side<=MERGE_SIDE2;++side){+unsignedside_mask=(1<<side);++/* Check for deletion on side */+if((filemask&1)&&!(filemask&side_mask))+add_pair(opt,names,fullname,side,0/* delete */);++/* Check for addition on side */+if(!(filemask&1)&&(filemask&side_mask))+add_pair(opt,names,fullname,side,1/* add */);+}}staticintcollect_merge_info_callback(intn,
@@ -2089,8 +2143,6 @@ static int compare_pairs(const void *a_, const void *b_)/* Call diffcore_rename() to compute which files have changed on given side */staticvoiddetect_regular_renames(structmerge_options*opt,-structtree*merge_base,-structtree*side,unsignedside_index){structdiff_optionsdiff_opts;
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-14 07:53:10
From: Elijah Newren <redacted>
It is not uncommon in real world repositories for the majority of file
renames to not change the basename of the file; i.e. most "renames" are
just a move of files into different directories. We can make use of
this to avoid comparing all rename source candidates with all rename
destination candidates, by first comparing sources to destinations with
the same basenames. If two files with the same basename are
sufficiently similar, we record the rename; if not, we include those
files in the more exhaustive matrix comparison.
This means we are adding a set of preliminary additional comparisons,
but for each file we only compare it with at most one other file. For
example, if there was a include/media/device.h that was deleted and a
src/module/media/device.h that was added, and there are no other
device.h files in the remaining sets of added and deleted files after
exact rename detection, then these two files would be compared in the
preliminary step.
This commit does not yet actually employ this new optimization, it
merely adds a function which can be used for this purpose. The next
commit will do the necessary plumbing to make use of it.
Note that this optimization might give us different results than without
the optimization, because it's possible that despite files with the same
basename being sufficiently similar to be considered a rename, there's
an even better match between files without the same basename. I think
that is okay for four reasons: (1) it's easy to explain to the users
what happened if it does ever occur (or even for them to intuitively
figure out), (2) as the next patch will show it provides such a large
performance boost that it's worth the tradeoff, and (3) it's somewhat
unlikely that despite having unique matching basenames that other files
serve as better matches. Reason (4) takes a full paragraph to
explain...
If the previous three reasons aren't enough, consider what rename
detection already does. Break detection is not the default, meaning
that if files have the same _fullname_, then they are considered related
even if they are 0% similar. In fact, in such a case, we don't even
bother comparing the files to see if they are similar let alone
comparing them to all other files to see what they are most similar to.
Basically, we override content similarity based on sufficient filename
similarity. Without the filename similarity (currently implemented as
an exact match of filename), we swing the pendulum the opposite
direction and say that filename similarity is irrelevant and compare a
full N x M matrix of sources and destinations to find out which have the
most similar contents. This optimization just adds another form of
filename similarity comparison, but augments it with a file content
similarity check as well. Basically, if two files have the same
basename and are sufficiently similar to be considered a rename, mark
them as such without comparing the two to all other rename candidates.
Signed-off-by: Elijah Newren <redacted>
---
diffcore-rename.c | 82 +++++++++++++++++++++++++++++++++++++++++++++--
1 file changed, 79 insertions(+), 3 deletions(-)
@@ -422,12 +466,44 @@ static int find_basename_matches(struct diff_options *options,strintmap_set(&dests,base,i);}-/* TODO: Make use of basenames source and destination basenames */+/* Now look for basename matchups and do similarity estimation */+strintmap_for_each_entry(&sources,&iter,entry){+constchar*base=entry->key;+intptr_tsrc_index=(intptr_t)entry->value;+intptr_tdst_index;+if(src_index==-1)+continue;++if(0<=(dst_index=strintmap_get(&dests,base))){+structdiff_filespec*one,*two;+intscore;++/* Estimate the similarity */+one=rename_src[src_index].p->one;+two=rename_dst[dst_index].p->two;+score=estimate_similarity(options->repo,one,two,+minimum_score,skip_unmodified);++/* If sufficiently similar, record as rename pair */+if(score<minimum_score)+continue;+record_rename_pair(dst_index,src_index,score);+renames++;++/*+*Foundarenamesodon'tneedtextanymore;ifwe+*didn'tfindarename,thefilespec_blobwouldget+*re-usedwhendoingthematrixofcomparisons.+*/+diff_free_filespec_blob(one);+diff_free_filespec_blob(two);+}+}strintmap_clear(&sources);strintmap_clear(&dests);-return0;+returnrenames;}#define NUM_CANDIDATE_PER_DST 4
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-14 07:53:21
From: Elijah Newren <redacted>
The last few patches have introduced a new preliminary step when rename
detection is on but both break detection and copy detection are off.
Document this new step. While we're at it, add a testcase that checks
the new behavior as well.
Signed-off-by: Elijah Newren <redacted>
---
Documentation/gitdiffcore.txt | 20 ++++++++++++++++++++
1 file changed, 20 insertions(+)
@@ -168,6 +168,26 @@ a similarity score different from the default of 50% by giving a number after the "-M" or "-C" option (e.g. "-M8" to tell it to use 8/10 = 80%).+Note that when rename detection is on but both copy and break+detection are off, rename detection adds a preliminary step that first+checks if files are moved across directories while keeping their+filename the same. If there is a file added to a directory whose+contents is sufficiently similar to a file with the same name that got+deleted from a different directory, it will mark them as renames and+exclude them from the later quadratic step (the one that pairwise+compares all unmatched files to find the "best" matches, determined by+the highest content similarity). So, for example, if a deleted+docs/ext.txt and an added docs/config/ext.txt are similar enough, they+will be marked as a rename and prevent an added docs/ext.md that may+be even more similar to the deleted docs/ext.txt from being considered+as the rename destination in the later step. For this reason, the+preliminary "match same filename" step uses a bit higher threshold to+mark a file pair as a rename and stop considering other candidates for+better matches. At most, one comparison is done per file in this+preliminary pass; so if there are several remaining ext.txt files+throughout the directory hierarchy after exact rename detection, this+preliminary step will be skipped for those files.+ Note. When the "-C" option is used with `--find-copies-harder` option, 'git diff-{asterisk}' commands feed unmodified filepairs to diffcore mechanism as well as modified ones. This lets the copy
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-14 07:53:26
This series depends on ort-perf-batch-6. It appears Junio has appended an
earlier round of this series on that one and called the combined series
en/diffcore-rename. I'm still resubmitting the two separately to preserve
the threaded discussion in the archives and because gitgitgadget can provide
proper range-diffs that way.
This series uses file basenames (portion of the path after final '/',
including extension) in a basic fashion to guide rename detection.
Changes since v4:
* add wording to make it clearer that we are considering remaining
basenames after exact rename detection
* add three minor optimizations to patch 3. (All three will have to be
undone by the next series, but this series is probably clearer with
them.)
* a typo fix or two
* v2 of ort-perf-batch-6 added some changes around consistency of
rename_src_nr; make similar changes in using this variable in
find_basename_changes() for consistency
* fix the testcase so the expected comments about the change in behavior
only show up after we change the behavior
* attempt a rewrite of the commit message for the new testcase, who knows
if I'll get it right this time.
Elijah Newren (6):
t4001: add a test comparing basename similarity and content similarity
diffcore-rename: compute basenames of source and dest candidates
diffcore-rename: complete find_basename_matches()
diffcore-rename: guide inexact rename detection based on basenames
gitdiffcore doc: mention new preliminary step for rename detection
merge-ort: call diffcore_rename() directly
Documentation/gitdiffcore.txt | 20 ++++
diffcore-rename.c | 190 +++++++++++++++++++++++++++++++++-
merge-ort.c | 66 ++++++++++--
t/t4001-diff-rename.sh | 24 +++++
4 files changed, 289 insertions(+), 11 deletions(-)
base-commit: dd6595b45640ee9894293e8b729ef9a254564a49
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-843%2Fnewren%2Fort-perf-batch-7-v5
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-843/newren/ort-perf-batch-7-v5
Pull-Request: https://github.com/gitgitgadget/git/pull/843
Range-diff vs v4:
1: 3e6af929d135 ! 1: 6848422e47e8 t4001: add a test comparing basename similarity and content similarity
@@ Commit message
Add a simple test where a removed file is similar to two different added
files; one of them has the same basename, and the other has a slightly
- higher content similarity. Without break detection, filename similarity
- of 100% trumps content similarity for pairing up related files. For
- any filename similarity less than 100%, the opposite is true -- content
- similarity is all that matters. Add a testcase that documents this.
+ higher content similarity. In the current test, content similarity is
+ weighted higher than filename similarity.
- Subsequent commits will add a new rule that includes an inbetween state,
- where a mixture of filename similarity and content similarity are
- weighed, and which will change the outcome of this testcase.
+ Subsequent commits will add a new rule that weighs a mixture of filename
+ similarity and content similarity in a manner that will change the
+ outcome of this testcase.
Signed-off-by: Elijah Newren [off-list ref]
@@ t/t4001-diff-rename.sh: test_expect_success 'diff-tree -l0 defaults to a big ren
+ git add file.txt file.md &&
+ git commit -a -m "rename" &&
+ git diff-tree -r -M --name-status HEAD^ HEAD >actual &&
-+ # subdir/file.txt is 89% similar to file.md, 78% similar to file.txt,
-+ # but since same basenames are checked first...
++ # subdir/file.txt is 88% similar to file.md and 78% similar to file.txt
+ cat >expected <<-\EOF &&
+ R088 subdir/file.txt file.md
+ A file.txt
2: 4fff9b1ff57b ! 2: 73baae2535d0 diffcore-rename: compute basenames of all source and dest candidates
@@ Metadata
Author: Elijah Newren [off-list ref]
## Commit message ##
- diffcore-rename: compute basenames of all source and dest candidates
+ diffcore-rename: compute basenames of source and dest candidates
- We want to make use of unique basenames to help inform rename detection,
- so that more likely pairings can be checked first. (src/moduleA/foo.txt
- and source/module/A/foo.txt are likely related if there are no other
- 'foo.txt' files among the deleted and added files.) Add a new function,
- not yet used, which creates a map of the unique basenames within
- rename_src and another within rename_dst, together with the indices
- within rename_src/rename_dst where those basenames show up. Non-unique
- basenames still show up in the map, but have an invalid index (-1).
+ We want to make use of unique basenames among remaining source and
+ destination files to help inform rename detection, so that more likely
+ pairings can be checked first. (src/moduleA/foo.txt and
+ source/module/A/foo.txt are likely related if there are no other
+ 'foo.txt' files among the remaining deleted and added files.) Add a new
+ function, not yet used, which creates a map of the unique basenames
+ within rename_src and another within rename_dst, together with the
+ indices within rename_src/rename_dst where those basenames show up.
+ Non-unique basenames still show up in the map, but have an invalid index
+ (-1).
This function was inspired by the fact that in real world repositories,
files are often moved across directories without changing names. Here
@@ diffcore-rename.c: static int find_exact_renames(struct diff_options *options)
+static const char *get_basename(const char *filename)
+{
+ /*
-+ * gitbasename() has to worry about special drivers, multiple
++ * gitbasename() has to worry about special drives, multiple
+ * directory separator characters, trailing slashes, NULL or
+ * empty strings, etc. We only work on filenames as stored in
+ * git, and thus get to ignore all those complications.
@@ diffcore-rename.c: static int find_exact_renames(struct diff_options *options)
+
+MAYBE_UNUSED
+static int find_basename_matches(struct diff_options *options,
-+ int minimum_score,
-+ int num_src)
++ int minimum_score)
+{
+ int i;
+ struct strintmap sources;
+ struct strintmap dests;
+
-+ /* Create maps of basename -> fullname(s) for sources and dests */
++ /*
++ * Create maps of basename -> fullname(s) for remaining sources and
++ * dests.
++ */
+ strintmap_init_with_options(&sources, -1, NULL, 0);
+ strintmap_init_with_options(&dests, -1, NULL, 0);
-+ for (i = 0; i < num_src; ++i) {
++ for (i = 0; i < rename_src_nr; ++i) {
+ char *filename = rename_src[i].p->one->path;
+ const char *base;
+
3: dc26881e4ed3 ! 3: ece76429dc35 diffcore-rename: complete find_basename_matches()
@@ Commit message
This means we are adding a set of preliminary additional comparisons,
but for each file we only compare it with at most one other file. For
example, if there was a include/media/device.h that was deleted and a
- src/module/media/device.h that was added, and there were no other
- device.h files added or deleted between the commits being compared,
- then these two files would be compared in the preliminary step.
+ src/module/media/device.h that was added, and there are no other
+ device.h files in the remaining sets of added and deleted files after
+ exact rename detection, then these two files would be compared in the
+ preliminary step.
This commit does not yet actually employ this new optimization, it
merely adds a function which can be used for this purpose. The next
@@ Commit message
Signed-off-by: Elijah Newren [off-list ref]
## diffcore-rename.c ##
-@@ diffcore-rename.c: static int find_basename_matches(struct diff_options *options,
- int minimum_score,
- int num_src)
+@@ diffcore-rename.c: MAYBE_UNUSED
+ static int find_basename_matches(struct diff_options *options,
+ int minimum_score)
{
- int i;
+ /*
@@ diffcore-rename.c: static int find_basename_matches(struct diff_options *options
+ int i, renames = 0;
struct strintmap sources;
struct strintmap dests;
-
++ struct hashmap_iter iter;
++ struct strmap_entry *entry;
++
+ /*
+ * The prefeteching stuff wants to know if it can skip prefetching
+ * blobs that are unmodified...and will then do a little extra work
@@ diffcore-rename.c: static int find_basename_matches(struct diff_options *options
+ * unmodified would be a small waste.
+ */
+ int skip_unmodified = 0;
-+
- /* Create maps of basename -> fullname(s) for sources and dests */
- strintmap_init_with_options(&sources, -1, NULL, 0);
- strintmap_init_with_options(&dests, -1, NULL, 0);
+
+ /*
+ * Create maps of basename -> fullname(s) for remaining sources and
@@ diffcore-rename.c: static int find_basename_matches(struct diff_options *options,
strintmap_set(&dests, base, i);
}
- /* TODO: Make use of basenames source and destination basenames */
+ /* Now look for basename matchups and do similarity estimation */
-+ for (i = 0; i < num_src; ++i) {
-+ char *filename = rename_src[i].p->one->path;
-+ const char *base = NULL;
-+ intptr_t src_index;
++ strintmap_for_each_entry(&sources, &iter, entry) {
++ const char *base = entry->key;
++ intptr_t src_index = (intptr_t)entry->value;
+ intptr_t dst_index;
-+
-+ /* Find out if this basename is unique among sources */
-+ base = get_basename(filename);
-+ src_index = strintmap_get(&sources, base);
+ if (src_index == -1)
-+ continue; /* not a unique basename; skip it */
-+ assert(src_index == i);
++ continue;
+
-+ if (strintmap_contains(&dests, base)) {
++ if (0 <= (dst_index = strintmap_get(&dests, base))) {
+ struct diff_filespec *one, *two;
+ int score;
+
-+ /* Find out if this basename is unique among dests */
-+ dst_index = strintmap_get(&dests, base);
-+ if (dst_index == -1)
-+ continue; /* not a unique basename; skip it */
-+
-+ /* Ignore this dest if already used in a rename */
-+ if (rename_dst[dst_index].is_rename)
-+ continue; /* already used previously */
-+
+ /* Estimate the similarity */
+ one = rename_src[src_index].p->one;
+ two = rename_dst[dst_index].p->two;
4: 2493f4b2f55d ! 4: 122902e2706f diffcore-rename: guide inexact rename detection based on basenames
@@ Commit message
files based on basenames. As a quick reminder (see the last two commit
messages for more details), this means for example that
docs/extensions.txt and docs/config/extensions.txt are considered likely
- renames if there are no 'extensions.txt' files elsewhere among the added
- and deleted files, and if a similarity check confirms they are similar,
- then they are marked as a rename without looking for a better similarity
- match among other files. This is a behavioral change, as covered in
- more detail in the previous commit message.
+ renames if there are no remaining 'extensions.txt' files elsewhere among
+ the added and deleted files, and if a similarity check confirms they are
+ similar, then they are marked as a rename without looking for a better
+ similarity match among other files. This is a behavioral change, as
+ covered in more detail in the previous commit message.
We do not use this heuristic together with either break or copy
detection. The point of break detection is to say that filename
@@ diffcore-rename.c: static const char *get_basename(const char *filename)
-MAYBE_UNUSED
static int find_basename_matches(struct diff_options *options,
- int minimum_score,
- int num_src)
+ int minimum_score)
+ {
@@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)
if (minimum_score == MAX_SCORE)
goto cleanup;
-+ num_sources = rename_src_nr;
-+
+- /* Calculate how many renames are left */
+- num_destinations = (rename_dst_nr - rename_count);
+- remove_unneeded_paths_from_src(want_copies);
+ num_sources = rename_src_nr;
+
+ if (want_copies || break_idx) {
+ /*
+ * Cull sources:
@@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)
+ /* Utilize file basenames to quickly find renames. */
+ trace2_region_enter("diff", "basename matches", options->repo);
+ rename_count += find_basename_matches(options,
-+ min_basename_score,
-+ rename_src_nr);
++ min_basename_score);
+ trace2_region_leave("diff", "basename matches", options->repo);
+
+ /*
@@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)
+ trace2_region_leave("diff", "cull basename", options->repo);
+ }
+
- /*
-- * Calculate how many renames are left
-+ * Calculate how many rename destinations are left
- */
- num_destinations = (rename_dst_nr - rename_count);
-- remove_unneeded_paths_from_src(want_copies);
-- num_sources = rename_src_nr;
++ /* Calculate how many rename destinations are left */
++ num_destinations = (rename_dst_nr - rename_count);
+ num_sources = rename_src_nr; /* rename_src_nr reflects lower number */
-
++
/* All done? */
if (!num_destinations || !num_sources)
+ goto cleanup;
@@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)
struct diff_score *m;
@@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)
## t/t4001-diff-rename.sh ##
@@ t/t4001-diff-rename.sh: test_expect_success 'basename similarity vs best similarity' '
- # subdir/file.txt is 89% similar to file.md, 78% similar to file.txt,
- # but since same basenames are checked first...
+ git add file.txt file.md &&
+ git commit -a -m "rename" &&
+ git diff-tree -r -M --name-status HEAD^ HEAD >actual &&
+- # subdir/file.txt is 88% similar to file.md and 78% similar to file.txt
++ # subdir/file.txt is 88% similar to file.md, 78% similar to file.txt,
++ # but since same basenames are checked first...
cat >expected <<-\EOF &&
- R088 subdir/file.txt file.md
- A file.txt
5: 4e86ed3f29d4 ! 5: 6f5584f61350 gitdiffcore doc: mention new preliminary step for rename detection
@@ Documentation/gitdiffcore.txt: a similarity score different from the default of
+preliminary "match same filename" step uses a bit higher threshold to
+mark a file pair as a rename and stop considering other candidates for
+better matches. At most, one comparison is done per file in this
-+preliminary pass; so if there are several ext.txt files throughout the
-+directory hierarchy that were added and deleted, this preliminary step
-+will be skipped for those files.
++preliminary pass; so if there are several remaining ext.txt files
++throughout the directory hierarchy after exact rename detection, this
++preliminary step will be skipped for those files.
+
Note. When the "-C" option is used with `--find-copies-harder`
option, 'git diff-{asterisk}' commands feed unmodified filepairs to
6: fedb3d323d94 = 6: aeca14f748af merge-ort: call diffcore_rename() directly
--
gitgitgadget
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-14 07:53:40
From: Elijah Newren <redacted>
Add a simple test where a removed file is similar to two different added
files; one of them has the same basename, and the other has a slightly
higher content similarity. In the current test, content similarity is
weighted higher than filename similarity.
Subsequent commits will add a new rule that weighs a mixture of filename
similarity and content similarity in a manner that will change the
outcome of this testcase.
Signed-off-by: Elijah Newren <redacted>
---
t/t4001-diff-rename.sh | 23 +++++++++++++++++++++++
1 file changed, 23 insertions(+)
@@ -262,4 +262,27 @@ test_expect_success 'diff-tree -l0 defaults to a big rename limit, not zero' 'grep"myotherfile.*myfile"actual'+test_expect_success'basename similarity vs best similarity''+mkdirsubdir&&+test_write_linesline1line2line3line4line5\+line6line7line8line9line10>subdir/file.txt&&+gitaddsubdir/file.txt&&+gitcommit-m"base txt"&&++gitrmsubdir/file.txt&&+test_write_linesline1line2line3line4line5\+line6line7line8>file.txt&&+test_write_linesline1line2line3line4line5\+line6line7line8line9>file.md&&+gitaddfile.txtfile.md&&+gitcommit-a-m"rename"&&+gitdiff-tree-r-M--name-statusHEAD^HEAD>actual&&+# subdir/file.txt is 88% similar to file.md and 78% similar to file.txt+cat>expected<<-\EOF&&+R088subdir/file.txtfile.md+Afile.txt+EOF+test_cmpexpectedactual+'+ test_done
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-14 07:54:01
From: Elijah Newren <redacted>
We want to make use of unique basenames among remaining source and
destination files to help inform rename detection, so that more likely
pairings can be checked first. (src/moduleA/foo.txt and
source/module/A/foo.txt are likely related if there are no other
'foo.txt' files among the remaining deleted and added files.) Add a new
function, not yet used, which creates a map of the unique basenames
within rename_src and another within rename_dst, together with the
indices within rename_src/rename_dst where those basenames show up.
Non-unique basenames still show up in the map, but have an invalid index
(-1).
This function was inspired by the fact that in real world repositories,
files are often moved across directories without changing names. Here
are some sample repositories and the percentage of their historical
renames (as of early 2020) that preserved basenames:
* linux: 76%
* gcc: 64%
* gecko: 79%
* webkit: 89%
These statistics alone don't prove that an optimization in this area
will help or how much it will help, since there are also unpaired adds
and deletes, restrictions on which basenames we consider, etc., but it
certainly motivated the idea to try something in this area.
Signed-off-by: Elijah Newren <redacted>
---
diffcore-rename.c | 63 +++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 63 insertions(+)
@@ -367,6 +367,69 @@ static int find_exact_renames(struct diff_options *options)returnrenames;}+staticconstchar*get_basename(constchar*filename)+{+/*+*gitbasename()hastoworryaboutspecialdrives,multiple+*directoryseparatorcharacters,trailingslashes,NULLor+*emptystrings,etc.Weonlyworkonfilenamesasstoredin+*git,andthusgettoignoreallthosecomplications.+*/+constchar*base=strrchr(filename,'/');+returnbase?base+1:filename;+}++MAYBE_UNUSED+staticintfind_basename_matches(structdiff_options*options,+intminimum_score)+{+inti;+structstrintmapsources;+structstrintmapdests;++/*+*Createmapsofbasename->fullname(s)forremainingsourcesand+*dests.+*/+strintmap_init_with_options(&sources,-1,NULL,0);+strintmap_init_with_options(&dests,-1,NULL,0);+for(i=0;i<rename_src_nr;++i){+char*filename=rename_src[i].p->one->path;+constchar*base;++/* exact renames removed in remove_unneeded_paths_from_src() */+assert(!rename_src[i].p->one->rename_used);++/* Record index within rename_src (i) if basename is unique */+base=get_basename(filename);+if(strintmap_contains(&sources,base))+strintmap_set(&sources,base,-1);+else+strintmap_set(&sources,base,i);+}+for(i=0;i<rename_dst_nr;++i){+char*filename=rename_dst[i].p->two->path;+constchar*base;++if(rename_dst[i].is_rename)+continue;/* involved in exact match already. */++/* Record index within rename_dst (i) if basename is unique */+base=get_basename(filename);+if(strintmap_contains(&dests,base))+strintmap_set(&dests,base,-1);+else+strintmap_set(&dests,base,i);+}++/* TODO: Make use of basenames source and destination basenames */++strintmap_clear(&sources);+strintmap_clear(&dests);++return0;+}+#define NUM_CANDIDATE_PER_DST 4staticvoidrecord_if_better(structdiff_scorem[],structdiff_score*o){
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-14 07:55:05
From: Elijah Newren <redacted>
Make use of the new find_basename_matches() function added in the last
two patches, to find renames more rapidly in cases where we can match up
files based on basenames. As a quick reminder (see the last two commit
messages for more details), this means for example that
docs/extensions.txt and docs/config/extensions.txt are considered likely
renames if there are no remaining 'extensions.txt' files elsewhere among
the added and deleted files, and if a similarity check confirms they are
similar, then they are marked as a rename without looking for a better
similarity match among other files. This is a behavioral change, as
covered in more detail in the previous commit message.
We do not use this heuristic together with either break or copy
detection. The point of break detection is to say that filename
similarity does not imply file content similarity, and we only want to
know about file content similarity. The point of copy detection is to
use more resources to check for additional similarities, while this is
an optimization that uses far less resources but which might also result
in finding slightly fewer similarities. So the idea behind this
optimization goes against both of those features, and will be turned off
for both.
For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
this change improves the performance as follows:
Before After
no-renames: 13.815 s ± 0.062 s 13.294 s ± 0.103 s
mega-renames: 1799.937 s ± 0.493 s 187.248 s ± 0.882 s
just-one-mega: 51.289 s ± 0.019 s 5.557 s ± 0.017 s
Signed-off-by: Elijah Newren <redacted>
---
diffcore-rename.c | 53 ++++++++++++++++++++++++++++++++++++++----
t/t4001-diff-rename.sh | 7 +++---
2 files changed, 52 insertions(+), 8 deletions(-)
@@ -716,11 +715,55 @@ void diffcore_rename(struct diff_options *options)if(minimum_score==MAX_SCORE)gotocleanup;-/* Calculate how many renames are left */-num_destinations=(rename_dst_nr-rename_count);-remove_unneeded_paths_from_src(want_copies);num_sources=rename_src_nr;+if(want_copies||break_idx){+/*+*Cullsources:+*-removeonescorrespondingtoexactrenames+*/+trace2_region_enter("diff","cull after exact",options->repo);+remove_unneeded_paths_from_src(want_copies);+trace2_region_leave("diff","cull after exact",options->repo);+}else{+/* Determine minimum score to match basenames */+doublefactor=0.5;+char*basename_factor=getenv("GIT_BASENAME_FACTOR");+intmin_basename_score;++if(basename_factor)+factor=strtol(basename_factor,NULL,10)/100.0;+assert(factor>=0.0&&factor<=1.0);+min_basename_score=minimum_score++(int)(factor*(MAX_SCORE-minimum_score));++/*+*Cullsources:+*-removeonesinvolvedinrenames(foundviaexactmatch)+*/+trace2_region_enter("diff","cull after exact",options->repo);+remove_unneeded_paths_from_src(want_copies);+trace2_region_leave("diff","cull after exact",options->repo);++/* Utilize file basenames to quickly find renames. */+trace2_region_enter("diff","basename matches",options->repo);+rename_count+=find_basename_matches(options,+min_basename_score);+trace2_region_leave("diff","basename matches",options->repo);++/*+*Cullsources,again:+*-removeonesinvolvedinrenames(foundviabasenames)+*/+trace2_region_enter("diff","cull basename",options->repo);+remove_unneeded_paths_from_src(want_copies);+trace2_region_leave("diff","cull basename",options->repo);+}++/* Calculate how many rename destinations are left */+num_destinations=(rename_dst_nr-rename_count);+num_sources=rename_src_nr;/* rename_src_nr reflects lower number */+/* All done? */if(!num_destinations||!num_sources)gotocleanup;
@@ -751,7 +794,7 @@ void diffcore_rename(struct diff_options *options)structdiff_score*m;if(rename_dst[i].is_rename)-continue;/* dealt with exact match already. */+continue;/* exact or basename match already handled */m=&mx[dst_cnt*NUM_CANDIDATE_PER_DST];for(j=0;j<NUM_CANDIDATE_PER_DST;j++)
@@ -277,10 +277,11 @@ test_expect_success 'basename similarity vs best similarity' 'gitaddfile.txtfile.md&&gitcommit-a-m"rename"&&gitdiff-tree-r-M--name-statusHEAD^HEAD>actual&&-# subdir/file.txt is 88% similar to file.md and 78% similar to file.txt+# subdir/file.txt is 88% similar to file.md, 78% similar to file.txt,+# but since same basenames are checked first...cat>expected<<-\EOF&&-R088subdir/file.txtfile.md-Afile.txt+Afile.md+R078subdir/file.txtfile.txtEOFtest_cmpexpectedactual'
From: Elijah Newren via GitGitGadget <hidden> Date: 2021-02-14 07:55:36
From: Elijah Newren <redacted>
We want to pass additional information to diffcore_rename() (or some
variant thereof) without plumbing that extra information through
diff_tree_oid() and diffcore_std(). Further, since we will need to
gather additional special information related to diffs and are walking
the trees anyway in collect_merge_info(), it seems odd to have
diff_tree_oid()/diffcore_std() repeat those tree walks. And there may
be times where we can avoid traversing into a subtree in
collect_merge_info() (based on additional information at our disposal),
that the basic diff logic would be unable to take advantage of. For all
these reasons, just create the add and delete pairs ourself and then
call diffcore_rename() directly.
This change is primarily about enabling future optimizations; the
advantage of avoiding extra tree traversals is small compared to the
cost of rename detection, and the advantage of avoiding the extra tree
traversals is somewhat offset by the extra time spent in
collect_merge_info() collecting the additional data anyway. However...
For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
this change improves the performance as follows:
Before After
no-renames: 13.294 s ± 0.103 s 12.775 s ± 0.062 s
mega-renames: 187.248 s ± 0.882 s 188.754 s ± 0.284 s
just-one-mega: 5.557 s ± 0.017 s 5.599 s ± 0.019 s
Signed-off-by: Elijah Newren <redacted>
---
merge-ort.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++------
1 file changed, 59 insertions(+), 7 deletions(-)
@@ -554,6 +572,21 @@ static void collect_rename_info(struct merge_options *opt,if(sides&2)strset_add(&renames->dirs_removed[2],fullname);}++if(filemask==0||filemask==7)+return;++for(side=MERGE_SIDE1;side<=MERGE_SIDE2;++side){+unsignedside_mask=(1<<side);++/* Check for deletion on side */+if((filemask&1)&&!(filemask&side_mask))+add_pair(opt,names,fullname,side,0/* delete */);++/* Check for addition on side */+if(!(filemask&1)&&(filemask&side_mask))+add_pair(opt,names,fullname,side,1/* add */);+}}staticintcollect_merge_info_callback(intn,
@@ -2089,8 +2143,6 @@ static int compare_pairs(const void *a_, const void *b_)/* Call diffcore_rename() to compute which files have changed on given side */staticvoiddetect_regular_renames(structmerge_options*opt,-structtree*merge_base,-structtree*side,unsignedside_index){structdiff_optionsdiff_opts;