forked from TrueCloudLab/frostfs-node
Evgenii Stratonikov
c0135f8a65
When we have N items, sorting then iterating provides `O(n log n)` latency
in the worst case scenario (flat bucket), because we must return items
from a level in the sorted order. Some heap implementations allow O(1)
insertion and O(log n) dequeue, this means that we can decrease the
latency for the first received operation to O(log n), albeit with a
slight increase in the total time.
Pairing heap was chosen as one of the most simplest implementations.
```
goos: linux
goarch: amd64
pkg: git.frostfs.info/TrueCloudLab/frostfs-node/pkg/services/tree
cpu: 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
│ old │ new │
│ sec/op │ sec/op vs base │
GetSubTree/latency-8 5.034m ± 23% 1.110m ± 22% -77.95% (p=0.000 n=10)
GetSubTree/total_time-8 81.03m ± 1% 95.02m ± 14% +17.26% (p=0.000 n=10)
geomean 20.20m 10.27m -49.15%
│ old │ new │
│ B/op │ B/op vs base │
GetSubTree/latency-8 32.14Mi ± 0% 37.49Mi ± 0% +16.63% (p=0.000 n=10)
GetSubTree/total_time-8 32.14Mi ± 0% 37.49Mi ± 0% +16.63% (p=0.000 n=10)
geomean 32.14Mi 37.49Mi +16.63%
│ old │ new │
│ allocs/op │ allocs/op vs base │
GetSubTree/latency-8 400.0k ± 0% 400.0k ± 0% +0.00% (p=0.000 n=10)
GetSubTree/total_time-8 400.0k ± 0% 400.0k ± 0% +0.00% (p=0.000 n=10)
geomean 400.0k 400.0k +0.00%
```
Signed-off-by: Evgenii Stratonikov <e.stratonikov@yadro.com>
|
||
|---|---|---|
| .. | ||
| core | ||
| innerring | ||
| local_object_storage | ||
| metrics | ||
| morph | ||
| network | ||
| services | ||
| util | ||