This is an archive of the discontinued Mercurial Phabricator instance.

Differential D5945

rust: itering less on MissingAncestors.bases for max()
ClosedPublic

Authored by gracinet on Feb 12 2019, 7:02 AM.

Details

Reviewers
kevincox
Group Reviewers
hg-reviewers
Commits
rHG9060af281be7: rust: itering less on MissingAncestors.bases for max()
Summary

Instead of iterating on the whole self.bases each time to find
its max, we keep the latter in a separate member attribute and
keep it up to date in add_bases()

On a perfdiscovery done on PyPy, with repos prepared with
contrib/discovery-helper.sh 50 100, this gives a slight
improvement (around 0.5% on wall time, but 10% on CPU)

before:
! wall 0.172801 comb 0.180000 user 0.180000 sys 0.000000 (median of 541)
after:
! wall 0.171798 comb 0.160000 user 0.160000 sys 0.000000 (median of 551)

(perf command run time upped because of bigger variability during this test).

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.Feb 12 2019, 7:02 AM
kevincox accepted this revision.Feb 12 2019, 9:58 AM
kevincox added inline comments.
rust/hg-core/src/ancestors.rs
41

Does it make sense to just default this to -1 and remove the option?

gracinet updated this revision to Diff 14046.Feb 12 2019, 11:27 AM
gracinet added inline comments.Feb 12 2019, 11:32 AM
rust/hg-core/src/ancestors.rs
41

I must confess to have hesitated a bit on that one. On one hand, it would work, but semantically if ever a new "special" revision -2 is introduced, this could become problematic. On the other hand, there are probably a few areas that already depend on the fact that NULL_REVISION is the smallest one.

From the graph side of things, NULL_REVISION being a common ancestor of all revisions, so it must be smaller or equal than all, so it doesn't matter much.

Option<Revision> was merely a simple way to be sure not to be wrong, I'm open to suggestions.

kevincox added inline comments.Feb 12 2019, 5:20 PM
rust/hg-core/src/ancestors.rs
41

If you don't want to depend on the value of NULL_REVISION you can use the minimum value for the type backing revision.

Other special revisions shouldn't be relevant because you shouldn't be comparing them as the max anyways.

That being said the currents state is fine. So if you think it makes more sense that sounds good to me.

gracinet added inline comments.Feb 13 2019, 5:18 AM
rust/hg-core/src/ancestors.rs
41

Ok, I've made up my mind: whatever the representation, NULL_REVISION must be smaller than all other Revision. Using it, rather than -1will indeed make this patch simpler.

Also, in subsequent (not yet submitted) works, I'm already liberally using this fact that NULL_REVISION is the smallest of all, so…

gracinet updated this revision to Diff 14057.Feb 13 2019, 6:55 AM
Closed by commit rHG9060af281be7: rust: itering less on MissingAncestors.bases for max() (authored by gracinet). · Explain WhyFeb 15 2019, 10:34 PM
This revision was automatically updated to reflect the committed changes.
kevincox added inline comments.Feb 16 2019, 1:37 AM
rust/hg-core/src/ancestors.rs
347

You are doing an empty check and an unwrap. I think it would be nice to combine these to make it obvious that there is no panic chance here.

let max_revs = revs_visit.iter().cloned().max();
let max_revs = match max_revs {
  Some(max) => max,
  None => return Ok(Vec::new()),
};

Revision Contents
Changeset List

Diff 14127

rust/hg-core/src/ancestors.rs

