diff options
| author | Luca Milanesio <luca.milanesio@gmail.com> | 2022-06-13 23:09:55 +0100 |
|---|---|---|
| committer | Matthias Sohn <matthias.sohn@sap.com> | 2024-01-19 01:28:04 +0100 |
| commit | b4c66104fb7502f133989291a4a5595f965771d3 (patch) | |
| tree | ce76680b90ddd2fa117bff7974c3009d4e118719 /Documentation | |
| parent | 2d52df15465b85c5f90a0e2052bcf35ef9b58e39 (diff) | |
| download | jgit-b4c66104fb7502f133989291a4a5595f965771d3.tar.gz jgit-b4c66104fb7502f133989291a4a5595f965771d3.zip | |
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>
Diffstat (limited to 'Documentation')
| -rw-r--r-- | Documentation/config-options.md | 8 |
1 files changed, 7 insertions, 1 deletions
diff --git a/Documentation/config-options.md b/Documentation/config-options.md index 36b25c8e36..9075a5903d 100644 --- a/Documentation/config-options.md +++ b/Documentation/config-options.md @@ -123,4 +123,10 @@ Proxy configuration uses the standard Java mechanisms via class `java.net.ProxyS | option | default | git option | description | |---------|---------|------------|-------------| -| `repack.packKeptObjects` | `true` when `pack.buildBitmaps` is set, `false` otherwise | ✅ | Include objects in packs locked by a `.keep` file when repacking. |
\ No newline at end of file +| `repack.packKeptObjects` | `true` when `pack.buildBitmaps` is set, `false` otherwise | ✅ | Include objects in packs locked by a `.keep` file when repacking. | + +## Java System Properties + +| system property | default | description | +|-----------------|---------|-------------| +| `REVWALK_USE_PRIORITY_QUEUE` | `false` | If set to `true` `RevWalk` uses `DateRevPriorityQueue` which is faster, otherwise it uses the old `DateRevQueue`. | |