view contrib/clang-format-ignorelist @ 40918:3764330f76a6

sparse-revlog: enabled by default

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 |

Differential Revision: https://phab.mercurial-scm.org/D5345

# Files that just need to be migrated to the formatter.
# Do not add new files here!
mercurial/cext/dirs.c
mercurial/cext/manifest.c
mercurial/cext/osutil.c
# Vendored code that we should never format:
contrib/python-zstandard/c-ext/bufferutil.c
contrib/python-zstandard/c-ext/compressionchunker.c
contrib/python-zstandard/c-ext/compressiondict.c
contrib/python-zstandard/c-ext/compressionparams.c
contrib/python-zstandard/c-ext/compressionreader.c
contrib/python-zstandard/c-ext/compressionwriter.c
contrib/python-zstandard/c-ext/compressobj.c
contrib/python-zstandard/c-ext/compressor.c
contrib/python-zstandard/c-ext/compressoriterator.c
contrib/python-zstandard/c-ext/constants.c
contrib/python-zstandard/c-ext/decompressionreader.c
contrib/python-zstandard/c-ext/decompressionwriter.c
contrib/python-zstandard/c-ext/decompressobj.c
contrib/python-zstandard/c-ext/decompressor.c
contrib/python-zstandard/c-ext/decompressoriterator.c
contrib/python-zstandard/c-ext/frameparams.c
contrib/python-zstandard/c-ext/python-zstandard.h
contrib/python-zstandard/zstd.c
contrib/python-zstandard/zstd/common/bitstream.h
contrib/python-zstandard/zstd/common/compiler.h
contrib/python-zstandard/zstd/common/cpu.h
contrib/python-zstandard/zstd/common/debug.c
contrib/python-zstandard/zstd/common/debug.h
contrib/python-zstandard/zstd/common/entropy_common.c
contrib/python-zstandard/zstd/common/error_private.c
contrib/python-zstandard/zstd/common/error_private.h
contrib/python-zstandard/zstd/common/fse_decompress.c
contrib/python-zstandard/zstd/common/fse.h
contrib/python-zstandard/zstd/common/huf.h
contrib/python-zstandard/zstd/common/mem.h
contrib/python-zstandard/zstd/common/pool.c
contrib/python-zstandard/zstd/common/pool.h
contrib/python-zstandard/zstd/common/threading.c
contrib/python-zstandard/zstd/common/threading.h
contrib/python-zstandard/zstd/common/xxhash.c
contrib/python-zstandard/zstd/common/xxhash.h
contrib/python-zstandard/zstd/common/zstd_common.c
contrib/python-zstandard/zstd/common/zstd_errors.h
contrib/python-zstandard/zstd/common/zstd_internal.h
contrib/python-zstandard/zstd/compress/fse_compress.c
contrib/python-zstandard/zstd/compress/hist.c
contrib/python-zstandard/zstd/compress/hist.h
contrib/python-zstandard/zstd/compress/huf_compress.c
contrib/python-zstandard/zstd/compress/zstd_compress.c
contrib/python-zstandard/zstd/compress/zstd_compress_internal.h
contrib/python-zstandard/zstd/compress/zstd_double_fast.c
contrib/python-zstandard/zstd/compress/zstd_double_fast.h
contrib/python-zstandard/zstd/compress/zstd_fast.c
contrib/python-zstandard/zstd/compress/zstd_fast.h
contrib/python-zstandard/zstd/compress/zstd_lazy.c
contrib/python-zstandard/zstd/compress/zstd_lazy.h
contrib/python-zstandard/zstd/compress/zstd_ldm.c
contrib/python-zstandard/zstd/compress/zstd_ldm.h
contrib/python-zstandard/zstd/compress/zstdmt_compress.c
contrib/python-zstandard/zstd/compress/zstdmt_compress.h
contrib/python-zstandard/zstd/compress/zstd_opt.c
contrib/python-zstandard/zstd/compress/zstd_opt.h
contrib/python-zstandard/zstd/decompress/huf_decompress.c
contrib/python-zstandard/zstd/decompress/zstd_decompress.c
contrib/python-zstandard/zstd/deprecated/zbuff_common.c
contrib/python-zstandard/zstd/deprecated/zbuff_compress.c
contrib/python-zstandard/zstd/deprecated/zbuff_decompress.c
contrib/python-zstandard/zstd/deprecated/zbuff.h
contrib/python-zstandard/zstd/dictBuilder/cover.c
contrib/python-zstandard/zstd/dictBuilder/cover.h
contrib/python-zstandard/zstd/dictBuilder/divsufsort.c
contrib/python-zstandard/zstd/dictBuilder/divsufsort.h
contrib/python-zstandard/zstd/dictBuilder/fastcover.c
contrib/python-zstandard/zstd/dictBuilder/zdict.c
contrib/python-zstandard/zstd/dictBuilder/zdict.h
contrib/python-zstandard/zstd/zstd.h
hgext/fsmonitor/pywatchman/bser.c
mercurial/thirdparty/xdiff/xdiff.h
mercurial/thirdparty/xdiff/xdiffi.c
mercurial/thirdparty/xdiff/xdiffi.h
mercurial/thirdparty/xdiff/xemit.c
mercurial/thirdparty/xdiff/xemit.h
mercurial/thirdparty/xdiff/xhistogram.c
mercurial/thirdparty/xdiff/xinclude.h
mercurial/thirdparty/xdiff/xmacros.h
mercurial/thirdparty/xdiff/xmerge.c
mercurial/thirdparty/xdiff/xpatience.c
mercurial/thirdparty/xdiff/xprepare.c
mercurial/thirdparty/xdiff/xprepare.h
mercurial/thirdparty/xdiff/xtypes.h
mercurial/thirdparty/xdiff/xutils.c
mercurial/thirdparty/xdiff/xutils.h
mercurial/thirdparty/zope/interface/_zope_interface_coptimizations.c