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 |