This is an archive of the discontinued Mercurial Phabricator instance.

Differential D5943

rust: less set lookups in MissingAncestors
ClosedPublic

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

Details

Reviewers
kevincox
Group Reviewers
hg-reviewers
Commits
rHGfccb61a1777b: rust: less set lookups in MissingAncestors
Summary

using the return values of HashSet::remove(), we can factor
pairs of contains()/remove() into a single remove().

On a perfdiscovery run done on the PyPy repository, prepared
with contrib/discovery-helper.sh 50 100, I do get a modest improvement
with this (mean of medians of three runs is better by 2%)

Sample readings, before this change:

! wall 0.175609 comb 0.180000 user 0.180000 sys 0.000000 (median of 58)

With this change:

! wall 0.171662 comb 0.180000 user 0.170000 sys 0.010000 (median of 60)

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:42 AM
Closed by commit rHGfccb61a1777b: rust: less set lookups in MissingAncestors (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 (20 lines)

Diff 14125

rust/hg-core/src/ancestors.rs

let start = max(max_bases, max_revs); 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.contains(&curr) { if both_visit.remove(&curr) {
// curr's parents might have made it into revs_visit through // curr's parents might have made it into revs_visit through
// another path // another path
// TODO optim: Rust's HashSet.remove returns a boolean telling
// if it happened. This will spare us one set lookup
both_visit.remove(&curr);
for p in self.graph.parents(curr)?.iter().cloned() { for p in self.graph.parents(curr)?.iter().cloned() {
if p == NULL_REVISION { if p == NULL_REVISION {
continue; continue;
} }
revs_visit.remove(&p); revs_visit.remove(&p);
bases_visit.insert(p); bases_visit.insert(p);
both_visit.insert(p); both_visit.insert(p);
} }
} else if revs_visit.remove(&curr) { } else if revs_visit.remove(&curr) {
missing.push(curr); missing.push(curr);
for p in self.graph.parents(curr)?.iter().cloned() { for p in self.graph.parents(curr)?.iter().cloned() {
if p == NULL_REVISION { if p == NULL_REVISION {
continue; continue;
} }
if bases_visit.contains(&p) || both_visit.contains(&p) { if bases_visit.contains(&p) {
// p is an ancestor of revs_visit, and is implicitly // p is already known to be an ancestor of revs_visit
// in bases_visit, which means p is ::revs & ::bases.
// TODO optim: hence if bothvisit, we look up twice
revs_visit.remove(&p); revs_visit.remove(&p);
bases_visit.insert(p);
both_visit.insert(p); both_visit.insert(p);
} else if both_visit.contains(&p) {
// p should have been in bases_visit
revs_visit.remove(&p);
bases_visit.insert(p);
} else { } else {
// visit later // visit later
revs_visit.insert(p); revs_visit.insert(p);
} }
} }
} else if bases_visit.contains(&curr) { } else if bases_visit.contains(&curr) {
for p in self.graph.parents(curr)?.iter().cloned() { for p in self.graph.parents(curr)?.iter().cloned() {
if p == NULL_REVISION { if p == NULL_REVISION {
continue; continue;
} }
if revs_visit.contains(&p) || both_visit.contains(&p) { if revs_visit.remove(&p) || both_visit.contains(&p) {
// p is an ancestor of bases_visit, and is implicitly // p is an ancestor of bases_visit, and is implicitly
// in revs_visit, which means p is ::revs & ::bases. // in revs_visit, which means p is ::revs & ::bases.
// TODO optim: hence if bothvisit, we look up twice
revs_visit.remove(&p);
bases_visit.insert(p); bases_visit.insert(p);
both_visit.insert(p); both_visit.insert(p);
} else { } else {
bases_visit.insert(p); bases_visit.insert(p);
} }
} }
} }
} }