Skip to content
Snippets Groups Projects
  1. Sep 30, 2021
  2. Sep 29, 2021
  3. Sep 30, 2021
  4. Sep 29, 2021
  5. Sep 30, 2021
  6. Sep 29, 2021
  7. Sep 30, 2021
  8. Oct 01, 2021
  9. Sep 10, 2021
  10. Sep 13, 2021
  11. Sep 01, 2021
  12. Sep 30, 2021
  13. Sep 28, 2021
  14. Sep 27, 2021
    • Simon Sapin's avatar
      dirstate: Remove the Rust abstraction DirstateMapMethods · 3d0a9c6e
      Simon Sapin authored
      This Rust trait used to exist in order to allow the DirstateMap class exposed
      to Python to be backed by either of two implementations: one similar to the
      Python implementation based on a "flat" `HashMap<HgPathBuf, DirstateEntry>`,
      and the newer one based on a tree of nodes matching the directory structure
      of tracked files. A boxed trait object was used with dynamic dispatch.
      
      With the flat implementation removed and only the tree one remaining, this
      abstraction is not useful anymore and the concrete type can be stored directly.
      
      It remains that the trait was implemented separately for `DirstateMap<'_>`
      (which takes a lifetime parameter) and `OwningDirstateMap` (whose job is to
      wrap the former and hide the lifetime parameter), with the latter impl only
      forwarding calls.
      
      This changeset also removes this forwarding. Instead, the methods formerly of
      the `DirstateMapMethods` trait are now inherent methods implemented for
      `OwningDirstateMap` (where they will actually be used) but in the module that
      defines `DirstateMap`. This unusual setup gives access to the private fields
      of `DirstateMap` from those methods.
      
      Differential Revision: https://phab.mercurial-scm.org/D11517
      3d0a9c6e
    • Simon Sapin's avatar
      dirstate: Remove the flat Rust DirstateMap implementation · bf8837e3
      Simon Sapin authored
      Before this changeset we had two Rust implementations of `DirstateMap`.
      This removes the "flat" DirstateMap so that the "tree" DirstateMap is always
      used when Rust enabled. This simplifies the code a lot, and will enable
      (in the next changeset) further removal of a trait abstraction.
      
      This is a performance regression when:
      
      * Rust is enabled, and
      * The repository uses the legacy dirstate-v1 file format, and
      * For `hg status`, unknown files are not listed (such as with `-mard`)
      
      The regression is about 100 milliseconds for `hg status -mard` on a
      semi-large repository (mozilla-central), from ~320ms to ~420ms.
      We deem this to be small enough to be worth it.
      
      The new dirstate-v2 is still experimental at this point, but we aim to
      stabilize it (though not yet enable it by default for new repositories)
      in Mercurial 6.0. Eventually, upgrating repositories to dirsate-v2 will
      eliminate this regression (and enable other performance improvements).
      
      
      # Background
      
      The flat DirstateMap was introduced with the first Rust implementation of the
      status algorithm. It works similarly to the previous Python + C one, with a
      single `HashMap` that associates file paths to a `DirstateEntry` (where Python
      has a dict).
      
      We later added the tree DirstateMap where the root of the tree contains nodes
      for files and directories that are directly at the root of the repository,
      and nodes for directories can contain child nodes representing the files and
      directly that *they* contain directly. The shape of this tree mirrors that of
      the working directory in the filesystem. This enables the status algorithm to
      traverse this tree in tandem with traversing the filesystem tree, which in
      turns enables a more efficient algorithm.
      
      Furthermore, the new dirstate-v2 file format is also based on a tree of the
      same shape. The tree DirstateMap can access a dirstate-v2 file without parsing
      it: binary data in a single large (possibly memory-mapped) bytes buffer is
      traversed on demand. This allows `DirstateMap` creation to take `O(1)` time.
      (Mutation works by creating new in-memory nodes with copy-on-write semantics,
      and serialization is append-mostly.)
      
      The tradeoff is that for "legacy" repositories that use the dirstate-v1 file
      format, parsing that file into a tree DirstateMap takes more time. Profiling
      shows that this time is dominated by `HashMap`. For a dirstate containing `F`
      files with an average `D` directory depth, the flat DirstateMap does parsing
      in `O(F)` number of HashMap operations but the tree DirstateMap in `O(F × D)`
      operations, since each node has its own HashMap containing its child nodes.
      This slower costs ~140ms on an old snapshot of mozilla-central, and ~80ms
      on an old snapshot of the Netbeans repository.
      
      The status algorithm is faster, but with `-mard` (when not listing unknown
      files) it is typically not faster *enough* to compensate the slower parsing.
      
      Both Rust implementations are always faster than the Python + C implementation
      
      
      # Benchmark results
      
      All benchmarks are run on changeset 98c0408324e6, with repositories that use
      the dirstate-v1 file format, on a server with 4 CPU cores and 4 CPU threads
      (no HyperThreading).
      
      `hg status` benchmarks show wall clock times of the entire command as the
      average and standard deviation of serveral runs, collected by
      https://github.com/sharkdp/hyperfine and reformated.
      
      Parsing benchmarks are wall clock time of the Rust function that converts a
      bytes buffer of the dirstate file into the `DirstateMap` data structure as
      used by the status algorithm. A single run each, collected by running
      `hg status` this environment variable:
      
          RUST_LOG=hg::dirstate::dirstate_map=trace,hg::dirstate_tree::dirstate_map=trace
      
      
      Benchmark 1: Rust flat DirstateMap → Rust tree DirstateMap
      
          hg status
      
          mozilla-clean    	562.3 ms ± 2.0 ms	→	462.5 ms ± 0.6 ms	 1.22 ± 0.00 times faster
          mozilla-dirty    	859.6 ms ± 2.2 ms	→	719.5 ms ± 3.2 ms	 1.19 ± 0.01 times faster
          mozilla-ignored  	558.2 ms ± 3.0 ms	→	457.9 ms ± 2.9 ms	 1.22 ± 0.01 times faster
          mozilla-unknowns 	859.4 ms ± 5.7 ms	→	716.0 ms ± 4.7 ms	 1.20 ± 0.01 times faster
          netbeans-clean   	336.5 ms ± 0.9 ms	→	339.5 ms ± 0.4 ms	 0.99 ± 0.00 times faster
          netbeans-dirty   	491.4 ms ± 1.6 ms	→	475.1 ms ± 1.2 ms	 1.03 ± 0.00 times faster
          netbeans-ignored 	343.7 ms ± 1.0 ms	→	347.8 ms ± 0.4 ms	 0.99 ± 0.00 times faster
          netbeans-unknowns	484.3 ms ± 1.0 ms	→	466.0 ms ± 1.2 ms	 1.04 ± 0.00 times faster
      
          hg status -mard
      
          mozilla-clean    	317.3 ms ± 0.6 ms	→	422.5 ms ± 1.2 ms	 0.75 ± 0.00 times faster
          mozilla-dirty    	315.4 ms ± 0.6 ms	→	417.7 ms ± 1.1 ms	 0.76 ± 0.00 times faster
          mozilla-ignored  	314.6 ms ± 0.6 ms	→	417.4 ms ± 1.0 ms	 0.75 ± 0.00 times faster
          mozilla-unknowns 	312.9 ms ± 0.9 ms	→	417.3 ms ± 1.6 ms	 0.75 ± 0.00 times faster
          netbeans-clean   	212.0 ms ± 0.6 ms	→	283.6 ms ± 0.8 ms	 0.75 ± 0.00 times faster
          netbeans-dirty   	211.4 ms ± 1.0 ms	→	283.4 ms ± 1.6 ms	 0.75 ± 0.01 times faster
          netbeans-ignored 	211.4 ms ± 0.9 ms	→	283.9 ms ± 0.8 ms	 0.74 ± 0.01 times faster
          netbeans-unknowns	211.1 ms ± 0.6 ms	→	283.4 ms ± 1.0 ms	 0.74 ± 0.00 times faster
      
          Parsing
      
          mozilla-clean       38.4ms → 177.6ms
          mozilla-dirty       38.8ms → 177.0ms
          mozilla-ignored     38.8ms → 178.0ms
          mozilla-unknowns    38.7ms → 176.9ms
          netbeans-clean      16.5ms → 97.3ms
          netbeans-dirty      16.5ms → 98.4ms
          netbeans-ignored    16.9ms → 97.4ms
          netbeans-unknowns   16.9ms → 96.3ms
      
      
      Benchmark 2: Python + C dirstatemap → Rust tree DirstateMap
      
          hg status
      
          mozilla-clean    	1261.0 ms ± 3.6 ms	→	461.1 ms ± 0.5 ms	 2.73 ± 0.00 times faster
          mozilla-dirty    	2293.4 ms ± 9.1 ms	→	719.6 ms ± 3.6 ms	 3.19 ± 0.01 times faster
          mozilla-ignored  	1240.4 ms ± 2.3 ms	→	457.7 ms ± 1.9 ms	 2.71 ± 0.00 times faster
          mozilla-unknowns 	2283.3 ms ± 9.0 ms	→	719.7 ms ± 3.8 ms	 3.17 ± 0.01 times faster
          netbeans-clean   	879.7 ms ± 3.5 ms	→	339.9 ms ± 0.5 ms	 2.59 ± 0.00 times faster
          netbeans-dirty   	1257.3 ms ± 4.7 ms	→	474.6 ms ± 1.6 ms	 2.65 ± 0.01 times faster
          netbeans-ignored 	943.9 ms ± 1.9 ms	→	347.3 ms ± 1.1 ms	 2.72 ± 0.00 times faster
          netbeans-unknowns	1188.1 ms ± 5.0 ms	→	465.2 ms ± 2.3 ms	 2.55 ± 0.01 times faster
      
          hg status -mard
      
          mozilla-clean    	903.2 ms ± 3.6 ms	→	423.4 ms ± 2.2 ms	 2.13 ± 0.01 times faster
          mozilla-dirty    	884.6 ms ± 4.5 ms	→	417.3 ms ± 1.4 ms	 2.12 ± 0.01 times faster
          mozilla-ignored  	881.9 ms ± 1.3 ms	→	417.3 ms ± 0.8 ms	 2.11 ± 0.00 times faster
          mozilla-unknowns 	878.5 ms ± 1.9 ms	→	416.4 ms ± 0.9 ms	 2.11 ± 0.00 times faster
          netbeans-clean   	434.9 ms ± 1.8 ms	→	284.0 ms ± 0.8 ms	 1.53 ± 0.01 times faster
          netbeans-dirty   	434.1 ms ± 0.8 ms	→	283.1 ms ± 0.8 ms	 1.53 ± 0.00 times faster
          netbeans-ignored 	431.7 ms ± 1.1 ms	→	283.6 ms ± 1.8 ms	 1.52 ± 0.01 times faster
          netbeans-unknowns	433.0 ms ± 1.3 ms	→	283.5 ms ± 0.7 ms	 1.53 ± 0.00 times faster
      
      Differential Revision: https://phab.mercurial-scm.org/D11516
      bf8837e3
Loading