commit b4c66104fb7502f133989291a4a5595f965771d3
author Luca Milanesio <luca.milanesio@gmail.com> Mon Jun 13 23:09:55 2022 +0100
committer Matthias Sohn <matthias.sohn@sap.com> Fri Jan 19 01:28:04 2024 +0100
tree ce76680b90ddd2fa117bff7974c3009d4e118719
parent 2d52df15465b85c5f90a0e2052bcf35ef9b58e39

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>