]> source.dussan.org Git - jgit.git/commit
Optimize RevWalk.getMergedInto() 06/184806/6
authorkylezhao <kylezhao@tencent.com>
Tue, 31 Aug 2021 11:36:44 +0000 (19:36 +0800)
committerMatthias Sohn <matthias.sohn@sap.com>
Fri, 8 Oct 2021 10:05:47 +0000 (12:05 +0200)
commitc5b30547355327c1536593cc7c4213d4949f5024
treef80fbcac394ccce2d084afa5e175df5b7b3cb408
parentc0380e9cddb26bb9b983305ec0a8051664782ae8
Optimize RevWalk.getMergedInto()

Transitive Relation Definition:
On the DAG of commit history, if A can reach B, C can reach A, then C
can reach B.

Example:
As is shown in the graph below:

  1 - 2 - 3 - 4 (side)
            \
             5 -  6^ (master) - 7 (topic)

Find out which branches is 2 merged into:
After we calculated that master contains 2, we can mark 6 as TEMP_MARK
to avoid unwanted walks.
When we want to figure out if 2 is merge into the topic, the traversal
path would be [7, 6] instead of [7, 6, 5, 3, 2].

Test:
This change can significantly improve performance for tags.
On a copy of the Linux repository, the command 'git tag --contains
<commit>' had the following performance improvement:

commit      | Before   | After   | Rel %
47a44d27ca  | 29251ms  | 6687ms  | -77%
90327e7dff  | 21388ms  | 6256ms  | -70%
f85fac0efa  | 11150ms  | 7338ms  | -34%

The current version ignores tags, even though the tag is a type of
the ref.
Follow-up commits I'll fix it.

Change-Id: Ie6295ca4d16070499912af462239e679a97cce47
Signed-off-by: kylezhao <kylezhao@tencent.com>
Reviewed-by: Christian Halstrick <christian.halstrick@sap.com>
Reviewed-by: Martin Fick <mfick@codeaurora.org>
org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkUtilsReachableTest.java
org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java