This is an archive of the discontinued Mercurial Phabricator instance.

Differential D6260

rust-discovery: takefullsample() core implementation
ClosedPublic

Authored by gracinet on Apr 17 2019, 8:17 AM.

Details

Reviewers
kevincox
Group Reviewers
hg-reviewers
Commits
rHG6a8aec3f03df: rust-discovery: takefullsample() core implementation
Summary

take_full_sample() browses the undecided set in both directions: from
its roots as well as from its heads.

Following what's done on the Python side, we alter update_sample()
signature to take a closure returning an iterator: either ParentsIterator
or an iterator over the children found in children_cache. These constructs
should probably be split off in a separate module.

This is a first concrete example where a more abstract graph notion (probably
a trait) would be useful, as this is nothing but an operation on the reversed
DAG.

A similar motivation in the context of the discovery
process would be to replace the call to dagops::range in
add_missing_revisions() with a simple iteration over descendents, again an
operation on the reversed graph.

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.Apr 17 2019, 8:17 AM
gracinet added a comment.Apr 17 2019, 8:27 AM

As I've tried to make clear in the changeset description, this is still work in progress.

That being said, I wanted to put in on display because:

  • together with its descendants, it leads to a drop-in replacement for the Python partialdiscovery object
  • it's a good support for feedback on the question of more abstract DAG representations
  • the children cache leads to the same design problem as the undecided member attributed had (see D6231). I expect to get more across similar issues while translating Python code

Thanks !

kevincox accepted this revision.Apr 17 2019, 8:57 AM
kevincox added inline comments.
rust/hg-core/src/discovery.rs
107

You might also consider an enum

enum Parents {
  Zero,
  One(Revision),
  Two(Revision, Revision),
}

This also makes the iterator implementation a little clearer.

136

Can't you just call self.next() in both cases?

273

Generally I would just do this.

