Mercurial > hg
view mercurial/dirstateutils/v2.py @ 51594:e3a5ec2d236a
outgoing: rework the handling of the `missingroots` case to be faster
The previous implementation was slow, to the point it was taking a significant
amount of `hg bundle --type none-streamv2` call. We rework the code to compute
the same value much faster, making the operation disappear from the `hg bundle
--type none-streamv2` profile. Someone would remark that producing a streamclone
does not requires an `outgoing` object. However that is a matter for another
day. There is other user of `missingroots` (non stream `hg bundle` call for
example), and they will also benefit from this rework.
We implement an old TODO in the process, directly computing the missing and
common attribute as we have most element at hand already.
### benchmark.name = hg.command.bundle
# bin-env-vars.hg.flavor = default
# bin-env-vars.hg.py-re2-module = default
# benchmark.variants.revs = all
# benchmark.variants.type = none-streamv2
## data-env-vars.name = heptapod-public-2024-03-25-zstd-sparse-revlog
before: 7.750458
after: 6.665565 (-14.00%, -1.08)
## data-env-vars.name = mercurial-public-2024-03-22-zstd-sparse-revlog
before: 0.700229
after: 0.496050 (-29.16%, -0.20)
## data-env-vars.name = mozilla-try-2023-03-22-zstd-sparse-revlog
before: 346.508952
after: 316.749699 (-8.59%, -29.76)
## data-env-vars.name = pypy-2024-03-22-zstd-sparse-revlog
before: 3.401700
after: 2.915810 (-14.28%, -0.49)
## data-env-vars.name = tryton-public-2024-03-22-zstd-sparse-revlog
before: 1.870798
after: 1.461583 (-21.87%, -0.41)
note: this whole `missingroots` of outgoing has a limited number of callers and
could likely be replace by something simpler (like taking an explicit
"missing_revs" set for example). However this is a wider change and we focus on
a small impact, quick rework that does not change the API for now.
author | Pierre-Yves David <pierre-yves.david@octobus.net> |
---|---|
date | Tue, 09 Apr 2024 22:36:35 +0200 |
parents | fc719967efd0 |
children | 278af66e6595 |
line wrap: on
line source
# v2.py - Pure-Python implementation of the dirstate-v2 file format # # Copyright Mercurial Contributors # # This software may be used and distributed according to the terms of the # GNU General Public License version 2 or any later version. import struct from ..thirdparty import attr from .. import error, policy parsers = policy.importmod('parsers') # Must match the constant of the same name in # `rust/hg-core/src/dirstate_tree/on_disk.rs` TREE_METADATA_SIZE = 44 NODE_SIZE = 44 # Must match the `TreeMetadata` Rust struct in # `rust/hg-core/src/dirstate_tree/on_disk.rs`. See doc-comments there. # # * 4 bytes: start offset of root nodes # * 4 bytes: number of root nodes # * 4 bytes: total number of nodes in the tree that have an entry # * 4 bytes: total number of nodes in the tree that have a copy source # * 4 bytes: number of bytes in the data file that are not used anymore # * 4 bytes: unused # * 20 bytes: SHA-1 hash of ignore patterns TREE_METADATA = struct.Struct('>LLLLL4s20s') # Must match the `Node` Rust struct in # `rust/hg-core/src/dirstate_tree/on_disk.rs`. See doc-comments there. # # * 4 bytes: start offset of full path # * 2 bytes: length of the full path # * 2 bytes: length within the full path before its "base name" # * 4 bytes: start offset of the copy source if any, or zero for no copy source # * 2 bytes: length of the copy source if any, or unused # * 4 bytes: start offset of child nodes # * 4 bytes: number of child nodes # * 4 bytes: number of descendant nodes that have an entry # * 4 bytes: number of descendant nodes that have a "tracked" state # * 1 byte: flags # * 4 bytes: expected size # * 4 bytes: mtime seconds # * 4 bytes: mtime nanoseconds NODE = struct.Struct('>LHHLHLLLLHlll') assert TREE_METADATA_SIZE == TREE_METADATA.size assert NODE_SIZE == NODE.size # match constant in mercurial/pure/parsers.py DIRSTATE_V2_DIRECTORY = 1 << 13 def parse_dirstate(map, copy_map, data, tree_metadata): """parse a full v2-dirstate from a binary data into dictionaries: - map: a {path: entry} mapping that will be filled - copy_map: a {path: copy-source} mapping that will be filled - data: a binary blob contains v2 nodes data - tree_metadata:: a binary blob of the top level node (from the docket) """ ( root_nodes_start, root_nodes_len, _nodes_with_entry_count, _nodes_with_copy_source_count, _unreachable_bytes, _unused, _ignore_patterns_hash, ) = TREE_METADATA.unpack(tree_metadata) parse_nodes(map, copy_map, data, root_nodes_start, root_nodes_len) def parse_nodes(map, copy_map, data, start, len): """parse <len> nodes from <data> starting at offset <start> This is used by parse_dirstate to recursively fill `map` and `copy_map`. All directory specific information is ignored and do not need any processing (DIRECTORY, ALL_UNKNOWN_RECORDED, ALL_IGNORED_RECORDED) """ for i in range(len): node_start = start + NODE_SIZE * i node_bytes = slice_with_len(data, node_start, NODE_SIZE) ( path_start, path_len, _basename_start, copy_source_start, copy_source_len, children_start, children_count, _descendants_with_entry_count, _tracked_descendants_count, flags, size, mtime_s, mtime_ns, ) = NODE.unpack(node_bytes) # Parse child nodes of this node recursively parse_nodes(map, copy_map, data, children_start, children_count) item = parsers.DirstateItem.from_v2_data(flags, size, mtime_s, mtime_ns) if not item.any_tracked: continue path = slice_with_len(data, path_start, path_len) map[path] = item if copy_source_start: copy_map[path] = slice_with_len( data, copy_source_start, copy_source_len ) def slice_with_len(data, start, len): return data[start : start + len] @attr.s class Node: path = attr.ib() entry = attr.ib() parent = attr.ib(default=None) children_count = attr.ib(default=0) children_offset = attr.ib(default=0) descendants_with_entry = attr.ib(default=0) tracked_descendants = attr.ib(default=0) def pack(self, copy_map, paths_offset): path = self.path copy = copy_map.get(path) entry = self.entry path_start = paths_offset path_len = len(path) basename_start = path.rfind(b'/') + 1 # 0 if rfind returns -1 if copy is not None: copy_source_start = paths_offset + len(path) copy_source_len = len(copy) else: copy_source_start = 0 copy_source_len = 0 if entry is not None: flags, size, mtime_s, mtime_ns = entry.v2_data() else: # There are no mtime-cached directories in the Python implementation flags = DIRSTATE_V2_DIRECTORY size = 0 mtime_s = 0 mtime_ns = 0 return NODE.pack( path_start, path_len, basename_start, copy_source_start, copy_source_len, self.children_offset, self.children_count, self.descendants_with_entry, self.tracked_descendants, flags, size, mtime_s, mtime_ns, ) def pack_dirstate(map, copy_map): """ Pack `map` and `copy_map` into the dirstate v2 binary format and return the tuple of (data, metadata) bytearrays. The on-disk format expects a tree-like structure where the leaves are written first (and sorted per-directory), going up levels until the root node and writing that one to the docket. See more details on the on-disk format in `mercurial/helptext/internals/dirstate-v2`. Since both `map` and `copy_map` are flat dicts we need to figure out the hierarchy. This algorithm does so without having to build the entire tree in-memory: it only keeps the minimum number of nodes around to satisfy the format. # Algorithm explanation This explanation does not talk about the different counters for tracked descendants and storing the copies, but that work is pretty simple once this algorithm is in place. ## Building a subtree First, sort `map`: this makes it so the leaves of the tree are contiguous per directory (i.e. a/b/c and a/b/d will be next to each other in the list), and enables us to use the ordering of folders to have a "cursor" of the current folder we're in without ever going twice in the same branch of the tree. The cursor is a node that remembers its parent and any information relevant to the format (see the `Node` class), building the relevant part of the tree lazily. Then, for each file in `map`, move the cursor into the tree to the corresponding folder of the file: for example, if the very first file is "a/b/c", we start from `Node[""]`, create `Node["a"]` which points to its parent `Node[""]`, then create `Node["a/b"]`, which points to its parent `Node["a"]`. These nodes are kept around in a stack. If the next file in `map` is in the same subtree ("a/b/d" or "a/b/e/f"), we add it to the stack and keep looping with the same logic of creating the tree nodes as needed. If however the next file in `map` is *not* in the same subtree ("a/other", if we're still in the "a/b" folder), then we know that the subtree we're in is complete. ## Writing the subtree We have the entire subtree in the stack, so we start writing it to disk folder by folder. The way we write a folder is to pop the stack into a list until the folder changes, revert this list of direct children (to satisfy the format requirement that children be sorted). This process repeats until we hit the "other" subtree. An example: a dir1/b dir1/c dir2/dir3/d dir2/dir3/e dir2/f Would have us: - add to the stack until "dir2/dir3/e" - realize that "dir2/f" is in a different subtree - pop "dir2/dir3/e", "dir2/dir3/d", reverse them so they're sorted and pack them since the next entry is "dir2/dir3" - go back up to "dir2" - add "dir2/f" to the stack - realize we're done with the map - pop "dir2/f", "dir2/dir3" from the stack, reverse and pack them - go up to the root node, do the same to write "a", "dir1" and "dir2" in that order ## Special case for the root node The root node is not serialized in the format, but its information is written to the docket. Again, see more details on the on-disk format in `mercurial/helptext/internals/dirstate-v2`. """ data = bytearray() root_nodes_start = 0 root_nodes_len = 0 nodes_with_entry_count = 0 nodes_with_copy_source_count = 0 # Will always be 0 since this implementation always re-writes everything # to disk unreachable_bytes = 0 unused = b'\x00' * 4 # This is an optimization that's only useful for the Rust implementation ignore_patterns_hash = b'\x00' * 20 if len(map) == 0: tree_metadata = TREE_METADATA.pack( root_nodes_start, root_nodes_len, nodes_with_entry_count, nodes_with_copy_source_count, unreachable_bytes, unused, ignore_patterns_hash, ) return data, tree_metadata sorted_map = sorted(map.items(), key=lambda x: x[0].split(b"/")) # Use a stack to have to only remember the nodes we currently need # instead of building the entire tree in memory stack = [] current_node = Node(b"", None) stack.append(current_node) for index, (path, entry) in enumerate(sorted_map, 1): nodes_with_entry_count += 1 if path in copy_map: nodes_with_copy_source_count += 1 current_folder = get_folder(path) current_node = move_to_correct_node_in_tree( current_folder, current_node, stack ) current_node.children_count += 1 # Entries from `map` are never `None` if entry.tracked: current_node.tracked_descendants += 1 current_node.descendants_with_entry += 1 stack.append(Node(path, entry, current_node)) should_pack = True next_path = None if index < len(sorted_map): # Determine if the next entry is in the same sub-tree, if so don't # pack yet next_path = sorted_map[index][0] should_pack = not is_ancestor(next_path, current_folder) if should_pack: pack_directory_children(current_node, copy_map, data, stack) while stack and current_node.path != b"": # Go up the tree and write until we reach the folder of the next # entry (if any, otherwise the root) parent = current_node.parent in_ancestor_of_next_path = next_path is not None and ( is_ancestor(next_path, get_folder(stack[-1].path)) ) if parent is None or in_ancestor_of_next_path: break pack_directory_children(parent, copy_map, data, stack) current_node = parent # Special case for the root node since we don't write it to disk, only its # children to the docket current_node = stack.pop() assert current_node.path == b"", current_node.path assert len(stack) == 0, len(stack) tree_metadata = TREE_METADATA.pack( current_node.children_offset, current_node.children_count, nodes_with_entry_count, nodes_with_copy_source_count, unreachable_bytes, unused, ignore_patterns_hash, ) return data, tree_metadata def get_folder(path): """ Return the folder of the path that's given, an empty string for root paths. """ return path.rsplit(b'/', 1)[0] if b'/' in path else b'' def is_ancestor(path, maybe_ancestor): """Returns whether `maybe_ancestor` is an ancestor of `path`. >>> is_ancestor(b"a", b"") True >>> is_ancestor(b"a/b/c", b"a/b/c") False >>> is_ancestor(b"hgext3rd/__init__.py", b"hgext") False >>> is_ancestor(b"hgext3rd/__init__.py", b"hgext3rd") True """ if maybe_ancestor == b"": return True if path <= maybe_ancestor: return False path_components = path.split(b"/") ancestor_components = maybe_ancestor.split(b"/") return all(c == o for c, o in zip(path_components, ancestor_components)) def move_to_correct_node_in_tree(target_folder, current_node, stack): """ Move inside the dirstate node tree to the node corresponding to `target_folder`, creating the missing nodes along the way if needed. """ while target_folder != current_node.path: if is_ancestor(target_folder, current_node.path): # We need to go down a folder prefix = target_folder[len(current_node.path) :].lstrip(b'/') subfolder_name = prefix.split(b'/', 1)[0] if current_node.path: subfolder_path = current_node.path + b'/' + subfolder_name else: subfolder_path = subfolder_name next_node = stack[-1] if next_node.path == target_folder: # This folder is now a file and only contains removed entries # merge with the last node current_node = next_node else: current_node.children_count += 1 current_node = Node(subfolder_path, None, current_node) stack.append(current_node) else: # We need to go up a folder current_node = current_node.parent return current_node def pack_directory_children(node, copy_map, data, stack): """ Write the binary representation of the direct sorted children of `node` to `data` """ direct_children = [] while stack[-1].path != b"" and get_folder(stack[-1].path) == node.path: direct_children.append(stack.pop()) if not direct_children: raise error.ProgrammingError(b"no direct children for %r" % node.path) # Reverse the stack to get the correct sorted order direct_children.reverse() packed_children = bytearray() # Write the paths to `data`. Pack child nodes but don't write them yet for child in direct_children: packed = child.pack(copy_map=copy_map, paths_offset=len(data)) packed_children.extend(packed) data.extend(child.path) data.extend(copy_map.get(child.path, b"")) node.tracked_descendants += child.tracked_descendants node.descendants_with_entry += child.descendants_with_entry # Write the fixed-size child nodes all together node.children_offset = len(data) data.extend(packed_children)