Skip to content
Snippets Groups Projects
  1. Sep 11, 2018
  2. Aug 21, 2018
    • Pulkit Goyal's avatar
      sparse: add local files to temporaryfiles if they exist out of sparse · 9db856446298
      Pulkit Goyal authored
      We get the f1 from args if it's merge and check that whether that exists in
      sparse checkout or not. If that does not, we add that for merging.
      
      The error comes from very low-level where we try to read data of a
      working-filectx which does not exists in the working directory. It will be
      extremely ugly to plug in logic to update sparse copy with new file at such a
      low level.
      
      We already have logic related to updating the checkout with required files in
      calculateupdates() and let's handle this case there only. calculateupdates()
      call sparse.filterupdatesactions() and the logic is added into the latter
      function.
      
      To get the exact traceback, this patch can be backed out and
      test-sparse-merges.t can be run with ui.traceback=True.
      
      Differential Revision: https://phab.mercurial-scm.org/D4341
      9db856446298
    • Pulkit Goyal's avatar
      tests: show that merging with sparse is broken when rename is involved · c6eb2118f44f
      Pulkit Goyal authored
      This patch adds test to show that merging with sparse is broken when you have a
      rename on one side and just modification on another side.
      
      Differential Revision: https://phab.mercurial-scm.org/D4340
      c6eb2118f44f
  3. Aug 25, 2018
  4. Sep 10, 2018
    • Pulkit Goyal's avatar
      narrow: build the known set of nodes only when ellipses is enabled · 294c571490f0
      Pulkit Goyal authored
      We don't need to build the known set in non-ellipses case because we don't have
      a shallow repo. In this patch, this checks whether the server has ellipses
      enabled or not using the server capability and then build the known set of
      nodes.
      
      Building the known set of nodes can take ~3-4 minutes on repositories with
      millions of csets so this patch speeds up extending a non-shallow narrow clone
      on large repositories.
      
      In future, we should first check whether local repository is an ellipses repo
      using a new ellipses repo requirement and then control all the combinations
      between local repo requirement and server capability.
      
      Differential Revision: https://phab.mercurial-scm.org/D4520
      294c571490f0
    • Pulkit Goyal's avatar
      narrow: add narrow and ellipses as server capabilities · c90514043eaa
      Pulkit Goyal authored
      Right now we don't have a way to differentiate between whether a server can
      serve ellipsis or not. The way we check whether a server is narrow enabled is by
      checking bundle2 capability which does not scale outside of bundle2 world.
      
      The goal is to use have wireprotocol commands just like remotefilelog for
      widening the narrow clone, atleast in non-ellipses cases. Having a server
      capability will help there as we can't rely on bundle2 capability there.
      
      Also having a server capability is neat than having a bundle2 capability.
      
      There are lot of things we can optimize locally on the client side by knowing
      before hand that whether the server supports ellipses or not.
      
      This will also help us in making sure that a client ellipses repo does not
      communicate with a server repo without ellipses.
      
      Differential Revision: https://phab.mercurial-scm.org/D4521
      c90514043eaa
  5. Aug 24, 2018
    • Kyle Lippincott's avatar
      treemanifest: use visitchildrenset when doing a walk · 3ba9ef0fb693
      Kyle Lippincott authored
      For this series, starting at 'introduce lazy loading of subdirs' and ending with
      this commit, we get the following timing numbers, using roughly the same
      methodology and setup that we did in an earlier commit.
      
      "before" is 6268fed317d0.
      
          diff --git:
          repo  | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
          ------+---+---+------------------------+-----------------------+------------
          m-u   |   |   | 1.585 s +-  0.034 s    | 1.574 s +-  0.045 s   |  99.3%
          m-u   |   | x | 1.591 s +-  0.024 s    | 1.601 s +-  0.034 s   | 100.6%
          m-u   | x |   | 1.579 s +-  0.032 s    | 1.603 s +-  0.029 s   | 101.5%
          m-u   | x | x | 109.8 ms +-   2.1 ms   | 108.8 ms +-   2.2 ms  |  99.1%
          l-d-r |   |   | 234.6 ms +-   5.1 ms   | 240.1 ms +-   7.9 ms  | 102.3%
          l-d-r |   | x | 238.3 ms +-   8.1 ms   | 232.2 ms +-   6.3 ms  |  97.4%
          l-d-r | x |   | 120.0 ms +-   2.7 ms   | 119.6 ms +-   2.1 ms  |  99.7%
          l-d-r | x | x | 120.2 ms +-   1.6 ms   | 119.1 ms +-   1.6 ms  |  99.1%
      
          diff -c . --git:
          repo  | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
          ------+---+---+------------------------+-----------------------+------------
          m-u   |   |   | 356.9 ms +-   5.6 ms   | 355.9 ms +-   5.6 ms  |  99.7%
          m-u   |   | x | 209.1 ms +-   3.3 ms   | 205.8 ms +-   2.6 ms  |  98.4%
          m-u   | x |   | 418.3 ms +-  14.0 ms   | 350.8 ms +-   7.7 ms  |  83.9% <--
          m-u   | x | x | 168.3 ms +-   1.5 ms   | 168.1 ms +-   2.7 ms  |  99.9%
          l-d-r |   |   | 100.5 ms +-   2.1 ms   | 99.1 ms +-   1.6 ms   |  98.6%
          l-d-r |   | x | 5.672 s +-  0.133 s    | 4.335 s +-  0.051 s   |  76.4% <--
          l-d-r | x |   | 102.8 ms +-   2.8 ms   | 100.4 ms +-   1.7 ms  |  97.7%
          l-d-r | x | x | 1.025 s +-  0.028 s    | 875.9 ms +-  12.1 ms  |  85.5% <--
      
          rebase -r . --keep -d .^^:
          repo  | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
          ------+---+---+------------------------+-----------------------+------------
          m-u   |   |   | 6.654 s +-  0.137 s    | 6.718 s +-  0.046 s   | 101.0%
          m-u   |   | x | 6.672 s +-  0.104 s    | 6.716 s +-  0.143 s   | 100.7%
          m-u   | x |   | 6.661 s +-  0.072 s    | 6.658 s +-  0.066 s   | 100.0%
          m-u   | x | x | 696.0 ms +-  49.0 ms   | 696.2 ms +-  54.8 ms  | 100.0%
          l-d-r |   |   | 789.1 ms +-  12.5 ms   | 793.5 ms +-  17.3 ms  | 100.6%
          l-d-r |   | x | 7.621 s +-  0.194 s    | 7.144 s +-  0.116 s   |  93.7% <--
          l-d-r | x |   | 335.4 ms +-   9.7 ms   | 339.6 ms +-  10.8 ms  | 101.3%
          l-d-r | x | x | 6.315 s +-  0.085 s    | 5.633 s +-  0.105 s   |  89.2% <--
      
          status --change . --copies:
          repo  | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
          ------+---+---+------------------------+-----------------------+------------
          m-u   |   |   | 331.2 ms +-   7.0 ms   | 335.1 ms +-   6.5 ms  | 101.2%
          m-u   |   | x | 184.0 ms +-   3.8 ms   | 183.1 ms +-   3.4 ms  |  99.5%
          m-u   | x |   | 330.5 ms +-   7.2 ms   | 332.7 ms +-   6.9 ms  | 100.7%
          m-u   | x | x | 148.7 ms +-   3.5 ms   | 147.5 ms +-   2.2 ms  |  99.2%
          l-d-r |   |   | 97.3 ms +-   1.3 ms    | 98.2 ms +-   2.5 ms   | 100.9%
          l-d-r |   | x | 5.196 s +-  0.030 s    | 4.281 s +-  0.025 s   |  82.4% <--
          l-d-r | x |   | 101.4 ms +-   3.1 ms   | 100.9 ms +-   1.8 ms  |  99.5%
          l-d-r | x | x | 1.015 s +-  0.018 s    | 861.2 ms +-  11.2 ms  |  84.8% <--
      
          status --copies:
          repo  | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
          ------+---+---+------------------------+-----------------------+------------
          m-u   |   |   | 2.356 s +-  0.032 s    | 2.369 s +-  0.027 s   | 100.6%
          m-u   |   | x | 2.371 s +-  0.041 s    | 2.385 s +-  0.028 s   | 100.6%
          m-u   | x |   | 2.366 s +-  0.036 s    | 2.379 s +-  0.030 s   | 100.5%
          m-u   | x | x | 121.8 ms +-   3.8 ms   | 121.1 ms +-   2.7 ms  |  99.4%
          l-d-r |   |   | 726.2 ms +-  12.9 ms   | 723.1 ms +-  12.7 ms  |  99.6%
          l-d-r |   | x | 738.7 ms +-  11.2 ms   | 741.3 ms +-  11.1 ms  | 100.4%
          l-d-r | x |   | 215.9 ms +-   3.6 ms   | 214.7 ms +-   5.9 ms  |  99.4%
          l-d-r | x | x | 213.1 ms +-   2.5 ms   | 212.8 ms +-   4.5 ms  |  99.9%
      
          update $rev^; ~/src/hg/hg{hg}/hg update $rev:
          repo  | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
          ------+---+---+------------------------+-----------------------+------------
          m-u   |   |   | 3.922 s +-  0.045 s    | 3.937 s +-  0.034 s   | 100.4%
          m-u   |   | x | 3.673 s +-  0.028 s    | 3.660 s +-  0.035 s   |  99.6%
          m-u   | x |   | 3.959 s +-  0.073 s    | 3.904 s +-  0.051 s   |  98.6%
          m-u   | x | x | 417.0 ms +-  13.0 ms   | 406.2 ms +-   6.5 ms  |  97.4%
          l-d-r |   |   | 534.3 ms +-  12.2 ms   | 537.9 ms +-   8.8 ms  | 100.7%
          l-d-r |   | x | 10.671 s +-  0.275 s   | 10.111 s +-  0.114 s  |  94.8% <--
          l-d-r | x |   | 309.7 ms +-   3.5 ms   | 307.9 ms +-   4.0 ms  |  99.4%
          l-d-r | x | x | 1.837 s +-  0.014 s    | 1.887 s +-  0.035 s   | 102.7%
      
      Differential Revision: https://phab.mercurial-scm.org/D4371
      3ba9ef0fb693
  6. Aug 23, 2018
  7. Sep 11, 2018
  8. May 29, 2018
  9. Aug 23, 2018
  10. Aug 16, 2018
    • Kyle Lippincott's avatar
      treemanifest: introduce lazy loading of subdirs · 93486cc46125
      Kyle Lippincott authored
      An earlier patch series made it so that what to load was up to the calling code,
      which works fine until manifests are copied - when they're copied, they're
      loaded completely and thus we lose the entire benefit.
      
      By lazy loading everything, we can avoid having to pass in the matcher to ~every
      manifest function, and handle copies correctly as well. This changeset doesn't
      go as far as it could with loading only the necessary subsets, that will happen
      in later changes in this series; at the moment, except in a few situations, we
      just load everything the moment we want to interact with treemanifest._dirs.
      This is thus most likely to be a small slowdown if treemanifests is in use
      regardless of whether narrow is in use, but hopefully easier to verify
      correctness and review.
      
      This is part of a series of speedups, it is not expected to produce any real speed
      improvements itself, but the numbers show that it doesn't produce a large speed
      penalty in any common case, and for the cases it does provide a penalty in, it
      is not a large absolute amount (even if it is a large percentage amount).
      
      Timing numbers according to command:
      
          hyperfine --prepare <preparation_script> 'hg status'
      
      HGRCPATH points to a file with the following contents:
      
          [extensions]
          narrow =
          strip =
          rebase =
      
      mozilla-unified (called m-u below) was at revision #468856.
              regular hash: eb39298e432d
        treemanifests hash: 0553b7f29eaf
      
      large-dir-repo (called l-d-r below) was generated with the following script:
      
          #!/bin/bash
          hg init large-dir-repo
          mkdir -p large-dir-repo/third_party/rust/log
          touch large-dir-repo/third_party/rust/log/foo.txt
          for i in $(seq 1 30000); do
              d=$(mktemp -d large-dir-repo/third_party/XXXXXXXXX)
              touch $d/file.txt
          done
          hg -R large-dir-repo ci -Am 'rev0' --user test --date '0 0'
          echo hi > large-dir-repo/third_party/rust/log/bar.txt
          hg -R large-dir-repo ci -Am 'rev1' --user test --date '0 0'
          echo hi > large-dir-repo/third_party/rust/log/baz.txt
          hg -R large-dir-repo ci -Am 'rev2' --user test --date '0 0'
      
      for the repos that use narrow, the narrowspec was this:
      
          [include]
          rootfilesin:accessible/jsat
          rootfilesin:accessible/tests/mochitest/jsat
          rootfilesin:mobile/android/chrome/content
          rootfilesin:mobile/android/modules/geckoview
          rootfilesin:third_party/rust/log
          [exclude]
      
      This narrowspec was chosen due to the size of the third_party/rust directory
      (this directory was *not* modified in revision #468856 in mozilla-unified),
      plus all the directories that *were* modified in revision #468856 of
      mozilla-unified.
      
      Importantly, when using narrow, these repos had everything checked out (in the
      case of large-dir-repo, that means all 30,001 directories), *before* adding the
      narrowspec. This is to simulate the behavior when using a virtual filesystem
      that shows everything for the user even if they haven't added it to the
      narrowspec yet. This is not a supported configuration, and `hg update` and `hg
      rebase` will not really do the "correct" thing if there are mutations outside
      of the narrowspec (which is not the case in these tests, due to a carefully
      crafted narrowspec), but non-mutating commands should behave correctly.
      
      I'm not claiming anything less than a 5% speed win as improvements due to this
      change; these are probably eiter measurement artifacts or constant time
      improvements. The numbers that aren't changing are shown primarily to prove that
      this doesn't make anything worse in any case I plan on testing during this
      series.
      
      'before' is hg from commit 6268fed317d0
      'N' indicates narrow in use
      'T' indicates treemanifest in use
      
      Please note that these commands and the narrowspec are a little different than
      the ones in a similar table that I made in a3cabe9415e1.
      
      Important: it is my understanding that these numbers below are *not super reliable*,
      the large slowdowns may be artifacts of some odd interaction between GC and
      python module/code complexity. Another changeset of mine (D4351) had shown large
      timing differences when ~empty, uncalled functions were added to match.py,
      though only when using --color=never or redirecting to /dev/null. We seem to be
      on some cusp of complexity or code size that is causing, at my best guess
      (according to linux `perf` benchmarks) GC to alter behavior and cause a
      200-400ms difference in timings. I haven't had a chance to replicate these
      results on another machine.
      
          diff --git:
          repo  | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
          ------+---+---+------------------------+-----------------------+------------
          m-u   |   |   | 1.580 s +-  0.034 s    | 1.576 s +-  0.022 s   |  99.7%
          m-u   |   | x | 1.568 s +-  0.025 s    | 1.584 s +-  0.044 s   | 101.0%
          m-u   | x |   | 1.569 s +-  0.031 s    | 1.554 s +-  0.025 s   |  99.0%
          m-u   | x | x | 107.3 ms +-   1.6 ms   | 106.3 ms +-   1.5 ms  |  99.1%
          l-d-r |   |   | 232.5 ms +-   5.9 ms   | 233.5 ms +-   5.3 ms  | 100.4%
          l-d-r |   | x | 236.6 ms +-   6.3 ms   | 233.6 ms +-   7.0 ms  |  98.7%
          l-d-r | x |   | 118.4 ms +-   2.1 ms   | 118.4 ms +-   1.4 ms  | 100.0%
          l-d-r | x | x | 116.8 ms +-   1.5 ms   | 118.9 ms +-   1.6 ms  | 101.8%
      
          diff -c . --git:
          repo  | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
          ------+---+---+------------------------+-----------------------+------------
          m-u   |   |   | 354.4 ms +-  16.6 ms   | 351.0 ms +-   6.9 ms  |  99.0%
          m-u   |   | x | 207.2 ms +-   3.0 ms   | 206.2 ms +-   2.7 ms  |  99.5%
          m-u   | x |   | 422.0 ms +-  26.0 ms   | 351.2 ms +-   6.4 ms  |  83.2% <--
          m-u   | x | x | 166.7 ms +-   2.1 ms   | 169.5 ms +-   4.1 ms  | 101.7%
          l-d-r |   |   | 98.4 ms +-   4.5 ms    | 98.5 ms +-   2.1 ms   | 100.1%
          l-d-r |   | x | 5.519 s +-  0.060 s    | 5.149 s +-  0.042 s   |  93.3% <--
          l-d-r | x |   | 99.1 ms +-   3.2 ms    | 102.6 ms +-   9.7 ms  | 103.5% <--?
          l-d-r | x | x | 994.9 ms +-  10.7 ms   | 1.026 s +-  0.012 s   | 103.1% <--?
      
          rebase -r . --keep -d .^^:
          repo  | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
          ------+---+---+------------------------+-----------------------+------------
          m-u   |   |   | 6.639 s +-  0.168 s    | 6.559 s +-  0.097 s   |  98.8%
          m-u   |   | x | 6.601 s +-  0.143 s    | 6.640 s +-  0.207 s   | 100.6%
          m-u   | x |   | 6.582 s +-  0.098 s    | 6.543 s +-  0.098 s   |  99.4%
          m-u   | x | x | 678.4 ms +-  57.7 ms   | 703.7 ms +-  52.4 ms  | 103.7% <--?
          l-d-r |   |   | 780.0 ms +-  23.9 ms   | 776.0 ms +-  12.6 ms  |  99.5%
          l-d-r |   | x | 7.520 s +-  0.255 s    | 7.395 s +-  0.044 s   |  98.3%
          l-d-r | x |   | 331.9 ms +-  16.5 ms   | 327.0 ms +-   3.4 ms  |  98.5%
          l-d-r | x | x | 6.228 s +-  0.113 s    | 5.924 s +-  0.044 s   |  95.1%
      
          status --change . --copies:
          repo  | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
          ------+---+---+------------------------+-----------------------+------------
          m-u   |   |   | 330.8 ms +-   7.2 ms   | 329.0 ms +-   7.1 ms  |  99.5%
          m-u   |   | x | 182.9 ms +-   2.7 ms   | 183.5 ms +-   2.7 ms  | 100.3%
          m-u   | x |   | 330.0 ms +-   7.6 ms   | 327.1 ms +-   5.4 ms  |  99.1%
          m-u   | x | x | 146.2 ms +-   2.4 ms   | 147.1 ms +-   1.3 ms  | 100.6%
          l-d-r |   |   | 95.3 ms +-   1.4 ms    | 95.9 ms +-   1.5 ms   | 100.6%
          l-d-r |   | x | 5.157 s +-  0.035 s    | 5.166 s +-  0.058 s   | 100.2%
          l-d-r | x |   | 99.7 ms +-   3.0 ms    | 100.2 ms +-   4.4 ms  | 100.5%
          l-d-r | x | x | 993.6 ms +-  13.1 ms   | 1.025 s +-  0.015 s   | 103.2% <--?
      
          status --copies:
          repo  | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
          ------+---+---+------------------------+-----------------------+------------
          m-u   |   |   | 2.348 s +-  0.031 s    | 2.329 s +-  0.019 s   |  99.2%
          m-u   |   | x | 2.337 s +-  0.026 s    | 2.346 s +-  0.034 s   | 100.4%
          m-u   | x |   | 2.354 s +-  0.015 s    | 2.342 s +-  0.021 s   |  99.5%
          m-u   | x | x | 120.6 ms +-   4.3 ms   | 119.2 ms +-   2.1 ms  |  98.8%
          l-d-r |   |   | 731.5 ms +-  11.1 ms   | 719.6 ms +-   9.8 ms  |  98.4%
          l-d-r |   | x | 729.0 ms +-  15.5 ms   | 725.7 ms +-  10.6 ms  |  99.5%
          l-d-r | x |   | 211.0 ms +-   3.9 ms   | 212.8 ms +-   3.7 ms  | 100.9%
          l-d-r | x | x | 211.5 ms +-   4.2 ms   | 211.0 ms +-   3.3 ms  |  99.8%
      
          update $rev^; ~/src/hg/hg{hg}/hg update $rev:
          repo  | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
          ------+---+---+------------------------+-----------------------+------------
          m-u   |   |   | 3.910 s +-  0.055 s    | 3.920 s +-  0.075 s   | 100.3%
          m-u   |   | x | 3.613 s +-  0.056 s    | 3.630 s +-  0.056 s   | 100.5%
          m-u   | x |   | 3.873 s +-  0.055 s    | 3.864 s +-  0.049 s   |  99.8%
          m-u   | x | x | 400.4 ms +-   7.4 ms   | 403.6 ms +-   5.0 ms  | 100.8%
          l-d-r |   |   | 531.6 ms +-  10.0 ms   | 528.8 ms +-   9.6 ms  |  99.5%
          l-d-r |   | x | 10.377 s +-  0.049 s   | 9.955 s +-  0.046 s   |  95.9%
          l-d-r | x |   | 308.3 ms +-   4.4 ms   | 306.8 ms +-   3.7 ms  |  99.5%
          l-d-r | x | x | 1.805 s +-  0.015 s    | 1.834 s +-  0.020 s   | 101.6%
      
      Differential Revision: https://phab.mercurial-scm.org/D4366
      93486cc46125
  11. Sep 07, 2018
  12. Sep 06, 2018
  13. Sep 07, 2018
  14. Sep 06, 2018
  15. Sep 11, 2018
  16. Sep 07, 2018
    • Boris Feld's avatar
      sparse-revlog: set max delta chain length to on thousand · b66ea3fc3a86
      Boris Feld authored
      The new snapshot system used in the sparse-revlog case gave us some small size
      benefit so far. However its most important property is to gracefully handle
      harder limit on delta chainlength.
      
      Long delta chain has a very detrimental impact on read (and write) performance
      in revlog. Being able to shorter them provide a great boost. However, shorting
      delta used to result significantly lower compression ratio. The intermediate
      snapshots effectively suppress most of this effect (even all in some case).
      
      # Effect on the test repository
      
      The repository we use for test is not "realistic" but can still show this in
      action using an unreasonably low chain limit. Limiting the chain length show a
      sizeable increase but stay under control: +6% for limit=15; +15% for limit=10.
      Without the snapshot system the increase is significantly bigger: +45% for
      limit=15; +80% for limit=10. Even slightly larger than without delta chain
      limit, the resulting size is still smaller than before we started doing
      snapshots.
      
      Here is a table for comparison. *Since the repository is not branchy, the
      initial sparse-revlog version does not bring much benefit compare to the
      non-sparse one):
      
             chain length limit |     none   |   limit=15  |   limit=10  |
          without sparse-revlog | 62 818 987 | 112 664 615 | 131 222 574 |
          without snapshot      | 74 365 490 | 108 211 410 | 133 857 764 |
          with    snapshot      | 59 230 936 |  63 002 924 |  68 415 329 |
      
      
      # Effect On Real Life Repositories
      
      The series provides significant benefits on all kind of repositories.
      
      Using `hg debugupgraderepo -o redeltaparent --run`, we recomputed delta chain
      for various repositories with different settings:
        - delta chain length: unlimited or 1000 limit
        - sparse-revlog:      enabled or disabled
        - this series:        applied or not applied
      
      We can observe multiple types of effect:
      
       - On very branchy repositories:
         * The delta chain limit as low impact on the repo size.
         * Intermediate snapshot greatly reduces manifest size:
           - pypy:     -80%
           - netbeans: -95%
         * The delta chain limit is effective, without a size impact:
           - netbeans average:      613 -> 282
           - private #1 average:  1 068 -> 307
      
       - On more linear repository:
         * Intermediate snapshot limit the impact of delta chain limit:
           - mozilla:
               without the series: +360%
               with the series:     +25%
         * The delta chain limit provides large improvement:
           - mozilla's average chain length:
              unlimited: 15 338
              limited:      469
         * Despite the chain length limit, the manifest size is reduced:
           - mercurial: -25%
           - mozilla:   -30%
      
      It is clear that the use of chains of intermediate snapshots provide large
      benefits both in storage size and delta chains quality. We should now switch our
      effort toward making sure the write performance are acceptable. Then,
      `sparse-revlog` will be a suitable format for all new repository.
      
      # Raw Statistic
      
        * no-sparse:   general delta repository not using sparse-revlog
        * no-snapshot: sparse-revlog repository not using this series
        * snapshot:    sparse-revlog repository using this series
      
      mercurial
      
          Manifest Size:
              limit       | none        |        1000
              ------------|-------------|------------
              no-sparse   |   8 021 373 |  8 199 366
              no-snapshot |   8 103 561 |  8 259 719
              snapshot    |   6 137 116 |  6 126 433
      
          Manifest Chain length data
              limit       ||       none        ||       1000        ||
              value       || average |   max   || average |   max   ||
              ------------||---------|---------||---------|---------||
              no-sparse   ||     307 |    1456 ||     279 |    1000 ||
              no-snapshot ||     312 |    1456 ||     283 |    1000 ||
              snapshot    ||     248 |    1208 ||     241 |    1000 ||
      
          Full Store Size
              limit       | none        |        1000
              ------------|-------------|------------
              no-sparse   |  51 013 198 | 51 201 574
              no-snapshot |  50 930 795 | 51 141 006
              snapshot    |  48 072 037 | 48 093 572
      
      pypy
      
          Manifest Size:
              limit       | none        |        1000
              ------------|-------------|------------
              no-sparse   | 193 987 784 | 193 987 784
              no-snapshot | 163 171 745 | 163 312 229
              snapshot    |  34 605 900 |  34 600 750
      
          Manifest Chain length data
              limit       ||       none        ||       1000        ||
              value       || average |   max   || average |   max   ||
              ------------||---------|---------||---------|---------||
              no-sparse   ||     101 |     692 ||     101 |     692 ||
              no-snapshot ||     151 |    1307 ||     148 |    1000 ||
              snapshot    ||     128 |    1309 ||     125 |    1000 ||
      
          Full Store Size
              limit       | none        |        1000
              ------------|-------------|------------
              no-sparse   | 495 931 473 | 495 931 473
              no-snapshot | 465 441 017 | 465 581 501
              snapshot    | 355 467 301 | 355 472 451
      
      Mozilla
      
          Manifest Size:
              limit       | none           |        1000
              ------------|----------------|---------------
              no-sparse   |    416 757 148 |  1 869 009 668
              no-snapshot |    401 592 370 |  1 843 493 795
              snapshot    |    224 359 521 |    284 615 500
      
          Manifest Chain length data
              limit       ||       none        ||       1000        ||
              value       || average |   max   || average |   max   ||
              ------------||---------|---------||---------|---------||
              no-sparse   ||  15 333 |  58 980 ||     468 |   1 000 ||
              no-snapshot ||  15 336 |  58 980 ||     469 |   1 000 ||
              snapshot    ||  15 338 |  58 983 ||     469 |   1 000 ||
      
          Full Store Size
              limit       | none           |        1000
              ------------|----------------|---------------
              no-sparse   |  2 712 477 887 | 4 164 995 451
              no-snapshot |  2 698 887 835 | 4 141 054 304
              snapshot    |  2 518 130 385 | 2 578 587 596
      
      Netbeans
      
          Manifest Size:
              limit       | none           |        1000
              ------------|----------------|---------------
              no-sparse   |  4 766 794 101 |  4 870 642 687
              no-snapshot |  4 334 806 082 |  4 428 681 309
              snapshot    |    232 659 666 |    240 330 665
      
          Manifest Chain length data
              limit       ||       none        ||       1000        ||
              value       || average |   max   || average |   max   ||
              ------------||---------|---------||---------|---------||
              no-sparse   ||     597 |   6802  ||     254 |   1 000 ||
              no-snapshot ||     648 |   6 802 ||     305 |   1 000 ||
              snapshot    ||     613 |   6 804 ||     282 |   1 000 ||
      
          Full Store Size
              limit       | none           |        1000
              ------------|----------------|---------------
              no-sparse   |  5 807 347 998 |  5 911 196 584
              no-snapshot |  5 375 398 602 |  5 469 273 829
              snapshot    |  1 282 519 928 |  1 290 190 927
      
      Private repo #1
      
          Manifest Size:
              limit       | none            |        1000
              ------------|-----------------|---------------
              no-sparse   | 41 389 010 840  | 41 398 162 091
              no-snapshot |  9 737 319 435  | 10 223 773 150
              snapshot    |    744 215 807  |    747 961 822
      
          Manifest Chain length data
              limit       ||       none        ||       1000        ||
              value       || average |   max   || average |   max   ||
              ------------||---------|---------||---------|---------||
              no-sparse   ||     245 |   8 885 ||     81  |   1 000 ||
              no-snapshot ||   1 225 |   8 885 ||    336  |   1 000 ||
              snapshot    ||   1 068 |   7 909 ||    307  |   1 000 ||
      
          Full Store Size
              limit       | none           |        1000
              ------------|----------------|---------------
              no-sparse   | 49 646 065 126 | 49 655 216 377
              no-snapshot | 17 924 862 856 | 18 411 316 571
              snapshot    |  9 009 024 710 |  9 012 770 725
      
      Private repo #2
      
        We currently have less data available for that repository.
          * Before is a sparse-revlog repository without this series
          * After is a sparse-revlog repository with this series + 1000 chain limit
      
      
        Manifest Size:
          Before: 1 531 485 040 bytes
          After:  1 091 422 451 bytes
        Manifest Chain:
          Before: 2 218 avg; 6 575 Max
          After:    442 avg; 1 000 Max
      
        Full Store Size
          Before: 15 203 955 615
          after:   8 207 180 693
      b66ea3fc3a86
    • Boris Feld's avatar
      snapshot: also consider the snapshot chain of one unrelated revision · c6b8eab5db19
      Boris Feld authored
      To maximize the chance of good delta chain reuse, we inject an unrelated delta
      chain into our search. To do so, we search for the highest revision unrelated
      to the parents of the current revision and use its snapshot chain too.
      
      Adding this extra snapshot into the mix can have a performance impact. We'll
      deal with performance impact in a later series.
      c6b8eab5db19
    • Boris Feld's avatar
      snapshot: extract parent chain computation · 05a165dc4f55
      Boris Feld authored
      The final step of this series is to include chain related to "prev" in the
      search. Before adding that code we do some simple code movement to clarify the
      next diff.
      05a165dc4f55
    • Boris Feld's avatar
      snapshot: refine candidate snapshot base upward · 5aef5afa8654
      Boris Feld authored
      Once we found a suitable snapshot base it is useful to check if it has a
      "children" snapshot that would provide a better diff. This is useful when base
      not directly related to stored revision are picked. In those case, we "jumped"
      to this new chain at an arbitrary point, checking if a higher point is more
      appropriate will help to provide better results and increase snapshot reuse.
      5aef5afa8654
    • Boris Feld's avatar
      snapshot: try to refine new snapshot base down the chain · e4d4361d0bcd
      Boris Feld authored
      There are cases where doing a diff against a snapshot's parent will be shorter
      than against the snapshot itself. Reusing snapshot not directly related to the
      revision we are trying to store increase this odd.
      
      So once we found a possible candidate, we check the snapshots lower in the
      chain.
      
      This will involve extra processing, but this extra processing will only happen
      when we are doing building a snapshot, a rare situation.
      e4d4361d0bcd
    • Boris Feld's avatar
      snapshot: make sure we'll never refine delta base from a reused source · 993d7e2c8b79
      Boris Feld authored
      The point of reusing delta from the source is to avoid doing computation when
      applying a bundle. Refining such delta would go against that spirit.
      
      We do not have refining logic in place yet. This code needed to be moved out
      of the way before we could start adding such logic.
      993d7e2c8b79
    • Boris Feld's avatar
      snapshot: turn _refinedgroups into a coroutine · cc85ebb68ff9
      Boris Feld authored
      We are now almost ready to start adding refining logic.
      cc85ebb68ff9
    • Boris Feld's avatar
      snapshot: also use None as a stop value for `_refinegroup` · 51cec7fb672e
      Boris Feld authored
      This is yet another small step toward turning `_refinegroups` into a co-routine.
      51cec7fb672e
    • Boris Feld's avatar
      snapshot: add refining logic at the findeltainfo level · 04b75f3a3f2a
      Boris Feld authored
      Once we found a delta, we want to have the candidates logic challenge it,
      searching for a better candidate.
      
      The logic at the lower level is still missing. We'll introduce it later.
      Adding small changes in individual commits make it simpler to explain the code
      change.
      
      This is another small step toward turning `_refinegroups` into a co-routine.
      04b75f3a3f2a
    • Boris Feld's avatar
      snapshot: use None as a stop value when looking for a good delta · 5b308a4e6d03
      Boris Feld authored
      Having clear stop value should help keep clear logic around the co-routine.
      The alternative of using a StopIteration exception give a messier result.
      
      This is one small step toward turning `_refinegroups` into a co-routine.
      5b308a4e6d03
    • Boris Feld's avatar
      snapshot: introduce an intermediate `_refinedgroups` generator · 2f9f7889549b
      Boris Feld authored
      This method will be used to improve the search for a good snapshot base. To
      keep things simpler, we introduce the necessary function before doing any
      delta base logic change. The next handful of commits will focus on refactoring
      the code to let that new logic land as clearly as possible.
      
      # General Idea
      
      Right now, the search for a good delta base stop whenever we found a good one.
      However, when using sparse-revlog, we should probably try a bit harder.
      
      We do significant effort to increase delta re-use by jumping on "unrelated"
      delta chains that provide better results. Moving to another chain for a better
      result is good, but we have no guarantee we jump at a reasonable point in that
      new chain. When we consider over the chains related to the parents, we start
      from the higher-level snapshots. This is a way to consider the snapshot closer
      to the current revision that has the best chance to produce a small delta. We
      do benefit from this walk order when jumping to a better "unrelated" stack.
      
      To counter-balance this, we'll introduce a way to "refine" the result. After a
      good delta have been found, we'll keep searching for a better delta, using the
      current best one as a starting point.
      
      # Target Setup
      
      The `finddeltainfo` method is responsible for the general search for a good
      delta. It requests candidates base from `_candidategroups` and decides which
      one are usable.
      
      The `_candidategroups` generator act as a top-level filter, it does not care
      about how we pick candidates, it just does basic filtering, excluding
      revisions that have been tested already or that are an obvious misfit.
      
      The `_rawgroups` generator is the one with the actual ancestors walking logic,
      It does not care about what would do a good delta and what was already tested,
      it just issues the initial candidates.
      
      We introduce a new `_refinedgroup` function to bridge the gap between
      `_candidategroups` and `_rawgroups`. It delegates the initial iteration logic
      and then performing relevant refining of the valid base once found. (This
      logic is yet to be added to function)
      
      All these logics are fairly independent and easier to understand when standing
      alone, not mixed with each other. It also makes it easy to test and try
      different approaches for one of those four layers without affecting the other
      ones.
      
      # Technical details
      
      To communicate `finddeltainfo` choice of "current best delta base" to the
      `_refinegroup` logic, we plan to use python co-routine feature. The
      `_candidategroups` and `_refinegroup` generators will become co-routine. This
      will allow `_refinegroup` to detect when a good delta have been found and
      triggers various refining steps.
      
      For now, `_candidategroups` will just pass the value down the stack.
      
      After poking at various option, the co-routine appears the best to keep each
      layers focus on its duty, without the need to spread implementation details
      across layers.
      2f9f7889549b
    • Boris Feld's avatar
      snapshot: consider unrelated snapshots at a similar level first · 6a53842727c1
      Boris Feld authored
      This new step is inserted before considering using a level-N snapshot as a
      base for a level-N+1 snapshot. We first check if existing level-N+1 snapshots
      using the same base would be a suitable base for a level-N+2 snapshot.
      
      This increases snapshot reuse and limits the risk of snapshot explosion in
      very branchy repositories.
      
      Using a "deeper" snapshot as the base also results in a smaller snapshot since
      it builds a level-N+2 intermediate snapshot instead of an N+1 one.
      
      This logic is similar for the one we added in a previous commit. In that
      previous commit is only applied to level-0 "siblings".
      
      We can see this effect in the test repository. Snapshots moved from lower
      levels to higher levels.
      6a53842727c1
    • Boris Feld's avatar
      snapshot: consider all snapshots in the parents' chains · e72130f58f5d
      Boris Feld authored
      There are no reasons to only consider full snapshot as a possible base for an
      intermediate snapshot.  Now that the basic principles have been set, we can
      start adding more levels of snapshots.
      
      We now consider all snapshots in the parent's chains (full or intermediate).
      This creates a chain of intermediate snapshots, each smaller than the previous
      one.
      
      # Effect On The Test Repository
      
      In the test repository, we can see a decrease in the revlog size and slightly
      shorter delta chain.
      
      However, that approach creates snapshots more frequently, increasing the risk
      of ending into problematic cases in very branchy repositories (not triggered
      by the test repository). The next changesets will remove that risk by adding
      logic that increases deltas reuse.
      e72130f58f5d
    • Boris Feld's avatar
      snapshot: search for unrelated but reusable full-snapshot · 3ca144f1c8dd
      Boris Feld authored
      # New Strategy Step: Reusing Snapshot Outside Of Parents' Chain.
      
      If no suitable bases were found in the parent's chains, see if we could reuse
      a full snapshot not directly related to the current revision. Such search can
      be expensive, so we only search for snapshots appended to the revlog *after*
      the bases used by the parents of the current revision (the one we just
      tested). We assume the parent's bases were created because the previous
      snapshots were unsuitable, so there are low odds they would be useful now.
      
      This search gives a chance to reuse a delta chain unrelated to the current
      revision. Without this re-use, topological branches would keep reopening new
      full chains. Creating more and more snapshots as the repository grow.
      
      In repositories with many topological branches, the lack of delta reuse can
      create too many snapshots reducing overall compression to nothing. This
      results in a very large repository and other usability issues.
      
      For now, we still focus on creating level-1 snapshots. However, this principle
      will play a large part in how we avoid snapshot explosion once we have more
      snapshot levels.
      
      # Effects On The Test Repository
      
      In the test repository we created, we can see the beneficial effect of such
      reuse. We need very few level-0 snapshots and the overall revlog size has
      decreased.
      
      The `hg debugrevlog` call, show a "lvl-2" snapshot. It comes from the existing
      delta logic using the `prev` revision (revlog's tip) as the base. In this
      specific case, it turns out the tip was a level-1 snapshot. This is a
      coincidence that can be ignored.
      
      Finding and testing against all these unrelated snapshots can have a
      performance impact at write time. We currently focus on building good deltas
      chain we build. Performance concern will be dealt with later in another
      series.
      3ca144f1c8dd
    • Boris Feld's avatar
      snapshot: try intermediate snapshot against parents' base · a33f394b2bfd
      Boris Feld authored
      # 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.
      a33f394b2bfd
Loading