comparison rust/hg-core/src/ancestors.rs @ 41715:fccb61a1777b

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

41714:70827ebba453

        let mut missing: Vec<Revision> = Vec::new();
        for curr in (0..=start).rev() {
            if revs_visit.is_empty() {
                break;
            }
            if both_visit.contains(&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;
                    }
                    revs_visit.remove(&p);

                missing.push(curr);
                for p in self.graph.parents(curr)?.iter().cloned() {
                    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
                        revs_visit.remove(&p);
                        bases_visit.insert(p);
                        both_visit.insert(p);
                    } else {
                        // visit later
                        revs_visit.insert(p);
                    }
                }
            } else if bases_visit.contains(&curr) {
                for p in self.graph.parents(curr)?.iter().cloned() {
                    if p == NULL_REVISION {
                        continue;
                    }
                    if revs_visit.contains(&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 {
                        bases_visit.insert(p);
                    }

41715:fccb61a1777b

        let mut missing: Vec<Revision> = Vec::new();
        for curr in (0..=start).rev() {
            if revs_visit.is_empty() {
                break;
            }
            if both_visit.remove(&curr) {
                // curr's parents might have made it into revs_visit through
                // another path
                for p in self.graph.parents(curr)?.iter().cloned() {
                    if p == NULL_REVISION {
                        continue;
                    }
                    revs_visit.remove(&p);

                missing.push(curr);
                for p in self.graph.parents(curr)?.iter().cloned() {
                    if p == NULL_REVISION {
                        continue;
                    }
                    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);
                    } else {
                        // visit later
                        revs_visit.insert(p);
                    }
                }
            } else if bases_visit.contains(&curr) {
                for p in self.graph.parents(curr)?.iter().cloned() {
                    if p == NULL_REVISION {
                        continue;
                    }
                    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.
                        bases_visit.insert(p);
                        both_visit.insert(p);
                    } else {
                        bases_visit.insert(p);
                    }