Licensing Concerns Regarding Three-Walk Topological Sorting Implementation

[flori-schwa]

I'm looking for feedback regarding potential licensing issues.

The discussion started by @fedejeanne in #243 outlines the performance problems we are facing when using the History View in EGit.
I have since then spent some time trying to improve the performance for repositories with large histories and ended up looking up how the C implementation of git performs topological sorting (https://github.com/git/git/tree/master/revision.c), where I've discovered the three-walk algorithm based on commit graph generation numbers.

As a prototype, I then transcribed this algorithm to java and integrated it into JGits Generator pipeline, by writing a new Generator, which completely replaces the existing chain of PendingGenerator->RewriteGenerator->TopoSortGenerator. This new Generator implemented the three-walk algorithm, applied the (Tree)RevFilter and performed commit history rewriting.
We have internally deployed this prototype for a while now and it has significantly improved the usability of the history view.

Other users and organisations with large repositories will most likely also profit from this algorithm. But since git's source code is licensed under a GPLv2 license (whereas JGit is licensed under a permissive BSD 3-Clause license), a simple transcription of the C code would probably be rejected by JGit, as per the README:

All portions of JGit are covered by the EDL. Absolutely no GPL, LGPL or EPL contributions are accepted within this package.

So I started re-implementing my prototype from scratch over the past few weeks, referencing my prototype occasionally when encountering performance problems or errors during commit rewriting.
The current version is available at https://github.com/vi-eclipse/jgit/tree/fschwabe/TopologicalRevWalk
The biggest differences are the adaption of the algorithm to work with JGits RevFilters and history rewriting as well as the separation of the monolithic prototype into multiple smaller components: ExplorePhase, InDegreePhase and the orchestrator ("TopoSortPendingGenerator")

I am happy to perform further refactoring (or attempt another clean-room re-implementation) if anyone has concerns with integrating this into JGit's codebase.

[fedejeanne]

Thank you for the clarification, @flori-schwa . To avoid confusion, can you please also explain what the other 2 commits in that branch are and if they are related to the three-walk algorithm? You already proposed to merge them, that's why I ask:

• https://eclipse.gerrithub.io/c/eclipse-jgit/jgit/+/1234062
• https://eclipse.gerrithub.io/c/eclipse-jgit/jgit/+/1234061

@msohn what is the normal procedure here? In the section Legal Paperwork, it only says that one needs to check for IP create a contribution questionnaire for review by the Eclipse IP team if the commit adds >1000 lines, which the 3rd commit (8e295a1) of https://github.com/vi-eclipse/jgit/tree/fschwabe/TopologicalRevWalk doesn't

With a valid ECA on file and the copyright and license header in place, we will be able to accept small patches (<1000 LoC) immediately. For larger patches, we will also have to create a contribution questionnaire for review by the Eclipse IP team, but this usually doesn't require additional actions from you.

Also, the algorithm that Florian used is described in the series of blog posts called Supercharging the Git Commit Graph by Derrick Stolee, Principal Software Engineer at Microsoft. This one explains the algorithm:

• https://devblogs.microsoft.com/devops/supercharging-the-git-commit-graph-iii-generations/

[flori-schwa]

The latest commit on the branch (the implementation of the three-walk algorithm) does not technically depend on the other two changes. But they (plus the patch below) are needed for testing the algorithm in EGit's history view:

diff --git a/org.eclipse.egit.ui/src/org/eclipse/egit/ui/internal/history/SWTCommit.java b/org.eclipse.egit.ui/src/org/eclipse/egit/ui/internal/history/SWTCommit.java
index c9dad2b..2663fbe 100644
--- a/org.eclipse.egit.ui/src/org/eclipse/egit/ui/internal/history/SWTCommit.java
+++ b/org.eclipse.egit.ui/src/org/eclipse/egit/ui/internal/history/SWTCommit.java
@@ -32,8 +32,8 @@ class SWTCommit extends PlotCommit<SWTCommitList.SWTLane>
 
 	private SWTWalk walk;
 
-	SWTCommit(final AnyObjectId id, SWTWalk walk) {
-		super(id);
+	SWTCommit(AnyObjectId id, SWTWalk walk, int graphPos) {
+		super(id, graphPos);
 		this.walk = walk;
 	}
 
diff --git a/org.eclipse.egit.ui/src/org/eclipse/egit/ui/internal/history/SWTWalk.java b/org.eclipse.egit.ui/src/org/eclipse/egit/ui/internal/history/SWTWalk.java
index 5113eac..c75e7b1 100644
--- a/org.eclipse.egit.ui/src/org/eclipse/egit/ui/internal/history/SWTWalk.java
+++ b/org.eclipse.egit.ui/src/org/eclipse/egit/ui/internal/history/SWTWalk.java
@@ -77,8 +77,8 @@ public Ref getHead() throws IOException {
 	}
 
 	@Override
-	protected RevCommit createCommit(final AnyObjectId id) {
-		return new SWTCommit(id, this);
+	protected RevCommit createCommit(AnyObjectId id, int graphPos) {
+		return new SWTCommit(id, this, graphPos);
 	}
 
 	private Ref determineHead() throws IOException {

[msohn]

Hi Florian, thanks for working on this 👍

I don't have concerns if you did the reimplementation from scratch and did it based on the published algorithm.
Please push it to GerritHub for code review.

The change seems rather large, maybe there's a way to split it into a series of smaller changes , e.g. if it contains refactorings which can be extracted into separate changes.

How will topo sorting be done if there is no commit-graph available or if the commit-graph is outdated ?

[flori-schwa]

Hi Matthias, thanks for the quick reply.

I could probably push the refactoring of RewriteGenerator as its own change to reduce the size.

Regarding topo-sorting without a commit graph: If there is no commit-graph available, all commits to be sorted will have the "effective" generation number COMMIT_GENERATION_UNKNOWN (Integer.MAX_VALUE). Since no commit will fail the if (candidate.getEffectiveGeneration() >= minGeneration) check in TopoPhase.tryRemove, the calculateInDegrees-Call in the initialize-Method of the TopoInDegreePhase will sort the complete history and fill the ready queue (similar to the current TopoSortGenerator)

If the commit-graph is outdated (i.e. the starting commits have an "effective" generation number of COMMIT_GENERATION_UNKNOWN), then only those commits will be sorted in the initialization. As soon as a commit, that is present in the graph is encountered, the if (candidate.getEffectiveGeneration() >= minGeneration) check fails and the sorting will continue, when commits are produced using the nextReady()-Method of the TopoInDegreePhase

[fedejeanne]

... so no performance gain but also no performance degradation, right @flori-schwa ?

It just occurs to me by reading Matthias' question: this information (the fact that the commit-graph needs to exist in order to see performance improvements) should be added to the commit message. We documented this internally so our colleagues knew it already, but the larger community needs to know it too.

[flori-schwa]

Correct, the performance without a commit-graph will be similar to the current TopoSortGenerator