rust: less set lookups in MissingAncestors
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)
Differential Revision: https://phab.mercurial-scm.org/D5943
--- a/rust/hg-core/src/ancestors.rs Mon Feb 04 11:39:28 2019 +0100
+++ b/rust/hg-core/src/ancestors.rs Mon Feb 04 12:04:59 2019 +0100
@@ -334,12 +334,9 @@
if revs_visit.is_empty() {
break;
}
- if both_visit.contains(&curr) {
+ if both_visit.remove(&curr) {
// curr's parents might have made it into revs_visit through
// 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() {
if p == NULL_REVISION {
continue;
@@ -354,13 +351,14 @@
if p == NULL_REVISION {
continue;
}
- if bases_visit.contains(&p) || both_visit.contains(&p) {
- // p is an ancestor of revs_visit, and is implicitly
- // in bases_visit, which means p is ::revs & ::bases.
- // TODO optim: hence if bothvisit, we look up twice
+ if bases_visit.contains(&p) {
+ // p is already known to be an ancestor of revs_visit
+ revs_visit.remove(&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);
- both_visit.insert(p);
} else {
// visit later
revs_visit.insert(p);
@@ -371,11 +369,9 @@
if p == NULL_REVISION {
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
// 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);
both_visit.insert(p);
} else {