D5943: rust: less set lookups in MissingAncestors

gracinet (Georges Racinet) phabricator at mercurial-scm.org
Tue Feb 12 12:02:10 UTC 2019


gracinet created this revision.
Herald added subscribers: mercurial-devel, kevincox, durin42.
Herald added a reviewer: hg-reviewers.

REVISION 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)

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D5943

AFFECTED FILES
  rust/hg-core/src/ancestors.rs

CHANGE DETAILS

diff --git a/rust/hg-core/src/ancestors.rs b/rust/hg-core/src/ancestors.rs
--- a/rust/hg-core/src/ancestors.rs
+++ b/rust/hg-core/src/ancestors.rs
@@ -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 {



To: gracinet, #hg-reviewers
Cc: durin42, kevincox, mercurial-devel


More information about the Mercurial-devel mailing list