This is an archive of the discontinued Mercurial Phabricator instance.

Differential D7795

rust-nodemap: insert method
ClosedPublic

Authored by gracinet on Jan 6 2020, 2:25 PM.

Details

Reviewers
kevincox
marmoute
Group Reviewers
hg-reviewers
Commits
rHGd2da8667125b: rust-nodemap: insert method
Summary

In this implementation, we are in direct competition
with the C version: this Rust version will have a clear
startup advantage because it will read the data from disk,
but the insertion happens all in memory for both.

Diff Detail

Repository
rHG Mercurial
Branch
default
Lint
No Linters Available
Unit
No Unit Test Coverage

Event Timeline

gracinet created this revision.Jan 6 2020, 2:25 PM
gracinet updated this revision to Diff 19328.Jan 15 2020, 6:47 PM
kevincox accepted this revision.Jan 16 2020, 6:01 AM
kevincox added inline comments.
rust/hg-core/src/revlog/nodemap.rs
270

It looks like this return value could use some abstraction but maybe its best to wait until there are more users?

275

I don't quite understand. You have the immutable copy and the mutable copy but that is WAI right?

308

nybble is very vague. Is this deepest_nibble or something?

506

Should these be #[cfg(test)]? We can always remove it later if there is a valid production use but it makes new users think twice.

gracinet updated this revision to Diff 19635.Jan 27 2020, 10:49 AM
marmoute accepted this revision.Feb 7 2020, 2:13 PM
marmoute added a subscriber: marmoute.

The change seesm good to me. However kevincox proposal to use #[cfg(test)] for pad_node seems worth applying inflight.

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

In pratice this function should have very few user, and they will all be internal. So I am not sure we need something more advanced.

308

This seems to have been updated because the code no longer mention nible on that line.

506

This seems like a good idea.

marmoute updated this revision to Diff 20024.Feb 8 2020, 12:44 PM
durin42 added a comment.Feb 12 2020, 11:38 AM
In D7795#119774, @marmoute wrote:

The change seesm good to me. However kevincox proposal to use #[cfg(test)] for pad_node seems worth applying inflight.

For future reference, I'm going to add it here, but if you're going to the trouble of uploading a new revision, it would have been nice to do this and save reviewer toil.

gracinet added a commit: rHGd2da8667125b: rust-nodemap: insert method.Feb 12 2020, 2:25 PM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHGd2da8667125b: rust-nodemap: insert method (authored by gracinet). · Explain Why
This revision was automatically updated to reflect the committed changes.
marmoute added a comment.Feb 13 2020, 6:04 PM
In D7795#120551, @durin42 wrote:
In D7795#119774, @marmoute wrote:

The change seesm good to me. However kevincox proposal to use #[cfg(test)] for pad_node seems worth applying inflight.

For future reference, I'm going to add it here, but if you're going to the trouble of uploading a new revision, it would have been nice to do this and save reviewer toil.

I juste rebased the revision on a more modern tip. I did not actually touched anything inside it.

Revision Contents
Changeset List

PathPackages
Mrust/hg-core/src/revlog/nodemap.rs (272 lines)

Diff 19044

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

// Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net> // Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net>
// and Mercurial contributors // and Mercurial contributors
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
//! Indexing facilities for fast retrieval of `Revision` from `Node` //! Indexing facilities for fast retrieval of `Revision` from `Node`
//! //!
//! This provides a variation on the radix tree with valency 16 that is //! This provides a variation on the radix tree with valency 16 that is
//! provided as "nodetree" in revlog.c, ready for append-only persistence //! provided as "nodetree" in revlog.c, ready for append-only persistence
//! on disk. //! on disk.
//! //!
//! 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::{NodeError, NodePrefix, NodePrefixRef, Revision, RevlogIndex}; use super::{
node::get_nybble, Node, NodeError, NodePrefix, NodePrefixRef, Revision,
RevlogIndex,
};
use std::fmt; use std::fmt;
use std::ops::Deref; use std::ops::Deref;
use std::ops::Index; use std::ops::Index;
#[derive(Debug, PartialEq)] #[derive(Debug, PartialEq)]
pub enum NodeMapError { pub enum NodeMapError {
MultipleResults, MultipleResults,
InvalidNodePrefix(NodeError), InvalidNodePrefix(NodeError),
&self, &self,
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())
} }
} }
pub trait MutableNodeMap: NodeMap {
fn insert<I: RevlogIndex>(
&mut self,
index: &I,
node: &Node,
rev: Revision,
) -> Result<(), NodeMapError>;
}
/// Low level NodeTree [`Blocks`] elements /// Low level NodeTree [`Blocks`] elements
/// ///
/// These are exactly as for instance on persistent storage. /// These are exactly as for instance on persistent storage.
type RawElement = i32; type RawElement = i32;
/// High level representation of values in NodeTree /// High level representation of values in NodeTree
/// [`Blocks`](struct.Block.html) /// [`Blocks`](struct.Block.html)
/// ///
NodeTreeVisitor { NodeTreeVisitor {
nt: self, nt: self,
prefix: prefix, prefix: prefix,
visit: self.len() - 1, visit: self.len() - 1,
nybble_idx: 0, nybble_idx: 0,
done: false, done: false,
} }
} }
/// Return a mutable reference for `Block` at index `idx`.
///
/// If `idx` lies in the immutable area, then the reference is to
/// a newly appended copy.
///
/// Returns (new_idx, glen, mut_ref) where
///
/// - `new_idx` is the index of the mutable `Block`
/// - `mut_ref` is a mutable reference to the mutable Block.
/// - `glen` is the new length of `self.growable`
///
/// Note: the caller wouldn't be allowed to query `self.growable.len()`
/// itself because of the mutable borrow taken with the returned `Block`
fn mutable_block(&mut self, idx: usize) -> (usize, &mut Block, usize) {
kevincoxUnsubmitted
Not Done

It looks like this return value could use some abstraction but maybe its best to wait until there are more users?

kevincox: It looks like this return value could use some abstraction but maybe its best to wait until…
marmouteUnsubmitted
Not Done

In pratice this function should have very few user, and they will all be internal. So I am not sure we need something more advanced.

marmoute: In pratice this function should have very few user, and they will all be internal. So I am not…
let ro_blocks = &self.readonly;
let ro_len = ro_blocks.len();
let glen = self.growable.len();
if idx < ro_len {
// TODO OPTIM I think this makes two copies
kevincoxUnsubmitted
Not Done

I don't quite understand. You have the immutable copy and the mutable copy but that is WAI right?

kevincox: I don't quite understand. You have the immutable copy and the mutable copy but that is WAI…
self.growable.push(ro_blocks[idx].clone());
(glen + ro_len, &mut self.growable[glen], glen + 1)
} else if glen + ro_len == idx {
(idx, &mut self.root, glen)
} else {
(idx, &mut self.growable[idx - ro_len], glen)
}
}
/// Main insertion method
///
/// This will dive in the node tree to find the deepest `Block` for
/// `node`, split it as much as needed and record `node` in there.
/// The method then backtracks, updating references in all the visited
/// blocks from the root.
///
/// All the mutated `Block` are copied first to the growable part if
/// needed. That happens for those in the immutable part except the root.
pub fn insert<I: RevlogIndex>(
&mut self,
index: &I,
node: &Node,
rev: Revision,
) -> Result<(), NodeMapError> {
let ro_len = &self.readonly.len();
let mut visit_steps: Vec<(usize, u8, Option<Revision>)> = self
.visit(node.into())
.map(|(_leaf, visit, nybble, rev_opt)| (visit, nybble, rev_opt))
.collect();
let read_nybbles = visit_steps.len();
// visit_steps cannot be empty, since we always visit the root block
let (deepest_idx, mut nybble, rev_opt) = visit_steps.pop().unwrap();
kevincoxUnsubmitted
Not Done

nybble is very vague. Is this deepest_nibble or something?

kevincox: nybble is very vague. Is this deepest_nibble or something?
marmouteUnsubmitted
Not Done

This seems to have been updated because the code no longer mention nible on that line.

marmoute: This seems to have been updated because the code no longer mention nible on that line.
let (mut block_idx, mut block, mut glen) =
self.mutable_block(deepest_idx);
match rev_opt {
None => {
// Free slot in the deepest block: no splitting has to be done
block.write(nybble, Element::Rev(rev));
}
Some(old_rev) => {
let old_node = index.node(old_rev).ok_or_else(|| {
NodeMapError::RevisionNotInIndex(old_rev)
})?;
if old_node == node {
return Ok(()); // avoid creating lots of useless blocks
}
// Looping over the tail of nybbles in both nodes, creating
// new blocks until we find the difference
let mut new_block_idx = ro_len + glen;
for nybble_pos in read_nybbles..40 {
block.write(nybble, Element::Block(new_block_idx));
let new_nybble = get_nybble(nybble_pos, node);
let old_nybble = get_nybble(nybble_pos, old_node);
if old_nybble == new_nybble {
self.growable.push(Block::new());
block = &mut self.growable[glen];
glen += 1;
new_block_idx += 1;
nybble = new_nybble;
} else {
let mut new_block = Block::new();
new_block.write(old_nybble, Element::Rev(old_rev));
new_block.write(new_nybble, Element::Rev(rev));
self.growable.push(new_block);
break;
}
}
}
}
// Backtrack over visit steps to update references
while let Some((visited, nybble, _)) = visit_steps.pop() {
let to_write = Element::Block(block_idx);
if visit_steps.is_empty() {
self.root.write(nybble, to_write);
break;
}
let (new_idx, block, _) = self.mutable_block(visited);
if block.read(nybble) == to_write {
break;
}
block.write(nybble, to_write);
block_idx = new_idx;
}
Ok(())
}
} }
struct NodeTreeVisitor<'n, 'p> { struct NodeTreeVisitor<'n, 'p> {
nt: &'n NodeTree, nt: &'n NodeTree,
prefix: NodePrefixRef<'p>, prefix: NodePrefixRef<'p>,
visit: usize, visit: usize,
nybble_idx: usize, nybble_idx: usize,
done: bool, done: bool,
write!( write!(
f, f,
"readonly: {:?}, growable: {:?}, root: {:?}", "readonly: {:?}, growable: {:?}, root: {:?}",
readonly, self.growable, self.root readonly, self.growable, self.root
) )
} }
} }
impl Default for NodeTree {
/// Create a fully mutable empty NodeTree
fn default() -> Self {
NodeTree::new(Box::new(Vec::new()))
}
}
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> {
self.lookup(prefix.clone()).and_then(|opt| { self.lookup(prefix.clone()).and_then(|opt| {
opt.map_or(Ok(None), |rev| has_prefix_or_none(idx, prefix, rev)) opt.map_or(Ok(None), |rev| has_prefix_or_none(idx, prefix, rev))
self.get(&rev) self.get(&rev)
} }
fn len(&self) -> usize { fn len(&self) -> usize {
self.len() self.len()
} }
} }
/// Pad hexadecimal Node prefix with zeros on the right, then insert /// Pad hexadecimal Node prefix with zeros on the right
/// ///
/// This is just to avoid having to repeatedly write 40 hexadecimal /// This is just to avoid having to repeatedly write 40 hexadecimal
/// digits for test data. /// digits for test data.
fn pad_node(hex: &str) -> Node {
node_from_hex(&format!("{:0<40}", hex)).unwrap()
}
kevincoxUnsubmitted
Not Done

Should these be #[cfg(test)]? We can always remove it later if there is a valid production use but it makes new users think twice.

kevincox: Should these be `#[cfg(test)]`? We can always remove it later if there is a valid production…
marmouteUnsubmitted
Not Done

This seems like a good idea.

marmoute: This seems like a good idea.
/// Pad hexadecimal Node prefix with zeros on the right, then insert
fn pad_insert(idx: &mut TestIndex, rev: Revision, hex: &str) { fn pad_insert(idx: &mut TestIndex, rev: Revision, hex: &str) {
idx.insert(rev, node_from_hex(&format!("{:0<40}", hex)).unwrap()); idx.insert(rev, pad_node(hex));
} }
fn sample_nodetree() -> NodeTree { fn sample_nodetree() -> NodeTree {
NodeTree::from(vec![ NodeTree::from(vec![
block![0: Rev(9)], block![0: Rev(9)],
block![0: Rev(0), 1: Rev(9)], block![0: Rev(0), 1: Rev(9)],
block![0: Block(1), 1:Rev(1)], block![0: Block(1), 1:Rev(1)],
]) ])
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.find_hex(&idx, "00")?, Some(0)); assert_eq!(nt.find_hex(&idx, "00")?, Some(0));
assert_eq!(nt.find_hex(&idx, "01")?, Some(9)); assert_eq!(nt.find_hex(&idx, "01")?, Some(9));
Ok(()) Ok(())
} }
struct TestNtIndex {
index: TestIndex,
nt: NodeTree,
}
impl TestNtIndex {
fn new() -> Self {
TestNtIndex {
index: HashMap::new(),
nt: NodeTree::default(),
}
}
fn insert(
&mut self,
rev: Revision,
hex: &str,
) -> Result<(), NodeMapError> {
let node = pad_node(hex);
self.index.insert(rev, node);
self.nt.insert(&self.index, &node, rev)?;
Ok(())
}
fn find_hex(
&self,
prefix: &str,
) -> Result<Option<Revision>, NodeMapError> {
self.nt.find_hex(&self.index, prefix)
}
/// Drain `added` and restart a new one
fn commit(self) -> Self {
let mut as_vec: Vec<Block> =
self.nt.readonly.iter().map(|block| block.clone()).collect();
as_vec.extend(self.nt.growable);
as_vec.push(self.nt.root);
Self {
index: self.index,
nt: NodeTree::from(as_vec).into(),
}
}
}
#[test]
fn test_insert_full_mutable() -> Result<(), NodeMapError> {
let mut idx = TestNtIndex::new();
idx.insert(0, "1234")?;
assert_eq!(idx.find_hex("1")?, Some(0));
assert_eq!(idx.find_hex("12")?, Some(0));
// let's trigger a simple split
idx.insert(1, "1a34")?;
assert_eq!(idx.nt.growable.len(), 1);
assert_eq!(idx.find_hex("12")?, Some(0));
assert_eq!(idx.find_hex("1a")?, Some(1));
// reinserting is a no_op
idx.insert(1, "1a34")?;
assert_eq!(idx.nt.growable.len(), 1);
assert_eq!(idx.find_hex("12")?, Some(0));
assert_eq!(idx.find_hex("1a")?, Some(1));
idx.insert(2, "1a01")?;
assert_eq!(idx.nt.growable.len(), 2);
assert_eq!(idx.find_hex("1a"), Err(NodeMapError::MultipleResults));
assert_eq!(idx.find_hex("12")?, Some(0));
assert_eq!(idx.find_hex("1a3")?, Some(1));
assert_eq!(idx.find_hex("1a0")?, Some(2));
assert_eq!(idx.find_hex("1a12")?, None);
// now let's make it split and create more than one additional block
idx.insert(3, "1a345")?;
assert_eq!(idx.nt.growable.len(), 4);
assert_eq!(idx.find_hex("1a340")?, Some(1));
assert_eq!(idx.find_hex("1a345")?, Some(3));
assert_eq!(idx.find_hex("1a341")?, None);
Ok(())
}
#[test]
fn test_insert_extreme_splitting() -> Result<(), NodeMapError> {
// check that the splitting loop is long enough
let mut nt_idx = TestNtIndex::new();
let nt = &mut nt_idx.nt;
let idx = &mut nt_idx.index;
let node0 = [4; 20];
let mut node1 = [4; 20];
node1[19] = 5;
idx.insert(0, node0);
nt.insert(idx, &node0, 0)?;
idx.insert(1, node1);
nt.insert(idx, &node1, 1)?;
assert_eq!(nt.find_bin(idx, (&node0).into())?, Some(0));
assert_eq!(nt.find_bin(idx, (&node1).into())?, Some(1));
Ok(())
}
#[test]
fn test_insert_partly_immutable() -> Result<(), NodeMapError> {
let mut idx = TestNtIndex::new();
idx.insert(0, "1234")?;
idx.insert(1, "1235")?;
idx.insert(2, "131")?;
idx.insert(3, "cafe")?;
let mut idx = idx.commit();
assert_eq!(idx.find_hex("1234")?, Some(0));
assert_eq!(idx.find_hex("1235")?, Some(1));
assert_eq!(idx.find_hex("131")?, Some(2));
assert_eq!(idx.find_hex("cafe")?, Some(3));
idx.insert(4, "123A")?;
assert_eq!(idx.find_hex("1234")?, Some(0));
assert_eq!(idx.find_hex("1235")?, Some(1));
assert_eq!(idx.find_hex("131")?, Some(2));
assert_eq!(idx.find_hex("cafe")?, Some(3));
assert_eq!(idx.find_hex("123A")?, Some(4));
idx.insert(5, "c0")?;
assert_eq!(idx.find_hex("cafe")?, Some(3));
assert_eq!(idx.find_hex("c0")?, Some(5));
assert_eq!(idx.find_hex("c1")?, None);
assert_eq!(idx.find_hex("1234")?, Some(0));
Ok(())
}
} }