This is an archive of the discontinued Mercurial Phabricator instance.

Differential D7819

rust-nodemap: core implementation for shortest
ClosedPublic

Authored by gracinet on Jan 10 2020, 10:04 AM.

Details

Reviewers
kevincox
marmoute
Group Reviewers
hg-reviewers
Commits
rHG5ac1eecc9c64: rust-nodemap: core implementation for shortest
rHG0e8a9c0fbc8c: rust-nodemap: core implementation for shortest
Summary

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.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

gracinet created this revision.Jan 10 2020, 10:04 AM
gracinet updated this revision to Diff 19331.Jan 15 2020, 6:48 PM
kevincox accepted this revision.Jan 16 2020, 7:24 AM
kevincox added inline comments.
rust/hg-core/src/revlog/nodemap.rs
431–444

Can you describe the return value in the doc comment.

698

How about unique_bin_prefix_len?

898

unique_bin_prefix_len?

martinvonz added a subscriber: martinvonz.Jan 22 2020, 1:22 PM
martinvonz added inline comments.
rust/hg-core/src/revlog/nodemap.rs
96

can the explicit lifetime be dropped?

319–328

s/cand/candidate/? I prefer to avoid unusual abbreviations.

gracinet added inline comments.Jan 22 2020, 1:28 PM
rust/hg-core/src/revlog/nodemap.rs
698

I have personally nothing against this, and actually find this shortest not to be clear, but… it's also the name in the C implementation and the Python API, IIRC.

@martinvonz I see you subscribed, what do you think ?

martinvonz added inline comments.Jan 22 2020, 1:39 PM
rust/hg-core/src/revlog/nodemap.rs
698

I'm fine with either. We'll expose it as "shortest" in the python API anyway, I assume. Feel free to change as far as I'm concerned.

gracinet updated this revision to Diff 19639.Jan 27 2020, 10:50 AM
gracinet marked 3 inline comments as done.Jan 27 2020, 11:08 AM
gracinet added inline comments.
rust/hg-core/src/revlog/nodemap.rs
431–444

Done

698

Okay, I've settled with unique_prefix_len_bin etc, keeping the convention that it's something_bin, something_hex, etc.

gracinet marked an inline comment as done.Jan 27 2020, 11:55 AM
gracinet updated this revision to Diff 19640.
marmoute accepted this revision.Feb 7 2020, 3:03 PM
marmoute added a subscriber: marmoute.

It seems like all the feedback have been applied, and the changeset looks good to me.

Alphare updated this revision to Diff 20218.Feb 14 2020, 6:02 AM
Alphare updated this revision to Diff 20237.Feb 15 2020, 6:50 AM
Alphare updated this revision to Diff 20278.Feb 24 2020, 5:13 AM
Alphare updated this revision to Diff 20283.Feb 24 2020, 8:15 AM
gracinet added a commit: rHG0e8a9c0fbc8c: rust-nodemap: core implementation for shortest.Feb 26 2020, 10:33 AM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHG0e8a9c0fbc8c: rust-nodemap: core implementation for shortest (authored by gracinet). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 20313

rust/hg-core/src/revlog/node.rs