initrevs: Vec<Revision>, initrevs: Vec<Revision>,
stoprev: Revision, stoprev: Revision,
inclusive: bool, inclusive: bool,
} }
pub struct MissingAncestors<G: Graph> { pub struct MissingAncestors<G: Graph> {
graph: G, graph: G,
bases: HashSet<Revision>, bases: HashSet<Revision>,
max_base: Revision,
kevincoxUnsubmitted
Not Done

Does it make sense to just default this to -1 and remove the option?

kevincox: Does it make sense to just default this to -1 and remove the option?
gracinetAuthorUnsubmitted
Not Done

I must confess to have hesitated a bit on that one. On one hand, it would work, but semantically if ever a new "special" revision -2 is introduced, this could become problematic. On the other hand, there are probably a few areas that already depend on the fact that NULL_REVISION is the smallest one.

From the graph side of things, NULL_REVISION being a common ancestor of all revisions, so it must be smaller or equal than all, so it doesn't matter much.

Option<Revision> was merely a simple way to be sure not to be wrong, I'm open to suggestions.

gracinet: I must confess to have hesitated a bit on that one. On one hand, it would work, but…
kevincoxUnsubmitted
Not Done

If you don't want to depend on the value of NULL_REVISION you can use the minimum value for the type backing revision.

Other special revisions shouldn't be relevant because you shouldn't be comparing them as the max anyways.

That being said the currents state is fine. So if you think it makes more sense that sounds good to me.

kevincox: If you don't want to depend on the value of NULL_REVISION you can use the minimum value for the…
gracinetAuthorUnsubmitted
Not Done

Ok, I've made up my mind: whatever the representation, NULL_REVISION must be smaller than all other Revision. Using it, rather than -1will indeed make this patch simpler.

Also, in subsequent (not yet submitted) works, I'm already liberally using this fact that NULL_REVISION is the smallest of all, so…

gracinet: Ok, I've made up my mind: whatever the representation, `NULL_REVISION` must be smaller than all…
} }
impl<G: Graph> AncestorsIterator<G> { impl<G: Graph> AncestorsIterator<G> {
/// Constructor. /// Constructor.
/// ///
/// if `inclusive` is true, then the init revisions are emitted in /// if `inclusive` is true, then the init revisions are emitted in
/// particular, otherwise iteration starts from their parents. /// particular, otherwise iteration starts from their parents.
pub fn new( pub fn new(
self.inclusive, self.inclusive,
) )
.unwrap() .unwrap()
} }
} }
impl<G: Graph> MissingAncestors<G> { impl<G: Graph> MissingAncestors<G> {
pub fn new(graph: G, bases: impl IntoIterator<Item = Revision>) -> Self { pub fn new(graph: G, bases: impl IntoIterator<Item = Revision>) -> Self {
MissingAncestors { graph: graph, bases: bases.into_iter().collect() } let mut created = MissingAncestors {
graph: graph,
bases: HashSet::new(),
max_base: NULL_REVISION,
};
created.add_bases(bases);
created
} }
pub fn has_bases(&self) -> bool { pub fn has_bases(&self) -> bool {
!self.bases.is_empty() !self.bases.is_empty()
} }
/// Return a reference to current bases. /// Return a reference to current bases.
/// ///
/// This is useful in unit tests, but also setdiscovery.py does /// This is useful in unit tests, but also setdiscovery.py does
/// read the bases attribute of a ancestor.missingancestors instance. /// read the bases attribute of a ancestor.missingancestors instance.
pub fn get_bases<'a>(&'a self) -> &'a HashSet<Revision> { pub fn get_bases<'a>(&'a self) -> &'a HashSet<Revision> {
&self.bases &self.bases
} }
/// Computes the relative heads of current bases. /// Computes the relative heads of current bases.
/// ///
/// The object is still usable after this. /// The object is still usable after this.
pub fn bases_heads(&self) -> Result<HashSet<Revision>, GraphError> { pub fn bases_heads(&self) -> Result<HashSet<Revision>, GraphError> {
dagops::heads(&self.graph, self.bases.iter()) dagops::heads(&self.graph, self.bases.iter())
} }
/// Consumes the object and returns the relative heads of its bases. /// Consumes the object and returns the relative heads of its bases.
pub fn into_bases_heads(mut self) -> Result<HashSet<Revision>, GraphError> { pub fn into_bases_heads(
mut self,
) -> Result<HashSet<Revision>, GraphError> {
dagops::retain_heads(&self.graph, &mut self.bases)?; dagops::retain_heads(&self.graph, &mut self.bases)?;
Ok(self.bases) Ok(self.bases)
} }
/// Add some revisions to `self.bases`
///
/// Takes care of keeping `self.max_base` up to date.
pub fn add_bases( pub fn add_bases(
&mut self, &mut self,
new_bases: impl IntoIterator<Item = Revision>, new_bases: impl IntoIterator<Item = Revision>,
) { ) {
self.bases let mut max_base = self.max_base;
.extend(new_bases.into_iter().filter(|&rev| rev != NULL_REVISION)); self.bases.extend(
new_bases
.into_iter()
.filter(|&rev| rev != NULL_REVISION)
.map(|r| {
if r > max_base {
max_base = r;
}
r
}),
);
self.max_base = max_base;
} }
/// Remove all ancestors of self.bases from the revs set (in place) /// Remove all ancestors of self.bases from the revs set (in place)
pub fn remove_ancestors_from( pub fn remove_ancestors_from(
&mut self, &mut self,
revs: &mut HashSet<Revision>, revs: &mut HashSet<Revision>,
) -> Result<(), GraphError> { ) -> Result<(), GraphError> {
revs.retain(|r| !self.bases.contains(r)); revs.retain(|r| !self.bases.contains(r));
// the null revision is always an ancestor. Logically speaking // the null revision is always an ancestor. Logically speaking
// it's debatable in case bases is empty, but the Python // it's debatable in case bases is empty, but the Python
// implementation always adds NULL_REVISION to bases, making it // implementation always adds NULL_REVISION to bases, making it
// unconditionnally true. // unconditionnally true.
revs.remove(&NULL_REVISION); revs.remove(&NULL_REVISION);
if revs.is_empty() { if revs.is_empty() {
return Ok(()); return Ok(());
} }
// anything in revs > start is definitely not an ancestor of bases // anything in revs > start is definitely not an ancestor of bases
// revs <= start need to be investigated // revs <= start need to be investigated
// TODO optim: if a missingancestors is to be used several times, if self.max_base == NULL_REVISION {
// we shouldn't need to iterate each time on bases
let start = match self.bases.iter().cloned().max() {
Some(m) => m,
None => { // self.bases is empty
return Ok(()); return Ok(());
} }
};
// whatever happens, we'll keep at least keepcount of them // whatever happens, we'll keep at least keepcount of them
// knowing this gives us a earlier stop condition than // knowing this gives us a earlier stop condition than
// going all the way to the root // going all the way to the root
let keepcount = revs.iter().filter(|r| **r > start).count(); let keepcount = revs.iter().filter(|r| **r > self.max_base).count();
let mut curr = start; let mut curr = self.max_base;
while curr != NULL_REVISION && revs.len() > keepcount { while curr != NULL_REVISION && revs.len() > keepcount {
if self.bases.contains(&curr) { if self.bases.contains(&curr) {
revs.remove(&curr); revs.remove(&curr);
self.add_parents(curr)?; self.add_parents(curr)?;
} }
curr -= 1; curr -= 1;
} }
Ok(()) Ok(())
} }
/// Add rev's parents to self.bases /// Add the parents of `rev` to `self.bases`
///
/// This has no effect on `self.max_base`
#[inline] #[inline]
fn add_parents(&mut self, rev: Revision) -> Result<(), GraphError> { fn add_parents(&mut self, rev: Revision) -> Result<(), GraphError> {
if rev == NULL_REVISION {
return Ok(());
}
for p in self.graph.parents(rev)?.iter().cloned() {
// No need to bother the set with inserting NULL_REVISION over and // No need to bother the set with inserting NULL_REVISION over and
// over // over
for p in self.graph.parents(rev)?.iter().cloned() {
if p != NULL_REVISION { if p != NULL_REVISION {
self.bases.insert(p); self.bases.insert(p);
} }
} }
Ok(()) Ok(())
} }
/// Return all the ancestors of revs that are not ancestors of self.bases /// Return all the ancestors of revs that are not ancestors of self.bases
.filter(|r| !bases_visit.contains(r)) .filter(|r| !bases_visit.contains(r))
.collect(); .collect();
let revs_visit = &mut revs; let revs_visit = &mut revs;
let mut both_visit: HashSet<Revision> = let mut both_visit: HashSet<Revision> =
revs_visit.intersection(&bases_visit).cloned().collect(); revs_visit.intersection(&bases_visit).cloned().collect();
if revs_visit.is_empty() { if revs_visit.is_empty() {
return Ok(Vec::new()); return Ok(Vec::new());
} }
let max_revs = revs_visit.iter().cloned().max().unwrap();
kevincoxUnsubmitted
Not Done

