This is an archive of the discontinued Mercurial Phabricator instance.

Differential D6429

rust-discovery: optimization of add commons/missings for empty arguments
ClosedPublic

Authored by gracinet on May 22 2019, 1:00 PM.

Details

Reviewers
kevincox
Group Reviewers
hg-reviewers
Commits
rHGc5748c6969b9: rust-discovery: optimization of add commons/missings for empty arguments
Summary

These two cases have to be catched early for different reasons.
In the case of add_missing_revisions, we don't want to trigger
the computation of the undecided set (and the children cache)
too early: the later the better.

In the case of add_common_revisions, the inner MissingAncestors
object wouldn't know that all ancestors of its bases have already
been removed from the undecided.
In principle, that would in itself be a lead for further
improvement: this remove_ancestors_from could be more incremental,
but the current performance seems to be good enough.

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

gracinet created this revision.May 22 2019, 1:00 PM
kevincox requested changes to this revision.Jun 10 2019, 8:53 AM

Wouldn't it be better to make add_missing_revisions work properly on empty inputs? It seems like it is too error prone to try and catch every caller. If possible I would like to push this check down as far as possible.

It seems easy enough to do in https://www.mercurial-scm.org/repo/hg/file/tip/rust/hg-core/src/discovery.rs#l56 by checking if common grew. This has the added benefit that attempting to re-add bases will also skill the work.

This revision now requires changes to proceed.Jun 10 2019, 8:53 AM
gracinet retitled this revision from rust-discovery: avoid useless calls to addcommons/addmissings to rust-discovery: optimization of add commons/missings for empty arguments.Jun 12 2019, 2:17 PM
gracinet edited the summary of this revision. (Show Details)
gracinet updated this revision to Diff 15472.
gracinet updated this revision to Diff 15486.Jun 13 2019, 9:33 AM
gracinet added a comment.Jun 13 2019, 9:33 AM
In D6429#94512, @kevincox wrote:

Wouldn't it be better to make add_missing_revisions work properly on empty inputs? It seems like it is too error prone to try and catch every caller. If possible I would like to push this check down as far as possible.
It seems easy enough to do in https://www.mercurial-scm.org/repo/hg/file/tip/rust/hg-core/src/discovery.rs#l56 by checking if common grew. This has the added benefit that attempting to re-add bases will also skill the work.

Done in the update version.

gracinet added a comment.Jun 13 2019, 9:41 AM

@kevincox, thanks for the review of this and its predecessors. I think I've addressed all your remarks and improvement suggestions.

kevincox accepted this revision.Jun 13 2019, 10:00 AM

Thanks, looks good.

Revision Contents
Changeset List

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

Diff 15472

rust/hg-core/src/discovery.rs

limited_slice.to_owned() limited_slice.to_owned()
} }
/// Register revisions known as being common /// Register revisions known as being common
pub fn add_common_revisions( pub fn add_common_revisions(
&mut self, &mut self,
common: impl IntoIterator<Item = Revision>, common: impl IntoIterator<Item = Revision>,
) -> Result<(), GraphError> { ) -> Result<(), GraphError> {
let before_len = self.common.get_bases().len();
self.common.add_bases(common); self.common.add_bases(common);
if self.common.get_bases().len() == before_len {
return Ok(())
}
if let Some(ref mut undecided) = self.undecided { if let Some(ref mut undecided) = self.undecided {
self.common.remove_ancestors_from(undecided)?; self.common.remove_ancestors_from(undecided)?;
} }
Ok(()) Ok(())
} }
/// Register revisions known as being missing /// Register revisions known as being missing
/// ///
/// We iterate on the children cache to consider the given missing /// We iterate on the children cache to consider the given missing
/// revisions together with their relevant descendents. /// revisions together with their relevant descendents.
/// ///
/// Enforcing the children cache like we do is very much faster in /// Enforcing the children cache like we do is very much faster in
/// practice than using `dagop::range` except on very large undecided /// practice than using `dagop::range` except on very large undecided
/// sets, for which the discovery process will engage into sampling /// sets, for which the discovery process will engage into sampling
/// that needs the children cache anyway. /// that needs the children cache anyway.
pub fn add_missing_revisions( pub fn add_missing_revisions(
&mut self, &mut self,
missing: impl IntoIterator<Item = Revision>, missing: impl IntoIterator<Item = Revision>,
) -> Result<(), GraphError> { ) -> Result<(), GraphError> {
let mut tovisit: VecDeque<Revision> = missing.into_iter().collect();
self.ensure_children_cache()?; self.ensure_children_cache()?;
self.ensure_undecided()?; // for safety of possible future refactors self.ensure_undecided()?; // for safety of possible future refactors
let children = self.children_cache.as_ref().unwrap(); let children = self.children_cache.as_ref().unwrap();
let mut seen: HashSet<Revision> = HashSet::new(); let mut seen: HashSet<Revision> = HashSet::new();
let mut tovisit: VecDeque<Revision> = missing.into_iter().collect();
let undecided_mut = self.undecided.as_mut().unwrap(); let undecided_mut = self.undecided.as_mut().unwrap();
while let Some(rev) = tovisit.pop_front() { while let Some(rev) = tovisit.pop_front() {
if !self.missing.insert(rev) { if !self.missing.insert(rev) {
// either it's known to be missing from a previous // either it's known to be missing from a previous
// invocation, and there's no need to iterate on its // invocation, and there's no need to iterate on its
// children (we now they are all missing) // children (we now they are all missing)
// or it's from a previous iteration of this loop // or it's from a previous iteration of this loop
// and its children have already been queued // and its children have already been queued