Raphaël Gomès <rgomes@octobus.net> [Thu, 30 Sep 2021 17:34:28 +0200] rev 48085
branching: merge with stable
Simon Sapin <simon.sapin@octobus.net> [Mon, 27 Sep 2021 13:52:49 +0200] rev 48084
dirstate: Remove the Rust abstraction DirstateMapMethods
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
Simon Sapin <simon.sapin@octobus.net> [Mon, 27 Sep 2021 12:09:15 +0200] rev 48083
dirstate: Remove the flat Rust DirstateMap implementation
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
Pierre-Yves David <pierre-yves.david@octobus.net> [Tue, 28 Sep 2021 20:00:19 +0200] rev 48082
dirstate: drop the from_p2_removed method
It it no longer in use.
Differential Revision: https://phab.mercurial-scm.org/D11515
Pierre-Yves David <pierre-yves.david@octobus.net> [Tue, 28 Sep 2021 19:29:44 +0200] rev 48081
dirstate: inline the `from_p2_removed` logic
It is used internally for compatibilty with size used in the `v1` format, but
this is the only use. So we can simply inline it.
Differential Revision: https://phab.mercurial-scm.org/D11514
Pierre-Yves David <pierre-yves.david@octobus.net> [Tue, 28 Sep 2021 19:15:46 +0200] rev 48080
dirstate: drop the merged_removed method
It it no longer in use.
Differential Revision: https://phab.mercurial-scm.org/D11513
Pierre-Yves David <pierre-yves.david@octobus.net> [Tue, 28 Sep 2021 19:12:44 +0200] rev 48079
dirstate: inline the merged_removed logic
It is used internally for compatibilty with size used in the `v1` format, but
this is the only use. So we can simply inline it.
Differential Revision: https://phab.mercurial-scm.org/D11512
Pierre-Yves David <pierre-yves.david@octobus.net> [Tue, 28 Sep 2021 18:57:20 +0200] rev 48078
dirstate: drop some safety assert in largefile
The code involved in `set_possibly_dirty` is now simpler and safe to use even
in the cases that the assert covered. So we can drop this assert.
It was the last user of `merged_removed` and `from_p2_removed`.
Differential Revision: https://phab.mercurial-scm.org/D11511
Pierre-Yves David <pierre-yves.david@octobus.net> [Tue, 28 Sep 2021 18:29:57 +0200] rev 48077
dirstate: drop unused condition in `from_p2`
This conditional was added (by me) tentatively because "it seemed more
correct", but it is not used anywhere yet, and it is missing from the C and the
Rust implementation. So it seems more consistent to drop it for now.
This effectively backout f94cc63df859c
Differential Revision: https://phab.mercurial-scm.org/D11510
Pierre-Yves David <pierre-yves.david@octobus.net> [Tue, 28 Sep 2021 20:05:37 +0200] rev 48076
dirstate: drop all logic around the "non-normal" sets
The dirstate has a lot of code to compute a set of all "non-normal" and
"from_other_parent" entries.
This is all used in one, unique, location, when `setparent` is called and moved
from a merge to a non merge. At that time, any "merge related" information has
to be dropped. This is mostly useful for command like `graft` or `shelve` that
move to a single-parent state -before- the commit. Otherwise the commit will
already have removed all traces of the merge information in the dirstate (e.g.
for a regular merges).
The bookkeeping for these sets is quite invasive. And it seems simpler to just
drop it and do the full computation in the single location where we actually
use it (since we have to do the computation at least once anyway).
This simplify the code a lot, and clarify why this kind of computation is
needed.
The possible drawback compared to the previous code are:
- if the operation happens in a loop, we will end up doing it multiple time,
- the C code to detect entry of interest have been dropped, for now. It will be
re-introduced later, with a processing code directly in C for even faster
operation.
Differential Revision: https://phab.mercurial-scm.org/D11507
Pierre-Yves David <pierre-yves.david@octobus.net> [Wed, 22 Sep 2021 17:46:29 +0200] rev 48075
dirstate: use a new `drop_merge_data` in `setparent`
What is happening in this `setparent` loop is that we remove all `merge`
related information when the dirstate is moved out of a `merge` situation.
So instead of shuffling state to get them where we want, we simply add a method
on the DirstateItem to do drop the information we want dropped.
Differential Revision: https://phab.mercurial-scm.org/D11506
Pierre-Yves David <pierre-yves.david@octobus.net> [Wed, 22 Sep 2021 15:17:12 +0200] rev 48074
dirstate: move parent state handling in the dirstatemap
This involves dirstatemap data mostly. Moving this one level down will remove
the needs for the dirstatemap to expose some of its internals.
This will help us to simplify more code further.
Differential Revision: https://phab.mercurial-scm.org/D11505
Pierre-Yves David <pierre-yves.david@octobus.net> [Wed, 22 Sep 2021 09:46:37 +0200] rev 48073
dirstate: stop checking for path collision when adjusting parents
This was already checked at a earlier point when adding the file.
Differential Revision: https://phab.mercurial-scm.org/D11504
Pierre-Yves David <pierre-yves.david@octobus.net> [Wed, 22 Sep 2021 15:08:47 +0200] rev 48072
dirstate: drop the `_updatedfiles` set
This is a lot of book keeping for something that was only used to clear
ambiguous time. Since this is no no longer in use, we can drop it.
Differential Revision: https://phab.mercurial-scm.org/D11503
Pierre-Yves David <pierre-yves.david@octobus.net> [Wed, 22 Sep 2021 15:23:03 +0200] rev 48071
dirstate: drop the `clearambiguoustimes` method for the map
This is no longer called anywhere.
Differential Revision: https://phab.mercurial-scm.org/D11502
Pierre-Yves David <pierre-yves.david@octobus.net> [Wed, 22 Sep 2021 14:54:42 +0200] rev 48070
dirstate: simplify the ambiguity clearing at write time
The serialization function is already doing this, so we don't need to do it
manually. We just need to propagate the right definition of "now".
Differential Revision: https://phab.mercurial-scm.org/D11501
Martin von Zweigbergk <martinvonz@google.com> [Tue, 28 Sep 2021 09:32:24 -0700] rev 48069
histedit: use more specific exceptions for more detailed exit codes
Differential Revision: https://phab.mercurial-scm.org/D11509
Martin von Zweigbergk <martinvonz@google.com> [Tue, 28 Sep 2021 09:25:05 -0700] rev 48068
histedit: remove redundant checks for unfinished histedit state
Both text-based and curses-based histedit already check for unfinished
operations (not just unfinished histedit), so there's no need to check
specifically for unfinished histedit.
Differential Revision: https://phab.mercurial-scm.org/D11508
Simon Sapin <simon.sapin@octobus.net> [Tue, 28 Sep 2021 13:43:14 +0200] rev 48067
dirstate: Appease pytype
test-check-pytype.t was failing since 98c0408324e6:
File "/home/simon/projects/hg/mercurial/dirstatemap.py", line 572, in
addfile: unsupported operand type(s) for &: 'size: None' and
'rangemask: int' [unsupported-operands]
No attribute '__and__' on 'size: None' or '__rand__' on 'rangemask: int'
File "/home/simon/projects/hg/mercurial/dirstatemap.py", line 573, in
addfile: unsupported operand type(s) for &: 'mtime: None' and
'rangemask: int' [unsupported-operands]
No attribute '__and__' on 'mtime: None' or '__rand__' on 'rangemask: int'
`None` is the default value of the `size` and `mtime` parameters of the
`addfile` method. However, the relevant lines are only used in a code path
where those defaults are never used. These `size` and `mtime` are passed
to `DirstateItem.new_normal` which (in the C implementation) calls
`dirstate_item_new_normal` which uses:
PyArg_ParseTuple(args, "iii", &mode, &size, &mtime)
So `None` values would cause an exception to be raised anyway.
The new `assert`s only move that exception earlier, and informs pytype
that we expect `None` to never happen in this code path.
Differential Revision: https://phab.mercurial-scm.org/D11500
Simon Sapin <simon.sapin@octobus.net> [Thu, 23 Sep 2021 18:29:40 +0200] rev 48066
dirstate: Pass the final DirstateItem to _rustmap.addfile()
Now that the Python DirstateItem class wraps a Rust DirstateEntry value,
use that value directly instead of converting through v1 data + 5 booleans.
Also remove propogating the return value. None of the callers look at it,
and it is always None.
Differential Revision: https://phab.mercurial-scm.org/D11494
Simon Sapin <simon.sapin@octobus.net> [Thu, 23 Sep 2021 15:36:43 +0200] rev 48065
dirstate: Replace dropfile with drop_item_and_copy_source
Those removing a DirstateItem and a copy source are always done together
Differential Revision: https://phab.mercurial-scm.org/D11493
Simon Sapin <simon.sapin@octobus.net> [Thu, 23 Sep 2021 15:29:38 +0200] rev 48064
rust: Remove some obsolete doc-comments
About parameters that have been removed or replaced
Differential Revision: https://phab.mercurial-scm.org/D11492
Simon Sapin <simon.sapin@octobus.net> [Thu, 23 Sep 2021 15:26:33 +0200] rev 48063
dirstate: Remove return boolean from dirstatemap.dropfile
None of the remaining callers use it.
Differential Revision: https://phab.mercurial-scm.org/D11491
Simon Sapin <simon.sapin@octobus.net> [Wed, 22 Sep 2021 18:56:58 +0200] rev 48062
dirstate: Propagate dirstate-v2 parse errors from set_dirstate_item
… so that Python sees a proper ValueError instead of only
`SystemError: Rust panic`
Differential Revision: https://phab.mercurial-scm.org/D11489
Simon Sapin <simon.sapin@octobus.net> [Wed, 22 Sep 2021 18:42:00 +0200] rev 48061
dirstate: Don’t drop unrelated data in DirstateMap::set_entry
For example, copy source are handled separately. Removing it goes through
the `copy_map_remove` method (exposed to Python as `.copymap.pop()`)
Differential Revision: https://phab.mercurial-scm.org/D11488
Simon Sapin <simon.sapin@octobus.net> [Wed, 22 Sep 2021 18:21:58 +0200] rev 48060
dirstate: Skip no-op conversion in Rust DirstateMap::set_v1
Now that the `DirstateItem` python class is implemented in Rust containing
a `DirstateEntry` value, use that value directly instead of reconstructing
it from v1 data.
Also rename from `set_v1` since dirstate-v1 data is not used anymore.
Differential Revision: https://phab.mercurial-scm.org/D11487
Simon Sapin <simon.sapin@octobus.net> [Wed, 22 Sep 2021 11:33:29 +0200] rev 48059
dirstate: Use the Rust implementation of DirstateItem when Rust is enabled
… instead of the C implementation, with C/Rust conversions at the FFI boundary
Differential Revision: https://phab.mercurial-scm.org/D11486
Simon Sapin <simon.sapin@octobus.net> [Wed, 22 Sep 2021 11:28:52 +0200] rev 48058
rust: Add Python bindings for DirstateEntry as rustext.dirstate.DirstateItem
Differential Revision: https://phab.mercurial-scm.org/D11485