/// Retrieve the `i`th half-byte from the prefix. /// Retrieve the `i`th half-byte from the prefix.
/// ///
/// This is also the `i`th hexadecimal digit in numeric form, /// This is also the `i`th hexadecimal digit in numeric form,
/// also called a [nybble](https://en.wikipedia.org/wiki/Nibble). /// also called a [nybble](https://en.wikipedia.org/wiki/Nibble).
pub fn get_nybble(&self, i: usize) -> u8 { pub fn get_nybble(&self, i: usize) -> u8 {
assert!(i < self.len()); assert!(i < self.len());
get_nybble(self.buf, i) 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 /// A shortcut for full `Node` references
impl<'a> From<&'a Node> for NodePrefixRef<'a> { impl<'a> From<&'a Node> for NodePrefixRef<'a> {
fn from(node: &'a Node) -> Self { fn from(node: &'a Node) -> Self {
NodePrefixRef { NodePrefixRef {
buf: &node.data, buf: &node.data,
is_odd: false, is_odd: false,
#[test] #[test]
fn test_get_nybble() -> Result<(), NodeError> { fn test_get_nybble() -> Result<(), NodeError> {
let prefix = NodePrefix::from_hex("dead6789cafe")?; let prefix = NodePrefix::from_hex("dead6789cafe")?;
assert_eq!(prefix.borrow().get_nybble(0), 13); assert_eq!(prefix.borrow().get_nybble(0), 13);
assert_eq!(prefix.borrow().get_nybble(7), 9); assert_eq!(prefix.borrow().get_nybble(7), 9);
Ok(()) 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)] #[cfg(test)]
pub use tests::hex_pad_right; pub use tests::hex_pad_right;

rust/hg-core/src/revlog/nodemap.rs

//! Following existing implicit conventions, the "nodemap" terminology //! Following existing implicit conventions, the "nodemap" terminology
//! is used in a more abstract context. //! is used in a more abstract context.
use super::{ use super::{
node::NULL_NODE, Node, NodeError, NodePrefix, NodePrefixRef, Revision, node::NULL_NODE, Node, NodeError, NodePrefix, NodePrefixRef, Revision,
RevlogIndex, NULL_REVISION, RevlogIndex, NULL_REVISION,
}; };
use std::cmp::max;
use std::fmt; use std::fmt;
use std::mem; use std::mem;
use std::ops::Deref; use std::ops::Deref;
use std::ops::Index; use std::ops::Index;
use std::slice; use std::slice;
#[derive(Debug, PartialEq)] #[derive(Debug, PartialEq)]
pub enum NodeMapError { pub enum NodeMapError {
/// Find the unique Revision whose `Node` hexadecimal string representation /// Find the unique Revision whose `Node` hexadecimal string representation
/// starts with a given prefix /// starts with a given prefix
/// ///
/// If no Revision matches the given prefix, `Ok(None)` is returned. /// If no Revision matches the given prefix, `Ok(None)` is returned.
/// ///
/// If several Revisions match the given prefix, a [`MultipleResults`] /// If several Revisions match the given prefix, a [`MultipleResults`]
/// error is returned. /// error is returned.
fn find_hex( fn find_hex(
&self, &self,
martinvonzUnsubmitted
Not Done

can the explicit lifetime be dropped?

martinvonz: can the explicit lifetime be dropped?
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
prefix: &str, prefix: &str,
) -> Result<Option<Revision>, NodeMapError> { ) -> Result<Option<Revision>, NodeMapError> {
self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow()) self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
} }
/// Give the size of the shortest node prefix that determines
/// the revision uniquely.
///
/// From a binary node prefix, if it is matched in the node map, this
/// returns the number of hexadecimal digits that would had sufficed
/// to find the revision uniquely.
///
/// Returns `None` if no `Revision` could be found for the prefix.
///
/// If several Revisions match the given prefix, a [`MultipleResults`]
/// error is returned.
fn unique_prefix_len_bin<'a>(
&self,
idx: &impl RevlogIndex,
node_prefix: NodePrefixRef<'a>,
) -> Result<Option<usize>, NodeMapError>;
/// Same as `unique_prefix_len_bin`, with the hexadecimal representation
/// of the prefix as input.
fn unique_prefix_len_hex(
&self,
idx: &impl RevlogIndex,
prefix: &str,
) -> Result<Option<usize>, NodeMapError> {
self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
}
/// Same as `unique_prefix_len_bin`, with a full `Node` as input
fn unique_prefix_len_node(
&self,
idx: &impl RevlogIndex,
node: &Node,
) -> Result<Option<usize>, NodeMapError> {
self.unique_prefix_len_bin(idx, node.into())
}
} }
pub trait MutableNodeMap: NodeMap { pub trait MutableNodeMap: NodeMap {
fn insert<I: RevlogIndex>( fn insert<I: RevlogIndex>(
&mut self, &mut self,
index: &I, index: &I,
node: &Node, node: &Node,
rev: Revision, rev: Revision,
/// validate that the candidate's node starts indeed with given prefix, /// validate that the candidate's node starts indeed with given prefix,
/// and treat ambiguities related to `NULL_REVISION`. /// and treat ambiguities related to `NULL_REVISION`.
/// ///
/// From the data in the NodeTree, one can only conclude that some /// From the data in the NodeTree, one can only conclude that some
/// revision is the only one for a *subprefix* of the one being looked up. /// revision is the only one for a *subprefix* of the one being looked up.
fn validate_candidate( fn validate_candidate(
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
prefix: NodePrefixRef, prefix: NodePrefixRef,
rev: Option<Revision>, candidate: (Option<Revision>, usize),
) -> Result<Option<Revision>, NodeMapError> { ) -> Result<(Option<Revision>, usize), NodeMapError> {
if prefix.is_prefix_of(&NULL_NODE) { let (rev, steps) = candidate;
// NULL_REVISION always matches a prefix made only of zeros if let Some(nz_nybble) = prefix.first_different_nybble(&NULL_NODE) {
rev.map_or(Ok((None, steps)), |r| {
has_prefix_or_none(idx, prefix, r)
.map(|opt| (opt, max(steps, nz_nybble + 1)))
})
} else {
// the prefix is only made of zeros; NULL_REVISION always matches it
martinvonzUnsubmitted
Not Done

s/cand/candidate/? I prefer to avoid unusual abbreviations.

martinvonz: s/cand/candidate/? I prefer to avoid unusual abbreviations.
// and any other *valid* result is an ambiguity // and any other *valid* result is an ambiguity
match rev { match rev {
None => Ok(Some(NULL_REVISION)), None => Ok((Some(NULL_REVISION), steps + 1)),
Some(r) => match has_prefix_or_none(idx, prefix, r)? { Some(r) => match has_prefix_or_none(idx, prefix, r)? {
None => Ok(Some(NULL_REVISION)), None => Ok((Some(NULL_REVISION), steps + 1)),
_ => Err(NodeMapError::MultipleResults), _ => Err(NodeMapError::MultipleResults),
}, },
} }
} else {
rev.map_or(Ok(None), |r| has_prefix_or_none(idx, prefix, r))
} }
} }
impl NodeTree { impl NodeTree {
/// Initiate a NodeTree from an immutable slice-like of `Block` /// Initiate a NodeTree from an immutable slice-like of `Block`
/// ///
/// We keep `readonly` and clone its root block if it isn't empty. /// We keep `readonly` and clone its root block if it isn't empty.
fn new(readonly: Box<dyn Deref<Target = [Block]> + Send>) -> Self { fn new(readonly: Box<dyn Deref<Target = [Block]> + Send>) -> Self {
/// ///
/// A `NodeTree` always has at least the mutable root block. /// A `NodeTree` always has at least the mutable root block.
#[allow(dead_code)] #[allow(dead_code)]
fn is_empty(&self) -> bool { fn is_empty(&self) -> bool {
false false
} }
/// Main working method for `NodeTree` searches /// Main working method for `NodeTree` searches
fn lookup<'p>( ///
/// The first returned value is the result of analysing `NodeTree` data
/// *alone*: whereas `None` guarantees that the given prefix is absent
/// from the `NodeTree` data (but still could match `NULL_NODE`), with
/// `Some(rev)`, it is to be understood that `rev` is the unique `Revision`
/// that could match the prefix. Actually, all that can be inferred from
/// the `NodeTree` data is that `rev` is the revision with the longest
/// common node prefix with the given prefix.
///
/// The second returned value is the size of the smallest subprefix
/// of `prefix` that would give the same result, i.e. not the
/// `MultipleResults` error variant (again, using only the data of the
/// `NodeTree`).
fn lookup(
kevincoxUnsubmitted
Not Done

Can you describe the return value in the doc comment.

kevincox: Can you describe the return value in the doc comment.
gracinetAuthorUnsubmitted
Done

Done

gracinet: Done
&self, &self,
prefix: NodePrefixRef<'p>, prefix: NodePrefixRef,
) -> Result<Option<Revision>, NodeMapError> { ) -> Result<(Option<Revision>, usize), NodeMapError> {
for visit_item in self.visit(prefix) { for (i, visit_item) in self.visit(prefix).enumerate() {
if let Some(opt) = visit_item.final_revision() { if let Some(opt) = visit_item.final_revision() {
return Ok(opt); return Ok((opt, i + 1));
} }
} }
Err(NodeMapError::MultipleResults) Err(NodeMapError::MultipleResults)
} }
fn visit<'n, 'p>( fn visit<'n, 'p>(
&'n self, &'n self,
prefix: NodePrefixRef<'p>, prefix: NodePrefixRef<'p>,
impl NodeMap for NodeTree { impl NodeMap for NodeTree {
fn find_bin<'a>( fn find_bin<'a>(
&self, &self,
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
prefix: NodePrefixRef<'a>, prefix: NodePrefixRef<'a>,
) -> Result<Option<Revision>, NodeMapError> { ) -> Result<Option<Revision>, NodeMapError> {
validate_candidate(idx, prefix.clone(), self.lookup(prefix)?) validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
.map(|(opt, _shortest)| opt)
}
fn unique_prefix_len_bin<'a>(
kevincoxUnsubmitted
Done

How about unique_bin_prefix_len?

kevincox: How about `unique_bin_prefix_len`?
gracinetAuthorUnsubmitted
Done

I have personally nothing against this, and actually find this shortest not to be clear, but… it's also the name in the C implementation and the Python API, IIRC.

@martinvonz I see you subscribed, what do you think ?

gracinet: I have personally nothing against this, and actually find this `shortest` not to be clear, but……
martinvonzUnsubmitted
Done

I'm fine with either. We'll expose it as "shortest" in the python API anyway, I assume. Feel free to change as far as I'm concerned.

martinvonz: I'm fine with either. We'll expose it as "shortest" in the python API anyway, I assume. Feel…
gracinetAuthorUnsubmitted
Done

Okay, I've settled with unique_prefix_len_bin etc, keeping the convention that it's something_bin, something_hex, etc.

gracinet: Okay, I've settled with `unique_prefix_len_bin` etc, keeping the convention that it's…
&self,
idx: &impl RevlogIndex,
prefix: NodePrefixRef<'a>,
) -> Result<Option<usize>, NodeMapError> {
validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
.map(|(opt, shortest)| opt.map(|_rev| shortest))
} }
} }
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use super::NodeMapError::*; use super::NodeMapError::*;
use super::*; use super::*;
use crate::revlog::node::{hex_pad_right, Node}; use crate::revlog::node::{hex_pad_right, Node};
pad_insert(&mut idx, 0, "00a"); pad_insert(&mut idx, 0, "00a");
let nt = sample_nodetree(); let nt = sample_nodetree();
assert_eq!(nt.find_hex(&idx, "0"), Err(MultipleResults)); assert_eq!(nt.find_hex(&idx, "0"), Err(MultipleResults));
assert_eq!(nt.find_hex(&idx, "01"), Ok(Some(9))); assert_eq!(nt.find_hex(&idx, "01"), Ok(Some(9)));
assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults)); assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults));
assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0))); assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0)));
assert_eq!(nt.unique_prefix_len_hex(&idx, "00a"), Ok(Some(3)));
assert_eq!(nt.find_hex(&idx, "000"), Ok(Some(NULL_REVISION))); assert_eq!(nt.find_hex(&idx, "000"), Ok(Some(NULL_REVISION)));
} }
#[test] #[test]
fn test_mutated_find() -> Result<(), NodeMapError> { fn test_mutated_find() -> Result<(), NodeMapError> {
let mut idx = TestIndex::new(); let mut idx = TestIndex::new();
pad_insert(&mut idx, 9, "012"); pad_insert(&mut idx, 9, "012");
pad_insert(&mut idx, 0, "00a"); pad_insert(&mut idx, 0, "00a");
pad_insert(&mut idx, 2, "cafe"); pad_insert(&mut idx, 2, "cafe");
pad_insert(&mut idx, 3, "15"); pad_insert(&mut idx, 3, "15");
pad_insert(&mut idx, 1, "10"); pad_insert(&mut idx, 1, "10");
let nt = NodeTree { let nt = NodeTree {
readonly: sample_nodetree().readonly, readonly: sample_nodetree().readonly,
growable: vec![block![0: Rev(1), 5: Rev(3)]], growable: vec![block![0: Rev(1), 5: Rev(3)]],
root: block![0: Block(1), 1:Block(3), 12: Rev(2)], root: block![0: Block(1), 1:Block(3), 12: Rev(2)],
}; };
assert_eq!(nt.find_hex(&idx, "10")?, Some(1)); assert_eq!(nt.find_hex(&idx, "10")?, Some(1));
assert_eq!(nt.find_hex(&idx, "c")?, Some(2)); assert_eq!(nt.find_hex(&idx, "c")?, Some(2));
assert_eq!(nt.unique_prefix_len_hex(&idx, "c")?, Some(1));
assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults)); assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults));
assert_eq!(nt.find_hex(&idx, "000")?, Some(NULL_REVISION)); assert_eq!(nt.find_hex(&idx, "000")?, Some(NULL_REVISION));
assert_eq!(nt.unique_prefix_len_hex(&idx, "000")?, Some(3));
assert_eq!(nt.find_hex(&idx, "01")?, Some(9)); assert_eq!(nt.find_hex(&idx, "01")?, Some(9));
Ok(()) Ok(())
} }
struct TestNtIndex { struct TestNtIndex {
index: TestIndex, index: TestIndex,
nt: NodeTree, nt: NodeTree,
} }
fn find_hex( fn find_hex(
&self, &self,
prefix: &str, prefix: &str,
) -> Result<Option<Revision>, NodeMapError> { ) -> Result<Option<Revision>, NodeMapError> {
self.nt.find_hex(&self.index, prefix) self.nt.find_hex(&self.index, prefix)
} }
fn unique_prefix_len_hex(
kevincoxUnsubmitted
Done

unique_bin_prefix_len?

kevincox: `unique_bin_prefix_len`?
&self,
prefix: &str,
) -> Result<Option<usize>, NodeMapError> {
self.nt.unique_prefix_len_hex(&self.index, prefix)
}
/// Drain `added` and restart a new one /// Drain `added` and restart a new one
fn commit(self) -> Self { fn commit(self) -> Self {
let mut as_vec: Vec<Block> = let mut as_vec: Vec<Block> =
self.nt.readonly.iter().map(|block| block.clone()).collect(); self.nt.readonly.iter().map(|block| block.clone()).collect();
as_vec.extend(self.nt.growable); as_vec.extend(self.nt.growable);
as_vec.push(self.nt.root); as_vec.push(self.nt.root);
Self { Self {
assert_eq!(idx.find_hex("1a340")?, Some(1)); assert_eq!(idx.find_hex("1a340")?, Some(1));
assert_eq!(idx.find_hex("1a345")?, Some(3)); assert_eq!(idx.find_hex("1a345")?, Some(3));
assert_eq!(idx.find_hex("1a341")?, None); assert_eq!(idx.find_hex("1a341")?, None);
Ok(()) Ok(())
} }
#[test] #[test]
fn test_unique_prefix_len_zero_prefix() {
let mut idx = TestNtIndex::new();
idx.insert(0, "00000abcd").unwrap();
assert_eq!(idx.find_hex("000"), Err(NodeMapError::MultipleResults));
// in the nodetree proper, this will be found at the first nybble
// yet the correct answer for unique_prefix_len is not 1, nor 1+1,
// but the first difference with `NULL_NODE`
assert_eq!(idx.unique_prefix_len_hex("00000a"), Ok(Some(6)));
assert_eq!(idx.unique_prefix_len_hex("00000ab"), Ok(Some(6)));
// same with odd result
idx.insert(1, "00123").unwrap();
assert_eq!(idx.unique_prefix_len_hex("001"), Ok(Some(3)));
assert_eq!(idx.unique_prefix_len_hex("0012"), Ok(Some(3)));
// these are unchanged of course
assert_eq!(idx.unique_prefix_len_hex("00000a"), Ok(Some(6)));
assert_eq!(idx.unique_prefix_len_hex("00000ab"), Ok(Some(6)));
}
#[test]
fn test_insert_extreme_splitting() -> Result<(), NodeMapError> { fn test_insert_extreme_splitting() -> Result<(), NodeMapError> {
// check that the splitting loop is long enough // check that the splitting loop is long enough
let mut nt_idx = TestNtIndex::new(); let mut nt_idx = TestNtIndex::new();
let nt = &mut nt_idx.nt; let nt = &mut nt_idx.nt;
let idx = &mut nt_idx.index; let idx = &mut nt_idx.index;
let node0_hex = hex_pad_right("444444"); let node0_hex = hex_pad_right("444444");
let mut node1_hex = hex_pad_right("444444").clone(); let mut node1_hex = hex_pad_right("444444").clone();