dirstate-tree: Use HashMap instead of BTreeMap BTreeMap has the advantage of its "natural" iteration order being the one we need in the status algorithm. With HashMap however, iteration order is undefined so we need to allocate a Vec and sort it explicitly. Unfortunately many BTreeMap operations are slower than in HashMap, and skipping that extra allocation and sort is not enough to compensate. Switching to HashMap + sort makes `hg status` 17% faster in one test case, as measure with hyperfine: ``` Benchmark #1: ../hg2/hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1 Time (mean ± σ): 765.0 ms ± 8.8 ms [User: 1.352 s, System: 0.747 s] Range (min … max): 751.8 ms … 778.7 ms 10 runs Benchmark #2: ./hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1 Time (mean ± σ): 651.8 ms ± 9.9 ms [User: 1.251 s, System: 0.799 s] Range (min … max): 642.2 ms … 671.8 ms 10 runs Summary './hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1' ran 1.17 ± 0.02 times faster than '../hg2/hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1' ``` * ./hg is this revision * ../hg2/hg is its parent * $REPO is an old snapshot of mozilla-central Differential Revision: https://phab.mercurial-scm.org/D10553

dirstate-tree: Add #[timed] attribute to `status` and `DirstateMap::read` When running with a `RUST_LOG=trace` environment variable, the `micro_timer` crate prints the duration taken by each call to functions with that attribute. Differential Revision: https://phab.mercurial-scm.org/D10552

dirstate-tree: Paralellize the status algorithm with Rayon The `rayon` crate exposes "parallel iterators" that work like normal iterators but dispatch work on different items to an implicit global thread pool. Differential Revision: https://phab.mercurial-scm.org/D10551

dirstate-tree: Avoid BTreeMap double-lookup when inserting a dirstate entry The child nodes of a given node in the tree-shaped dirstate are kept in a `BTreeMap` where keys are file names as strings. Finding or inserting a value in the map takes `O(log(n))` string comparisons, which adds up when constructing the tree. The `entry` API allows finding a "spot" in the map that may or may not be occupied and then access that value or insert a new one without doing map lookup again. However the current API is limited in that calling `entry` requires an owned key (and so a memory allocation), even if it ends up not being used in the case where the map already has a value with an equal key. This is still a win, with 4% better end-to-end time for `hg status` measured here with hyperfine: ``` Benchmark #1: ../hg2/hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1 Time (mean ± σ): 1.337 s ± 0.018 s [User: 892.9 ms, System: 437.5 ms] Range (min … max): 1.316 s … 1.373 s 10 runs Benchmark #2: ./hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1 Time (mean ± σ): 1.291 s ± 0.008 s [User: 853.4 ms, System: 431.1 ms] Range (min … max): 1.283 s … 1.309 s 10 runs Summary './hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1' ran 1.04 ± 0.02 times faster than '../hg2/hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1' ``` * ./hg is this revision * ../hg2/hg is its parent * $REPO is an old snapshot of mozilla-central Differential Revision: https://phab.mercurial-scm.org/D10550