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.

mercurial/revlogutils/deltas.py

@@ -618,8 +618,10 b' 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 b' 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,)

tests/test-sparse-revlog.t

@@ -77,7 +77,7 b' 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 b' 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%)