Patchwork D5943: rust: less set lookups in MissingAncestors

login
register
mail settings
Submitter phabricator
Date Feb. 16, 2019, 3:35 a.m.
Message ID <bf5875f4201299621ce8d9cbf6f6e97d@localhost.localdomain>
Download mbox | patch
Permalink /patch/38788/
State Not Applicable
Headers show

Comments

phabricator - Feb. 16, 2019, 3:35 a.m.
This revision was automatically updated to reflect the committed changes.
Closed by commit rHGfccb61a1777b: rust: less set lookups in MissingAncestors (authored by gracinet, committed by ).

REPOSITORY
  rHG Mercurial

CHANGES SINCE LAST UPDATE
  https://phab.mercurial-scm.org/D5943?vs=14040&id=14125

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

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

CHANGE DETAILS




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

Patch

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 {