sparse-revlog: implement algorithm to write sparse delta chains (
issue5480)
The classic behavior of revlog._isgooddeltainfo is to consider the span size
of the whole delta chain, and limit it to 4 * textlen.
Once sparse-revlog writing is allowed (and enforced with a requirement),
revlog._isgooddeltainfo considers the span of the largest chunk as the
distance used in the verification, instead of using the span of the whole
delta chain.
In order to compute the span of the largest chunk, we need to slice into
chunks a chain with the new revision at the top of the revlog, and take the
maximal span of these chunks. The sparse read density is a parameter to the
slicing, as it will stop when the global read density reaches this threshold.
For instance, a density of 50% means that 2 of 4 read bytes are actually used
for the reconstruction of the revision (the others are part of other chains).
This allows a new revision to be potentially stored with a diff against
another revision anywhere in the history, instead of forcing it in the last 4
* textlen. The result is a much better compression on repositories that have
many concurrent branches. Here are a comparison between using deltas from
current upstream (aggressive-merge-deltas on by default) and deltas from a
sparse-revlog
Comparison of `.hg/store/` size:
mercurial (6.74% merges):
before: 46,831,873 bytes
after: 46,795,992 bytes (no relevant change)
pypy (8.30% merges):
before: 333,524,651 bytes
after: 308,417,511 bytes -8%
netbeans (34.21% merges):
before: 1,141,847,554 bytes
after: 1,131,093,161 bytes -1%
mozilla-central (4.84% merges):
before: 2,344,248,850 bytes
after: 2,328,459,258 bytes -1%
large-private-repo-A (merge 19.73%)
before: 41,510,550,163 bytes
after: 8,121,763,428 bytes -80%
large-private-repo-B (23.77%)
before: 58,702,221,709 bytes
after: 8,351,588,828 bytes -76%
Comparison of `00manifest.d` size:
mercurial (6.74% merges):
before: 6,143,044 bytes
after: 6,107,163 bytes
pypy (8.30% merges):
before: 52,941,780 bytes
after: 27,834,082 bytes -48%
netbeans (34.21% merges):
before: 130,088,982 bytes
after: 119,337,636 bytes -10%
mozilla-central (4.84% merges):
before: 215,096,339 bytes
after: 199,496,863 bytes -8%
large-private-repo-A (merge 19.73%)
before: 33,725,285,081 bytes
after: 390,302,545 bytes -99%
large-private-repo-B (23.77%)
before: 49,457,701,645 bytes
after: 1,366,752,187 bytes -97%
The better delta chains provide a performance boost in relevant repositories:
pypy, bundling 1000 revisions:
before: 1.670s
after: 1.149s -31%
Unbundling got a bit slower. probably because the sparse algorithm is still
pure
python.
pypy, unbundling 1000 revisions:
before: 4.062s
after: 4.507s +10%
Performance of bundle/unbundle in repository with few concurrent branches (eg:
mercurial) are unaffected.
No significant differences have been noticed then timing `hg push` and `hg
pull` locally. More state timings are being gathered.
Same as for aggressive-merge-delta, better delta comes with longer delta
chains. Longer chains have a performance impact. For example. The length of
the chain needed to get the manifest of pypy's tip moves from 82 item to 1929
items. This moves the restore time from 3.88ms to 11.3ms.
Delta chain length is an independent issue that affects repository without
this changes. It will be dealt with independently.
No significant differences have been observed on repositories where
`sparse-revlog` have not much effect (mercurial, unity, netbeans). On pypy,
small differences have been observed on some operation affected by delta chain
building and retrieval.
pypy, perfmanifest
before: 0.006162s
after: 0.017899s +190%
pypy, commit:
before: 0.382
after: 0.376 -1%
pypy, status:
before: 0.157
after: 0.168 +7%
More comprehensive and stable timing comparisons are in progress.
# All revsets ever used with revsetbenchmarks.py script
#
# The goal of this file is to gather all revsets ever used for benchmarking
# revset's performance. It should be used to gather revsets that test a
# specific usecase or a specific implementation of revset predicates.
# If you are working on the smartset implementation itself, check
# 'base-revsets.txt'.
#
# Please update this file with any revsets you use for benchmarking a change so
# that future contributors can easily find and retest it when doing further
# modification. Feel free to highlight interesting variants if needed.
## Revset from this section are all extracted from changelog when this file was
# created. Feel free to dig and improve documentation.
# Used in revision da05fe01170b
(20000::) - (20000)
# Used in revision 95af98616aa7
parents(20000)
# Used in revision 186fd06283b4
(_intlist('20000\x0020001')) and merge()
# Used in revision 911f5a6579d1
p1(20000)
p2(10000)
# Used in revision b6dc3b79bb25
0::
# Used in revision faf4f63533ff
bookmark()
# Used in revision 22ba2c0825da
tip~25
# Used in revision 0cf46b8298fe
bisect(range)
# Used in revision 5b65429721d5
divergent()
# Used in revision 6261b9c549a2
file(COPYING)
# Used in revision 44f471102f3a
follow(COPYING)
# Used in revision 8040a44aab1c
origin(tip)
# Used in revision bbf4f3dfd700
rev(25)
# Used in revision a428db9ab61d
p1()
# Used in revision c1546d7400ef
min(0::)
# Used in revision 546fa6576815
author(lmoscovicz) or author(mpm)
author(mpm) or author(lmoscovicz)
# Used in revision 9bfe68357c01
public() and id("d82e2223f132")
# Used in revision ba89f7b542c9
rev(25)
# Used in revision eb763217152a
rev(210000)
# Used in revision 69524a05a7fa
10:100
parents(10):parents(100)
# Used in revision 6f1b8b3f12fd
100~5
parents(100)~5
(100~5)~5
# Used in revision 7a42e5d4c418
children(tip~100)
# Used in revision 7e8737e6ab08
100^1
parents(100)^1
(100^1)^1
# Used in revision 30e0dcd7c5ff
matching(100)
matching(parents(100))
# Used in revision aafeaba22826
0|1|2|3|4|5|6|7|8|9
# Used in revision 33c7a94d4dd0
tip:0
# Used in revision 7d369fae098e
(0:100000)
# Used in revision b333ca94403d
0 + 1 + 2 + ... + 200
0 + 1 + 2 + ... + 1000
sort(0 + 1 + 2 + ... + 200)
sort(0 + 1 + 2 + ... + 1000)
# Used in revision 7fbef7932af9
first(0 + 1 + 2 + ... + 1000)
# Used in revision ceaf04bb14ff
0:1000
# Used in revision 262e6ad93885
not public()
(tip~1000::) - public()
not public() and branch("default")
# Used in revision 15412bba5a68
0::tip
## all the revsets from this section have been taken from the former central file
# for revset's benchmarking, they are undocumented for this reason.
all()
draft()
::tip
draft() and ::tip
::tip and draft()
author(lmoscovicz)
author(mpm)
::p1(p1(tip))::
public()
:10000 and public()
:10000 and draft()
(not public() - obsolete())
# The one below is used by rebase
(children(ancestor(tip~5, tip)) and ::(tip~5))::
# those two `roots(...)` inputs are close to what phase movement use.
roots((tip~100::) - (tip~100::tip))
roots((0::) - (0::tip))
# more roots testing
roots(tip~100:)
roots(:42)
roots(not public())
roots((0:tip)::)
roots(0::tip)
42:68 and roots(42:tip)
# Used in revision f140d6207cca
roots(0:tip)
# test disjoint set with multiple roots
roots((:42) + (tip~42:))
# Testing the behavior of "head()" in various situations
head()
head() - public()
draft() and head()
head() and author("mpm")
# testing the mutable phases set
draft()
secret()
# test finding common ancestors
heads(commonancestors(last(head(), 2)))
heads(commonancestors(head()))