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
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.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 16191

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