changeset 39509:a33f394b2bfd

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.
author Boris Feld <boris.feld@octobus.net>
date Fri, 07 Sep 2018 11:17:29 -0400
parents 4ca7a67c94c8
children 3ca144f1c8dd
files mercurial/revlogutils/deltas.py tests/test-sparse-revlog.t
diffstat 2 files changed, 33 insertions(+), 20 deletions(-) [+]
line wrap: on
line diff
--- a/mercurial/revlogutils/deltas.py	Mon Sep 10 09:08:24 2018 -0700
+++ b/mercurial/revlogutils/deltas.py	Fri Sep 07 11:17:29 2018 -0400
@@ -618,8 +618,10 @@
     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 @@
             # 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,)
--- a/tests/test-sparse-revlog.t	Mon Sep 10 09:08:24 2018 -0700
+++ b/tests/test-sparse-revlog.t	Fri Sep 07 11:17:29 2018 -0400
@@ -77,7 +77,7 @@
   
 
   $ 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 @@
       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%)