# HG changeset patch # User Boris Feld # Date 2018-09-07 15:17:29 # Node ID a33f394b2bfd90da4bffa69a6bad624f49fd2446 # Parent 4ca7a67c94c84c1141c18fab083fa60fd0639d1a snapshot: try intermediate snapshot against parents' base # Regarding The Series Started By This Changeset This is the first changesets of a group adjusting delta chain strategy to build a useful chain of intermediate snapshots. The series will introduce a full strategy to produce chains of multiple snapshots on top of which a "usual" delta chain will be built. That strategy will have multiple steps to maximize snapshot reuse, avoiding pathological cases and improving overall compression in very branchy repositories. An important property of sparse-revlog using such snapshot-chain is that they can use very short delta chain without problematic impact on the resulting compression. Shorter delta chains are important to achieve good performance. To make each step clear, we'll introduce them one by one. See the end of this series for full details. # Regarding This Changeset Before this change, if we cannot store the current revision as a delta against a "simple" candidate (p1, p2, prev), we created a new level-0 snapshot (also called full snapshot). As the first step, we introduce a simple strategy: try an intermediate level-1 snapshot against the chain base of the "current revision" parents. The "current revision" is the one we are currently trying to store in the revlog, triggering this search for a good delta base. The first item in the chain is always a level-0 snapshot. # Effect On The Test Repository We can already see the effect on the test-repository. Most of the snapshots have shifted from level 0 to level 1. The overall size has slightly decreased. (However, keep in mind that this repository only emulates real data) # Regarding Statistic The current series focuses on improving the chain built. Improving the performance of this logic will be done as a second step. Sparse-revlog is still experimental and disabled by default. We'll provide more statistic about resulting size and delta chain at the end of this series. diff --git a/mercurial/revlogutils/deltas.py b/mercurial/revlogutils/deltas.py --- a/mercurial/revlogutils/deltas.py +++ b/mercurial/revlogutils/deltas.py @@ -618,8 +618,10 @@ def _rawgroups(revlog, p1, p2, cachedelt The group order aims at providing fast or small candidates first. """ gdelta = revlog._generaldelta + sparse = revlog._sparserevlog curr = len(revlog) prev = curr - 1 + deltachain = lambda rev: revlog._deltachain(rev)[0] # First we try to reuse a the delta contained in the bundle. # (or from the source revlog) @@ -647,6 +649,14 @@ def _rawgroups(revlog, p1, p2, cachedelt # Test all parents (1 or 2), and keep the best candidate yield parents + if sparse and parents: + # See if we can use an existing snapshot in the parent chains to use as + # a base for a new intermediate-snapshot + bases = [] + for p in parents: + bases.append(deltachain(p)[0]) + yield tuple(sorted(bases)) + # other approach failed try against prev to hopefully save us a # fulltext. yield (prev,) diff --git a/tests/test-sparse-revlog.t b/tests/test-sparse-revlog.t --- a/tests/test-sparse-revlog.t +++ b/tests/test-sparse-revlog.t @@ -77,7 +77,7 @@ repeatedly while some of it changes rare $ f -s .hg/store/data/*.d - .hg/store/data/_s_p_a_r_s_e-_r_e_v_l_o_g-_t_e_s_t-_f_i_l_e.d: size=74365490 + .hg/store/data/_s_p_a_r_s_e-_r_e_v_l_o_g-_t_e_s_t-_f_i_l_e.d: size=72315280 $ hg debugrevlog * format : 1 flags : generaldelta @@ -89,33 +89,36 @@ repeatedly while some of it changes rare empty : 0 ( 0.00%) text : 0 (100.00%) delta : 0 (100.00%) - snapshot : 101 ( 2.02%) - lvl-0 : 101 ( 2.02%) - deltas : 4900 (97.98%) - revision size : 74365490 - snapshot : 20307865 (27.31%) - lvl-0 : 20307865 (27.31%) - deltas : 54057625 (72.69%) + snapshot : 145 ( 2.90%) + lvl-0 : 15 ( 0.30%) + lvl-1 : 130 ( 2.60%) + deltas : 4856 (97.10%) + revision size : 72315280 + snapshot : 18481085 (25.56%) + lvl-0 : 3016019 ( 4.17%) + lvl-1 : 15465066 (21.39%) + deltas : 53834195 (74.44%) chunks : 5001 0x78 (x) : 5001 (100.00%) - chunks size : 74365490 - 0x78 (x) : 74365490 (100.00%) + chunks size : 72315280 + 0x78 (x) : 72315280 (100.00%) - avg chain length : 23 + avg chain length : 18 max chain length : 45 - max chain reach : 11039464 + max chain reach : 32095083 compression ratio : 23 uncompressed data size (min/max/avg) : 346468 / 346472 / 346471 - full revision size (min/max/avg) : 200927 / 201202 / 201067 - inter-snapshot size (min/max/avg) : 0 / 0 / 0 - delta size (min/max/avg) : 10649 / 103898 / 11032 + full revision size (min/max/avg) : 200990 / 201151 / 201067 + inter-snapshot size (min/max/avg) : 37202 / 173034 / 118962 + level-1 (min/max/avg) : 37202 / 173034 / 118962 + delta size (min/max/avg) : 10649 / 104791 / 11086 - deltas against prev : 4231 (86.35%) - where prev = p1 : 4172 (98.61%) + deltas against prev : 4185 (86.18%) + where prev = p1 : 4139 (98.90%) where prev = p2 : 0 ( 0.00%) - other : 59 ( 1.39%) - deltas against p1 : 651 (13.29%) - deltas against p2 : 18 ( 0.37%) + other : 46 ( 1.10%) + deltas against p1 : 647 (13.32%) + deltas against p2 : 24 ( 0.49%) deltas against other : 0 ( 0.00%)