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
@@ -39,7 +39,7 @@
     graph: G, // plays the role of self._repo
     common: MissingAncestors<G>,
     undecided: HashSet<Revision>,
-    children_cache: Option<FastHashMap<Revision, Vec<Revision>>>,
+    children_cache: FastHashMap<Revision, Vec<Revision>>,
     missing: HashSet<Revision>,
     rng: Rng,
     respect_size: bool,
@@ -370,9 +370,14 @@
     }
 
     fn compute_undecided(mut self) -> Result<WithUndecided<G>, GraphError> {
-        self.common
-            .missing_ancestors(self.target_heads.iter().cloned())
-            .map(|undecided| WithUndecided::new(self, undecided))
+        let undecided = self
+            .common
+            .missing_ancestors(self.target_heads.iter().cloned())?;
+        let children = WithUndecided::compute_children_cache(
+            &self.graph,
+            undecided.iter().cloned(),
+        )?;
+        Ok(WithUndecided::new(self, undecided, children))
     }
 }
 
@@ -380,10 +385,11 @@
     fn new(
         disco: OnlyCommon<G>,
         undecided: impl IntoIterator<Item = Revision>,
+        children_cache: FastHashMap<Revision, Vec<Revision>>,
     ) -> Self {
         WithUndecided {
             undecided: undecided.into_iter().collect(),
-            children_cache: None,
+            children_cache: children_cache,
             rng: Rng::from_seed(disco.seed),
             graph: disco.graph.clone(),
             missing: HashSet::new(),
@@ -444,10 +450,9 @@
         &mut self,
         mut tovisit: VecDeque<Revision>,
     ) -> Result<(), GraphError> {
-        self.ensure_children_cache()?;
-        let children = self.children_cache.as_ref().unwrap();
         let mut seen: HashSet<Revision> = HashSet::new();
         let undecided_mut = &mut self.undecided;
+        let children = &self.children_cache;
         while let Some(rev) = tovisit.pop_front() {
             if !self.missing.insert(rev) {
                 // either it's known to be missing from a previous
@@ -499,19 +504,18 @@
         self.common.bases_heads()
     }
 
-    fn ensure_children_cache(&mut self) -> Result<(), GraphError> {
-        if self.children_cache.is_some() {
-            return Ok(());
-        }
+    fn compute_children_cache(
+        graph: &G,
+        undecided: impl Iterator<Item = Revision>,
+    ) -> Result<(FastHashMap<Revision, Vec<Revision>>), GraphError> {
         let mut children: FastHashMap<Revision, Vec<Revision>> =
             FastHashMap::default();
-        for rev in self.undecided.iter() {
-            for p in ParentsIterator::graph_parents(&self.graph, *rev)? {
-                children.entry(p).or_insert_with(|| Vec::new()).push(*rev);
+        for rev in undecided.into_iter() {
+            for p in ParentsIterator::graph_parents(graph, rev)? {
+                children.entry(p).or_insert_with(|| Vec::new()).push(rev);
             }
         }
-        self.children_cache = Some(children);
-        Ok(())
+        Ok(children)
     }
 
     /// Provide statistics about the current state of the discovery process
@@ -567,7 +571,6 @@
             return Ok((self.undecided.clone(), size));
         }
 
-        self.ensure_children_cache()?;
         let revs = &self.undecided;
         let mut sample: HashSet<Revision> = revs.clone();
 
@@ -590,7 +593,7 @@
             dagops::roots(&self.graph, revs)?.into_iter().collect();
         let prescribed_size = max(size, min(revroots.len(), revsheads.len()));
 
-        let children = self.children_cache.as_ref().unwrap();
+        let children = &self.children_cache;
         let empty_vec: Vec<Revision> = Vec::new();
         update_sample(
             Some(revs),
@@ -697,10 +700,20 @@
         let undecided_set: HashSet<Revision> = undecided.into_iter().collect();
         disco
             .mutate_undecided(
-                |oc| Ok(WithUndecided::new(oc, Vec::new())),
+                |oc| {
+                    Ok(WithUndecided::new(
+                        oc,
+                        Vec::new(),
+                        FastHashMap::default(),
+                    ))
+                },
                 |wu| {
-                    wu.undecided = undecided_set;
-                    Ok(())
+                    WithUndecided::compute_children_cache(
+                        &wu.graph,
+                        undecided_set.iter().cloned(),
+                    )
+                    .map(|children| wu.children_cache = children)
+                    .map(|_| wu.undecided = undecided_set)
                 },
             )
             .unwrap()
@@ -868,11 +881,9 @@
     }
 
     #[test]
-    fn test_children_cache() -> Result<(), GraphError> {
-        let mut disco = full_disco_with_undecided();
-        disco.ensure_children_cache()?;
+    fn test_children_cache() {
+        let cache = full_disco_with_undecided().children_cache;
 
-        let cache = disco.children_cache.unwrap();
         assert_eq!(cache.get(&2).cloned(), Some(vec![4]));
         assert_eq!(cache.get(&10).cloned(), None);
 
@@ -883,8 +894,6 @@
         let mut children_7 = cache.get(&7).cloned().unwrap();
         children_7.sort();
         assert_eq!(children_7, vec![9, 11]);
-
-        Ok(())
     }
 
     #[test]