The feature provides large benefits. It now seems mature enough to be enabled
by default.
- It solves catastrophic issues regarding delta storage in revlog,
- It allows for shorter delta chain in all repositories, improving performances.
Running benchmark of a wide range of operation did not reveal problematic
impact. Performance gains are observed where expected.
The format is supported by Mercurial version 4.7. So it seems safe to enable
it by default now.
Here is a reminder of key numbers regarding this delta strategy effect on
repository size and performance.
Effect on Size:
For repositories with a lot of branches, sparse-revlog significantly improve
size, fixing limitation associated with the span of a delta chain. In
addition, sparse-revlog, deal well with limitations of the delta chain length.
For large repositories, this allows for a stiff reduction of the delta chain
without a problematic impact on the repository size. This delta chain length
improvement helps all repositories, not just the ones with many branches.
As a reminder, here are the default chain limits for each "format":
- no-sparse: none
- sparse: 1000
Mercurial
Manifest Size:
limit | none | 1000
------------|-------------|------------
no-sparse | 6 143 044 | 6 269 496
sparse | 5 798 796 | 5 827 025
Manifest Chain length data
limit || none || 1000
value || average | max || average | max
------------||---------|---------||---------|---------
no-sparse || 429 | 1 397 || 397 | 1 000
sparse || 326 | 1 290 || 313 | 1 000
Full Store Size
limit | none | 1000
------------|-------------|------------
no-sparse | 46 944 775 | 47 166 129
sparse | 46 622 445 | 46 723 774pypy
Manifest Size:
limit | none | 1000
------------|-------------|------------
no-sparse | 52 941 760 | 56 200 970
sparse | 26 348 229 | 27 384 133
Manifest Chain length data
limit || none || 1000
value || average | max || average | max
------------||---------|---------||---------|---------
no-sparse || 769 | 3 889 || 390 | 1 000
sparse || 1 223 | 3 846 || 495 | 1 000
Full Store Size
limit | none | 1000
------------|-------------|------------
no-sparse | 336 050 203 | 339 309 413
sparse | 338 673 985 | 339 709 889Mozilla
Manifest Size:
limit | none | 1000
------------|----------------|---------------
no-sparse | 215 096 339 | 1 708 853 525
sparse | 188 947 271 | 278 894 170
Manifest Chain length data
limit || none || 1000
value || average | max || average | max
------------||---------|---------||---------|--------
no-sparse || 20 454 | 59 562 || 491 | 1 000
sparse || 23 509 | 69 891 || 489 | 1 000
Full Store Size
limit | none | 1000
------------|----------------|---------------
no-sparse | 2 377 578 715 | 3 876 258 798
sparse | 2 441 677 137 | 2 535 997 381Netbeans
Manifest Size:
limit | none | 1000
------------|----------------|---------------
no-sparse | 130 088 982 | 741 590 565
sparse | 118 836 887 | 159 161 207
Manifest Chain length data
limit || none || 1000
value || average | max || average | max
------------||---------|---------||---------|---------
no-sparse || 19 321 | 61 397 || 510 | 1 000
sparse || 21 240 | 61 583 || 503 | 1 000
Full Store Size
limit | none | 1000
------------|----------------|---------------
no-sparse | 1 160 013 008 | 1 771 514 591
sparse | 1 164 959 988 | 1 205 284 308Private repo #1
Manifest Size:
limit | none | 1000
------------|-----------------|---------------
no-sparse | 33 725 285 081 | 33 724 834 190
sparse | 350 542 420 | 423 470 579
Manifest Chain length data
limit || none || 1000
value || average | max || average | max
------------||---------|---------||---------|---------
no-sparse || 282 | 8 885 || 113 | 1 000
snapshot || 3 655 | 8 951 || 530 | 1 000
Full Store Size
limit | none | 1000
------------|----------------|---------------
no-sparse | 41 544 149 652 | 41 543 698 761
sparse | 8 448 037 300 | 8 520 965 459Effect on speed:
Performances are strongly impacted by the delta chain length. Longer chain
results in slower revision restoration. For this reason, the 1000 chain limit
introduced by sparse-revlog helps repository with previously large chains a
lot. In our corpus, this means netbeans and mozilla-central who suffered
from unreasonable manifest delta chain length.
Another way sparse revlog helps, is by producing better delta's. For
repositories with many branches, the pathological patterns that resulted in
many sub-optimal deltas are gone. Smaller delta help with operations where
deltas are directly relevant, like bundle.
However, the sparse-revlog logic introduces some extra processing and a more
throughout testing of possible delta candidates. Adding an extra cost in some
cases. This cost is usually counterbalanced by the other performance gain.
However, for smaller repositories not affected by delta chain length issues or
branching related issues, this might make things a bit slower. However, these
are also repository where revlog performance is dwarfed by other costs.
Below are the summary of some timing from the performance test suite running
at http://perf.octobus.net/ for a handful of key commands and operation.
It is important to keep in mind that most of this command works on the tip
part of the repository. The non-sparse and sparse version produce different
delta chains and the tip revision can end up at an arbitrary point of these
chains. This will impact some performance number listed in this summary.
For the record: here is the delta chain length for the tip revision of
manifest log in the benchmarked repository:
| no-sparse | sparse | mercurial | 94 | 904 | pypy | 23 | 673 | netbeans | 4158 | 258 | mozilla | 63263 | 781 |
As you can see, the chain length for mercurial and pypy turn out to be
significantly longer. The netbeans and mozilla one get shorter because these
repositories benefit from the maximum chain length.
Timing for hg commit:
The time taken by hg commit does not varies significantly, no drawback for
using sparse here.
| no-sparse | sparse | mercurial | 68.1ms | 66.7ms | pypy | 95.0ms | 94.1ms | netbeans | 614.0ms | 611.0ms | mozilla | 1340.0ms | 1.320.0ms |
Check the final section for statistics on a wider array of write.
Timing for bundling 10 000 changesets
The repository that benefits from better delta see a good performance boost.
The other ones are not significantly affected.
| no-sparse | sparse | mercurial | 3.1s | 3.0s | pypy | 25.1s | 7.5s | netbeans | 24.2s | 17.0s | mozilla | 23.7s | 25.0s |
Timing for unbundling 1 000 changesets
Mercurial and mozilla are unaffected. The pypy repository benefit well from
the better delta.
However, the netbeans repository takes a visible hit. Digging that difference
reveals that it comes from the sparse-revlog bundle having to deal with a
snapshot that was re-encoded in the bundle. The slow path for adding new a revision
had to be triggered for it, slowing things down. The Sparse versions do not have
such snapshot to handle similar cases in the tested configuration.
| no-sparse | sparse | mercurial | 519ms | 502ms | pypy | 1.270ms | 886ms | netbeans | 1.370ms | 2.250ms | mozilla | 3.230ms | 3.210ms |
Netbeans benefits from the better deltas in other dimensions too. For
example, the produced bundle is significantly smaller:
- netbeans-no-sparse.hg: 2.3MB
- netbeans-sparse.hg: 1.9MB
Timing to restore the tip most manifest entry:
Nothing surprising here. The timing for mercurial and pypy are within a small
range where they won't affect performance much. In our tested case, they are
slower as they use a longer chain.
Timing for netbeans and mozilla improves a lot. Removing a significant amount
of time.
| no-sparse | sparse | mercurial | 1.09ms | 3.15ms | pypy | 4.11ms | 10.70ms | netbeans | 239.00ms | 112.00ms | mozilla | 688.00ms | 198.00ms |
Reading 100 revision in descending order:
We see the same kind of effect when reading the last 100 revisions. Large
boost for netbeans and mozilla, as they use much smaller delta chain.
Mercurial and pypy longer chain means slower reads, but nothing gets out of
control.
| no-sparse | sparse | mercurial | 0.089s | 0.268s | pypy | 0.259s | 0.698s | netbeans | 125.000s | 20.600s | mozilla | 23.000s | 11.400s |
Writing from full text: statistic for the last 30K revisions
This benchmark adds revisions to revlog from their full text. This is similar
to the work done during a commit, but for a large amount of revisions so that
we get a more relevant view.
We see better overall performances with sparse-revlog. The very worst case is
usually slower with sparse-revlog, but does not gets out of control. For the
vast majorities of the other writes, sparse-revlog is significantly faster for
larger repositories. This is reflected in the accumulated rewrite time for
netbeans and mozilla.
The notable exception is the pypy repository where things get slower. The
extra processing is not balanced by shorter delta chain. However, this is to
be seen as a blocking issue. First, the overall time spend dealing with revlog
for the repository pypy size is small compared to the other costs, so we get
slower on operations that matter less than for other larger repository.
Second, we still get nice size benefit from using sparse-revlog, smaller repo
size brings other usability and speed benefit (eg: bundle size).
max time | no-sparse | sparse |
mercurial | 0.010143s | 0.045280s |
pypy | 0.034924s | 0.243288s |
netbeans | 0.605371s | 2.130876s |
mozilla | 1.478342s | 3.424541s |
99% time | no-sparse | sparse |
mercurial | 0.003774s | 0.003758s |
pypy | 0.017387s | 0.025310s |
netbeans | 0.576913s | 0.271195s |
mozilla | 1.478342s | 0.449661s |
95% time | no-sparse | sparse |
mercurial | 0.002069s | 0.002120s |
pypy | 0.010141s | 0.014797s |
netbeans | 0.540202s | 0.258644s |
mozilla | 0.654830s | 0.243440s |
full time | no-sparse | sparse |
mercurial | 14.15s | 14.87s |
pypy | 90.50s | 137.12s |
netbeans | 6401.06s | 3411.14s |
mozilla | 3086.89s | 1991.97s |