Mercurial > public > mercurial-scm > hg-stable
diff rust/hg-core/src/revlog/node.rs @ 44419:5ac1eecc9c64
rust-nodemap: core implementation for shortest
In this implementation, we just make `lookup()` return also the number
of steps that have been needed to come to a conclusion from the
nodetree data, and `validate_candidate()` takes care of the special
cases related to `NULL_NODE`.
This way of doing minimizes code duplication, but it means that
the comparatively slower finding of first non zero nybble will run
for all calls to `find()` where it is not needed.
Still running on the file generated for the mozilla-central repository,
it seems indeed that we now get more ofter 320 ns than 310. The odds that
this could have a significant impact on real life Mercurial performance
are still looking low. Let's wait for actual benchmark runs to see if
an optimization is needed here.
Differential Revision: https://phab.mercurial-scm.org/D7819
| author | Georges Racinet <georges.racinet@octobus.net> |
|---|---|
| date | Tue, 18 Feb 2020 19:11:17 +0100 |
| parents | be52b7372ec2 |
| children | 166349510398 |
line wrap: on
line diff
--- a/rust/hg-core/src/revlog/node.rs Tue Feb 18 19:11:16 2020 +0100 +++ b/rust/hg-core/src/revlog/node.rs Tue Feb 18 19:11:17 2020 +0100 @@ -226,6 +226,36 @@ assert!(i < self.len()); get_nybble(self.buf, i) } + + /// Return the index first nybble that's different from `node` + /// + /// If the return value is `None` that means that `self` is + /// a prefix of `node`, but the current method is a bit slower + /// than `is_prefix_of`. + /// + /// Returned index is as in `get_nybble`, i.e., starting at 0. + pub fn first_different_nybble(&self, node: &Node) -> Option<usize> { + let buf = self.buf; + let until = if self.is_odd { + buf.len() - 1 + } else { + buf.len() + }; + for i in 0..until { + if buf[i] != node.data[i] { + if buf[i] & 0xf0 == node.data[i] & 0xf0 { + return Some(2 * i + 1); + } else { + return Some(2 * i); + } + } + } + if self.is_odd && buf[until] & 0xf0 != node.data[until] & 0xf0 { + Some(until * 2) + } else { + None + } + } } /// A shortcut for full `Node` references @@ -362,6 +392,36 @@ assert_eq!(prefix.borrow().get_nybble(7), 9); Ok(()) } + + #[test] + fn test_first_different_nybble_even_prefix() { + let prefix = NodePrefix::from_hex("12ca").unwrap(); + let prefref = prefix.borrow(); + let mut node = Node::from([0; NODE_BYTES_LENGTH]); + assert_eq!(prefref.first_different_nybble(&node), Some(0)); + node.data[0] = 0x13; + assert_eq!(prefref.first_different_nybble(&node), Some(1)); + node.data[0] = 0x12; + assert_eq!(prefref.first_different_nybble(&node), Some(2)); + node.data[1] = 0xca; + // now it is a prefix + assert_eq!(prefref.first_different_nybble(&node), None); + } + + #[test] + fn test_first_different_nybble_odd_prefix() { + let prefix = NodePrefix::from_hex("12c").unwrap(); + let prefref = prefix.borrow(); + let mut node = Node::from([0; NODE_BYTES_LENGTH]); + assert_eq!(prefref.first_different_nybble(&node), Some(0)); + node.data[0] = 0x13; + assert_eq!(prefref.first_different_nybble(&node), Some(1)); + node.data[0] = 0x12; + assert_eq!(prefref.first_different_nybble(&node), Some(2)); + node.data[1] = 0xca; + // now it is a prefix + assert_eq!(prefref.first_different_nybble(&node), None); + } } #[cfg(test)]