This is an archive of the discontinued Mercurial Phabricator instance.

sparse-revlog: enabled by default
ClosedPublic

Authored by lothiraldan on Nov 28 2018, 3:54 PM.

Details

Summary

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 774

pypy

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 889

Mozilla

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 381

Netbeans

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 308

Private 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 459

Effect 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 |

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

lothiraldan created this revision.Nov 28 2018, 3:54 PM
pulkit added a subscriber: pulkit.Nov 29 2018, 1:28 PM

Thanks for all the numbers and a detailed commit message \o/. Can you help finding answers to following extra questions?

  • What will be effect on existing repositories which don't convert to sparse revlog due to some reasons?
  • If enabled by default in 4.9, will a user who uses some old mercurial like 4.6 or 4.0 will be able to clone a repository created by hg-4.9?
  • Will a client who is non-sparse revlog enabled be able to interact with a server who is sparse revlog enabled?

I am not following the work closely so these questions.

It now seems mature enough to be enabled by default.

While I don't know much about revlog internals, I do see a lot of patches related to sparse revlog being pushed in this cycle which is great. The concern is that those patches are not yet a part of release. In other words, I am not feeling confident that it's much tested yet.

Irrespective of whether it become part of 4.9 or not, thanks for the awesome work on improving existing revlog storage.

In D5345#79390, @pulkit wrote:

Thanks for all the numbers and a detailed commit message \o/. Can you help finding answers to following extra questions?

  • What will be effect on existing repositories which don't convert to sparse revlog due to some reasons?

The default only affects the creation of new repositories. Nothing will change for existing repository.

  • If enabled by default in 4.9, will a user who uses some old mercurial like 4.6 or 4.0 will be able to clone a repository created by hg-4.9?

Sure, as for the previous changes (eg: general-delta), everything is fully compatible over the wire. Mercurial 1.9 could successfully pull and push from a 4.9 server using sparse-revlog.

  • Will a client who is non-sparse revlog enabled be able to interact with a server who is sparse revlog enabled?

Absolutely, same as for the previous requirements introduction.

I am not following the work closely so these questions.

It now seems mature enough to be enabled by default.

While I don't know much about revlog internals, I do see a lot of patches related to sparse revlog being pushed in this cycle which is great. The concern is that those patches are not yet a part of release. In other words, I am not feeling confident that it's much tested yet.

There is a chicken and eggs issue here. We won't get much more testing until it is turned on by default. We are doing it early in the cycle to increase the amount of time it will be tested. 4.9 is two months away, we can always revert the default before 4.9 if we are not confident enough.

In addition, the most radical changes happened in 4.8, we are just doing minor adjustment here.

Finally, we are backporting these patch to make sure they get tested on a large repository using sparse-revlog. So by the time 4.9 is released they would have run in production for a while.

Irrespective of whether it become part of 4.9 or not, thanks for the awesome work on improving existing revlog storage.

durin42 accepted this revision as: durin42.Dec 3 2018, 3:08 PM
durin42 added a subscriber: durin42.

I'm +1, but would like someone else to before I push.

indygreg accepted this revision.Dec 10 2018, 11:08 AM
indygreg added a subscriber: indygreg.

I'll be queuing this shortly.

I just posted on mercurial-devel about introducing a revlog feature flag in the revlog itself to denote the revlog as using sparse. I think this is more consistent with how existing functionality works and I'd prefer we introduce that flag before 4.9. There is a discussion to be had about backwards compatibility, however. We can do that on the mailing list thread, I suppose.

This revision is now accepted and ready to land.Dec 10 2018, 11:08 AM
This revision was automatically updated to reflect the committed changes.