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 (9 lines)

Diff 15486

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
/// ///
/// # Performance note /// # Performance note
/// ///
/// Except in the most trivial case, the first call of this method has /// Except in the most trivial case, the first call of this method has
/// the side effect of computing `self.undecided` set for the first time, /// the side effect of computing `self.undecided` set for the first time,
/// and the related caches it might need for efficiency of its internal /// and the related caches it might need for efficiency of its internal
/// computation. This is typically faster if more information is /// computation. This is typically faster if more information is
/// available in `self.common`. Therefore, for good performance, the /// available in `self.common`. Therefore, for good performance, the
/// caller should avoid calling this too early. /// caller should avoid calling this too early.
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();
if tovisit.is_empty() {
return Ok(());
}
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