( )⚙ D5942 rust: less set lookups in AncestorsIterator

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D5942

rust: less set lookups in AncestorsIterator
ClosedPublic

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

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHG70827ebba453: rust: less set lookups in AncestorsIterator
Summary

This uses the boolean return of HashSet::insert() to factor
pairs of contains()/insert() into a single insert()

On the mozilla-central repository (450k changesets), I get about a bit more
than 10% better medians in perfancestors (taking the mean of three runs)

Best run for parent changeset:

! wall 0.106474 comb 0.110000 user 0.110000 sys 0.000000 (median of 93)

Best run fot this changeset:

! wall 0.093191 comb 0.090000 user 0.090000 sys 0.000000 (median of 100)

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

gracinet created this revision.Feb 12 2019, 7:01 AM
Closed by commit rHG70827ebba453: rust: less set lookups in AncestorsIterator (authored by gracinet). · Explain WhyFeb 15 2019, 10:34 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mrust/hg-core/src/ancestors.rs (6 lines)

Diff 14039

rust/hg-core/src/ancestors.rs

this.conditionally_push_rev(parent); this.conditionally_push_rev(parent);
} }
} }
Ok(this) Ok(this)
} }
#[inline] #[inline]
fn conditionally_push_rev(&mut self, rev: Revision) { fn conditionally_push_rev(&mut self, rev: Revision) {
if self.stoprev <= rev && !self.seen.contains(&rev) { if self.stoprev <= rev && self.seen.insert(rev) {
self.seen.insert(rev);
self.visit.push(rev); self.visit.push(rev);
} }
} }
/// Consumes partially the iterator to tell if the given target /// Consumes partially the iterator to tell if the given target
/// revision /// revision
/// is in the ancestors it emits. /// is in the ancestors it emits.
/// This is meant for iterators actually dedicated to that kind of /// This is meant for iterators actually dedicated to that kind of
return None; return None;
} }
Some(c) => *c, Some(c) => *c,
}; };
let [p1, p2] = match self.graph.parents(current) { let [p1, p2] = match self.graph.parents(current) {
Ok(ps) => ps, Ok(ps) => ps,
Err(e) => return Some(Err(e)), Err(e) => return Some(Err(e)),
}; };
if p1 < self.stoprev || self.seen.contains(&p1) { if p1 < self.stoprev || !self.seen.insert(p1) {
self.visit.pop(); self.visit.pop();
} else { } else {
*(self.visit.peek_mut().unwrap()) = p1; *(self.visit.peek_mut().unwrap()) = p1;
self.seen.insert(p1);
}; };
self.conditionally_push_rev(p2); self.conditionally_push_rev(p2);
Some(Ok(current)) Some(Ok(current))
} }
} }
impl<G: Graph + Clone> LazyAncestors<G> { impl<G: Graph + Clone> LazyAncestors<G> {