]> source.dussan.org Git - jgit.git/commit
Introduce a PriorityQueue sorting RevCommits by commit timestamp 40/194140/36
authorLuca Milanesio <luca.milanesio@gmail.com>
Mon, 13 Jun 2022 22:09:55 +0000 (23:09 +0100)
committerMatthias Sohn <matthias.sohn@sap.com>
Fri, 19 Jan 2024 00:28:04 +0000 (01:28 +0100)
commitb4c66104fb7502f133989291a4a5595f965771d3
treece76680b90ddd2fa117bff7974c3009d4e118719
parent2d52df15465b85c5f90a0e2052bcf35ef9b58e39
Introduce a PriorityQueue sorting RevCommits by commit timestamp

The DateRevQueue uses a tailor-made algorithm to keep
RevCommits sorted by reversed commit timestamp, which has a O(n*n/2)
complexity and caused the explosion of the Git fetch times to
tens of seconds.

The standard Java PriorityQueue provides a O(n*log(n)) complexity
and scales much better with the increase of the number of
RevCommits.

Introduce a new implementation DateRevPriorityQueue of the DateRevQueue
based on PriorityQueue.

Enable usage of the new DateRevPriorityQueue implementation by setting
the system property REVWALK_USE_PRIORITY_QUEUE=true. By default the old
implementation DateRevQueue is used.

Benchmark results:
```
(numCommits)  (usePriorityQueue)  Mode  Cnt     Score Error  Units
           5                true  avgt   10    39,4 ±   6,1  ns/op
           5               false  avgt   10    14,1 ±   2,2  ns/op
          10                true  avgt   10    29,7 ±   3,5  ns/op
          10               false  avgt   10    13,2 ±   2,0  ns/op
          50                true  avgt   10    50,4 ±   5,3  ns/op
          50               false  avgt   10    18,6 ±   0,2  ns/op
         100                true  avgt   10    58,3 ±   5,0  ns/op
         100               false  avgt   10    20,5 ±   0,8  ns/op
         500                true  avgt   10    51,7 ±   2,6  ns/op
         500               false  avgt   10    43,3 ±   0,5  ns/op
        1000                true  avgt   10    49,2 ±   2,4  ns/op
        1000               false  avgt   10    62,7 ±   0,2  ns/op
        5000                true  avgt   10    48,8 ±   1,5  ns/op
        5000               false  avgt   10   228,3 ±   0,5  ns/op
       10000                true  avgt   10    44,2 ±   0,9  ns/op
       10000               false  avgt   10   377,6 ±   2,7  ns/op
       50000                true  avgt   10    50,3 ±   1,6  ns/op
       50000               false  avgt   10   637,0 ± 111,8  ns/op
      100000                true  avgt   10    61,8 ±   4,4  ns/op
      100000               false  avgt   10   965,1 ± 268,0  ns/op
      500000                true  avgt   10   127,2 ±   7,9  ns/op
      500000               false  avgt   10  9610,2 ± 184,8  ns/op
```

Memory allocation results:
```
Number of commits loaded: 850 000
Custom implementation: 378 245 120 Bytes
Priority queue implementation: 340 495 616 Bytes
```

Bug: 580137
Change-Id: I8b33df6e9ee88933098ecc81ce32bdb189715041
Signed-off-by: Luca Milanesio <luca.milanesio@gmail.com>
Documentation/config-options.md
org.eclipse.jgit.benchmarks/src/org/eclipse/jgit/revwalk/DateRevQueueBenchmark.java [new file with mode: 0644]
org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/DateRevPriorityQueueTest.java [new file with mode: 0644]
org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkCarryFlagsTest.java
org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevPriorityQueue.java [new file with mode: 0644]
org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevQueue.java
org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java