changeset 41726: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
author Georges Racinet <georges.racinet@octobus.net>
date Mon, 04 Feb 2019 12:04:59 +0100
parents 70827ebba453
children 977432970080
files rust/hg-core/src/ancestors.rs
diffstat 1 files changed, 8 insertions(+), 12 deletions(-) [+]
line wrap: on
line diff
--- 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 {