for &rev in self.undecided.as_ref().unwrap() {
274

Same.

gracinet updated this revision to Diff 15022.May 6 2019, 11:30 AM
gracinet marked an inline comment as done.May 6 2019, 11:38 AM

I think it's maybe ready to land in that form. In the future, I'd like to put this ParentsIterator in a more generic place, and IMHO, it should become part of an AbstractGraph trait, that could live in a graph module.

Ideally, we should even be able to generically reverse these graphs, so that the children iteration that's been done in this discovery process would just be the same, as seen from update_sample, but it's maybe too much asking.

rust/hg-core/src/discovery.rs
136

Yes that's what I actually did first, and then I tried this variant to see if it's faster. It may be a bit, but nothing worth doing in a first inclusion.

273

yes, same as in parent commit. Indeed it's a nicer way to iterate on references to Copy objects

274

for this one, I can actually use ParentsIterator, now, spares me the NULL_REVISION check

gracinet marked an inline comment as done.May 16 2019, 12:43 PM
Closed by commit rHG6a8aec3f03df: rust-discovery: takefullsample() core implementation (authored by gracinet). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mrust/hg-core/src/discovery.rs (213 lines)

Diff 15146

rust/hg-core/src/discovery.rs

type Rng = self::rand_pcg::Pcg32; type Rng = self::rand_pcg::Pcg32;
pub struct PartialDiscovery<G: Graph + Clone> { pub struct PartialDiscovery<G: Graph + Clone> {
target_heads: Option<Vec<Revision>>, target_heads: Option<Vec<Revision>>,
graph: G, // plays the role of self._repo graph: G, // plays the role of self._repo
common: MissingAncestors<G>, common: MissingAncestors<G>,
undecided: Option<HashSet<Revision>>, undecided: Option<HashSet<Revision>>,
children_cache: Option<HashMap<Revision, Vec<Revision>>>,
missing: HashSet<Revision>, missing: HashSet<Revision>,
rng: Rng, rng: Rng,
} }
pub struct DiscoveryStats { pub struct DiscoveryStats {
pub undecided: Option<usize>, pub undecided: Option<usize>,
} }
/// Update an existing sample to match the expected size /// Update an existing sample to match the expected size
/// ///
/// The sample is updated with revisions exponentially distant from each /// The sample is updated with revisions exponentially distant from each
/// element of `heads`. /// element of `heads`.
/// ///
/// If a target size is specified, the sampling will stop once this size is /// If a target size is specified, the sampling will stop once this size is
/// reached. Otherwise sampling will happen until roots of the <revs> set are /// reached. Otherwise sampling will happen until roots of the <revs> set are
/// reached. /// reached.
/// ///
/// - `revs`: set of revs we want to discover (if None, `assume` the whole dag /// - `revs`: set of revs we want to discover (if None, `assume` the whole dag
/// represented by `parentfn` /// represented by `parentfn`
/// - `heads`: set of DAG head revs /// - `heads`: set of DAG head revs
/// - `sample`: a sample to update /// - `sample`: a sample to update
/// - `parentfn`: a callable to resolve parents for a revision /// - `parentfn`: a callable to resolve parents for a revision
/// - `quicksamplesize`: optional target size of the sample /// - `quicksamplesize`: optional target size of the sample
fn update_sample( fn update_sample<I>(
revs: Option<&HashSet<Revision>>, revs: Option<&HashSet<Revision>>,
heads: impl IntoIterator<Item = Revision>, heads: impl IntoIterator<Item = Revision>,
sample: &mut HashSet<Revision>, sample: &mut HashSet<Revision>,
parentsfn: impl Fn(Revision) -> Result<[Revision; 2], GraphError>, parentsfn: impl Fn(Revision) -> Result<I, GraphError>,
quicksamplesize: Option<usize>, quicksamplesize: Option<usize>,
) -> Result<(), GraphError> { ) -> Result<(), GraphError>
where
I: Iterator<Item = Revision>,
{
let mut distances: HashMap<Revision, u32> = HashMap::new(); let mut distances: HashMap<Revision, u32> = HashMap::new();
let mut visit: VecDeque<Revision> = heads.into_iter().collect(); let mut visit: VecDeque<Revision> = heads.into_iter().collect();
let mut factor: u32 = 1; let mut factor: u32 = 1;
let mut seen: HashSet<Revision> = HashSet::new(); let mut seen: HashSet<Revision> = HashSet::new();
loop { loop {
let current = match visit.pop_front() { let current = match visit.pop_front() {
None => { None => {
break; break;
if d == factor { if d == factor {
sample.insert(current); sample.insert(current);
if let Some(sz) = quicksamplesize { if let Some(sz) = quicksamplesize {
if sample.len() >= sz { if sample.len() >= sz {
return Ok(()); return Ok(());
} }
} }
} }
for &p in &parentsfn(current)? { for p in parentsfn(current)? {
if p == NULL_REVISION {
continue;
}
if let Some(revs) = revs { if let Some(revs) = revs {
if !revs.contains(&p) { if !revs.contains(&p) {
continue; continue;
} }
} }
distances.entry(p).or_insert(d + 1); distances.entry(p).or_insert(d + 1);
visit.push_back(p); visit.push_back(p);
} }
} }
Ok(()) Ok(())
} }
struct ParentsIterator {
parents: [Revision; 2],
cur: usize,
}
kevincoxUnsubmitted
Not Done

You might also consider an enum

enum Parents {
  Zero,
  One(Revision),
  Two(Revision, Revision),
}

This also makes the iterator implementation a little clearer.

kevincox: You might also consider an enum ``` enum Parents { Zero, One(Revision), Two(Revision…
impl ParentsIterator {
fn graph_parents(
graph: &impl Graph,
r: Revision,
) -> Result<ParentsIterator, GraphError> {
Ok(ParentsIterator {
parents: graph.parents(r)?,
cur: 0,
})
}
}
impl Iterator for ParentsIterator {
type Item = Revision;
fn next(&mut self) -> Option<Revision> {
if self.cur > 1 {
return None;
}
let rev = self.parents[self.cur];
self.cur += 1;
if rev == NULL_REVISION {
return self.next();
}
Some(rev)
}
}
impl<G: Graph + Clone> PartialDiscovery<G> { impl<G: Graph + Clone> PartialDiscovery<G> {
kevincoxUnsubmitted
Done

Can't you just call self.next() in both cases?

kevincox: Can't you just call `self.next()` in both cases?
gracinetAuthorUnsubmitted
Not Done

Yes that's what I actually did first, and then I tried this variant to see if it's faster. It may be a bit, but nothing worth doing in a first inclusion.

gracinet: Yes that's what I actually did first, and then I tried this variant to see if it's faster. It…
/// Create a PartialDiscovery object, with the intent /// Create a PartialDiscovery object, with the intent
/// of comparing our `::<target_heads>` revset to the contents of another /// of comparing our `::<target_heads>` revset to the contents of another
/// repo. /// repo.
/// ///
/// For now `target_heads` is passed as a vector, and will be used /// For now `target_heads` is passed as a vector, and will be used
/// at the first call to `ensure_undecided()`. /// at the first call to `ensure_undecided()`.
/// ///
/// If we want to make the signature more flexible, /// If we want to make the signature more flexible,
/// we'll have to make it a type argument of `PartialDiscovery` or a trait /// we'll have to make it a type argument of `PartialDiscovery` or a trait
/// object since we'll keep it in the meanwhile /// object since we'll keep it in the meanwhile
pub fn new(graph: G, target_heads: Vec<Revision>) -> Self { pub fn new(graph: G, target_heads: Vec<Revision>) -> Self {
let mut seed: [u8; 16] = [0; 16]; let mut seed: [u8; 16] = [0; 16];
thread_rng().fill_bytes(&mut seed); thread_rng().fill_bytes(&mut seed);
Self::new_with_seed(graph, target_heads, seed) Self::new_with_seed(graph, target_heads, seed)
} }
pub fn new_with_seed( pub fn new_with_seed(
graph: G, graph: G,
target_heads: Vec<Revision>, target_heads: Vec<Revision>,
seed: [u8; 16], seed: [u8; 16],
) -> Self { ) -> Self {
PartialDiscovery { PartialDiscovery {
undecided: None, undecided: None,
children_cache: None,
target_heads: Some(target_heads), target_heads: Some(target_heads),
graph: graph.clone(), graph: graph.clone(),
common: MissingAncestors::new(graph, vec![]), common: MissingAncestors::new(graph, vec![]),
missing: HashSet::new(), missing: HashSet::new(),
rng: Rng::from_seed(seed), rng: Rng::from_seed(seed),
} }
} }
return Ok(()); return Ok(());
} }
let tgt = self.target_heads.take().unwrap(); let tgt = self.target_heads.take().unwrap();
self.undecided = self.undecided =
Some(self.common.missing_ancestors(tgt)?.into_iter().collect()); Some(self.common.missing_ancestors(tgt)?.into_iter().collect());
Ok(()) Ok(())
} }
fn ensure_children_cache(&mut self) -> Result<(), GraphError> {
if self.children_cache.is_some() {
return Ok(());
}
self.ensure_undecided()?;
let mut children: HashMap<Revision, Vec<Revision>> = HashMap::new();
for &rev in self.undecided.as_ref().unwrap() {
kevincoxUnsubmitted
Not Done

Generally I would just do this.

for &rev in self.undecided.as_ref().unwrap() {
kevincox: Generally I would just do this. ``` for &rev in self.undecided.as_ref().unwrap() { ```
gracinetAuthorUnsubmitted
Not Done

yes, same as in parent commit. Indeed it's a nicer way to iterate on references to Copy objects

gracinet: yes, same as in parent commit. Indeed it's a nicer way to iterate on references to `Copy`…
for p in ParentsIterator::graph_parents(&self.graph, rev)? {
kevincoxUnsubmitted
Not Done

Same.

kevincox: Same.
gracinetAuthorUnsubmitted
Not Done

for this one, I can actually use ParentsIterator, now, spares me the NULL_REVISION check

gracinet: for this one, I can actually use `ParentsIterator`, now, spares me the `NULL_REVISION` check
children.entry(p).or_insert_with(|| Vec::new()).push(rev);
}
}
self.children_cache = Some(children);
Ok(())
}
/// Provide statistics about the current state of the discovery process /// Provide statistics about the current state of the discovery process
pub fn stats(&self) -> DiscoveryStats { pub fn stats(&self) -> DiscoveryStats {
DiscoveryStats { DiscoveryStats {
undecided: self.undecided.as_ref().map(|s| s.len()), undecided: self.undecided.as_ref().map(|s| s.len()),
} }
} }
pub fn take_quick_sample( pub fn take_quick_sample(
}; };
if sample.len() >= size { if sample.len() >= size {
return Ok(self.limit_sample(sample.into_iter().collect(), size)); return Ok(self.limit_sample(sample.into_iter().collect(), size));
} }
update_sample( update_sample(
None, None,
headrevs, headrevs,
&mut sample, &mut sample,
|r| self.graph.parents(r), |r| ParentsIterator::graph_parents(&self.graph, r),
Some(size), Some(size),
)?; )?;
Ok(sample.into_iter().collect()) Ok(sample.into_iter().collect())
} }
/// Extract a sample from `self.undecided`, going from its heads and roots.
///
/// The `size` parameter is used to avoid useless computations if
/// it turns out to be bigger than the whole set of undecided Revisions.
///
/// The sample is taken by using `update_sample` from the heads, then
/// from the roots, working on the reverse DAG,
/// expressed by `self.children_cache`.
///
/// No effort is being made to complete or limit the sample to `size`
fn bidirectional_sample(
&mut self,
size: usize,
) -> Result<HashSet<Revision>, GraphError> {
self.ensure_undecided()?;
{
// we don't want to compute children_cache before this
// but doing it after extracting self.undecided takes a mutable
// ref to self while a shareable one is still active.
let undecided = self.undecided.as_ref().unwrap();
if undecided.len() <= size {
return Ok(undecided.clone());
}
}
self.ensure_children_cache()?;
let revs = self.undecided.as_ref().unwrap();
let mut sample: HashSet<Revision> = revs.clone();
// it's possible that leveraging the children cache would be more
// efficient here
dagops::retain_heads(&self.graph, &mut sample)?;
let revsheads = sample.clone(); // was again heads(revs) in python
// update from heads
update_sample(
Some(revs),
revsheads.iter().cloned(),
&mut sample,
|r| ParentsIterator::graph_parents(&self.graph, r),
None,
)?;
// update from roots
let revroots: HashSet<Revision> =
dagops::roots(&self.graph, revs)?.into_iter().collect();
let children = self.children_cache.as_ref().unwrap();
let empty_vec: Vec<Revision> = Vec::new();
update_sample(
Some(revs),
revroots,
&mut sample,
|r| Ok(children.get(&r).unwrap_or(&empty_vec).iter().cloned()),
None,
)?;
Ok(sample)
}
/// Fill up sample up to the wished size with random undecided Revisions.
///
/// This is intended to be used as a last resort completion if the
/// regular sampling algorithm returns too few elements.
fn random_complete_sample(
&mut self,
sample: &mut Vec<Revision>,
size: usize,
) {
let sample_len = sample.len();
if size <= sample_len {
return;
}
let take_from: Vec<Revision> = self
.undecided
.as_ref()
.unwrap()
.iter()
.filter(|&r| !sample.contains(r))
.cloned()
.collect();
sample.extend(self.limit_sample(take_from, size - sample_len));
}
pub fn take_full_sample(
&mut self,
size: usize,
) -> Result<Vec<Revision>, GraphError> {
let sample = self.bidirectional_sample(size)?.into_iter().collect();
let mut sample = self.limit_sample(sample, size);
self.random_complete_sample(&mut sample, size);
Ok(sample)
}
} }
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use super::*; use super::*;
use crate::testing::SampleGraph; use crate::testing::SampleGraph;
/// A PartialDiscovery as for pushing all the heads of `SampleGraph` /// A PartialDiscovery as for pushing all the heads of `SampleGraph`
let mut sample_vec = disco.take_quick_sample(vec![12], 4)?; let mut sample_vec = disco.take_quick_sample(vec![12], 4)?;
sample_vec.sort(); sample_vec.sort();
// r12's only parent is r9, whose unique grand-parent through the // r12's only parent is r9, whose unique grand-parent through the
// diamond shape is r4. This ends there because the distance from r4 // diamond shape is r4. This ends there because the distance from r4
// to the root is only 3. // to the root is only 3.
assert_eq!(sample_vec, vec![4, 9, 12]); assert_eq!(sample_vec, vec![4, 9, 12]);
Ok(()) Ok(())
} }
#[test]
fn test_children_cache() -> Result<(), GraphError> {
let mut disco = full_disco();
disco.ensure_children_cache()?;
let cache = disco.children_cache.unwrap();
assert_eq!(cache.get(&2).cloned(), Some(vec![4]));
assert_eq!(cache.get(&10).cloned(), None);
let mut children_4 = cache.get(&4).cloned().unwrap();
children_4.sort();
assert_eq!(children_4, vec![5, 6, 7]);
let mut children_7 = cache.get(&7).cloned().unwrap();
children_7.sort();
assert_eq!(children_7, vec![9, 11]);
Ok(())
}
#[test]
fn test_complete_sample() {
let mut disco = full_disco();
let undecided: HashSet<Revision> =
[4, 7, 9, 2, 3].iter().cloned().collect();
disco.undecided = Some(undecided);
let mut sample = vec![0];
disco.random_complete_sample(&mut sample, 3);
assert_eq!(sample.len(), 3);
let mut sample = vec![2, 4, 7];
disco.random_complete_sample(&mut sample, 1);
assert_eq!(sample.len(), 3);
}
#[test]
fn test_bidirectional_sample() -> Result<(), GraphError> {
let mut disco = full_disco();
disco.undecided = Some((0..=13).into_iter().collect());
let mut sample: Vec<Revision> =
disco.bidirectional_sample(7)?.into_iter().collect();
sample.sort();
// our DAG is a bit too small for the results to be really interesting
// at least it shows that
// - we went both ways
// - we didn't take all Revisions (6 is not in the sample)
assert_eq!(sample, vec![0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13]);
Ok(())
}
} }