Patchwork D6428: rust-discovery: using the children cache in add_missing

login
register
mail settings
Submitter phabricator
Date May 22, 2019, 5 p.m.
Message ID <differential-rev-PHID-DREV-jsxdk336dj4t67fdxckx-req@phab.mercurial-scm.org>
Download mbox | patch
Permalink /patch/40188/
State New
Headers show

Comments

phabricator - May 22, 2019, 5 p.m.
gracinet created this revision.
Herald added subscribers: mercurial-devel, kevincox, durin42.
Herald added a reviewer: hg-reviewers.

REVISION SUMMARY
  The DAG range computation often needs to get back to very old
  revisions, and turns out to be disproportionately long, given
  that the end goal is to remove the descendents of the given
  missing revisons from the undecided set.
  
  The fast iteration capabilities available in the Rust case make
  it possible to avoid the DAG range entirely, at the cost of
  precomputing the children cache, and to simply iterate on
  children of the given missing revisions.
  
  This is a case where staying on the same side of the interface
  between the two languages has clear benefits.
  
  On discoveries with initial undecided sets
  small enough to bypass sampling entirely, the total cost of
  computing the children cache and the subsequent iteration
  becomes better than the Python + C counterpart, which relies on
  reachableroots2.
  
  For example, on a repo with more than one million revisions with
  an initial undecided set of 11 elements, we get these figures:
  
  Rust version with simple iteration
  
    addcommons: 57.287us
    first undecided computation: 184.278334ms
    first children cache computation: 131.056us
    addmissings iteration: 42.766us
    first addinfo total: 185.24 ms
  
  Python + C version
  
    first addcommons: 0.29 ms
    addcommons 0.21 ms
    first undecided computation 191.35 ms
    addmissings 45.75 ms
    first addinfo total: 237.77 ms
  
  On discoveries with large undecided sets, the initial price paid
  makes the first addinfo slower than the Python + C version,
  but that's more than compensated by the gain in sampling and
  subsequent iterations.
  Here's an extreme example with an undecided set of a million revisions:
  
  Rust version:
  
    first undecided computation: 293.842629ms
    first children cache computation: 407.911297ms
    addmissings iteration: 34.312869ms
    first addinfo total: 776.02 ms
    taking initial sample
    query 2: sampling time: 1318.38 ms
    query 2; still undecided: 1005013, sample size is: 200
    addmissings: 143.062us
  
  Python + C version:
  
    first undecided computation 298.13 ms
    addmissings 80.13 ms
    first addinfo total: 399.62 ms
    taking initial sample
    query 2: sampling time: 3957.23 ms
    query 2; still undecided: 1005013, sample size is: 200
    addmissings 52.88 ms

REPOSITORY
  rHG Mercurial

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

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

CHANGE DETAILS




To: gracinet, #hg-reviewers
Cc: durin42, kevincox, mercurial-devel
phabricator - May 22, 2019, 5:17 p.m.
gracinet added a comment.


  This revision is new. At the time I submitted the previous series, it was almost always the case that the advantage of the C `reachableroots2()` over the Rust ``dagop::range()` was more than compensated by sampling been done in Rust instead of Python.
  I originally planned to finish that one and submit it as a follow-up optimization, but now it's necessary to prevent being slower in the fastest cases where there's no sampling.

REPOSITORY
  rHG Mercurial

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

To: gracinet, #hg-reviewers
Cc: durin42, kevincox, mercurial-devel
phabricator - June 10, 2019, 12:59 p.m.
kevincox accepted this revision.
kevincox added inline comments.

INLINE COMMENTS

> discovery.rs:233
> +    /// sets, for which the discovery process will engage into sampling
> +    /// that needs the children cache anyway.
>      pub fn add_missing_revisions(

These added comments seem more relevant to the implementation of the method than they are to the caller. Would it make sense to move them inside of the function body so that they don't busy the doc-comment?

REPOSITORY
  rHG Mercurial

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

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

Patch

diff --git a/rust/hg-core/src/discovery.rs b/rust/hg-core/src/discovery.rs
--- a/rust/hg-core/src/discovery.rs
+++ b/rust/hg-core/src/discovery.rs
@@ -223,20 +223,46 @@ 
     }
 
     /// Register revisions known as being missing
+    ///
+    /// We iterate on the children cache to consider the given missing
+    /// revisions together with their relevant descendents.
+    ///
+    /// Enforcing the children cache like we do is very much faster in
+    /// practice than using `dagop::range` except on very large undecided
+    /// sets, for which the discovery process will engage into sampling
+    /// that needs the children cache anyway.
     pub fn add_missing_revisions(
         &mut self,
         missing: impl IntoIterator<Item = Revision>,
     ) -> Result<(), GraphError> {
-        self.ensure_undecided()?;
-        let range = dagops::range(
-            &self.graph,
-            missing,
-            self.undecided.as_ref().unwrap().iter().cloned(),
-        )?;
+        self.ensure_children_cache()?;
+        self.ensure_undecided()?;  // for safety of possible future refactors
+        let children = self.children_cache.as_ref().unwrap();
+        let mut seen: HashSet<Revision> = HashSet::new();
+        let mut tovisit: VecDeque<Revision> = missing.into_iter().collect();
         let undecided_mut = self.undecided.as_mut().unwrap();
-        for missrev in range {
-            self.missing.insert(missrev);
-            undecided_mut.remove(&missrev);
+        while let Some(rev) = tovisit.pop_front() {
+            if !self.missing.insert(rev) {
+                // either it's known to be missing from a previous
+                // invocation, and there's no need to iterate on its
+                // children (we now they are all missing)
+                // or it's from a previous iteration of this loop
+                // and its children have already been queued
+                continue;
+            }
+            undecided_mut.remove(&rev);
+            match children.get(&rev) {
+                None => {
+                    continue;
+                }
+                Some(this_children) => {
+                    for child in this_children.iter().cloned() {
+                        if seen.insert(child) {
+                            tovisit.push_back(child);
+                        }
+                    }
+                }
+            }
         }
         Ok(())
     }
@@ -520,6 +546,22 @@ 
     }
 
     #[test]
+    fn test_add_missing_early_continue() -> Result<(), GraphError> {
+        eprintln!("test_add_missing_early_stop");
+        let mut disco = full_disco();
+        disco.add_common_revisions(vec![13, 3, 4])?;
+        disco.ensure_children_cache()?;
+        // 12 is grand-child of 6 through 9
+        // passing them in this order maximizes the chances of the
+        // early continue to do the wrong thing
+        disco.add_missing_revisions(vec![6, 9, 12])?;
+        assert_eq!(sorted_undecided(&disco), vec![5, 7, 10, 11]);
+        assert_eq!(sorted_missing(&disco), vec![6, 9, 12]);
+        assert!(!disco.is_complete());
+        Ok(())
+    }
+
+    #[test]
     fn test_limit_sample_no_need_to() {
         let sample = vec![1, 2, 3, 4];
         assert_eq!(full_disco().limit_sample(sample, 10), vec![1, 2, 3, 4]);