You are doing an empty check and an unwrap. I think it would be nice to combine these to make it obvious that there is no panic chance here.

let max_revs = revs_visit.iter().cloned().max();
let max_revs = match max_revs {
  Some(max) => max,
  None => return Ok(Vec::new()),
};
kevincox: You are doing an empty check and an unwrap. I think it would be nice to combine these to make…
let max_bases = let start = max(self.max_base, max_revs);
bases_visit.iter().cloned().max().unwrap_or(NULL_REVISION);
let max_revs =
revs_visit.iter().cloned().max().unwrap_or(NULL_REVISION);
let start = max(max_bases, max_revs);
// TODO heuristics for with_capacity()? // TODO heuristics for with_capacity()?
let mut missing: Vec<Revision> = Vec::new(); let mut missing: Vec<Revision> = Vec::new();
for curr in (0..=start).rev() { for curr in (0..=start).rev() {
if revs_visit.is_empty() { if revs_visit.is_empty() {
break; break;
} }
if both_visit.remove(&curr) { if both_visit.remove(&curr) {
/// Test constructor, add/get bases and heads /// Test constructor, add/get bases and heads
fn test_missing_bases() -> Result<(), GraphError> { fn test_missing_bases() -> Result<(), GraphError> {
let mut missing_ancestors = let mut missing_ancestors =
MissingAncestors::new(SampleGraph, [5, 3, 1, 3].iter().cloned()); MissingAncestors::new(SampleGraph, [5, 3, 1, 3].iter().cloned());
let mut as_vec: Vec<Revision> = let mut as_vec: Vec<Revision> =
missing_ancestors.get_bases().iter().cloned().collect(); missing_ancestors.get_bases().iter().cloned().collect();
as_vec.sort(); as_vec.sort();
assert_eq!(as_vec, [1, 3, 5]); assert_eq!(as_vec, [1, 3, 5]);
assert_eq!(missing_ancestors.max_base, 5);
missing_ancestors.add_bases([3, 7, 8].iter().cloned()); missing_ancestors.add_bases([3, 7, 8].iter().cloned());
as_vec = missing_ancestors.get_bases().iter().cloned().collect(); as_vec = missing_ancestors.get_bases().iter().cloned().collect();
as_vec.sort(); as_vec.sort();
assert_eq!(as_vec, [1, 3, 5, 7, 8]); assert_eq!(as_vec, [1, 3, 5, 7, 8]);
assert_eq!(missing_ancestors.max_base, 8);
as_vec = missing_ancestors.bases_heads()?.iter().cloned().collect(); as_vec = missing_ancestors.bases_heads()?.iter().cloned().collect();
as_vec.sort(); as_vec.sort();
assert_eq!(as_vec, [3, 5, 7, 8]); assert_eq!(as_vec, [3, 5, 7, 8]);
Ok(()) Ok(())
} }
fn assert_missing_remove( fn assert_missing_remove(

rust/hg-core/src/dagops.rs

/// construct it comes from. /// construct it comes from.
pub fn heads<'a>( pub fn heads<'a>(
graph: &impl Graph, graph: &impl Graph,
iter_revs: impl Clone + Iterator<Item = &'a Revision>, iter_revs: impl Clone + Iterator<Item = &'a Revision>,
) -> Result<HashSet<Revision>, GraphError> { ) -> Result<HashSet<Revision>, GraphError> {
let mut heads: HashSet<Revision> = iter_revs.clone().cloned().collect(); let mut heads: HashSet<Revision> = iter_revs.clone().cloned().collect();
heads.remove(&NULL_REVISION); heads.remove(&NULL_REVISION);
for rev in iter_revs { for rev in iter_revs {
if *rev != NULL_REVISION {
remove_parents(graph, *rev, &mut heads)?; remove_parents(graph, *rev, &mut heads)?;
} }
}
Ok(heads) Ok(heads)
} }
/// Retain in `revs` only its relative heads. /// Retain in `revs` only its relative heads.
/// ///
/// This is an in-place operation, so that control of the incoming /// This is an in-place operation, so that control of the incoming
/// set is left to the caller. /// set is left to the caller.
/// - a direct Python binding would probably need to build its own `HashSet` /// - a direct Python binding would probably need to build its own `HashSet`
/// from an incoming iterable, even if its sole purpose is to extract the /// from an incoming iterable, even if its sole purpose is to extract the
/// heads. /// heads.
/// - a Rust caller can decide whether cloning beforehand is appropriate /// - a Rust caller can decide whether cloning beforehand is appropriate
/// ///
/// # Performance notes /// # Performance notes
/// Internally, this function will store a full copy of `revs` in a `Vec`. /// Internally, this function will store a full copy of `revs` in a `Vec`.
pub fn retain_heads( pub fn retain_heads(
graph: &impl Graph, graph: &impl Graph,
revs: &mut HashSet<Revision>, revs: &mut HashSet<Revision>,
) -> Result<(), GraphError> { ) -> Result<(), GraphError> {
revs.remove(&NULL_REVISION); revs.remove(&NULL_REVISION);
// we need to construct an iterable copy of revs to avoid itering while // we need to construct an iterable copy of revs to avoid itering while
// mutating // mutating
let as_vec: Vec<Revision> = revs.iter().cloned().collect(); let as_vec: Vec<Revision> = revs.iter().cloned().collect();
for rev in as_vec { for rev in as_vec {
if rev != NULL_REVISION {
remove_parents(graph, rev, revs)?; remove_parents(graph, rev, revs)?;
} }
}
Ok(()) Ok(())
} }
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use super::*; use super::*;
use crate::testing::SampleGraph; use crate::testing::SampleGraph;

rust/hg-core/src/lib.rs

// Copyright 2018 Georges Racinet <gracinet@anybox.fr> // Copyright 2018 Georges Racinet <gracinet@anybox.fr>
// //
// 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.
mod ancestors; mod ancestors;
pub mod dagops; pub mod dagops;
pub use ancestors::{AncestorsIterator, LazyAncestors, MissingAncestors}; pub use ancestors::{AncestorsIterator, LazyAncestors, MissingAncestors};
pub mod testing; // unconditionally built, for use from integration tests pub mod testing; // unconditionally built, for use from integration tests
/// Mercurial revision numbers /// Mercurial revision numbers
/// ///
/// As noted in revlog.c, revision numbers are actually encoded in /// As noted in revlog.c, revision numbers are actually encoded in
/// 4 bytes, and are liberally converted to ints, whence the i32 /// 4 bytes, and are liberally converted to ints, whence the i32
pub type Revision = i32; pub type Revision = i32;
/// Marker expressing the absence of a parent
///
/// Independently of the actual representation, `NULL_REVISION` is guaranteed
/// to be smaller that all existing revisions.
pub const NULL_REVISION: Revision = -1; pub const NULL_REVISION: Revision = -1;
/// Same as `mercurial.node.wdirrev` /// Same as `mercurial.node.wdirrev`
/// ///
/// This is also equal to `i32::max_value()`, but it's better to spell /// This is also equal to `i32::max_value()`, but it's better to spell
/// it out explicitely, same as in `mercurial.node` /// it out explicitely, same as in `mercurial.node`
pub const WORKING_DIRECTORY_REVISION: Revision = 0x7fffffff; pub const WORKING_DIRECTORY_REVISION: Revision = 0x7fffffff;